Partitioning and mapping of nested loops for linear array multicomputers |
| |
Authors: | Jang-Ping Sheu Tzung-Shi Chen |
| |
Affiliation: | (1) Department of Computer Science and Information Engineering, National Central University, 32054 Chung-Li, Taiwan, R.O.C. |
| |
Abstract: | In distributed-memory multicomputers, minimizing interprocessor communication is the key to the efficient execution of parallel programs. In order to reduce the amount of communication overhead, parallel programs on multicomputers must be carefully scheduled by parallelizing compilers. This paper proposes some compilation techniques for partitioning and mapping nested loops with constant data dependences onto linear array multicomputers. First, a systematic partition strategy is proposed to project ann-dimensional computational structure, representing ann-nested loop, onto a line to form a one-dimensional projected structure with low communication overhead. Then, a mapping algorithm is proposed for mapping the partitioned loops onto linear arrays in a way that balances the workload and minimizes the communication cost among processors. Finally, parallel execution codes can be automatically generated for such linear array multicomputers. |
| |
Keywords: | Data dependence vectors distributed-memory multicomputers interprocessor communication linear array multicomputers parallelizing compilers |
本文献已被 SpringerLink 等数据库收录! |
|