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

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

展编译器,能够通过分载(offload)子句将任务指派到 MIC 协处理上予以执行 [22] .另外,StarPU [23] 是一套支持主流
异构平台(如 CPU+MIC 和 CPU+GPGPU)上的通用任务并行的编程框架.StarPU 需要将任务透明地通过互联总
线映射到协处理器予以计算.由于 SW26010 的 MPE 与 CPE 阵列能够统一访存,因此 SWAN 框架无需负责任务
在不同设备间的来回传输.值得一提的是,在典型的 SIMD 平台 GPGPU 上,任务并行也日渐受到重视,文献[24]
阐述了如何在 GPGPU 平台上以线程束(warp)为逻辑处理器核心,实现多任务并行的实现机制.由于 GPGPU 和
SW26010 在处理器架构,内存层次结构和访存特性上有较大差异,因此在 GPGPU 上实现的任务并行框架难以
在本文的目标平台上予以直接应用.
3 SWAN 框架的结构与行为

如图 2 所示,SWAN 系统由 4 个模块组成,分别是 CI(concurrent infrastructure,并发基础结构)模块、
MC-Modeling(MPE/CPE modeling,MPE/CPE 建模)模块、QPP(queuing and parallelization policy、排队及并行策
略)模块和 UI(user interface,用户接口)模块.其中,CI 模块与 MC-Modeling 模块描述 SWAN 框架的静态结构,QPP
模块定义 SWAN 框架的动态行为,UI 模块为用户提供 API 以屏蔽底层的并行处理的细节.

Fig.2 Software architecture of SWAN
图 2 SWAN 软件体系结构
3.1 SWAN框架的静态结构
鉴于当前 CPE 阵列缺少灵活的细粒度线程同步机制,CI 模块基于平台的“取并加一”原子操作实现面向 CPE
阵列全体的互斥锁.由于被锁保护的临界区一次只能容纳一个 CPE 线程进行访问和 CPE 无法进行线程切换等原
因,其余想要访问该临界区的 CPE 不得不处于“忙等”状态——反复读取并判别存储在内存中的同步信号以获取
临界区访问权限.大量线程的忙等导致访存量剧增,极大地影响了临界区中工作线程的访存能力.因此,为了减少加
锁导致的冗余访存,CI 模块中的互斥锁还具备睡眠功能:获取锁访问权限失败的线程将进入“睡眠”状态以避免对
内存的高频访问.睡眠时间可由程序员自主调优.此外,CI 模块中包含了能够让众多 CPE 线程并发申请内存空间的
内存管理子模块.在互斥锁和内存管理子模块基础上,CI 模块中还使用泛型技术实现了并发循环队列和并发 Hash
表等关键数据结构.出于性能考虑,这些并发数据结构需结合平台特性予以实现,具体内容在第 3.2 节中详述.
在 CI 模块基础上,本文对单组 CG 的 MPE 和各个 CPE 分别进行建模,形成 SWAN-MPE 和 SWAN-CPE,旨在
使得一组 CG 的所有处理核心形成一个具有生产、交换、维护和处理任务的有机整体.由于程序的主进程运行于
MPE 上,SWAN-MPE 对象需要管理整个 SWAN 框架.因此,其需要包含一个由指定数量的 SWAN-CPE 对象形成的
集合和诸多共享数据:任务总量及完成任务总量,任务参数总表及各个 SWAN-CPE 线程的内存使用量、处理器时
间等运行时信息以为 SWAN 框架的负载均衡行为提供依据.SWAN-CPE 对象用来对一个 CPE 进行建模,其包括了
若干私有及公共的数据结构.其中,就绪任务队列负责存放当前已经就绪的可执行任务,在必要情况下,就绪任务队
列中的任务可以被其他线程偷取 [17,19,25] ,以保证负载平衡.挂起任务队列属于一个 SWAN-CPE 的私有队列,当一个
任务由于依赖关系未被满足而中止时,该 SWAN-CPE 将其加入挂起队列并获取其他任务继续执行.待某一时刻该