PROGRAM REPARTITIONING ON VARYING COMMUNICATION COST PARALLEL ARCHITECTURES

In an earlier work, a Threshold Scheduling Algorithm was proposed to s chedule the functional (DAG) parallelism in a program on distributed m emory systems. In this work, we address the issue of adapting the sche dule for a set of distributed memory architectures with the same compu tation costs but higher communication costs. We introduce a new concep t of dominant edges of 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 und er which schedule on the whole or at least part of the graph can be re used for a different architecture keeping the cost of program repartit ioning and rescheduling to a minimum. We demonstrate the practical sig nificance of the method by incorporating it in the compiler backend fo r targeting Sisal (Streams and Iterations in a Single Assignment Langu age) on a family of Intel i860 architectures, Gamma, Delta, and Parago n, which vary in their communication costs. It is shown that almost 30 to 65% of the schedule can be reused unchanged, thereby avoiding prog ram repartitioning to a large degree. The remainder of the schedule ca n be regenerated through a linear algorithm at run time. (C) 1996 Acad emic Press, Inc.