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

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

行过程中,该算法有着大量的并行性值得挖掘:假设已经成功摆放了 K–1 个棋子,那么验证第 K 个棋子的各种摆
放方法是否合法的计算间是相互独立的.通过 SWAN 可以让该算法的并行性充分地实现在 CPE 核组上.
对棋子合法性进行判断的计算代码可以得到针对性的简化,但这并不影响 SWAN 框架的使用.因此在图 4
中我们分别展示了使用经过计算简化的程序和未经计算简化的程序的可扩展性.但该算法无论是否经过计算
简化,CPE 阵列并行版本相对于使用同样计算代码的 MPE 串行版本都有显著的加速比.而且加速比随着问题规
模的增大而显著提高.这是因为随着问题规模的增大,更多独立的任务能够被分配到各个 CPE 得以并行处理.进
一步的测试表明在执行 14-queens 算法的过程中,各个从核的负载均衡率能够达到了 91%.但值得我们注意的是:
第一,计算简化对 MPE 串行程序带来了更优的加速效果,进而使得对应的并行加速比整体较低.第二,虽然在实
验中我们开启了 64 个 CPE 线程,但程序整体的并行加速比并不超过 4.5.这是因为一方面 MPE 的数据缓存能够
容纳整张棋盘,因此 MPE 串行实现的访存效率很高;另一方面,每一个 CPE 任务的访存规模太小而导致众核并
行版访存时 DMA 性能较低.

Fig.4 Speedup of the parallel N-Queens problem against the serial reference on the MPE
图 4 并行版 N-皇后问题相对于 MPE 串行版的加速比
5.2 二叉树遍历
二叉树遍历算法要求(并行地)访问二叉树的每一个节点,并保证每个节点仅被访问一次.在实际应用中各
个二叉树的节点可代表不一样的处理逻辑.不失一般性,我们拟统计二叉树各个节点所含字符串中含有给定字
符的数量.在本例中,我们采用二叉树的后根遍历算法,以验证 SWAN 框架确保任务执行顺序的能力.为了让
SWAN 框架体现其在大规模计算中带来的加速效果,各个节点的字符串的长度被设置为 5 000~10 000;为了进
一步验证 SWAN 框架的负载均衡能力,对于每一个节点,我们产生随机长度的字符串并使其左右子节点的字符
串总长度的比值达到 30%.
如图 5 所示,以 SWAN 框架实现的并行二叉树遍历程序的性能大幅度高于 MPE 串行版本,随着树的规模的
增大,加速比可提高到 35 倍左右.这一方面由于 SWAN 能够将计算负载分配到各个 CPE 进行并行处理,另一方
面是因为在各个任务的访存量较大,DMA 机制传输效率高.我们还发现,在问题规模较小的测试条件下(树高度
小于 15 时),基于运行时信息的工作窃取策略优于基于轮询的工作窃取策略.在此用例中,我们还发现使用 LDM
缓冲的并发循环队列能够使性能进一步提高约 30%.经过进一步测试我们还发现即便在非规整的数据结构上,
整个并行程序的负载均衡率也到达了 85 以上,这说明 SWAN 框架有着较强的负载均衡能力.