[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.14 No.4, pp.695-723 (December 1998)
Compiling Array References with Affine Functions
for Data-Parallel Programs

Wen-Hsing Wei, Kuei-Ping Shih and Jang-Ping Sheu
Department of Computer Science and Information Engineering
National Centeral University
Chungli, Taiwan 320, R.O.C.

An important research topic is parallelizing of compilers to generate local memory access sequences and communication sets while compiling a data-parallel language into an SPMD (Single Program Multiple Data) program. In this paper, we present a scheme to efficiently enumerate local memory access sequences and to evaluate communication sets. We use a class table to store information that is extracted from array sections and data distribution patterns. Given array references and data distributions, we can utilize the class table to generate communication sets in closed forms. Furthermore, we derive the algorithms for sending and receiving necessary data between processors. An algorithm for generating the class table is presented, and the time complexity of this algorithm is O(s), where s is the array section stride. The technique of generating communication sets for one index variable has been implemented on a DEC Alpha 3000 workstation. The experimental results confirm the advantage of our scheme, especially when the array section stride is larger than the block size. Finally, we adapt our approach to handle array references with multiple index variables. The time complexity for constructing the whole class table is O(s2).

Keywords: communication set, data-parallel language, distributed memory multicomputers, HPF, parallelizing compilers, SPMD

Full Text () Retrieve PDF document (199812_01.pdf : 187,639 bytes)

Received April 16, 1996; accepted December 22, 1996.
Communicated by Shing-Tsaan Huang.