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

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

that each of the algorithms can gain a significant speedup, from 4.5x to 32x, against its serial counterpart, which suggests that SWAN has
a high usability and performance.
Key words: task parallel framework; parallel computing; nested parallel algorithm; SWAN; SW26010 many-core CPU

任务并行模式 [1,2] 是并行程序设计的一种基本设计模式,在并行计算领域中有着广泛的应用.一个任务是由
相关数据及其操作形成的集合 [1,3] .相互独立的任务可以同时被分派到不同的处理器得以并行处理,从而使程序
获得较为理想的并行加速比.相对于朴素的数据并行模式,采用任务并行模式可以更高效地并行化诸如快速排
序,二叉树遍历及凸包计算等一系列具有递归结构的算法 [4,5] .然而在实际应用中,不同任务间往往具有复杂的
[1]
前驱后继关系,一些任务还可能需要衍生出其他任务,形成任务嵌套(nested task) .因此任务并行程序的正确性
不仅依赖于各个任务的正确定义,还依赖于任务间恰当的时序.因此若要全盘考虑上述要素,则任务并行程序的
设计和实现会有着相当的难度.从而一个通用的支持任务并行模式的运行时框架 [6,7] (下称:任务并行框架)成为
程序员开发任务并行程序的必需.
[8]
SW26010(申威 26010)CPU 是我国自主研发的一款高性能众核 CPU .如图 1 所示,一片 SW26010 CPU 由
4 个 CG(core group,核组)构成.每组 CG 包括 1 个控制核心 MPE(management processing unit)和 64 个 CPE
(computing processing element).从本质上讲,MPE 是一个通用处理器,负责处理程序的逻辑密集部分和系统资源
的控制;众多 CPE 则是一些轻量级计算核心,主要负责加速程序的计算密集部分.64 个 CPE 被排布成 8×8 阵列,
每个 CPE 可通过唯一的标识或其在阵列中所处的行(列)号进行索引.每个 CPE 有程序可控的 64KB 高速 LDM
(local data memory,本地数据内存)作为其数据缓存.一组 CG 中的 MPE 和 CPE 阵列能够共享进程的内存空间.
除了常规的访存方式外,单个 CPE 与内存间还能通过 DMA(direct memory access)机制进行数据块的高效传输.

Fig.1 Architecture of a SW26010 many-core CPU
图 1 SW26010 众核 CPU 体系结构

一片 SW26010 CPU 的 4 组 CG 通过片上高速互联网络相连,其间实现了缓存一致性协议.但由于每组 CG
拥有各自临近的内存空间,因此在常规情况下,一片 SW26010 CPU 的 4 个 CG 需分别运行单独的进程,以避免延
迟较高的远端内存访问.运行于 SW26010 CPU 的进程由 CPE 阵列对计算密集但逻辑简单的部分进行并行加速
处理,从而一系列科学计算类应用能够得以有效加速.然而随着计算机应用的日益广泛,一系列非规整算法也亟
待通过并行化得以有效加速.因此本文针对上述情况,面向 SW26010 CPU 的单组 CG,设计实现任务并行框架
SWAN.其对降低 SW26010 CPU 的使用难度及扩大平台的适用性有着重要的现实意义.
本文第 1 节将进一步描述对 SWAN 的设计实现有着重要影响的目标平台特性,并针对性地提出 SWAN 框
架的设计目标.第 2 节具体描述 SWAN 的静态结构与和动态行为.第 3 节进一步介绍 SWAN 框架采用的关键技