第39卷  计  算  机  学  报  Vol. 39    2016年  论文在线出版号  No.158  CHINESE J OF COMPUTERS  Online Publishing No.158 ——————————————— 本课题得到国家863高技术研究发展计划基金(2012AA01A302)、国家自然科学基金(61133004,61361126011,61502019,91530324)资助.  李慧娟，女, 1990年生,  硕士研究生,  计算机学会(CCF)会员,主要研究方向为并行计算. E-mail: huijuanli@buaa.edu.cn.  栾钟治,  男, 1971年生,  博士,  副教授,  计算机学会(CCF)高级会员,主要研究领域为分布式计算、高性能计算及并行计算等.E-mail: luan.zhongzhi@buaa.edu.cn.王辉,  男, 1987年生,  博士,  计算机学会(CCF)会员,主要研究方向为计算机体系结构和计算机系统等. E-mail: hui.wang@buaa.edu.cn.  杨海龙（通讯作者）,  男, 1985年生,  博士,  讲师,  计算机学会(CCF)会员,主要研究方向为运行时系统、性能建模、服务质量及高能效计算机体系结构等，E-mail: hailong.yang@buaa.edu.cn.  钱德沛,  男, 1952年生,  硕士,  教授,  博士生导师,  计算机学会(CCF)会士,  主要研究领域为高性能计算和计算机体系结构等. E-mail: depeiq@buaa.edu.cn  NUMA架构内多个节点间访存延时平衡的内存分配策略 李慧娟  栾钟治  王辉  杨海龙  钱德沛 （北京航空航天大学计算机学院中德联合软件研究所北京 100091） 摘  要  随着多核架构的发展和普及，NUMA多核架构凭借其本地访存低延时的优势，被各大商业数据中心以及科学计算集群广泛采用。NUMA架构通过增加多个内存控制器，缓解了多核架构下对同一个内存控制器的争用问题，但同时也增加了内存管理的负担。Linux的系统开发者为了实现充分利用NUMA本地访存低延时的特点，在为进程分配内存时，选择进程当前正在运行的NUMA节点作为分配内存的目标节点。这种分配会导致进/线程之间共享内存的不公平。针对这一问题，本文设计了一种保证NUMA架构内各内存节点间访存延时平衡的内存分配策略，并在Linux系统中实现和验证。实验结果表明，与Linux默认的内存分配策略相比，进/线程间的不公平性平均降低了16%（最多34%），并且各进/线程的性能没有较大抖动。 关键词  NUMA架构；内存分配策略；访存延时；访存延时感知；访存延时平衡 中图法分类号  TP302    论文引用格式： 李慧娟，栾钟治，王辉，杨海龙，钱德沛，NUMA架构内多个节点间访存延时平衡的内存分配策略，2016，Vol.39,在线出版号  No.158 LI Hui-Juan, LUANZhong-Zhi, WANG Hui, YANG Hai-Long, QIAN De-Pei，A Memory Allocation Policy for the Balance of Access Latency among Multiple Memory Nodes in NUMA Architecture，2016，Vol.39,Online Publishing No.158  A Memory Allocation Policy for the Balance of Access Latency among Multiple Memory Nodes in NUMA Architecture LI Hui-Juan, LUANZhong-Zhi, WANG Hui, YANG Hai-Long, QIAN De-Pei (Sino-German Joint Software Institute, School of Computer Science and Engineering, Beihang University, Beijing 100091) Abstract  Non-uniform memory access (NUMA) is a computer memory design used in multiprocessing, where the memory access time depends on the memory location relative to the processor. Modern data centers and the scientific  computing  clusters  widely  adapt  the  NUMA  architecture  due  to  its  low  latency  of  local  memory accessing,  which  is  achieved  by  partitioning  the  whole  memory  into  multiple  nodes  and  each  memory  node  is connected to a processors’ memory controller. However, this partitioning make the memory  management  much complicated. To achieve a low memory access latency, the default Linux memory policy chooses to allocate the physical  memory  pages  from  the  memory  node  where  the  process  is  running.  Unfortunately,  this  allocation policy  may  potentially  result  in  the  unfairness  among  the  processes,  e.g.,  due  to  the  process  scheduling,  one 网络出版时间：2016-10-16 23:57:21网络出版地址：http://www.cnki.net/kcms/detail/11.1826.TP.20161016.2357.002.html2  计  算  机  学  报  2016年 process with many local memory access may execute on remote node, which leads to the performance variation. To solve this problem, this paper proposes a node access latency indicator. Based on the indicator, we design a memory allocation policy assuring the balance of access latency among memory nodes in NUMA architecture, and implement it in the Linux kernel. To obtain the latency is platform dependent, but the policy in system kernel could be universal. The real system based evaluation results show that our proposal can reduce the unfairness up to 34% (with an average of 16%) while keeping a stable performance, compared to Linux’s default memory allocation algorithm. Key words  Non-Uniform  Memory  Access  architecture;  memory  allocation  policy; memory  access  latency; awareness of memory access latency; the balance of memory access latency 1   引言 现代数据中心、科学计算集群以及云架构普遍采用多核架构作为基础平台设施。多核架构凭借可扩展的计算资源提高了计算能力，然而内存一直是限制整体性能的瓶颈。主要表现有：有限的内存容量、有限的内存带宽和内存控制器的争用。虽然内存的容量已经足够大，但是相对于片上多核处理器的核数而言，内存资源依旧是有限的。并且所有的进程访问内存都需要通过唯一的内存控制器，当多个进程同时需要访存时，将会导致多数进程处于等待内存控制器的状态。非一致访存（Non-Uniform Memory  Access，NUMA）多核架构通过把一块内存划分成多个内存节点并且每一个节点附加一个内存控制器的方式，缓解了内存控制器的争用。在此基础上，所有的片上多核都可以通过高速片上互联和内存控制器访问每一个内存节点。现在NUMA架构的服务器有很多，这些服务器至少含有2个片上多处理器，比如戴尔的PowerEdge1和惠普的ProLiant2。 但是NUMA架构也使得内存管理更加复杂，尤其是片上高速互联和内存控制器的引入以及远程内存节点的可访问。访问远端内存节点相较于访问本地节点会增加通过片上互联的额外延时。现在已有一些研究以实现本地访存获得低延时来提高NUMA架构的整体性能。在NUMA架构下，与访存相关的开销可以分为四种：最后一级缓存（Last Level Cache, LLC）的争用、内存控制器的拥塞、高速片上互联的拥塞和远端内存访问的延时[1]。当前大多数研究集中在多级内存资源（LLC和内存）的争用。最常使用的解决方法是对应用进行分类学习，使相互干扰达到最小，以获取较高的整体性能                                                                 1 Dell PowerEdge Server,http://www.dell.com/PowerEdge 2012 2  HP Proliant Server, http://www.hp.com/go/proliant 2011 [2]。在这些研究中，一些集中在应用间的干扰识别和降低，另一些集中在实时调度策略[5]。但是它们侧重于从调度策略入手提高应用运行过程中访存的命中率，进而提升系统的整体性能，而忽略了系统内存分配策略是影响应用运行时行为的直接因素，内存分配的结果直接影响应用的后期运行行为和系统调度。因此本文从内存分配策略入手解决NUMA架构下共享内存资源时，各应用进程面临不公平的访存延时问题。这里不公平的访存延时是指：NUMA架构内各内存节点在分配时已具有的访存延时差异，这种内存节点的延时差异会使并行运行的应用进程遭受不公平的访存延时。这种不公平性是内存分配策略在分配时未考虑内存节点已具有的访存延时引起的。运行在这种内存分配策略下，各应用性能差异很大，这种不公平性在单物理机上很常见。 在多核架构下，多个进/线程公平地共享资源将会提高整个系统的性能，这点已有研究证实[7]，并且对访存延时是性能瓶颈的应用而言，访存的公平性是整体性能制约的关键。前人研究多集中在以调度的方式解决争用问题，而据我们研究发现，共享内存资源的各应用进程会由于操作系统的内存分配策略直接导致访存的不公平，进而影响系统整体性能。Linux系统的内存分配策略仅考虑到尽可能访问本地内存以实现低延时访存，但是忽略了内存节点在分配时已具有的访存延时差异。而这些访存延时差异直接影响应用的性能，尤其是访存密集型应用。由于系统内进/线程的实时调度，进程会被调度在远端节点上运行，此时访存延时会在原有的基础上增加片间互联的传输开销。最终导致应用的访存延时远远超过平均延时，进而影响整体性能。因此，在NUMA架构中，访存延时仍然是应用性能的主要制约因素，而在当前的内存分配策略下，它们还忍受着不公平的访存延时带来的性能抖动。 本文针对以上观察到的问题，提出一种内存分配策略，该策略可以感知每一个内存节点的访存延论文在线出版号  No.158            李慧娟等：NUMA架构内多个节点间访存延时平衡的内存分配策略  3 时，并且根据这些节点的访存延时是否平衡做出分配节点的选择，保证每次所选节点的访存延时最低。为了使多个进程具有相对公平的访存延时，在分配内存时实时分析各节点的访存延时并选出分配节点。本文在Linux系统中对默认的内存分配策略进行修改，并增加底层微体系结构的支持，实现了访存延时平衡的内存分配策略。实验结果表明：将Linux系统的原内存分配策略替换为本文提出的策略后，进程间共享内存的不公平度最多可由原来的1.52降低为1.04，降低原来的32%（平均降低15%），同时可以保证各个进程的性能稳定。 本文主要的贡献如下： 1.  提出一个可以衡量NUMA架构中内存节点访存延时的指标。该指标可以反映出整体访存开销（详见3.2节NUMA架构中GQ队列所支持的硬件事件信息与所处位置以及3.4.1小节的实现）。 2.  提出针对NUMA架构的内存分配策略，该策略可以实时感知内存节点的访存延时，并且在保证访存延时平衡的基础上选出分配节点。该策略用于选出访存延时最小节点并在该节点上分配物理页面，保证访存延时平衡和进程共享内存的公平性。 3.  在Linux系统中实现并且用访存密集型应用验证了提出的策略。实验结果表明进/线程间的不公平性被显著降低，同时保证了应用整体性能的稳定性。 后面文章组织结构如下：第2 章详细介绍了Linux系统的内存分配策略，通过一组简单实验展示了目前的分配效果，深入分析了造成该分配效果的原因。第3章详细介绍本文提出策略的设计并引入NUMA架构的关键部件以及策略中各部分的实现和该策略的执行过程。第4章展示和分析实验结果。第5章总结本文。 2   相关概念及问题阐述 2.1   Linux系统的内存分配策略 访问本地内存节点的延时要比访问远端节点低的多是NUMA架构的一个重要特征。因此，Linux操作系统为了充分利用这一特征，对物理内存的组织方式进行了改进。现有Linux系统采用三层结构来管理内存，它们分别是：节点、内存区和内存页面，它们之间的关系如图1所示。 N O RM A L内 存 区H IG H M EM 内 存 区节 点文本内 存 块 0内 存 块 1内 存 块 N…………页 面D M A 内 存 区 图1  Linux内存组织结构 其中页面（Page）是一个逻辑结构并且与物理内存页框一一对应，页面大小一般是4KB。大量连续的页面组成一个内存管理区，也称内存区（Zone）。内存区是为了有效地管理物理页面的使用而引入的。内存区可被分为3 种类型：DMA内存区，NORMAL内存区和HIGHMEM内存区。它们按照内存的地址分类，DMA内存区包含16MB的低地址内存页，用于硬盘I/O；NORMAL内存区包含地址高于16MB的内存页，用于给一般的进程分配内存页面；HIGHMEM内存区比较特殊，在32位系统中可能包含一些页面，但是在64位系统中，该区域不包含任何页面。32位操作系统的寻址能力是4G，如果系统内存大于4G，那么超出的内存页面就属于HIGHMEN内存区；但是对于64位操作系统，它的寻址能力对于当前的内存容量是足够的。每一种类型的内存区都包含一些小的内存块，这些内存块以单链表的形式存在。内存节点（Node）与NUMA架构中的物理内存节点一一对应，每一个节点内都包含上述的3 类内存区（如果HIGHMEM内存区存在）。 节 点   0N O RM A L内 存 区 0H IG H M EM 内 存 区 0D M A 内 存 区 0N O RM A L内 存 区 1H IG H M EM 内 存 区 1D M A 内 存 区 1N O RM A L内 存 区 0H IG H M EM 内 存 区 0D M A内 存 区 0单 链 表 0 单 链 表 1 图2节点内存区组织形式 4  计  算  机  学  报  2016年 为了实现NUMA架构内远端内存节点的可访问，内存的组织方式也做了调整，其中每个内存节点都包含两个单链表（如图2所示，以系统中包含两个内存节点为例），每个单链表上的结点包含一定数量内存页面的内存块。单链表0包含整个系统中所有内存区的内存块，不同节点的内存区按照节点间距离的远近来排列（Linux默认内存分配策略选择此链表上的内存块进行内存分配，所选内存块可能分散在多个内存节点）；单链表1只包含属于该物理内存节点的内存块（以图2为例，节点0的单链表1仅仅包含属于它的三种内存区）。 Linux系统的默认内存分配策略从单链表0上选择合适的内存块，并将选定的内存块交给Buddy分配器进行具体的内存页面分配。选择的合适内存块，是指该内存块上的空闲页面对于本次分配是足够的。为了防止某个内存块的所有页面全部被分配，Linux系统为每个内存块定义了三个“水位线”。它们分别是：pages_high，pages_low和pages_min。这些水位线用来表示内存块内剩余的空闲页面数量的多少，可以反映当前内存块经受的内存分配压力，图3中显示了内存块内可用空闲页面在系统运行过程中随着时间的变化情况。 p ages_h ighp ages_lowp ages_min时 间 初 始页 面 总数可 使 用 的 空闲 页 面页 面 回 收 进程 唤 醒 图3内存块水位线 在分配过程中，如果一个内存块中空闲页面数量已经降至pages_low，表示该内存块的分配压力已经很大。此时分配策略将会选择空闲页面数量在pages_low以上的内存块进行分配，这样可以保证每个内存承受的压力处在同一level。当所有内存块的空闲页面数量降至pages_low，系统将会唤醒内存回收进程，为那些空闲页面数量将达到pages_min 的内存块回收内存页面。这样做可以保证，系统中每个内存块承受的分配压力相当，但是这种平衡并不能保证访存延时的平衡。当两个内存块的分配压力一致，假设其中一个内存主要分配给访存密集型应用，而另一个分配给访存非密集型应用。由于访存频率的极大差异，他们的访存延时很难一致，并且处于不同内存节点的多个内存块，需要经过不同的内存控制器被访问，因此在内存分配时，仅考虑内存块的分配压力并不充足，综合考虑内存块所处内存节点的访存延时是必要的。 当一个进程需要申请内存时，Linux系统为其分配内存的过程如下：首先选择当前节点作为分配的目标内存节点。然后选择节点的两个内存单链表之一：如果这个进程的所有分配行为已被用户指定为完全在当前节点，那么将会选择只含有本节点内存块的单链表1；如果用户没有指定，则根据Linux默认分配策略选择单链表0，并且优先选择属于本节点的内存块。在单链表上选出合适的内存块后，交给Buddy内存分配器，分配物理页面并且将页面的地址返回给上层分配策略。 2.2   Linux系统的内存分配效果 Linux 分配策略在选择内存块给进程分配内存时，不考虑为进程选择的内存块是否属于同一个内存节点，会造成进程所分配的内存分散在多个内存节点。并且分配时不考虑所选内存块已经具有的访存延时，会造成应用进程间共享内存资源的不公平。这两点从访存密集型应用的运行情况可以看到直观的影响。 下面通过一组简单的实验来展示内存分配策略的内存分配结果和带给应用的不良影响。选用SPEC CPU 2006[8]。测试集中的leslie3d 测试程序在配置了2路IntelXeon  E5620多核处理器3。的IBM刀片服务器上运行。在关闭处理器的预取和超线程机制的情况下，该服务器单次可并行运行8个进程。配置leslie3d 测试程序运行时的8个运行场景，每个运行场景下运行不同数量的并行运行副本，分别是1-8。本次实验选取运行时间作为性能评估标准，这些运行时间是多次运行的平均值。 图4所示为测试程序leslie3d 在Linux系统内存分配策略下运行8个场景的性能。其中场景1中只运行一个进程副本，该进程的运行时间将作为并行运行时性能下降的基准线。从图中可以看出，平均运行时间随着进程数的增加而加长，但是运行时间并不是均匀增加。在一些场景会出现激增，并且leslie3d 在多次并行运行时整体性能抖动。                                                                  3   Intel  XeonProcessor  E5620  Specifications,  http://ark.intel.com/ products/47925/Intel-Xeon-Processor-E5620-12M-Cache-2_40-GHz-5_86-GTs-Intel-QPI, 2010 论文在线出版号  No.158            李慧娟等：NUMA架构内多个节点间访存延时平衡的内存分配策略  5  图4  Leslie3d在8个并行场景运行的性能 同一个场景中多个进程参差不齐的运行时间，反映了它们共享资源的不公平。对于访存密集型应用在计算资源充足的前提下，存储是主要的共享资源。在本文关注的范围内，存储资源主要指内存，访存延时的不均衡是造成运行时间不稳定的主要原因，这也是引起性能抖动的主要原因。为了量化这种不公平性，下面给出计算公式，该计算公式引用了Ebrahimi等提出的不公平度定义[7]。计算公式如下： ,ico runialoneTIST-=0 1 10 1 1{ , ,..., }{ , ,..., }NsoloNMAX IS IS ISUnfairnessMIN IS IS IS--=(1) 其中，ISi 表示进程i 的性能降低比例,Tico-run表示进程i 在并行运行时的运行时间，Talone表示单独运行一个进程的运行时间，则通过它们的比值得到任意进 程 并 行 运 行 时 的 性 能 降 低 比 例 。0 1 1 { , ,..., }N MAX IS IS IS-表示并行运行时性能相对最差进程的性能降低比例，0 1 1{ , ,..., }N MIN IS IS IS-表示并行运行时性能相对最好进程的性能降低比例，通过它们的比值得到该次并行运行时各进程间的不公平度[7]。 IS的值越接近1，表示并行运行的进/线程运行时间与单独运行相差越小，也从侧面反映访存延时比较小，接近单独运行时的延时；如果IS的值比1大很多，这表示并行运行的进程的访存延时偏高，导致IS 增大。同一个场景多个进程的IS 值接近，则表示该场景下运行的多个进程公平地共享内存，反之，则表示共享内存的不公平性很大。由Unfairness的计算公式可知，Unfairness的数值大于1，并且并行运行多个进程得到的IS 值差异越大，Unfairness的值越大，反之越小，趋近于1。  (a)  Leslie3d 在并行运行场景中的性能降低比例  (b)  Leslie3d 在并行运行场景中的不公平度 图5  Leslie3d在Linux策略下运行的效果 如图5所示为leslie3d 并行运行时，进程间的性能降低和不公平性（性能降低比例和不公平度分别由公式(1)计算得到）。其中(a)子图是leslie3d 在7个并行场景中每个进程的性能降低比例，(b)子图是leslie3d 在每个场景中进程间的不公平度。从(a)子图可以看出在各并行场景中，不同进程的性能降低比例差异很大。对照(b)子图可以发现，进程间性能降低比例差异较大的场景，其进程间的不公平度很明显。同时对照图4发现应用平均运行时间激增发生在不公平显著的场景下。  由此看来，Linux系统内存分配策略在运行过程中会增大多个进程间共享内存的不公平，并最终导致应用性能不稳定。这主要是由于运行过程中进程间较大的访存延时差异引起的。 2.3   应用运行效果的深入分析 为了查明形成性能抖动和进程访存不公平的原因，本节分析了应用运行过程中各进程的“进程 (PID) -核-物理内存”三者的映射关系。其中以并行运行6个进程的场景为例，如图6所示。    (a)  内存分配阶段运行分析  (b)  进程运行结束过程分析 图6并行运行6个进程时的运行过程分析 其中(a)子图展示了6个进程在内存分配阶段进6  计  算  机  学  报  2016年 程所分配的内存与运行所在处理器的对应关系，(b)子图展示了6个进程运行结束时的状态。从(a)子图中可以发现，进程在进入系统后的内存分配阶段，首先是有5个运行处理器1上，对应的内存节点1的内存分配量也很大；而同时只有一个进程运行在处理器0上，对应的内存节点0的内存分配量为内存节点1的一半。由于系统的负载均衡的进/线程调度，运行过程中两个处理器上运行的进程数趋于平衡，在内存分配结束后，两个处理器上的进程数达到平衡状态。从内存在各节点的分配比例和在各处理器上的进程数可以发现，有进程运行过程中处于远端访存状态。各进程的内存分配结果直接影响了进程后期的运行状态，对比(b)子图可以发现各进程完成结束的时间各不相同：首先是在处理器0上本地访存的进程结束（在8:34:50，处理器0上运行的进程只剩一个，对应内存节点0上的已分配内存全部释放）；其次是在处理器1上本地访存的进程结束（在8:35:10，处理器1上的进程全部执行完，只剩下处理器0上远端访存的进程运行）；最后是运行在处理器0上的远端访存进程运行结束。 经过以上分析可以看出应用进程的性能直接受内存分配阶段所分配的内存影响，不同的内存分配会导致进程遭受不同的访存延时，而访存延时也最终决定了应用的性能。内存分配策略分配在分配内存时不考虑当前节点已具有的访存延时，会使得进程所分配到的内存具有高访存延时，与其它的访存延时较低的其它进程相比，遭受着不公平的访存延时，而且会导致后期运行的性能下降，最终会影响应用的整体性能。并且在分配内存块时不对当前分配内存块与进程已分配到的内存块进行是否属于同一内存节点的检查，这会造成应用多次运行时所分配内存的分布情况不同，因而多次运行的性能差异性较大，也就是说应用性能抖动。结合Linux的内存组织方式可以看出，Linux内存分配策略需要从以下两点继续完善： 1）分配策略选择单链表0（包含所有内存节点内存块的链表）上的内存分配，分配过程中不进行严格的节点匹配（当前内存块是否与之前分配给进程的内存块属于同一个内存节点），可能会导致分配给一个进程的内存块分散在多个内存节点。 2）分配内存时没有考虑节点间的访存延时是否平衡。 因此，本文的目标是设计一个可以感知多个NUMA节点间访存延时平衡的内存分配策略，分配时选择当前最小延时节点可以有效降低进程的访存延时，降低进程间的不公平，同时保证性能的稳定。 3   访存延时平衡的内存分配策略 3.1   整体设计 实现访存延时平衡分配策略的整体设计如图7所示，该设计主要包括两个部分：延时感知部分和延时平衡的节点选择部分。 延时感知部分实时监测每个处理器的硬件事件计数器，并计算各节点的访存延时，然后对各节点的访存延时进行排序，得到访存延时的递增节点序列，最后根据有序序列选择延时最小节点和当前系统内各内存节点间的访存延时是否平衡，并且将这些信息发送给内存节点选择部分。延时平衡节点选择部分，根据延时感知部分提供的信息获取各内存节点的访存延时的平衡状态，并根据这些延时信息做出节点选择，并且对分配给同一进程的内存块所属内存节点的一致性进行验证。然后调用Buddy分配器分配物理内存页面。 延 时 感 知处 理 器   0 处 理 器   N-1 …事 件 监 控延时感知部件事 件 计 数 器 0事 件 计 数 器 7…事 件 计 数 器 0事 件 计 数 器 7…延 时 平 衡 节 点 选 择结 构 图…物 理 页 面Bu d d y内 存分 配 器操 作 系 统 层延 时 感 知平 衡 状 态 和 最 小 节 点 生 成 图7访存延时平衡内存分配策略的整体设计 3.2   延时感知 延时感知部分是基于NUMA架构中Uncore4子系统实现的，Uncore子系统是Intel 提出的概念，用来描述多核处理器上除去core以外的功能部件，该部分对系统的性能起关键作用5。Uncore子系统处于连接计算资源和内存资源的关键位置（详细位置如图8所示），并且访存延时可以用访存请求在                                                                 4  Uncore Wikipedia, http://en.wikipedia.org/wiki/Uncore 2014,12,29 5   IntelPerformance  Counter  Monitor,  Thomas,  W.  (Intel), https://software.intel.com/en-us/articles/intel-performance-counter-monitor-a-better-way-to-measure-cpu-utilization 2012,8,16 论文在线出版号  No.158            李慧娟等：NUMA架构内多个节点间访存延时平衡的内存分配策略  7 Uncore子系统内的平均滞留时间来衡量。 图8以含2个节点的Intel Westmare-EP架构为例来展示详细的NUMA结构。虚线框圈出多核处理器，每个处理器都可以分成Core和Uncore两部分，Core部分包含多个物理核，Uncore部分包含LLC，IMC 和QPI6。每一个物理核都含有一个队列Super Queue (SQ)，这个队列缓存了对应物理核上没有命中L2级cache的访存请求，这些请求会进入Uncore子系统等待内存服务。Global  Queue  (GQ)是Uncore子系统中缓存访存请求的队列，这些被缓存的请求最终被LLC，本地内存控制器或者通过QPI的远端内存控制器服务。而LLC，IMC 和QPI是整个系统内的三个主要共享资源，它们看似独立却相互影响，正是这种影响使得NUMA架构的内存管理更加复杂但是GQ队列却能通过访存请求的平均滞留时间来感知这种影响。针对访存密集型应用，这种Uncore子系统的数据阻塞会严重影响性能[9]，因为大部分请求都需要访问内存，因此通过借助GQ中访存请求的平均滞留时间可以得到访存密集型应用的访存延时（文中提到的访存延时严格来说指的是访存请求在GQ队列中的平均滞留时间）。 L L C Q P I内存控制器  IM C内存节点0L L C Q P I内存控制器 IM C内存节点1C 3C 0 C 1C 2G Q G Q    U n c o r e      C o r e处 理 器（ p r o c e s s o r ）S Q S QS Q S QC 3C 0 C 1C 2S QS QS QS Q 图8  Intel的Westmare-EP NUMA结构 延时感知部分由3个组件组成：1）事件监控组件，该组件周期性地监控每个处理器的Uncore事件计数器，并将采集到的信息，发送给上层延时感知组件，事件监控组件是延时感知部分实现的基                                                                 6   An  Introduction  to  the  Intel  QuickPath  Interconnect (  QPI  ),http://www.intel.com/content/www/us/en/io/quickpath-technology/quick-path-interconnect-introduction-paper.html 2009,1 础，该组件的实现细节见3.4.1小节；2）延时感知组件，该组件首先缓存来自监控部件的信息，然后提取有效数据并且按照滑动窗口的思想处理数据以获得稳定的访存延时，最后将各内存节点的访存延时序列发送给上层的平衡状态延时最小节点生成组件，该组件实现的延时获取方法见3.4.2小节；3）平衡状态与延时最小节点生成组件，该组件首先接收来自延时感知组件的延时序列，其次对该访存延时序列进行排序，然后根据有序的延时序列，决策多个节点间的访存延时是否平衡并且选择最低延时的节点，最后将节点间的延时平衡状态和最低延时节点发送节点选择模块，该组件的实现细节见3.4.3小节。 为了避免分配选择延时高的内存节点，将延时平衡感知添加在原Linux分配策略的上层，并且基于延时感知选择内存节点。 3.3   延时平衡的节点选择 延时平衡的节点选择部分首先接收来自延时感知部分的信息，并从信息中提取节点间的延时平衡状态和延时最小节点，然后根据分配进程的用户指定策略和系统平衡状态选择内存分配的目标节点。选定目标节点后，将该节点信息写入进程策略中，并且在该节点的单链表0上选择内存块，在选择内存块时，除了进行节点空闲页面容量是否充足的判断外，也进行内存块所属内存节点的验证，验证通过后内存块才被最终选定，以供Buddy内存分配器分配物理页面。 延时平衡的节点选择部分是访存延时平衡的内存分配策略的核心，并且在内核发挥作用。本节描述了该分配策略以及内存块的所属节点验证机制，其中分配策略的实现见算法1和3.4.4 小节。 算法1.  延时平衡的节点选择策略 1:输入:平衡状态：GQ_balance，最低延时节点：GQ_node 2:输出:目标内存分配节点.  3:  4:If task memory policy == NULL THEN 5: If GQ_balance == FALSE THEN 6:       memory allocation target node = GQ_node; 7:       ELSE 8:     memory allocation target node = current node; 9:     END IF 10:   END IF 11: 12: Buddy allocator; Linux内存分配策略在选择内存块分配内存时，根据内存块中空闲页面的数量进行选择，但是这样可能会导致为同一个进程分配的内存页面分散在不同的内存节点上。因此为8  计  算  机  学  报  2016年 了使其更加完善，本文在内存块选择机制中添加了所属内存节点验证机制。具体实现见3.4.5小节。 3.4   访存延时平衡分配策略的实现 本节在内核版本是2.6.32的Centos6.5系统中实现访存延时平衡的内存分配策略。所用主机是有2个内存节点的NUMA服务器（结构见图8），该服务器的详细配置如表1所示。本节主要讲述实现细节：1）监控硬件性能的工具；2）NUMA架构下访存延时的计算方法；3）延时分析处理方法；4）延时平衡的节点选择。前三个在内核模块中实现，主要功能由附加在模块内的进程实现，该进程的生命周期从模块载入内核开始至模块移除为止。 表1服务器配置信息 项目  配置参数 机器型号  IBM HS22刀片服务器 刀片参数  Intel Xeon CPU E5620，2.4GHz， 每个CPU含四个物理核 缓存系统  每个物理核含有L1，L2 cache两级 私有缓存，每个CPU共享L3 cache 内存  12G DDR2内存 软件环境  Numactl 操作系统  CentOS 6.5版本的操作系统 内核版本：linux-2.6.32-431.el6 3.4.1    硬件性能工具 该硬件性能工具是自己开发的工具，是基于MSR-tools 中的读写方式在内核模块中实现的，是一个运行在Linux内核的可读写Uncore  PMU事件的工具。该工具首先初始化Uncore事件的寄存器和计数器，然后周期性地读取和GQ队列相关的事件，这些事件列在表2中（所有这些事件来自于Intel 的软件开发手册7，但是更详细的信息来自与Intel研发人员的讨论8）。主要读取每个队列的occupancy和alloc事件，然后将通过收集的数据计算访存延时。 表2硬件性能事件 硬件事件  事件描述                                                                  7  Intel  64  and  IA-32  Architectures  Software  Developer’s  Manual, http://www.intel.cn/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-manual-325462.pdf 2014,9 8   Intel  forums:  The  uncore  event  about  GQ, https://software.intel.com/en-us/forums/topic/540643 2015,2,5 UNC_GQ_OCCUPANCY_READ_TRACKER  当前读队列中访存请求的占用周期数 UNC_GQ_ALLOC_READ_TRACKER 当前读队列中访存请求个数 UNC_GQ_OCCUPANCY_ WRITE _TRACKER 当前写队列中访存请求的占用周期数 UNC_GQ_ALLOC_WRITE_TRACKER 当前写队列中访存请求个数 UNC_GQ_OCCUPANCY_ PEER_PROBE _TRACKER 当前QPI队列中访存请求的占用周期数 UNC_GQ_ALLOC_PEER_PROBE_TRACKER 当前QPI队列中访存请求个数 3.4.2    访存延时的计算方法 为了对访存延时进行建模，本文提出一个延时指标。基于在3.2节中介绍的内容：GQ队列中访存请求的平均滞留时间可以计算访存延时，选择GQ队列中请求的平均滞留周期数GQ_Cycles作为指标。GQ_Cycles与Uncore penalty[5][7]有两点不同：首先计算方法不同，GQ_cycles完全通过性能计数器收集的数据计算得到；Uncore penalty通过估计不同资源的访问时间及比例计算得到。其次意义不同，GQ_cycles 预测当前运行在同一个处理器上多个应用的整体访存性能；Uncore penalty估计运行在某个物理核上的进程性能。通过表2中事件，可以计算出每一个GQ内分队列的访存延时，然后用线性回归的方法得到GQ_Cycles。 计算各队列的访存延时：用X表示表中提到的三种队列，分别是读请求队列，写请求队列和通过QPI远端访存的队列。每个队列有两个事件，共六个事件可分为两类表示为：GQ_OCCUPANCY_X和GQ_ALLOC_X。其中GQ_OCCUPANCY事件的计数器记录了访存请求占用的周期数，该计数器会在每个周期按照队列中的请求个数增加周期数。GQ_ALLOC事件的计数器记录了当前队列的访存请求个数，该计数器会在请求进入队列时增加请求个数。例如，当前请求队列只放入一个元素，此时GQ_ALLOC计数器增加至1，该请求在队列中滞留了100个周期，那么GQ_OCCUPANCY计数器会在每一个周期都增加1，最终GQ_OCCUPANCY的值增加为100，而GQ_ALLOC的值一直是1。然后用它们做除法可以得到GQ_X_Cycles，然后统计得到下边的式子： _ _ _ ,xGQ Cycles GQ X Cycles = ¶ * å（2） 论文在线出版号  No.158            李慧娟等：NUMA架构内多个节点间访存延时平衡的内存分配策略  9 其中x¶是统计得到的各分队列系数。最后得到延时指标GQ_Cycles。 3.4.3    延时分析处理方法 在得到GQ_cycles的前提下，用快排序的方法排列多个节点的访存延时。然后判断排序在第一位和最后一位的两个节点的延时是否处在同一个延时等级（在实际运行的系统中，同一延时等级是一个界限值，并且该界限值与系统状态和运行应用都有关系，本文设定的界限值是根据当前系统状态得到的）。如果它们的绝对差值小于界限值，那么将返回TRUE，表示当前多个节点间的访存延时平衡；如果差值大于界限值，那么返回FALSE，表示当前节点间的访存延时不平衡。无论当前访存延时是否平衡，最后都会把平衡标志和最低延时节点传递给决策部件。 3.4.4    延时平衡的节点选择 该选择机制在内核中实现，细节见算法1. 在分配内存时，首先判断当前任务内存策略是否为NULL，如果策略为空并且此时多节点间的延时不平衡，那么将选择当前的最低延时节点作为目标分配节点；如果策略为空，但是节点间的延时平衡，那么选择当前节点作为目标分配节点。当目标节点确定后，根据内存块选择机制，选定合适的内存块并调用底层Buddy分配器进行最后的物理页面分配。 访存延时平衡的内存分配策略可以实时感知访存延时并判断平衡，但是在Linux系统启动时，所感知的是“伪延时平衡”。在内核初始化时，将平衡设置为TRUE，因此系统启动过程中的系统进程申请的内存都选择它们运行时的节点作为分配。进入系统后，模块会自动加载进入内核，只要模块处于加载状态，内存分配策略就可以真实地感知系统内多节点间访存延时的平衡，并依照感知信息做出节点选择决策。 3.4.5    内存块所属节点的验证 该内存块所属节点的验证机制在内核中实现，在得到为进程分配的目标节点GQ_node之后，获取该GQ_node的节点掩码。这样该进程在后续内存分配时将根据进程的目标内存节点选择内存块分配内存，可以尽可能保证该进程多次分配的页面处在同一个内存节点上。 在分配过程中，根据GQ_node的掩码和内存块包含空闲页面的数量来确定最终选择的内存块。在当该GQ_node的节点上所有的内存块所包含的空闲页面都低于page_low的水位线时，会选择其他内存节点上的内存块分配内存以保证进程申请的内存被成功分配。如果进程在分配过程中遇到这种情况，需要配合调度策略保证该应用进程的性能，但是本文目前的解决方案中，还没有实现基于访存延时平衡状态的调度策略，这也将是未来的研究方向。 3.4.6    小结 开 始结 束读 取 进 程 策 略mem _p olicy读 取 节 点 间 延 时 平衡 状 态使 用 指 定 分 配 策 略否是 否 平 衡是否选 择 最 小 延 时 节 点 选 择 当 前 节 点Bu d d y 内 存分 配 器是策 略 是 否 为 N U LL延 时 感 知平 衡 状 态 和 最 小 节点 生 成延 时 感 知 模 块 加 载延 时 平 衡 分 配 策 略工 作事 件 监 控选 择 指 定 节 点最 小 延 时 节 点 的内 存 块 验 证当 前 节 点 的内 存 块 验 证指 定 策 略 节 点 的内 存 块 验 证 图9访存延时平衡内存分配策略的内存分配流程图 本章主要描述了访存延时平衡内存分配策略的设计与实现，图9是该策略在内存分配过程中的具体流程图。访存延时平衡内存分配策略的执行过程如下：进程申请内存，触发系统调用内存分配函数，此时进入访存延时平衡分配策略的入口。1）延时感知模块在后台实时运行，周期性地获取各内存节点的访存延时以及节点间的访存延时平衡状态。2）延时平衡策略读取进程的memory_policy并判断是否为NULL，若不为空，则按照memory_policy的内容分配；若为空，则置memory_policy为访存延时平衡的内存分配策略，同时读取GQ_balance，此时延时感知模块会返回GQ_balance和GQ_node给延时平衡策略。3）延时平衡策略根据GQ_balance10  计  算  机  学  报  2016年 判断当前多个内存节点间的延时平衡状态，如果GQ_balance为TRUE，则选择当前node作为目标内存分配节点并且记录为memory_policy的优先选择节点；若GQ_balance为FALSE，则选择最小延时节点GQ_node同时在memory_policy中记录节点信息。4）最后，将所选择的节点上合适的内存块交给Buddy进行物理页面分配。 延时感知模块未加载时，分配策略感知的伪平衡状态不会影响进程的内存分配。因为当延时平衡内存分配策略判断节点间延时平衡时，会按照默认操作系统策略的分配方式选择当前节点分配内存，唯一的区别是，延时平衡策略会选择同一内存节点的内存块为同一进程分配内存，以保证进程的内存在同一个内存节点保证进程访存的公平性。 4   实验结果分析与评价 本章通过对比分析实验结果来评价访存延时平衡内存分配策略（在本章后续小节中称为延时平衡策略）的效果。主要从宏观上延时平衡策略的分配效果和微观上各内存节点之间的访存延时两个方面进行评价。在4.1节选用SPEC CPU 2006，NPB9和stream10三种测试集应用进行实现效果的对比分析。首先通过2.2节描述的实验场景对比分析延时平衡策略和Linux系统内存分配策略（后续小节称为原Linux策略）的宏观实验效果，在不公平性对比分析中加入手动调优策略辅助对比分析，其中手动调优策略是指根据numactl 设置的本地访存（localalloc）配置，以实现所有进程的本地访存。然后在4.2 节对各测试应用在延时平衡策略和原Linux策略下运行时各内存节点的访存延时进行了对比分析。最后在4.3节通过多个访存密集型应用混合在原Linux策略，延时平衡策略以及手动调整最优的三种策略下执行的实验结果对比，验证延时平衡策略的有效性。 4.1   同一应用多个进程实验的对比分析 本节对比分析三个方面：并行运行时应用的整体性能（图10），并行运行时的各应用进程的性能降低图11-图18），并行运行时应用进程间的不公平（图12）。                                                                  9  NPB,http://www.nas.nasa.gov/publications/npb.html 10  McCalpin,  J.  D.  STREAM:  Sustainable  memory  bandwidthin  high performance computers, http://www.cs.virginia.edu/stream/ 1995 4.1.1    应用的整体性能 图10 中显示的是应用在延时平衡策略和原Linux策略下运行的性能对比图。为了清晰地展示图中信息，选用了SPC CPU 2006中的bwaves，milc，leslie3d，GemsFDTD和STREAM的5个应用。其中实线是在原Linux策略下运行的结果，虚线是采用本文策略运行的结果。从图中可以看出随着并行进程数的增加，实线图的运行时间不平稳地增长，并且有凸起；而虚线图的运行时间几乎是线性增长的，并且增长幅度整体低于实线。由此可见，延时平衡策略能够保证同一应用的多个进程并行时性能稳定。为了进一步验证，在图11至图18给出并行运行时，每一个进程的性能降低。  图10两种策略下的应用性能对比图 4.1.2    同一应用多个进程并行运行时的性能降低 本小节显示的是在两种策略下并行运行时，每个进程的性能降低的对比。图11 中上子图是leslie3d 在原Linux策略下运行的实验结果，下子图是leslie3d 在延时平衡策略下运行的实验结果。两副子图对比很明显，在延时平衡策略下运行的并行场景中，同时运行的多个进程由共享内存带来的性能降低比例趋于一致，而在原Linux策略下，并行的多个进程由共享内存带来的性能降低比例参差不齐，这种参差不齐反映出它们共享内存的不公平。同时对比 图11  Leslie3d 在两种策略下的性能降低对比中leslie3d 在各场景的性能情况，延时平衡策略的平稳性很好，因此减小进程间性能降低比例的差异可以应用的稳定整体性能。 论文在线出版号  No.158            李慧娟等：NUMA架构内多个节点间访存延时平衡的内存分配策略  11  图11 Leslie3d在两种策略下的性能降低对比 图12中显示了stream应用在延时平衡策略和原Linux策略下并行运行时，每个进程的性能降低比例对比。其中上子图是stream在原Linux策略下运行的实验结果，下子图是stream在延时平衡策略下运行的实验结果。两副子图对比很明显，从纵坐标的数值范围可以发现，Linux策略下运行的各并行场景中，性能减慢比例在8个进程并行运行时最大达到了1.70，而在延时感知策略下运行时最大仅为1.24。同时发现在延时平衡策略下，2-6个进程运行时各进程的性能减慢比例在1.10左右，在7-8个进程运行时进程性能减慢比增大，但是都小于Linux策略导致的性能降低比例。  图12 Stream在两种策略下的性能降低对比  图13 Bwaves在两种策略下的性能降低对比 图13显示了应用bwaves在延时平衡策略和原Linux策略下并行运行时，每个进程的性能降低比例对比。其中上子图是bwaves在原Linux策略下运行的实验结果，下子图是bwaves 在延时平衡策略下运行的实验结果。两副子图对比很明显，bwaves应用在延时平衡分配策略下运行时，7个并行场景中各进程的性能降低比例保持在1.12以下，即使在8个进程满负载运行时也同样保持，并且每个场景下各进程的性能降低比例趋于一致；但是在Linux策略下运行的各并行场景中，性能降低比例在8个进程并行运行时最大达到了1.32，最小1.1以下，且在每个并行场景中各进程的性能降低比例差异性比较大。在Linux策略下场景3运行时，各进程的性能降低比例维持在1.05以下，说明Linux策略的分配时的节点选择随机性直接影响了并行运行各进程的性能降低比例。延时平衡策略的节点确定选择机制保证了策略分配时各进程性能的稳定性。 图14中显示了应用milc在延时平衡策略和原Linux策略下并行运行时，每个进程的性能降低比例对比。其中上子图是milc在原Linux策略下运行的实验结果，下子图是milc在延时平衡策略下运行的实验结果。两副子图对比很明显，milc应用在延时平衡分配策略下运行时，每个并行场景下各进程的性能降低比例基本一致，并维持在1.20以下。而在Linux策略下运行时，各进程的性能降低比例不一致，体现出进程间访存的不公平。  图14 Milc在两种策略下的性能降低对比 图15显示了应用GemsFDTD在延时平衡策略和原Linux策略下并行运行时，每个进程的性能降低比例对比。其中上子图是GemsFDTD在原Linux策略下运行的实验结果，下子图是GemsFDTD在延时平衡策略下运行的实验结果。两副子图对比很明显，GemsFDTD应用在延时平衡策略下运行时，每个并行场景下各进程的性能降低比例都一致，但是相对其它应用，仅维持在1.30以下。即使如此各进程的性能降低比例也都小于Linux策略下运行的12  计  算  机  学  报  2016年 情况。  图15 GemsFDTD在两种策略下的性能降低对比 图16 中显示了应用IS 在延时平衡策略和原Linux策略下并行运行时，每个进程的性能降低比例对比。其中上子图是IS在原Linux策略下运行的实验结果，下子图是IS在延时平衡策略下运行的实验结果。IS应用在延时平衡策略下运行时，各进程的性能降低比例基本一致，但是相对其它应用，IS在并行运行时由于并行带来的性能降低明显，延时平衡策略也仅能将降低比例仅维持在3.15以下。  图16 IS在两种策略下的性能降低对比  图17 EP在两种策略下的性能降低对比 图17 中显示了应用EP 在延时平衡策略和原Linux策略下并行运行时，每个进程的性能降低比例对比。其中上子图是EP在原Linux策略下运行的实验结果，下子图是EP 在延时平衡策略下运行的实验结果。两副子图对比很明显，EP应用在延时平衡策略下运行时，各进程的性能降低比例都一致，且在进程数小于8的场景中性能降低比例接近1，EP并行运行时由并行带来的性能降低不明显，延时平衡策略将其性能降低比例维持在1.2以下。  图18 LU在两种策略下的性能降低对比 图18 中显示了应用LU 在延时平衡策略和原Linux策略下并行运行时，每个进程的性能降低比例对比。其中上子图是LU在原Linux策略下运行的实验结果，下子图是LU在延时平衡策略下运行的实验结果。两副子图对比很明显，LU应用在两种策略下运行时，每个并行场景下各进程的性能降低比例基本一致，随着进程数的增加，性能降低比例的差异越明显。延时平衡策略仅将性能降低比例维持在1.24以下，略微优于Linux策略。 SPEC CPU测试集中的应用主要是偏向CPU计算的应用集，NPB测试集中的应用包含了整型和浮点型运算，而stream测试集是经典的访存密集型应用。综合以上分析可得出结论：访存延时平衡内存分配策略缓解了并行进程运行时各进程的性能降低比例，稳定了应用运行的整体性能。 4.1.3    同一应用多个进程并行执行时的不公平 图19显示的是8个应用在原Linux策略，延时平衡策略以及手动调优的三种策略下分别运行时，同一应用的多个进程间访存延时的不公平。  (a)  Leslie3d在三种策略下进程间的不公平对比  (b)  Stream 在三种策略下进程间的不公平对比  论文在线出版号  No.158            李慧娟等：NUMA架构内多个节点间访存延时平衡的内存分配策略  13 (c)  Bwaves在三种策略下进程间的不公平对比  (d)  Milc在三种策略下进程间的不公平对比  (e)  GemsFDTD在三种策略下进程间的不公平对比  (f)  IS在三种策略下进程间的不公平对比  (g)  EP在三种策略下进程间的不公平对比  (h)  LU在三种策略下进程间的不公平对比 图19三种策略下进程间的不公平对比 上图中(a)子图展示了leslie3d 的多个进程运行不公平的实验对比。延时平衡策略维持进程间的不公平在1.1以下，并且接近于手动调优结果。与原Linux 策略相比极大地降低了进程间的不公平，同时提高了整体的性能。在leslie3d 的实验对比中，延时平衡策略可以将原Linux策略带来的不公平至多降低了24%，平均降低17%。其它子图给出的是剩余四个应用在这三种策略下运行时，进程间共享内存不公平的展示。 以上对比结果，表明延时平衡策略极大地降低了进程间的不公平性，并且与手动调优结果接近。其中stream在场景8的对比结果显示，延时平衡策略将原Linux策略带来的不公平性降低了35%。 4.2   并行运行时各内存节点访存延时的对比分析 为了分析访存延时平衡策略对各内存节点访存延时的影响，本节针对应用在原Linux策略和延时平衡策略下，并行运行时各内存节点所具有的访存延时进行了对比分析。其中访存延时通过访存请求在GQ队列中的平均滞留时间GQ_cycles来衡量。选择LU在场景6和场景7以及EP应用在场景7运行的实验数据进行分析。  （a）LU在两种策略下运行6个进程时节点间的访存延时  （b）LU在两种策略下运行7个进程时节点间的访存延时  （c）EP在两种策略下运行7个进程时节点间的访存延时 图20两种策略下内存节点间的访存延时 图20中显示了应用在两种策略下运行时的各内存节点访存延时随着采样的状态图，其中(a)子图是两种策略下LU在并行场景6中运行时两内存节点访存延时的状态；（b）子图是两种策略下LU在并行场景7中运行时两内存节点访存延时的状态，采14  计  算  机  学  报  2016年 样周期为0.5ms一次。对比两副子图可以发现，在延时平衡策略下运行时两内存节点的访存延时随着运行时间逐渐靠近，尤其是在场景6进程数为偶数时，每个内存节点提供访存服务的进程数是一致的，因此访存延时也趋于一致的。在场景7进程数为奇数时，会出现某个内存节点的访存延时高于另一个，这是因为该内存节点提供的访存服务的进程数多一个，这是有算法思想决定的。但是在原Linux策略下，无论哪个场景两内存节点的访存延时都相差甚远，是由Linux策略在分配内存时为同一进程分配的内存分散在多个节点引起的。（c）子图是两种策略下EP在并行场景7中运行时两内存节点访存延时的状态。两策略的对比结果明显，EP在延时平衡策略下运行时，两内存节点的访存延时基本一致。而在Linux策略下运行时，其中一个节点访存延时是另一节点的两倍。对比结果从微观角度验证了延时平衡策略对各内存节点间访存延时平衡的保证。但是关于远端内存访问的比例与GQ_cycles，不公平度以及应用性能下降之间的内在联系，是否有明确的定量关系，是我们后续的研究点之一。 4.3   混合实验 为了验证访存延时平衡内存分配策略的有效性，本文还设计了多个应用并行执行的混合实验。文中分别设置了混合2种，3种和4种访存密集型应用同时运行的实验，实现效果都很明显。在混合2个应用的实验中，延时平衡策略最大降低了原来不公平的32%，平均18%。在混合3个应用的实验中，延时平衡策略最大降低了原来不公平的24%。下面详细给出混合运行四个应用的实验配置和实验结果。 混合四个应用的实验有两个场景，场景1是每个应用分别运行1个进程，总共4个进程并行执行，场景2是每个应用运行2个进程，共8个。 4.3.1    应用的整体性能 图21中展示4个应用：stream，GemsFDTD，milc和leslie3d 同时运行在两个并行场景下的运行时间图。在场景1中，原Linux策略下的性能与延时平衡策略相当，这是因为此时进程总数只是系统满负载的一半，造成的数据阻塞还不明显。但在场景2中，结果明显很多，平均运行时间减少50s，性能提高5%。  图21两种策略下4个应用混合运行时性能对比 4.3.2    多应用多个进程并行运行时的性能降低 在前文的不公平度计算公式适用于在单应用多进程并行运行模式下的性能降低比例和不公平度的计算，对于多应用多进程并行运行模式通过下边的公式计算得到： ( , )( , ),i j co runijialoneTIST-=(0,0) ( , ) ( 1, 1)(0,0) ( , ) ( 1, 1){ ,..., ,..., }{ ,..., ,..., }i j M Nmixi j M NMAX IS IS ISUnfairnessMIN IS IS IS----=(2) 其中i 表示同一场景中的某个应用，j 表示该场景中某个进程，(i,j)表示该场景中属于i 应用的进程j；M表示该场景中的应用总数，N表示该场景中每一应用可运行的进程个数。其中，IS(i,j)表示进程i的性能降低比例，其中T(i,j)co-run 表示在并行运行时应用i 的进程j 的运行时间，Tialone 表示应用i 单独运行一个进程的运行时间，通过它们的比值得到应用i 的进程j 在多应用混合并行运行时的性能降低比例。通过并行运行时性能相对最差进程与相对最好进程的性能降低比例的比值，得到该次并行运行时各进程运行的不公平度。 并行运行场景1 2 性能降低比例（时间减慢程度）11.11.21.31.41.51.61.7mix4:stream leslie3d milc GemsFDTD (a)  四个应用混合运行在Linux策略下的性能降低 并行运行场景1 2 性能降低比例（时间减慢程度）11.051.11.151.2mix4:stream leslie3d milc GemsFDTD (b)  四个应用混合运行在延时平衡策略下的性能降低 图  22两种策略下4个应用混合运行时性能降低对比 图22 显示了在两种策略下四种应用混合运行论文在线出版号  No.158            李慧娟等：NUMA架构内多个节点间访存延时平衡的内存分配策略  15 实验的性能降低对比。(a)子图是它们在原Linux策略下运行的实验结果，(b)子图是在延时平衡策略下运行的实验结果。两副子图实验结果对比很明显，在延时平衡策略下相同场景多个进程的性能降低基本一致且都低于1.2，而在原Linux策略它们参差不齐，尤其是在场景2中，它们最小低于1.1，最大高于1.6。同时对比图21应用在场景2下的性能情况和图22进程间的不公平，在场景2时，延时平衡策略有效地降低了进程间的不公平同时性能稳定并得以提升。  4.3.3    多应用多个进程并行运行时的不公平  图23三种策略下4个应用混合运行时的不公平对比 图23显示了四个应用在原Linux策略，延时平衡策略以及手动调优的三种策略下混合运行时进程间的不公平。可以看出在8进程并行时实验结果对比很明显。显著降低了原来不公平的28%，平均值17%，并且接近手动调优。 总之，延时平衡策略能够有效地降低进程间共享内存资源的不公平性，进而稳定应用的整体性能。实验效果显示最大降低了原来不公平的34%，平均降低了16%。单一应用和混合应用实验都充分证明了延时平衡分配策略的有效性和稳定性。 4.4   整体开销 整体开销从理论和实验两个角度分析：1）本文策略实现的主要开销来自于两个方面：在内核中判断节点间访存延时的平衡和硬件性能工具读取计数器。首先，判断平衡的快排序算法，由于NUMA节点的有限性，快排序算法的开销可以忽略。其次，读取计数器仅使用极少的系统资源，因此读取事件计数器的开销也可以忽略。2）实验数据表明：在进程的内存分配阶段，该策略与原Linux策略所耗时间是一致的；在后期执行过程中，原Linux策略所引起的进程调度频繁，后期执行时间比本文提出策略长。综上两点，访存延时平衡内存分配策略的开销可以忽略。  图 24内存分配阶段两策略消耗时间对比 实验所用应用是多次配置的stream测试集，使其中数组占用的实际大小分别为：1G、2G、4G和8G，运行过程中实际分配内存为1.5G、3.1G、5.8G和11.3G。Linux策略和延时平衡策略为以上四个配置分配内存所占用的时间对比如图24 所示。延时平衡策略在内存分配阶段的耗时与Linux策略基本相同（±0.02s）。 5   相关工作 缓解因访存争用导致的应用间内存抢占和整体性能下降的研究方法，侧重于从调度角度入手提高应用运行过程中访存的命中率，进而提升系统的整体性能，忽略了系统内存分配策略是影响应用运行时行为的直接因素，内存分配的结果直接影响应用的后期运行行为和系统调度。 已有针对NUMA架构内存管理的研究，主要集中在进程内存分配阶段结束后的管理和调度，文献[10]首次设计了追踪NUMA中进程与其运行时访问路径的MemProf工具，借助该工具可以估计进程的访存模式，可在此基础上实现进程调度。文献[11]针对多核处理器设计实现了内存带宽预留系统MEMGuard，在该系统中预留的内存带宽可以暂时隔离应用间的访存性能。文献[12]设计实现了测试NUMA架构内存带宽的测试程序，该测试程序能够反映NUMA架构的内存结构特点。SchedNUMA实现了应用进程数据放置在本地内存节点，充分利用了NUMA多核架构的本地访存低延时的特点11。Auto-NUMA-Balancing实现了线程调度与内存资源迁移的结合12。以上研究通过调度方式实现了进/线                                                                 11   Sched  NUMA.  Linux  Kernel  Mailing  List,  “Sched  NUMA Rewrite,”https://lkml.org/lkml/2012/5/9/312/, May 2012 12   RedHat.  Auto-NUMA-Balancing.  https://access.redhat.com/docu mentation/en-US/Red_Hat_Enterprise_Linux/7/html/Virtualization_Tuning_16  计  算  机  学  报  2016年 程与其内存的动态映射，而通过内存分配实现内存管理的研究很少。文献[13]设计了针对NUMA架构的内存条分配算法，其设计思想为最大化分配本地内存节点上的内存条，避免使用交换区等内存资源，提高RAM资源的利用率[13]。 6   总结与展望 多核系统内并行运行多个应用共享内存时的有效性和公平性一直是研究的焦点，在NUMA架构引入多内存节点之后，这一问题的复杂程度又显著增加。针对这个问题，本文提出了一个节点访存延时指标，并在该指标的基础上提出节点间的访存延时平衡内存分配策略。该策略通过感知节点间访存延时的平衡和选择访存延时最低的内存节点分配内存使得多个应用可以高效公平地共享内存资源。该策略的实现是针对特定平台的，因为延时获取的方法与底层硬件紧密相关，但是策略本身是可以通用于NUMA架构的，针对不同的平台延时感知模块实现不同，但是内核策略是通用的。在Linux默认的内存分配策略的外层加入访存延时平衡感知实现了该策略，并且在Linux系统中对比访存延时平衡分配策略与原Linux内存分配策略的性能：综合单应用多进程和多应用多进程的并行实验，实验结果表明访存延时平衡的内存分配策略降低了原Linux内存分配策略引起的进程间共享内存资源不公平的16%，最大降低了34%。该策略实现对Linux内核改动很小，仅在内存分配部分做了改进，在未来的研究工作中会考虑结合基于访存延时平衡的调度策略。 参考文献 [1]  Ming,  L.  Tao,  L.  Optimizing  virtual  machine  consolidation performance  on  NUMA  server  architecture  for  cloud  workloads// Proceedings of  the 41st  annual  international symposium  on  Computer architecture(ISCA), Piscataway, USA, 2014: 325-336 [2]  Pusukuri,  K.  K  et  al.  ADAPT:  A  framework  for  coscheduling multithreadedprograms.  ACM  Transactions  on  Architecture  and  Code Optimization (TACO), 2013: 9(4), Article 45 [3]  Zhuravlev,  S  et  al.  Addressing  shared  resource  contention  in multicore  processors  via  scheduling//  Proceedingsof  the  15th international  conferenceon  Architectural  support  for  programming                                                                                                       and_Optimization_Guide/sect-Virtualization_Tuning_Optimization_Guide-NUMA-Auto_NUMA_Balancing.html languages  and  operating  systems (ASPLOS).  .Pittsburgh, USA, 2010: 129-142 [4]  Aravind,  A.,  and  Manickam,  V.  A  flexible  simulation  framework for  multicore  schedulers:  work  in  progress  paper// Proceedings  of  the 2013  ACM  SIGSIM  conference  on  Principles  of  advanced  discrete simulation , 2013,355-360 [5]  Jia,  R  et  al.  Optimizing  virtual  machine  scheduling  in  NUMA multicore  systems// Proceedings of  the 19th  International  Symposium onHigh  Performance  Computer  Architecture  (HPCA),  Shenzhen, China, 2013: 306-317 [6]  Jia,  R, Zhou,  X.  Towards  fair  and  efficient  SMP  virtual  machine scheduling// Proceedings of  the  19th  ACM  SIGPLAN  symposium  on Principles  and  practice  of  parallel  programming  (PPoPP).  Orlando,  USA, 2014: 273-286 [7]  Ebrahimi,E et  al. Fairness  via source throttling: a  configurable  and high-performance  fairness  substrate  for  multi-core  memory systems//Proceedingsof  the  15th  international  conferenceon Architectural  support  for  programming  languages  and  operating systems (ASPLOS). Pittsburgh, USA, 2010: 335-346 [8]  Henning, J. L SPEC CPU2006 memory footprint. ACM SIGARCH Computer Architecture News, 2007,35(1): 84-89 [9]  M. Dashti et al.Traffic management: a holistic approach to memory placement  on  NUMA  systems// Proceedingsof  the 18th international conferenceon  Architectural  support  for  programming  languages  and operating systems (ASPLOS). Houston, Texas, USA, 2013: 381-394 [10]  Renaud  L.,  Baptiste  L., Vivien  Q.. MemProf:  A  Memory  Profiler for NUMA Multicore Systems. Proceedings of the Proceedings of 2012 USENIX  Annual  Technical  Conference  (USENIX  ATC  12) , Boston,   USA, 2012:53-64 [11]  Caccamo  M.,  Pellizzoni  R.,  Sha  L.,  et  al..  MemGuard:  Memory bandwidth  reservation  system  for  efficient  performance  isolation  in multi-core  platforms.Proceedings  of  the  2013  IEEE  19th  Real-Time and  Embedded  Technology  and  Applications  Symposium  (RTAS), Philadelphia, USA, 2013:55-64 [12]  MolkaD., HackenbergD., SchoneR., et al. Memory Performance and Cache CoherencyEffects on an Intel Nehalem Multiprocessor System .   Proceedings  of  the  18th  International  Conference  on  Parallel Architectures  and  Compilation  Techniques,  Raleigh,USA, 2009:261-270 [13]  FarinaM.,  ZoniD.,  FornaciariW..  A  control-inspired  iterative algorithm for memory management in NUMA multicores . Proceedings of the  19th  World  Congress  of  the  International  Federation  of Automatic  Control  (IFAC-2014)  ,  Cape  Town,  South  Africa, 2014:24-29 论文在线出版号  No.158            李慧娟等：NUMA架构内多个节点间访存延时平衡的内存分配策略  17    Li Huijuan, born  in  1990,  M.S.  Her main  research  interest  is parallel computing. Luan Zhongzhi, born in  1971, Ph.D.,  associate professor. His research interests include tributed computing, high performance computing and parallel computing. Wang Hui, born  in  1987, Ph.D. His  research  interests  include computer architecture and computer systems. Yang Hailong, born  in  1985,  Ph.D.,  lecturer.  His  research interests  include  runtime  system,  performance  modeling,  QoS and energy-efficient computer architecture. Qian Depei,  born  in  1952,  M.S.,  professor.  His  research interests  include  high  performance  computing  and  computer architecture.  Background Non-uniform  memory  access  (NUMA)  is  a  computer memory  design  used  in  multiprocessing,  where  the  memory access  time  depends  on  the  memory  location  relative  to  the processor. Under NUMA, a processor can access its own local memory  faster  than  non-local  memory  (memory  local  to another processor or memory shared between processors).  The benefits of NUMA are limited to particular workloads, notably on  servers  where  the  data  are  often  associated  strongly  with certain tasks or users. Modern data centers and the scientific computing clusters widely  adapt  the  NUMA  architecture due to  its  low  latency  of local memory accessing, which is achieved by partitioning the whole  memory  into  multiple  nodes  and  each  memory  node  is connected to a processors’ memory controller. To achieve a low memory  access  latency,  the  default  Linux  memory  policy chooses  to  allocate  the physical  memory  pages  from  the memory node where the process is running. Unfortunately, this allocation policy may potentially result in the unfairness among the  processes,  which  leads  to  the  performance  variation.  To solve  this  problem,  this paper  designs  a  memory  allocation policy  assuring  the  balance  of  access  latency  among  memory nodes  in  NUMA  architecture,  and  implements  it  in  the  Linux kernel. The real  system based evaluation results show that  our approach  can  apparently  reduce  the  unfairness  among applications while  keeping  a  stable  performance,  compared  to Linux’s default memory allocation algorithm. This  work  is  supported  by High-tech  Research  and Development Program of China (863 Program) under the Grant No. 2012AA01A302 and National Natural Science Foundation of  China  (NSFC)  under  the  Grant  No. 61133004, 91530324, 61361126011,61502019.