Page 75 - 《软件学报》2021年第8期

孙乔 等:SW26010 众核任务并行调度系统及其嵌套并行算法应用 2357

起之前,用户还能将 LDM 中的关键数据移交至 SWAN 框架进行保存,以便在任务恢复执行时取回 LDM 加以使
用.我们发现,任务的挂起和重启功能不仅能妥善处理任务间的依赖关系,在一些算法(如凸包求解算法,见附录
2)中还有利于提高算法的并发度.

4.2 基于DMA和LDM的循环队列
在运行时,SWAN-CPE 需要不断地从就绪任务队列或挂起任务队列中获得任务进行执行,因此 SWAN-CPE
对这些队列的访问效率将影响 SWAN 框架本身的性能.由于目标平台拥有 DMA 高速访存机制和程序可控
LDM,我们采用了具有线性存储结构的环形链表,并将处于表头和表尾部分的若干任务指针缓存于拥有这些队
列 SWAN-CPE 的 LDM 中,形成缓存结构.该 SWAN-CPE 若需要获得位于表头的任务时,事先会向该队列的 LDM
缓存进行索取;若获取失败,则使用 DMA 将批量任务指针加载到缓存.与此类似,若该 SWAN-CPE 需要向队尾插
入任务时,可直接将该任务的指针放入进队缓存;当缓存队列放满时,则使用 DMA 向位于内存中的队尾进行批
量插入.由于工作窃取机制的存在,某一就绪任务队列在运行时将可能被多个 SWAN-CPE 并发访问.为了保持队
列中数据的一致性,我们限定来自其他 SWAN-CPE 的工作窃取请求只能作用于未被缓存入 LDM 的任务,而当
前处于缓存中的任务被认为是当前 SWAN-CPE 私有的.值得注意的是,任意循环队列的都有指定的容量,因此
SWAN-CPE 不能无限制地向某一队列加入任务而不及时获取任务进行处理.
4.3 负载均衡策略
任务并行框架需要采取一定的任务调度策略 [26,27] 确保程序的并发度和处理单元的负载均衡.SWAN 目前
提供两种工作窃取 [17,19,25,28,29] 手段保证 CPE 阵列的动态负载均衡:轮询窃取及基于动态信息的窃取.轮询窃取
策略的实现相对简单:每个 SWAN-CPE 持有一个私有的轮询计数器,每次线程饥饿时对计数器指定的 SWAN-
CPE 进行任务窃取并使计数器指向下一个 SWAN-CPE 的线程标志.轮询窃取机制实现简单,运行时开销较小并
能够确保 SWAN 框架产生的所有窃取行为均匀地分布于所有 SWAN-CPE.基于动态信息的窃取机制需要
SWAN-CPE 动态地维护自身运行时信息,如已执行的任务数.需要窃取任务的 SWAN-CPE 通过向 SWAN-MPE
对象查询以得知至此最为繁忙(已完成任务数量最大)的 SWAN-CPE,并在它的就绪任务队列中窃取任务.基于
动态信息的工作窃取机制由于需要维护全局运行信息,因此开销较大,但其窃取行为目标较为明确.一般而言,
基于动态信息的工作窃取在任务粒度较大时具有较高调度效率,而轮询窃取在任务粒度较小但数量多时效率
较高.

5 实 验

我们在 SW26010 CPU 的一组 CG 上对 SWAN 的可用性和性能进行测试.一组 CG 拥有大小为 7.7GB 的内
存空间.MPE 的主频为 1.25GHz,理论带宽大约为 5GB/s.单个 CPE 的主频为 1.45GHz,DMA 的理论聚合带宽为
34GB/s(实际峰值为 22GB/s).实验所使用的程序均采用 sw5cc 编译器编译,产生相应的 MPE 代码及 CPE 代码,
[5]
所有编译过程均采用“-O3”优化选项.我们在多个任务并行基准测试集如 Barcelona OpenMP Task Suite 和 Clik
Task Suite [14−16] 中选取了 4 个具有代表性的嵌套并行算法(算例),并使用 SWAN 框架在 CPE 阵列上实现它们.
这 4 个算例分别是 N-皇后问题,二叉树遍历,快速排序和凸包求解.我们采用运行在 MPE 上的各个算法的串行
版本作为性能参考基准,来衡量使用 SWAN 框架并行化带来的性能提高.并行程序运行的负载均衡率由运行时
单个 CPE 处理的平均任务数量和单个 CPE 处理的最大任务数量的比决定 [22] .对于 SWAN 的可用性,我们拟在
附录 1 和附录 2 中分别展示使用 SWAN 实现的具有尾递归特点的并行快速排序算法和具有首递归特点的并行
凸包求解算法.
5.1 N-皇后问题

N-皇后问题要求在一个 N×N 的国际象棋棋盘上放置 N 个“皇后”棋子,并保证每个皇后不能直接攻击其他
任意一个皇后.根据国际象行棋的规则,这些皇后棋子不能同时处于同一行、列及斜对角线.由于下一步棋子摆
放的方式依赖于当前已摆放的棋子的形态,因此 N-皇后问题通常使用递归方式进行求解.然而在具体的算法执