Title :
Communication-free data allocation techniques for parallelizing compilers on multicomputers
Author :
Chen, Tzung-Shi ; Sheu, Jang-Ping
Author_Institution :
Inst. of Comput. Sci. & Electron. Eng., Nat. Central Univ., Chung-Li, Taiwan
fDate :
9/1/1994 12:00:00 AM
Abstract :
In distributed memory multicomputers, local memory accesses are much faster than those involving interprocessor communication. For the sake of reducing or even eliminating the interprocessor communication, the array elements in programs must be carefully distributed to local memory of processors for parallel execution. We devote our efforts to the techniques of allocating array elements of nested loops onto multicomputers in a communication-free fashion for parallelizing compilers. We first analyze the pattern of references among all arrays referenced by a nested loop, and then partition the iteration space into blocks without interblock communication. The arrays can be partitioned under the communication-free criteria with nonduplicate or duplicate data. Finally, a heuristic method for mapping the partitioned array elements and iterations onto the fixed-size multicomputers under the consideration of load balancing is proposed. Based on these methods, the nested loops can execute without any communication overhead on the distributed memory multicomputers. Moreover, the performance of the strategies with nonduplicate and duplicate data for matrix multiplication is studied
Keywords :
distributed memory systems; parallel programming; program compilers; storage allocation; array elements; communication overhead; communication-free criteria; communication-free data allocation techniques; distributed memory multicomputers; duplicate data; fixed-size multicomputers; heuristic method; interblock communication; interprocessor communication; iteration space; load balancing; local memory accesses; matrix multiplication; multicomputers; nested loop; nested loops; parallel execution; parallelizing compilers; partitioned array elements; Computer science; Councils; Data mining; Load management; Magnetic heads; Parallel machines; Parallel processing; Pattern analysis; Program processors; Random access memory;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on