| タイトル | Aligning parallel arrays to reduce communication |
| 本文（外部サイト） | http://hdl.handle.net/2060/19950003592 |
| 著者（英） | Gilbert, John R.; Chatterjee, Siddhartha; Schreiber, Robert; Sheffler, Thomas J. |
| 著者所属（英） | Research Inst. for Advanced Computer Science |
| 発行日 | 1994-07-01 |
| 言語 | eng |
| 内容記述 | Axis and stride alignment is an important optimization in compiling data-parallel programs for distributed-memory machines. We previously developed an optimal algorithm for aligning array expressions. Here, we examine alignment for more general program graphs. We show that optimal alignment is NP-complete in this setting, so we study heuristic methods. This paper makes two contributions. First, we show how local graph transformations can reduce the size of the problem significantly without changing the best solution. This allows more complex and effective heuristics to be used. Second, we give a heuristic that can explore the space of possible solutions in a number of ways. We show that some of these strategies can give better solutions than a simple greedy approach proposed earlier. Our algorithms have been implemented; we present experimental results showing their effect on the performance of some example programs running on the CM-5. |
| NASA分類 | COMPUTER SYSTEMS |
| レポートNO | 95N10004
NASA-CR-196377
NAS 1.26:196377
RIACS-TP-94-10 |
| 権利 | No Copyright |
|
