Physical Sciences and Mathematics Commons^™

Contention-Free Scheduling Of Communication Induced By Array Operations On 2d Meshes, Andreas Bernhard Georg Eberhart

Dissertations and Theses

Whole array operations and array section operations are important features of many data-parallel languages. Efficient implementation of these operations on distributed-memory multicomputers is critical to the scalability and high-performance of data-parallel programs. This thesis presents an approach for analyzing communication patterns induced by array operations and for using run-time information to schedule the message flow. The distributed, dynamic scheduling algorithms guarantee link-contention-free data transfer and utilize network resources almost optimally. They incur little overhead, which is important in order not to reduce the speedup gained by the parallel execution. The algorithms can be used by compilers for the generation of …