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

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

任务的所有前驱依赖关系全部满足后,SWAN-CPE 可将该任务再度放入就绪任务队列中等待执行.每个 SWAN-
CPE 还有私有的已完成任务集,在该集合中的任务需要进一步被处理,以解除它们所有后继任务的依赖.每个
SWAN-CPE 还负责记录自己的内存使用量及处理器运行时间,在其空闲时更新 SWAN-MPE 对象中对应数据条目.
一个进程的所有共享内存空间被划分成若干部分,使得每个 SWAN-CPE 线程拥有独立的私有内存空间来存放相
应的数据结构.在私有内存空间不足的情况下,一个 SWAN-CPE 可将自己的内存分配请求发送给其他 SWAN-CPE.
这样,SWAN 框架在充分利用内存资源的同时还能有效地避免多个线程争相申请内存而带来的开销.综上所
述,MC-Modeling 模块的设计分散了 SWAN 框架的关键数据结构,尽可能地避免了共享资源的争用.
3.2 SWAN动态行为
SWAN 支持任务的动态生成及依赖关系的解析,这一关键过程被实现在 SWAN 的 QPP 模块中.如图 3 所示,一个
简单的尾递归程序的并行执行由“任务-0”开始.初始时,任务-0 被“SWAN-CPE 0”执行,在执行过程中,由于任务-0 的
进一步执行依赖于由它产生的两个子任务(“任务-1”和“任务-2”)的完成.因而,任务-0 被 SWAN-CPE 0 挂起(加入挂起
任务队列).同时,衍生出的任务-1 和任务-2 被加入 0 号 SWAN-CPE 的就绪任务队列中.此时,由于 SWAN-CPE x 处于
线程饥饿状态,由上文所述,它能够在 SWAN-CPE 0 的就绪任务队列中窃取某一任务(假设为任务-1)以进行处理.当
任务-1 和任务-2 被各个 SWAN-CPE 执行完毕之后,它们被放入相应的终止任务队列,等待后续处理.处理一个已被完
成的任务包括释放其占用的内存资源及解除与它相关的任务依赖关系.此时在 SWAN-CPE 0 的中挂起的任务-0 由
于其所有的依赖条件皆被满足,它将被重新放回 SWAN-CPE 0 的就绪队列中得以进一步执行.

(a) 初始时任务 0 被 (b) 由任务 0 产生的任务 1 (c) 任务 1 在本地执行,任务 2 (d) 子任务结束后,任务 0
放置于就绪队列 和任务 2,任务 0 挂起 被 SWAN-CPEx 窃取 继续得以执行

Fig.3 Process of task dependency resolvement in SWAN
图 3 SWAN 任务依赖关系解析过程

3.3 SWAN用户接口
SWAN 向用户提供了方便的编程 API,程序员并不需要显示操作“任务”这一数据结构.附录 1 和附录 2 分别
展现了由 SWAN API 编写的并行快速排序和并行凸包求解程序,用户可以与函数调用相似的方式向 SWAN 框
架动态地插入任务,程序的并行细节对程序员来说是透明的.

4 SWAN 框架的关键技术

4.1 任务挂起和上下文保存

在嵌套并行程序中,父任务的执行往往依赖其子任务执行的结果,在这种情况下父任务不得不暂停以等待
所有子任务的完成.在没有线程切换功能的 CPE 上,SWAN 框架为用户提供了任务断点以中止当前任务的继续
执行.在该任务的所有依赖关系被满足后,SWAN-CPE 可从任务断点开始继续处理先前被挂起的任务.在任务挂