Chinese Journal of Computers   Full Text
Title	Communication Set Generation for a Special Case of Irregular Parallel Applications
Authors	HU Chang-Jun LI Jing WANG Jue YAO Guang-Li LI Yong-Hong DING Liang LI Jian-Jiang
Address	(School of Information Engineering, University of Science and Technology Beijing, Beijing 100083)
Year	2008
Issue	No.1(120—126)
Abstract &   Background	Abstract Irregular computing significantly influences the performance of large scale parallel applications. How to generate local memory access sequence and communication set efficiently for irregular array reference is an important issue in compiling a data-parallel language into a single program multiple data (SPMD) code for distributed-memory machines. By far, many researches have focused on the problem of communication set generation under regular array references in parallel loops. However, little researches give attentions to generating communication set for irregular array accesses in loop nests. In general case of irregular accesses, Inspector/Executor model is adopted to scan over array elements at Inspector phase of run time such that communication set can be constructed. This paper proposes an approach to derive an algebraic solution of communication set enumeration at compile time for the situation of irregular array references in nested loops. And this paper introduces integer lattice into alignment and cyclic(k)-distribution for global-to-local and local-to-global index translations. Then it also presents the algorithm for the corresponding SPMD code generation. When the parameters of alignments and cyclic(k) and array references are known, the SPMD code can then be completely derived at compile time such that no inspector-like run-time code will be needed to construct enumeration of the communication set. keywords irregular computing; communication set generation; parallelizing compilers; communication optimization; SPMD scheme background The work in this paper belongs to communication set generation for irregular applications. Up to now, a lot of researches have focused on the problem of communication set generation under regular array references in parallel loops. However, little researches give attentions to generate communication set for irregular array accesses in loop nests. In general case of irregular accesses, Inspector/Executor model is adopted to scan over array elements at Inspector phase of run-time such that communication set can be constructed. The contributions of this work include: (1)Proposing an approach to derive an algebraic solution of communication set enumeration at compile time for the situation of irregular array references in nested loops; (2)Introducing integer lattice into alignment and cyclic(k)-distribution for global-to-local and local-to-global index translations; (3)Presenting the authors′ algorithm for the corresponding SPMD code generation. So when the parameters of alignments and cyclic(k) and array references are known, the SPMD code can then be completely derived at compile time such that no inspector-like run-time code will be needed to construct enumeration of the communication set. This work is supported by The National High Technology Research and Development Program (863 Program) under grant No.2006AA01Z105，the National Natural Science Foundation of China under grant No.60373008 and the Ministry of Education of the People′s Republic of China Major Foundation under grant No.106019. The objective of the National High Technology Research and Development Program (863 Program) is to improve the productivity of parallel programmer using parallel compiling techniques. The National Natural Science Foundation of China pays attentions to OpenMP extension on clusters. The Ministry of Education of the People′s Republic of China Major Foundation focuses on a difficult problem in parallel computing, i.e., out-of-core irregular problem. In communication scheduling area, The authors have improved efficiency of collective communication using compiling techniques. This paper proposes a communication generation approach, which integrates the benefits from the algebra method and the integer lattice method, to derive an algebraic solution of communication set enumeration.