本文是一篇计算机论文，本文分析了NUMA架构多节点的虚拟机放置问题的逻辑与原理以及服务器存在的资源竞争类型。为了有效地提升系统效率，从减少共享资源竞争角度出发，将虚拟机放置过程化为马尔科夫决策过程，并基于强化学习方法提出了Post算法。针对策略更新设计了差值奖励函数的形式，并加入了交叉熵最小化放置策略，大幅提高了训练效率，最后采用多模型决策找出全局最优策略。
第一章绪论
1.1研究背景和意义
中国拥有14亿多人口，近几年对数据存储的需求呈指数级增长，云计算这种新型资源计算模型的出现，为用户提供了强大的计算及存储服务，将处理大量信息的速度提升了近百倍，云计算数据中心实现高速发展。与此同时，据2021年5月的一份报告预测[2]，到2035年国内数据中心和5G网络的总碳排放量将达到2.3~3.1亿吨，占全国总排放量的2%~4%，其中数据中心的碳排放量将比2020年增长约103%，直接影响了我们的环境。可以说，快速增长的碳排放量是数据中心高速发展的“隐形杠杆”。虚拟化技术使云计算数据中心能够以虚拟机的形式按需提供服务，现有的虚拟化技术主要是将系统分为三层结构，虚拟机监控器（Virtual Machine Monitor，VMM）位于底层硬件的上面，它会根据各物理机的需求，使用调度模块将底层硬件的资源调度分配给上层的物理机，这一过程也被称为资源调度[3]。VMM可以将多个线程运行在单个物理机/虚拟机上，以实现最大化地利用硬件资源，然而当VMM采用不合适的调度策略或者只考虑负载均衡单方面优化时，往往会造成系统其他性能的下降，如访问时间较长等。虚拟机调度是解决云计算资源调度问题的一种方法，包括虚拟机放置（VirtualMachine Placement，VMP）和虚拟机迁移两种形式，本文主要研究虚拟机放置问题。
虚拟机放置是指系统软件在启动虚拟机时，如何将虚拟机的虚拟核心映射到物理核心上，简单来说就是将待分配的虚拟机绑定/放置到主机上的操作。虚拟机放置问题分为初始放置问题和动态放置问题，初始放置是指在数据中心初始状态，即没有任何负载的数据中心，依据以往经验，将虚拟机放置到相应的位置，以满足用户和供应商的不同需求，提出目标优化的虚拟机放置策略；动态虚拟机放置是指在虚拟机运行期间，考虑用户对虚拟机或虚拟机资源不断地需求，提出符合目标优化的虚拟机迁移策略[4]。
1.2国内外研究现状
虚拟机放置问题作为云计算资源管理问题的核心子问题之一，受到广泛关注，它常被研究者认为是装箱问题，而启发式算法是装箱问题的常见求解方法，因此本节首先调研了使用启发式算法求解虚拟机放置问题的解决方案，分析了现有解决方案的优势与不足；其次，虚拟机放置问题包含多个目标优化，在数学上属于组合优化问题，机器学习常被用来求解组合优化问题，因此随后本论文调研了将机器学习方法应用于虚拟机放置问题的研究现状；最后分析了现有的使用强化学习求解虚拟机放置问题的工作，并阐述了NUMA架构虚拟机放置问题研究现状，进而说明本论文的工作空间与意义。
1.2.1启发式方法
采用启发式算法求解数据中心的虚拟机放置问题已经有很多的研究成果。Chen Y等[8]基于对服务器资源分配的原则以及评价能耗的指标，设计了一种虚拟机整合算法，通过采用降序首次适应（First Fit Decreasing，FFD）算法来对虚拟机进行放置，达到降低服务器集群整体能耗的目的。Lu等[9]提出了一种基于置换的改进遗传算法和多维资源感知的最优匹配分配策略的混合VMP算法，该算法通过最小化主机虚拟机的主动服务器数量来降低云数据中心的能耗率。同样地，为了降低系统能耗，Hemraj Saini等[10]提出了一种面向虚拟机映射的节能VMP算法。该算法采用一种基于多目标优化的非支配排序遗传算法来求解虚拟机放置问题，达到优化能耗、降低SLA违规率和最小化迁移次数的目的。但以上两种算法在计算密集型任务虚拟化环境中，盲目地搜索使得完成时间不可估量。Fares Alharbi等[11]将数据中心中的虚拟机放置到物理机序列中作为一个约束组合优化问题，利用虚拟机和物理机分布的信息，提出了一种嵌入新启发式算法的蚁群优化算法。但该算法没有考虑到未放置虚拟机对计算结果的影响以及虚拟机放置对所有物理机总体资源利用率的影响，所以该算法易陷入局部最优解。
第二章相关理论知识
2.1 NUMA架构相关知识
由于一致性内存访问（Uniform Memory Access，UMA）服务器[25]在可伸缩性能力上的限制，研究者开始探索能够有效扩展，构建大型系统的技术，NUMA架构应运而生。NUMA体系结构具有高可扩展性，是目前数据中心采用最多的多处理器体系结构，本节主要介绍比较以下这两种架构体系。
（1）统一内存访问UMA架构
统一内存访问UMA架构是指多处理器计算机的硬件和软件体系结构，它包括两个或以上相同的处理器，这些处理器通过系统总线连接到同一个共享的内存上，并且可以访问相同的I/O控制器。UMA架构图如图2.1所示：
UMA架构服务器中包含多个平等工作，不存在优先级关系CPU，但每个CPU访问内存中的任何地址都需要经过系统总线，所消耗时间相同。“共享”是UMA服务器架构的主要特征，系统中所有资源（CPU、内存、I/O等）都是共享的，而这也是UMA服务器扩展能力受限制的主要原因。对UMA服务器进行扩展的方式，包括增加内存、使用更快的CPU、增加CPU、扩充I/O（槽口数与总线数），以及添加更多的外部设备（通常是磁盘存储）。对于UMA服务器而言，每一个资源共享的进程都可能造成UMA服务器内部的资源竞争，而竞争最激烈的就是内存。由于每个CPU必须通过相同的内存总线访问相同的内存资源，随着CPU数量的增加，内存访问冲突也将随之增加，因而UMA架构只适用于处理器内核数量相对较少的情况，不适用于系统中配置数十个甚至数百个处理器内核的情况。
2.2多NUMA节点的虚拟机放置问题
线程绑定的并行优化程度和服务器架构有密切关系，线程绑定的主要目的是提高线程访问CPU的cache（缓存）命中率，从而提高程序的并行性能。NUMA架构采用的是一种并行分布式存储器访问方式，处理器可以同时访问多个不同的存储器地址，因此NUMA架构相比UMA架构上使用线程绑定的方式更能提高并行效率。在NUMA系统架构中，可以理解为虚拟机是某核心的一个进程，而虚拟机的虚拟CPU是核心进程中的一种特殊的线程。不同的虚拟CPU是不同的线程，不同的线程是运行在不同的CPU上的。通过处理器的关联可以让虚拟机的虚拟CPU/内存绑定到固定主机的物理核心上，也可以进行动态分配，这一过程简称为“绑核”，绑核的虚拟CPU/内存只在所绑定的核上运行，但并不代表该虚拟CPU/内存独占这个核，其他虚拟CPU/内存也可以在这个核上工作。
在拥有多NUMA节点的主机中，虽然NUMA节点之间可以通信，但其通信速度远远低于节点内通信，这也是云服务提供商采用跨节点放置虚拟机的解决方案时，面临的系统性能下降的根本原因，其次，虚拟机之间通信需要经过互联总线或内存控制器，此时节点之间的资源竞争激烈，系统运行时间增加。因此，对于规格较小的虚拟机，为了保证其性能，一般选择将其放置在单个NUMA节点上；而对于规格较大或者复杂的虚拟机序列，可能存在单个节点难以放置甚至不能放置的情况，此时可以将其拆分开来，选择放置在多个NUMA节点上。
第三章基于强化学习的NUMA架构虚拟机放置算法设计........................21
3.1研究内容介绍...................................21
3.1.1问题描述...........................................22
3.1.2目标函数......................................23
第四章实验设计与分析...........................37
4.1仿真环境搭建........................................37
4.1.1基于TensorFlow的仿真环境搭建............................................37
4.1.2实验数据集...................................38
第五章总结与展望..................................50
5.1研究总结........................................50
5.2研究展望.............................50
第四章实验设计与分析
4.1仿真环境搭建
4.1.1基于TensorFlow的仿真环境搭建
本文使用基于TensorFlow[48]的强化学习框架进行仿真测试环境搭建，TensorFlow，简称TF，是Google在2015年发布的机器学习平台。
操作系统：Window10专业版；
开发工具：Anaconda3中Spyder4.1。
Spyder（前身是Pydee）是一个强大的交互式Python语言开发环境，提供高级的代码编辑、交互测试、调试等特性。Spyder是Anaconda自带的集成开发环境（IDE），可以在Spyder中进行TensorFlow的开发。Spyder中包括了Python、Matplotlib、NumPy、Scipy、Qt、IPython等多种工具及工具包的使用手册。
根据第三章对于整个模型的描述，实验设计需要实现的关键部分包括环境Environment部分以及智能体Agent部分。
对于环境Environment部分，本文需要生成虚拟机与物理机绑定关系的概率矩阵，并进行归一化，设置奖励机制的计算方式以及状态的更新方式（即概率矩阵的迭代）。对于智能体Agent部分，主要是实现与强化学习相关的内容，TensorFlow提供了完善的函数接口，因此，本文基于TensorFlow提供的函数接口，实现3.3-3.5节中关于强化学习模型的搭建、奖励函数、优化方法、模型训练以及3.6节中多模型决策等关键部分。此外，整个程序的框架中还包括任务数据管理、测试数据的记录和处理等内容。
第五章总结与展望
5.1研究总结
云计算中心的虚拟机放置问题是现代虚拟化数据中心的重要问题之一，近年来已逐渐成为研究的重点。本论文对国内外研究现状进行了详细的梳理，已有的算法研究或决策时间较长，或决策质量不够理想，或需要其他额外的成本，且目前只有少数研究者在NUMA架构的虚拟机放置问题上进行研究。本文分析了NUMA架构多节点的虚拟机放置问题的逻辑与原理以及服务器存在的资源竞争类型。为了有效地提升系统效率，从减少共享资源竞争角度出发，将虚拟机放置过程化为马尔科夫决策过程，并基于强化学习方法提出了Post算法。针对策略更新设计了差值奖励函数的形式，并加入了交叉熵最小化放置策略，大幅提高了训练效率，最后采用多模型决策找出全局最优策略。实验结果显示本文的方法可以在减少系统资源竞争的同时，在寻优时间上具有非常显著的优势，且具备较强的鲁棒性。本文的主要工作包括以下两个方面：
（1）提出解决云计算NUMA架构资源竞争的虚拟机放置方案，将当前系统存在的共享资源简单抽象为目标函数；将用户对系统资源需求抽象为概率矩阵来构建精确和可移植的模型，以预测在NUMA系统上不同位置的虚拟机的性能。使用离散概率分布来表示虚拟机选择放置的NUMA节点位置，将交叉熵方法作为一种采样技术更新概率矩阵，使用最大似然估计求得最佳概率质量。
（2）提出将PPO和交叉熵两种强化学习算法交替更新模型参数的算法进行问题求解，以此次采集样本与上次采集样本平均IPC值的差值作为奖励函数。本文还提出采用多决策模型算法改进策略，通过多模型同时决策并从中选取最优决策作为输出，从而提高算法的决策性能。最后搭建了基于Tensorflow的仿真环境，训练并测试算法模型，在算法寻优时间、最优解及算法鲁棒性等性能指标上分析本文提出的算法。本文对比了单模型决策和多模型决策的算法性能，并测试了多模型决策下不同模型数量对结果的影响，最后与监督学习算法、PPO等其他强化算法进行了性能的对比。经过实验后可以看出，Post算法可以在较短的迭代时间内寻得最优解，且具有较强的鲁棒性，虚拟机和NUMA节点个数等参数可根据实际情况进行调整，而不受数据中心规模限制，因此认为可以减少大型数据中心寻优计算总时长。
参考文献（略）