摘要
针对Jacobi迭代的海量计算问题,设计了大规模并行计算算法。通过非阻塞通信函数替代阻塞通信函数、采用虚拟进程拓扑方式改进数据的区块划分,并利用高性能集群系统多计算节点协同处理对Jacobi并行迭代进行了尝试。实现了基于MPI的C语言串行与并行算法,利用Taurus HPC分别对串行、并行,单节点、多节点并行算法进行了系统测试。测试结果表明,进程间数据通信效率是影响并行程序性能的重要因素;跨多节点执行对于海量计算任务可显著提高计算速度;合理的数据区块划分有利于处理器的任务调度,可有效提高Jacobi并行迭代算法的执行效率。
Large-scale parallel computing algorithms have been designed for Jacobi iterative computing problems.Systematic improved the algorithm efficiency of Jacobi iteration by using a non-blocking communication function against blocking one,the topology method of virtual process,and the high performance computing system.The MPI-based C language serial and parallel algorithms were implemented,and the Taurus HPC was used to test the serial,parallel,single-node and multi-node parallel algorithms respectively.Experimental results shows that data communication efficiency between processes was an important factor of parallel program performance;across multiple computing nodes for compute-intensive tasks could significantly speed up the calculation;reasonable data block division was helpful for the task scheduling of the processors,which could greatly improve the parallel execution efficiency of Jacobi iteration algorithms.
引文
[1]关治,陈景良.数值计算方法[M].北京:清华大学出版社,2004:406-413.
[2]狄鹏,胡长军,李建江.GPU上高效Jacobi迭代算法的研究与实现[J].小型微型计算机系统,2012,33(9):1962-1967.Di Peng,Hu Chang-jun,Li Jian-jiang.Research and implementation of effective Jacobi iteration algorithms on GPU[J].Journal of Chinese Computer Systems,2012,33(9):1962-1967.
[3]杨庆芳,刘冬,杨兆升.基于MPI+OpenMP混合编程模型的城市路网最短路径并行算法[J].吉林大学学报:工学版,2011,41(6):1581-1584.Yang Qing-fang,Liu Dong,Yang Zhao-sheng.Parallel algorithm for urban ro-ad network shortest path based on MPI+OpenMP hybrid programming model[J].Journal of Jilin University(Engineering and Technology Edition),2011,41(6):1581-1584.
[4]Jacobi Mothod[DB/OL]http:∥en.wikipedia.org/wiki/Jacobi_mothod,2017-12-13.
[5]刘婕,刘灿文.求解一类边界问题的最小曲面的数值并行算法[J].微型电脑应用,2003,19(3):13-15.Liu Jie,Liu Can-wen.A parallel algorithm for evaluating the smallest surface of a class of boundary equations[J].Microcom puter Applications,2003,19(3):13-15.
[6]陈国良.并行算法的设计与分析[M].北京:高等教育出版社,2002:364-367.
[7]张维儒,潘无名.基于MPI的并行计算实现Jacobi迭代[J].软件导刊,2008,7(9):16-17.Zhang Wei-ru,Pan Wu-ming.Jacobi iteration based on MPI parallel computing[J].Software Guide,2008,7(9):16-17.
[8]贺雨晴,张楠,李云东.行列块不同划分机制下矩阵向量乘的并行计算方法[J].电脑知识与技术,2015,11(20):164-167.He Yu-qing,Zhang Nan,Li Yun-dong.Parallel computing method of matrix-vector multiplication with different partition for line,column and block[J].Computer Knowledge and Technology,2015,11(20):164-167.
[9]王涛,卿鹏,魏迪,等.基于聚类分析的进程拓扑映射优化[J].计算机学报,2015,38(5):1044-1055.Wang Tao,Qing Peng,Wei Di,et al.Optimization of process-to-core mapping based on clustering analysis[J].Chinese Journal of Computers,2015,38(5):1044-1055.
[10]都志辉,李三立,陈渝等.高性能计算并行编程技术——MPI并行程序设计[M].北京:清华大学出版社,2001:200-202.
[11]严忻恺,郝子宇,吴东,等.MPI非阻塞广播算法及性能研究[J].计算机工程与科学,2013,35(9):20-26.Yan Xin-kai,Hao Zi-yu,Wu Dong,et al.Research of MPI non-blocking broadcast algorithm and its performance analysis[J].Computer Engineering and Science,2013,35(9):20-26.
[12]张海龙,冶鑫晨,聂俊,等.新疆天文台Taurus高性能计算系统[J].天文研究与技术,2018,15(3):332-338.Zhang Hai-long,Ye Xin-chen,Nie Jun,et al.Taurus high performance computing system of Xinjiang astronomical observatory[J].Astronomical Research&Technology,2018,15(3):332-338.
[13]卢可佩,祝永志.基于MPI的Jacobi迭代算法的并行化[J].电脑知识与技术,2014,10(31):7485-7487.Lu Ke-pei,Zhu Yong-zhi.Parallel of Jacobi iteration algorithm based on MPI[J].Computer Knowledge and Technology,2014,10(31):7485-7487.