Affordable Access

Publisher Website

Program Repartitioning on Varying Communication Cost Parallel Architectures

Journal of Parallel and Distributed Computing
Publication Date
DOI: 10.1006/jpdc.1996.0039
  • Communication
  • Computer Science


Abstract In an earlier work, a Threshold Scheduling Algorithmwas proposed to schedule the functional (DAG) parallelism in a program on distributed memory systems. In this work, we address the issue of adapting the schedule for a set of distributed memory architectures with the same computation costs but higher communication costs. We introduce a new concept of dominant edgesof a schedule to denote those edges which dictate the schedule time of the destination nodes due to the changes in their communication costs. Using this concept, we derive the conditions under which schedule on the whole or at least part of the graph can be reused for a different architecture keeping the cost of program repartitioning and rescheduling to a minimum. We demonstrate the practical significance of the method by incorporating it in the compiler backend for targeting Sisal (Streams and Iterations in a Single Assignment Language) on a family of Intel i860 architectures, Gamma, Delta, and Paragon, which vary in their communication costs. It is shown that almost 30 to 65% of the schedule can be reused unchanged, thereby avoiding program repartitioning to a large degree. The remainder of the schedule can be regeneratedthrough a linear algorithm at run time.

There are no comments yet on this publication. Be the first to share your thoughts.