Automatic Alignment of Array Data and Processes To Reduce Communication Time on DMPPs
| Title | Automatic Alignment of Array Data and Processes To Reduce Communication Time on DMPPs |
| Publication Type | Technical Report |
| Year of Publication | 1994 |
| Authors | Philippsen, M. |
| Other Numbers | 939 |
| Abstract | This paper investigates the problem of aligning array data and processes in a distributed-memory implementation. We present complete algorithms for compile-time analysis, the necessary program restructuring, and subsequent code-generation, and discuss their complexity. We finally evaluate the practical usefulness by quantitative experiments. The technique presented analyzes complete programs, including branches, loops, and nested parallelism. Alignment is determined with respect to offset, stride, and general axis relations. Both placement of data and processes are computed in a unifying framework based on an extended preference graph and its analysis. Furthermore, dynamic redistribution and replication are considered in the same technique. The experimental results are very encouraging. The optimization algorithms implemented in the Modula-2*, compiler, developed at the University of Kalrsruhe, improved the execution times of the programs by on average over 40% on a MasPar MP-1 with 16384 processors. Updated March 1995. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-070.pdf |
| Bibliographic Notes | ICSI Technical Report TR-94-070 |
| Abbreviated Authors | M. Philippsen |
| ICSI Publication Type | Technical Report |