神威平台上AceMesh编程模型的构图优化

叶雨曦，傅 游，梁建国，孟现粉，刘 颖，花 嵘

(1.山东科技大学 计算机科学与工程学院，山东 青岛 266590; 2.中科寒武纪科技股份有限公司, 北京 100191； 3. 中国科学院计算技术研究所，北京 100190)

任务并行编程模型把任务作为并行的基本单位，为编程人员提供任务划分和任务同步接口。编程人员需要考虑如何对应用程序进行合理的任务划分，而任务具体的要在哪个物理核上执行以及如何实现任务之间的同步都由运行时系统完成。任务并行编程模型可看作底层体系结构和上层程序应用之间的桥梁，向上隐藏并行处理的细节，提高编程层次，简化并行编程；向下充分利用硬件资源，高效正确地执行并行程序[1]。支持任务并行调度的并行编程模型主要有MIT的Cilk[2]/Cilk++[3]、Intel的Threading Building Blocks(TBB)[4]、BSC的OmpSs[5]、微软的Task Parallel Library(TPL)[6]等。

中国科学院计算技术研究所并行编译组提出了一种面向网格应用，以数据为中心，应用于多核、众核平台上的任务并行编程模型AceMesh[7-10]。AceMesh主要包括编译器和任务调度系统。AceMesh编译器作为一个源到源编译框架[5]，根据平台特性将带指导语句的程序代码自动生成指定平台的并行化程序，编程人员只需要关注指导语言和应用本身即可。AceMesh任务调度系统采用基于有向无环图[11](directed acyclic graph，DAG)的动态任务调度，能自动发掘结构化网格应用中存在的数据驱动的任务图并行性，其性能较其他的任务并行编程模型优越[12-13]。

AceMesh作为数据流驱动的任务并行模型，细粒度的任务划分会使其构图开销显著增加，降低应用的并行可扩展性。王松等[14]提出了并发构图的方法，对AceMesh构图进行了优化，但该方法在访存、内存申请和任务收集方面存在一定的问题，导致AceMesh构图过程开销仍过大。为提高构图效率，本研究从减少通信开销、设计内存池和优化任务收集策略等角度对AceMesh构图过程进行优化，通过数据测试验证构图优化的可行性和有效性。

1 “神威·太湖之光”平台简介

“神威·太湖之光”[13-15]计算机系统采用“申威26010”异构众核处理器，芯片工作频率1.45 GHz，峰值运算速度3.168 TFLOPS，采用了针对该处理器定制的64位申威指令系统，与X86指令系统不兼容。“申威26010”异构众核处理器架构如图1所示。

“申威26010”异构众核处理器集成了4个运算核组，共260个运算核心，核组间支持Cache一致性，通过高速片上网络相连。每个核组包含1个运算控制核心(management processing element, MPE)即主核、1个运算核心(computing processing elements,CPE)即从核阵列和1个存储控制器(memory controller,MC)，通过iMC与主存相连。众核处理器还集成系统接口总线用于连接标准PCIe接口，实现片间直连和互连，管理与维护接口负责系统管理、维护和测试。4个核组和系统接口总线通过群间传输网络实现存储共享和通信。主核具有两级片上存储层次：L1级数据和指令Cache、共享的L2级Cache。1个计算核组中的64个从核共享L2级指令Cache。每个从核具有私有L1级指令Cache和用于数据存储的LDM空间。应用程序由主核启动，借助高性能线程库Athread将计算任务加载到从核执行，双方通过同步接口协同。

2 AceMesh任务调度系统的构图过程及其存在的问题

AceMesh任务调度系统的工作机制如图2所示。用DAG将计算任务之间的依赖关系表达出来的过程称为构图，利用构建的DAG分析保持数据原有依赖关系的正确任务执行顺序，并对任务进行调度和计算的过程，称为图执行。DAG的构建由主核独自完成，执行由主核和从核共同完成。

图2 AceMesh任务调度系统工作机制

构图过程包括两步：一是数据域的划分及计算任务封装。根据代码访问数据区域的不同，将整个数据域划分成若干个数据区域。为减少通信量，尽可能把具有依赖关系的数据区域分配到一个数据块中，并将数据块、对该数据块的操作和需要通信的邻居节点封装成一个计算任务；二是计算任务注册。为了更好地发掘缓存中的数据重用性，初始化计算任务的亲和性设置，根据最近、可达的数据访问信息如变量地址、邻居关系、读写信息等，构建正在注册的计算任务与前驱计算任务间的数据依赖边，并记录为后继任务；将没有前驱的任务存放在无前驱任务列表need_spawn_tasks中，作为最先调度的任务；查找无后继任务并将其存放在无后继任务列表end_tasks中，用于检查DAG执行结束状态。

在构建DAG的过程中存在下面3个问题：

1) DAG构建由主核独立完成，为了在构建完成后唤醒从核，主核需要在主存上维护一个共享变量is_run。主核构建DAG时将is_run赋值为0，构建完成后将is_run赋值为1；处于等待状态的从核会访问is_run的值，若值为1则从核进入工作状态，执行计算任务。因此主核构建DAG期间所有的从核都在不断地访问主存，造成了很大的访存开销。

2) 系统使用new()、malloc()等申请分配内存，会调用操作系统的系统调用函数mmap2()，时间开销大，应尽量减少系统调用的次数。AceMesh任务调度系统中大量地使用动态数据结构，如任务的继承类、任务参数和任务后继列表等，当任务的总数很多时，这些动态数据结构的分配和释放造成大量的系统开销。

3) 无后继任务列表end_tasks是基于哈希表实现的，用于检查DAG执行结束状态。每个新任务注册后都需要对end_tasks列表执行添加和查找操作，每次更新后存在后继的任务需要从end_tasks列表中删除。若无后继任务占比较低，随着注册任务数增加，end_tasks列表的修改和查找开销会变得越来越大。

3 AceMesh任务调度系统的构图优化

AceMesh任务调度系统先构图后调度，合理高效的构图方法可以有助于减少线程的等待时间，提高程序的执行效率。本节针对第2节中AceMesh构图过程存在的3个问题进行构图优化。

3.1 主、从核通信优化

申威26010异构众核处理器单核组存储器访问方式如图3所示。每个核组的从核可以直接访问主存和局存，从核访问主存有gld/gst离散访存和DMA批量式访存两种方式。主核不能直接访问主存，但是可以通过I/O访问局存，借助宏h2ldm(elment,penum,cgnum)函数直接对从核LDM变量进行I/O存取操作，其中element是运算核心程序内的局存私有变量，penum是核号，cgnum是核组号。

图3 单核组存储器访问图

AceMesh任务调度系统中从核访问共享变量is_run的方式为gld/gst离散访存。在访存带宽方面，gld/gst方式单个核组内的访存带宽为1.5 GB/s，DMA方式单个核组内的访存带宽为26 GB/s；在延迟方面，gld/gst方式延迟278 cycle；DMA方式延迟29 cycle。可以看出，与gld/gst方式相比，DMA方式带宽利用率高，延迟小。

但是DMA批量式访存也存在一定的局限性。图4所展示的单核组DMA带宽增长趋势表明，只有当单次拷贝的数据块大于256 B而且主存地址256 B对齐时，DMA方式才能有效利用访存带宽。另一方面，从核在构图期间不断地进行变量的数据传输，会占用访存带宽。因此DMA方式不是有效的优化方式。

图4 单核组DMA访存带宽

为了减少从核访问主存的带宽开销，将主存上的共享变量is_run改为从核LDM私有变量，每个从核维护一个自己的通信变量is_run。如图5所示，主核构图完成后，通过h2ldm(is_run,i,cgid)=1访问每个从核的LDM空间并将私有变量is_run赋值为1。从核判断自己维护的私有变量is_run的值为1后开始执行任务。当任务执行完成后，主核再通过h2ldm(is_run,i,cgid)=0通知从核停止任务执行，等待下一个任务图的执行。将is_run变量改为从核私有变量减少了从核访问主存的次数，有效降低了构图过程中的访存开销。

图5 优化后的主、从核通信流程

3.2 内存池优化

AceMesh允许用户为一个应用程序设置多个并行区，随着应用计算规模的增加，单个并行区内提交的任务数也不断增加，这些并行任务提交时申请的内存空间将在并行区结束后释放。频繁的内存申请和释放会带来严重的内存碎片问题，同时malloc()和free()函数的使用也会造成很大的时间开销。

为解决上述问题，引入内存池管理存储资源。内存池实质上是一种内存分配方式，在真正使用内存之前，通过调用系统内存分配函数预先申请适当大小的内存块作为备用，之后应用程序对内存的分配和释放则通过这个内存池来完成。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够，需要动态扩展时，再继续申请新的内存块。

本研究提出一种采用内存池管理内存分配的方法，其内存池的申请和释放状态转换图如图6所示。内存池中可以申请多个内存块，申请的内存块中包含可分配的空闲节点，所有空闲块由内存池空闲列表管理，若空闲块被分配出去则将其从表中删除；若已分配的内存块被释放，则将其重新插入到空闲列表的头部。如果内存块中的空闲块不足，则申请新的内存块。内存池的分配和释放都是以固定大小的内存块为单位，不会产生内存碎片，因此可以有效避免内存泄露。

图6 内存池内存分配状态转换图

内存池和内存块的数据结构为：

typedef struct node{

void* data;

struct node* next;

}node;//内存块

typedef struct MemPool{

void* to; //指向当前空闲块的尾部

void* from; //指向当前空闲节点的可用位置

struct node* AllocatedMemNode; //指向内存块的已分配列表

struct node* FreeMemNode; //指向内存块的空闲列表

}MemPool;//内存池

根据内存池的工作流程，内存池申请算法如下。

Algorithm 1内存池申请算法输入:需要使用的内存空间大小data_size,一个内存块包含的内存节点数num_node,每个内存节点的存储空间大小node_size输出:内存池变量Mpool1 //内存池初始化2 struct MempoolMpool3 Mpool.AllocatedMemNode = NULL4 Mpool.FreeMemNode = NULL5 //为内存池加入新的内存块6 byte *new_memory_block = (byte *)malloc(node_size * sizeof(byte))7 do i = 1, num_node8 申请一个新的内存块node[i]9 node_i.data = new_memory_block + i * node_size10 if (i == 1) then continue11 else 上一个内存块node[i-1].next指向node[i]12 endif13 end do14 if (Mpool.FreeMemNode) //空闲列表不为空14 then将新内存节点链表加入到FreeMemNode列表15 else{16 Mpool.FreeMemNode = node[1]17 Mpool.from = node[1].data 18 Mpool.to = node[1].data + node_size}19 end if

内存池分配算法如下。

Algorithm 2内存池分配算法输入:已分配好的内存池变量Mpool,需要申请的内存大小data_size,需要申请空间的指针变量data_point输出:分配好内存空间的指针data_point1 int node_n, node_size = Mpool.to - Mpool.from2 根据node_size和data_size计算需要分配的节点数node_n3 void * point = Mpool.FreeMemNode->data4 do i = 1, node_n5 if (Mpool.FreeMemNode == NULL)//当前内存池内没有空闲节点6 then 为内存池加入新的内存块7 endif8 将Mpool.FreeMemNode第一个节点取出9 在Mpool.AllocatedMemNode加入新分配的节点10 end do11 data_point = point

从内存池的申请和分配算法中可以看出，只在新的内存节点申请时用到malloc()函数，内存节点的分配则是通过传递指针和修改链表来完成的，减少了malloc()和free()函数的调用次数，从而降低内存申请的时间开销。

3.3 无后继任务收集优化

无后继任务列表end_tasks是为了检测DAG是否执行结束而引入的一个任务集，用来记录应用程序的所有无后继任务。AceMesh任务调度系统中end_tasks列表的数据结构为unordered_set，利用哈希表实现。哈希表是根据键值进行直接访问的数据结构，通过相应的哈希函数处理关键字得到相应的键值，键值对应着一个特定位置，用该位置来存取相应的信息，能以较快的速度获取关键字的信息，具有可快速查找、删除和添加的优点。在AceMesh构图机制中，end_tasks列表的收集方法是在每个任务注册时将其添加到end_tasks，若发现任务有后继，再从end_tasks中查找并删除。

图7是对航天飞行器应用中部分代码进行任务划分后得到的DAG。该部分代码包含多个循环计算，通过对循环的划分来分配计算任务。每个圆圈代表一个计算任务，圆圈内第一个数字代表并行区内的循环的序号，第二个数字代表计算任务在循环内的序号，每个任务通过箭头指向其后继任务，相同颜色的计算任务在同一个计算线程上执行。这部分代码计算的数据访问很规则，所以计算任务之间的依赖关系比较简单，因为计算任务是按照循环的次序串行提交的，所以该DAG构建时，第一个循环内的任务(即第一行的任务)首先注册，并被加入到end_tasks列表中，第二行计算任务注册时，之前提交的计算任务都被检测到有后继任务，end_tasks列表需要将第一个循环内的任务删除，第三行计算任务提交后同样需要删除第二行计算任务，这就造成了很多不必要的哈希表查找和修改操作。若无后继任务占比极低，会使得注册时收集到的任务绝大多数被删除，导致哈希表相应数据项的操作失去意义，造成不必要的开销。

图7 航天飞行器应用规则部分DAG

对于无后继任务占比较小的并行区，通过为用户提供指定无后继任务的开关，由用户直接判断无后继任务，从而省去构图过程中end_tasks列表频繁修改的开销。在实现上增加开关SPECIFY_END_TASKS=true(false)和接口acemesh_specify_end_tasks()。如果应用并行区内无后继任务占比较小，用户设置SPECIFY_END_TASKS=true，AceMesh构图时将不再进行无后继任务列表end_tasks的收集，由用户在提交任务时利用接口acemesh_specify_end_tasks() 指定无后继任务并将其直接放入无后继任务列表end_tasks中，所有任务提交完成后无后继任务也收集完毕，避免对end_tasks列表频繁的插入和删除操作，提高构图效率。

4 构图优化测试

航天飞行器应用程序的循环有6层。外3层循环为速度空间，内3层循环为位置空间，外3层循环在进程级别对程序进行划分, 本研究只对内3层循环即位置空间i，j，k的3个维度进行划分。对航天飞行器应用程序进行分析得到具有代表性的7个计算循环，每个计算循环有不同的划分方向和分块尺寸，各循环的划分方向和分块尺寸如表1所示。各个循环在3个维度上的划分如表1所示。

表1 计算循环分块表

将7个计算循环作为热点子程序进行性能测试，由于在“神威·太湖之光”平台上，AceMesh任务调度系统的构图阶段是单线程执行的，故无论采用多少计算线程，构图时间均不变。对各热点子程序使用执行效率最高的线程数，在速度空间32×16×16、位置空间100×19×31、进程网格1×1×1规模下，对AceMesh任务调度系统的构图阶段测试5次，取5次测试结果的平均值，对比构图优化前后的性能，说明构图优化的效果，如表2所示。

表2中可见，对于不同的热点程序，构图优化对构图的性能提升程度不同，但加速比均在4.7以上，其中GaussLegendre的构图性能表现最好，加速比为7.18。因为AceMesh任务调度系统分为构图和执行两个依次进行的阶段，所以计算线程数对构图性能无影响。

表2 AceMesh任务调度系统的构图优化性能对比

任务调度系统各优化项构图优化贡献如图8所示，以优化前的构图作为基准，主、从核通信优化、内存池以及无后继任务收集等优化方法对构图有不同程度的加速贡献，其中无后继任务收集优化方法的加速贡献最大，加速比为2.6以上，所有优化方法总加速比最高达到8.19。

图8 AceMesh任务调度系统各优化项构图优化加速比

AceMesh任务调度系统构图优化的子程序总性能对比如图9所示，因为航天飞行器应用的7个子程序的任务数不同，构图优化对7个热点子程序的总体性能加速表现不同，但均在1.3倍以上，其中GaussLegendre的优化加速最好，达到3.13倍；其次是fcta1和fcta2，总性能加速比趋于相同，达到2.6倍以上。

图9 AceMesh任务调度系统构图优化子程序总性能对比

测试采用“神威·太湖之光”平台的测试队列，由于使用权限所致，最大进程数只能为64，运行时间最长为60 min。在速度空间64×64×64，位置空间100×19×31规模下，测试不同进程数下应用整体性能的提升。并对照神威OpenACC编程语言版本，说明AceMesh任务图并行化带来的性能提升，如表3所示。

表3 AceMesh与神威OpenACC版本的航天飞行器应用性能对比

表3数据表明，AceMesh编程语言的DAG并行版本比神威OpenACC的运行效率要高，在不同的进程数下，加速效果都约为OpenACC的1.5倍。究其原因，一是因为乱序执行是AceMesh独有的特性，二是因为AceMesh通过对计算循环进行多维度的划分，在保证足够任务数的同时每个任务有充足的计算量，充分利用访存带宽，使得DMA传输的效率提高。随着进程数的增加，AceMesh并行版本和神威OpenACC并行版本的执行时间均逐渐减小，在64线程时，运行速度最快，说明AceMesh和神威OpenACC任务并行编程模型都具有良好的扩展性。

5 结论

为提高AceMesh的构图性能，从主、从核通信优化、设计内存池、无后继任务收集等3个方面对AceMesh的构图进行优化，对航天飞行器应用的7个热点子程序在“神威·太湖之光”上进行了测试，结果证明优化为构图带来5倍的性能提升。后两个方面的优化具有普适性，可为所有超算平台上的优化提供参考。以上构图效率提高的主要原因来自无后继任务收集的优化，进一步可以考虑设计一种更高效的任务收集机制来减少哈希表的查找和修改开销。