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

2354 Journal of Software 软件学报 Vol.32, No.8, August 2021

术.第 4 节拟通过若干具有代表性的嵌套并行算法对 SWAN 的实用性及性能进行测试.第 5 节回顾在主流的多
(众)核平台上常用的诸多任务并行框架,并探讨其与 SWAN 的区别与联系.第 6 节对本文的工作进行总结.
1 平台特性

一组 CG 的诸多硬件特性对 SWAN 框架的设计实现提出了要求.首先,一个 CPE 目前只能运行单一线程,
无法进行线程切换.因此 CPE 上的任务调度环境应当具备上下文切换功能,旨在确保当前任务因依赖关系尚未
满足而挂起导致的 CPE 忙等.其次,由于所有 CPE 共享统一的内存空间,这虽有利于简化共享数据结构的设计实
现,但若不对共享数据加以适当处理,则会导致大量线程由于对共享数据的争用而导致的巨额开销.因此
SWAN 框架需对任务池等共享资源进行细粒度划分以提高 SWAN 框架本身的并发性.再次,单个 CPE 虽可以通
过 load/store 指令直接访问内存单元,但其效率低下.因此为了增大内存吞吐率,CPE 应尽可能地采用 DMA 机
制传输成块数据.这就意味着 SWAN 框架中的关键数据结构需有合适的物理结构,能够通过 DMA 进行高效的
访问.最后,SWAN 还需利用各个 CPE 的 LDM 以缓存任务管理所需的各种信息,以提高任务管理的效率.
在平台的软件特性方面,单个 CG 的线程控制、DMA 机制等功能通过调用“athread”库实现.athread 库提供
基本的线程发起(“athread_spawn()”)和线程集合(“athread_join()”)接口操纵 CPE 阵列.单个 CPE 上,athread_get()/
athread_put()接口通过 DMA 实现数据在 LDM 和内存间的交换.另外,单个 CPE 上拥有可作用于从核阵列的“取
并加一(fetch-and-add)”原子操作.从现有 API 上看,目前单个 CG 可方便地部署以“Fork-and-Join”方式并行的程
序,但对具有嵌套并行特性的算法,平台尚未向程序员提供更高层的接口及更高级的细粒度线程同步手段,如锁
和信号量等.
综上所述,在 SW26010 上实现通用的支持任务并行的运行时框架,需以现有的并行接口为基础,采用软件
方式跨越硬件限制并充分利用平台的各种资源.因此 SWAN 框架的设计和实现具有相当的难度.

2 相关工作
虽然 SWAN 框架为 SW26010 众核核组定制,结合了诸多平台的软硬件特性,但当今国内外在任务并行模式
及任务并行框架方面的研究对 SWAN 框架的设计与实现有着重要的借鉴意义.
[1]
任务并行模式主要应用在 SMP(对称多处理器)或 NUMA(非对称多处理器)环境下 .在这种环境下
OpenMP [4,5,9,10] 是一套指导性编译处理标准,用户能够通过编译制导语句方便地对程序实施并行化.OpenMP 标
准已被广泛接受,在学术界及开源社区有着众多实现,比如 OpenUH [11] .早先,OpenMP 被广泛应用于并行化大型
科学计算程序中结构规整的循环,但由于在版本 3.0 之前,OpenMP 并不支持任务并行,因此其应用范围受到了极
大的制约.在版本 3.0 之后,OpenMP 集成了任务并行功能 [12] ,用户可以通过编译制导语句方便地实施任务并行
及任务嵌套并行.遗憾的是,OpenMP 在当前 SW26010 核组上没有得到有效支持.因此本文中提出的支持任务并
行及任务嵌套并行的 SWAN 框架能够有效地拓展 SW26010 核组在任务并行领域的应用.于 2012 年提出的
OpenMP 4.0 标准增加了以任务间依赖有向无环图为基础的任务调度策略 [13] ,这亦为 SWAN 框架的进一步发展
指明了方向.除 OpenMP 之外,在当前主流的多核、众核平台上还有一些专门支持任务并行的并行编程框
架.Cilk [14,15] 及 Cilk-5 [16] 是由 MIT 于 2001 年提出的多核平台任务并行解决方案.与 OpenMP 不同,Cilk 扩展了 C
语言关键字以实现任务并行及任务嵌套并行.Cilk 采用了经典的工作窃取 [17] 调度策略并对其性能和内存使用
行为进行了理论评估.本文结合 SW26010 平台的特性,将工作窃取策略整合于 SWAN 框架中,构成任务管控逻
辑的核心.相似地,X10 [18,19] 定义了新的并行语言,能够使程序员高效地表达程序的并行性.X10 主要面向
NUMA 架构,以库所(place)概念为核心管理程序数据,缓解由平台访存不均匀性带来的程序性能损耗.Intel
TBB [20] 及 Microsoft 推出的 TBL [21] 以 C++语言为基础,为程序员提供了丰富的并行模板及数据结构.它们的出现
标志着任务并行编程模型走入了工业界.但是它们主要面向 C++程序,其实现也结合了诸多面向对象特性,因此
它们的高效使用需要程序员对 C++语言中的模板、泛型等概念有着深刻的理解.
随着异构平台的流行,任务并行编程的应用得到了进一步拓展.如 Intel 为 MIC 协处理器定制的 OpenMP 扩