自动并行化中不规则循环的通信代码生成

doi:10.11772/j.issn.1001-9081.2014.04.1014

计算机应用 ›› 2014, Vol. 34 ›› Issue (4): 1014-1018.DOI: 10.11772/j.issn.1001-9081.2014.04.1014

自动并行化中不规则循环的通信代码生成

傅立国¹,²,姚远¹,²,丁锐¹,²

1. 数学工程与先进计算国家重点实验室,郑州 450001
2. 信息工程大学,郑州 450001;

收稿日期:2013-09-29 修回日期:2013-12-16 出版日期:2014-04-01 发布日期:2014-04-29
通讯作者: 傅立国
作者简介:傅立国(1989-),男,山东沂水人,硕士研究生,主要研究方向:并行编译;
姚远(1972-),男,河南开封人,教授,博士,CCF会员,主要研究方向:先进编译技术、高性能计算;
丁锐(1985-),男,河南滑县人,博士,CCF会员,主要研究方向:并行编译。
基金资助:
“核高基”国家科技重大专项

Communication code generation for automatic parallelization of irregular loops

FU LiGuo¹,²,YAO Yuan¹,²,DING Rui¹,²

1. Information Engineering University, Zhengzhou Henan 450001, China
2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou Henan 450001, China

Received:2013-09-29 Revised:2013-12-16 Online:2014-04-01 Published:2014-04-29
Contact: FU LiGuo
Supported by:
National High Technology Research and Development Program

摘要/Abstract

摘要：

不规则计算在大规模并行应用中广泛存在。在面向分布存储结构的自动并行化过程中，较难在编译时为不规则循环生成并行代码。并行代码中的通信代码对程序运行结果的正确性以及加速效果有着严重的影响。通过分析程序的数组重分布图，使用部分冗余的通信方式来维持不规则数组访问的生产者消费者关系，可以在编译时为一类常见的不规则循环自动生成有效的通信代码。该方法使用计算分解和数组引用的访问表达式求解不规则数组在各处理器的本地定义集作为通信的数据集，分析针对此类不规则循环划分的通信策略，继而生成相应的通信代码。实验测试的结果取得了预期的加速效果，验证了方法的有效性。

Abstract:

Irregular computing exists in large scale parallel application widely and the automatic parallelization on distributed memory is hardly to generate parallel code for irregular loops at compile-time. The communication code of the parallel code influences the correctness and the efficiency to the runout of the program. It could automatically generate useful communication code for a common class of irregular loops at compile-time by using the approach of partial communication redundancy, that needed analyzing the array redistribution graph of the program to maintain the producer-consumer relation of irregular array references. The approach searched the local definition set of the irregular array on each processor by computation decomposition and accessed expression of array references as the communication data set, then analyzed the communication strategies for such irregular loops and generated the corresponding communication code. The experimental results show the validity of the approach and the expectant speedup of test applications.

中图分类号:

TP314

傅立国姚远丁锐. 自动并行化中不规则循环的通信代码生成[J]. 计算机应用, 2014, 34(4): 1014-1018.

FU LiGuo YAO Yuan DING Rui. Communication code generation for automatic parallelization of irregular loops[J]. Journal of Computer Applications, 2014, 34(4): 1014-1018.

参考文献

［1］HU C, ZHANG J, WANG J, et al.Overview of technologies for irregular and out-of-core parallel computing ［J］. Journal of Chinese Computer Systems, 2008, 29(11): 1969-1978. (胡长军,张纪林,王钰,等.非规则、核外并行计算研究综述［J］.小型微型计算机系统,2008,29(11):1969-1978.)
［2］FERNER C S. Revisiting communication code generation algorithms for message-passing systems ［J］. International Journal of Parallel, Emergent and Distributed Systems, 2006, 21(5): 323-344.
［3］BONDHUGULA U, HARTONO A, RAMANUJAM J, et al.A practical automatic polyhedral parallelizer and locality optimizer ［C］// PLDI'08: Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2008: 101-113.
［4］BONDHUGULA U. Automatic distributed-memory parallelization and code generation using the polyhedral framework, IISc-CSA-TR-2011-3 ［R］. Bangalore: Indian Institute of Science, 2011.
［5］GUO M, PAN Y, LIU Z. Symbolic communication set generation for irregular parallel applications ［J］. The Journal of Supercomputing, 2003, 25(3): 199-214.
［6］HU C, LI J, WANG J, et al.Communication set generation for a special case of irregular parallel applications ［J］. Chinese Journal of Computers, 2008, 31(1): 120-126. (胡长军,李静,王珏,等.一类非规则并行应用问题的通信集生成算法［J］.计算机学报, 2008, 31(1): 120-126.)
［7］RAVISHANKAR M, EISENLOHR J, POUCHET L-N, et al.Code generation for parallel execution of a class of irregular loops on distributed memory systems ［C］// SC'12: Proceedings of the 2012 International Conference for High Performance Computing, Networking, Storage, and Analysis. Los Alamitos: IEEE Computer Society, 2012: 1-11.
［8］STROUT M M, GEORGE G, OLSCHANOWSKY C. Set and relation manipulation for the sparse polyhedral framework ［C］// LCPC 2012: Proceedings of the 25th International Workshop on Languages and Compilers for Parallel Computing, LNCS 7760. Berlin: Springer-Verlag, 2012: 61-75.
［9］LAMIELLE A, STROUT M M. Enabling code generation within the sparse polyhedral framework, CS-10-102 ［R］. Fort Collins, CO: Colorado State University, 2010.
［10］BASUMALLIK A, EIGENMANN R. Optimizing irregular shared-memory applications for distributed-memory systems ［C］// PPOPP'06: Proceedings of the 11th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York: ACM, 2006: 119-128.
［11］CAMPANONI S, JONES T, HOLLOWAY G, et al.HELIX: automatic parallelization of irregular programs for chip multiprocessing ［C］// CGO'12: Proceedings of the 10th International Symposium on Code Generation and Optimization. New York: ACM, 2012: 84-93.
［12］KIM H, JOHNSON NP, LEE J W, et al.Automatic speculative DOALL for clusters ［C］// CGO'12: Proceedings of the 10th International Symposium on Code Generation and Optimization. New York: ACM, 2012: 94-103.
［13］ZHUANG X, EICHENBERGER AE, LUO Y, et al.Exploiting parallelism with dependence-aware scheduling ［C］// PACT'09: Proceedings of the 2009 International Conference on Parallel Architectures and Compilation Techniques. Washington, DC: IEEE Computer Society, 2009: 193-202.
［14］DING R, ZHAO R, HAN L. Automatic computation and data decomposition algorithm based on dominate value ［J］. Computer Science, 2012, 39(3): 290-294. (丁锐,赵荣彩,韩林.基于主导值的计算和数据划分算法［J］.计算机科学,2012,39(3):290-294.)
［15］DING R, ZHAO R, LIU X, et al.Partition method for automatic parallelization of irregular problems ［J］. Journal of Information Engineering University, 2013, 14(2): 235-242. (丁锐,赵荣彩,刘晓娴,等.自动并行化中不规则问题的划分方法［J］.信息工程大学学报,2013,14(2):235-242.)
［16］AMARASINGHE S P, LAM M S. Communication optimization and code generation for distributed memory machines ［C］// PLDI'93: Proceedings of The ACM SIGPLAN 1993 Conference on Programming Language Design and Implementation. New York: ACM, 1993: 126-138.

[1]	张素平, 韩林, 丁丽丽, 王鹏翔. 新型超字级并行改进算法[J]. 计算机应用, 2017, 37(2): 450-456.
[2]	徐金龙, 赵荣彩, 韩林. 分段约束的超字并行向量发掘路径优化算法[J]. 计算机应用, 2015, 35(4): 950-955.
[3]	闫国昌何炎祥李清安. 降低寄存器软错误的静态寄存器重分配方法[J]. 计算机应用, 2014, 34(9): 2730-2733.
[4]	霍元宏刘毅计卫星. 基于结构分析的高级语言控制结构恢复方法[J]. 计算机应用, 2013, 33(12): 3428-3431.
[5]	侯永生赵荣彩高伟高伟. 非正规化循环的单指令多数据向量化[J]. 计算机应用, 2013, 33(11): 3149-3154.
[6]	刘晓娴赵荣彩丁锐李雁冰. 基于循环分块的流水粒度优化算法[J]. 计算机应用, 2013, 33(08): 2171-2176.
[7]	黄品丰赵荣彩姚远赵捷. 面向异构多核处理器的并行代价模型[J]. 计算机应用, 2013, 33(06): 1544-1547.
[8]	雷根华张平健奚建清. MDX编译器设计与实现[J]. 计算机应用, 2007, (12): 3035-3038.
[9]	施海昕;佘堃. 用于C语言的错误处理预编译器[J]. 计算机应用, 2005, 25(10): 2453-2555.
[10]	苏铭;赵荣彩;齐宁. 代码翻译中Case语句的识别和恢复[J]. 计算机应用, 2005, 25(10): 2439-2440.
[11]	覃安，符红光. GiNaC编译器设计中双向循环的归一化处理[J]. 计算机应用, 2005, 25(09): 2041-2043.
[12]	琚小明，姚庆栋. 一种可用于编译器调试的目标代码验证方法[J]. 计算机应用, 2005, 25(07): 1674-1675.
[13]	任小西，李仁发，张克环. 一种基于ADL的编译器自动生成方法研究[J]. 计算机应用, 2005, 25(02): 367-369.

自动并行化中不规则循环的通信代码生成

Communication code generation for automatic parallelization of irregular loops

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics