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

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

Fig.8 Speedup of the parallel convex-hull algorithm against the MPE sequential convex-hull algorithm
图 8 并行版凸包算法相对于 MPE 串行版算法的加速比

6 结论及未来的工作

在新兴的 SW26010 众核处理器上,本文提出并实现了支持任务并行模式的 SWAN 框架,并成功将之应用于
若干典型的嵌套并行算法.在目标平台上,SWAN 框架为用户实现任务并行提供了高层次的抽象,能够大幅度降
低用户开发任务并行程序的难度.在现有 CPE 功能的基础上,SWAN 能够挂起并恢复任务的执行,使得具有递归
特性的嵌套并行算法能够得以有效并行.结合 SW26010 的访存特性,SWAN 框架中关键数据结构采用了高效的
DMA 访存机制和 LDM 缓存以有效地降低框架本身的执行开销.在并行程序执行过程中,SWAN 还能够确保任
务在各个处理单元上的负载平衡以充分发挥众核阵列的计算效能.实验表面,在若干典型嵌套并行程序算例
中,SWAN 能够有效加速目标程序,并随着问题规模的增大,加速效果更加明显.值得一提的是,通过对 SWAN 框
架的灵活应用,我们可将集中在凸包问题初始阶段的大量计算负载均分到各个可用的 CPE 核心上,缩短程序执
行的关键路径长度以大幅度提高程序的性能.
今后的工作将从两个方面展开.一方面,基于 SWAN 框架,我们将在 SW26010 众核核组上进一步研究各
类嵌套并行算法,在此过程中设计新颖的动态负载均衡策略以提高程序的执行效率.另一方面,我们将进一
步丰富和完善 SWAN 框架的功能,将基于任务有向无环图的任务调度技术整合于 SWAN 框架中以拓展其使
用领域.

References:
[1] Wang L, Cui HM, Chen L, Feng XB. Research on task parallel programming model. Ruan Jian Xue Bao/Journal of Software, 2013,
24(1):77−90 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4339.htm [doi: 10.3724/SP.J.1001.2013.04339]
[2] An H, Chen GL. Parallel programming models and languages. Ruan Jian Xue Bao/Journal of Software, 2002,13(1):118−124 (in
Chinese with English abstract). http://www.jos.org.cn/jos/ch/reader/create_pdf.aspx?file_no=20020117&year_id=2002&quarter_
id=1&falg=1
[3] Ian F, Krishnaiyer R, Choudhary A. A library-based approach to task parallelism in a data-parallel language. Journal of Parallel &
Distributed Computing, 1997,45(2):148−158.
[4] Blikberg R, Srevik T. Nested parallelism: Allocation of threads to tasks and OpenMP. Scientific Programming, 2001,9(2):185−194.
[5] Duran A, Teruel X, Ferrer R, Martorell X, AyguadE. Barcelona OpenMP tasks suite: A set of benchmarks targeting the exploitation
of task parallelism in OpenMP. In: Proc. of the 2009 Int’l Conf. on Parallel Processing. Vienna: IEEE, 2009. 124−131.
[6] Wang QX, Sun SX, Shang MS, Liu YB. Research of parallel computing model. Computer Science, 2004,31(9):130−133.
[7] Blumofe RD, Joerg CF, Kuszmaul BC, Leiserson CE, Randall KH, ZhouY. Cilk: An efficient multithreaded runtime system.
Journal of Parallel & Distributed Computing, 1996,37(1):55−69.