A SCALABLE SCHEDULING SCHEME FOR FUNCTIONAL PARALLELISM ON DISTRIBUTED-MEMORY MULTIPROCESSOR SYSTEMS

We attempt a new variant of the scheduling problem by investigating th e scalability of the schedule length with the required number of proce ssors, by performing scheduling partially at compile time and partiall y at run time. Assuming infinite number of processors, the compile tim e schedule is found using anew concept of the threshold of a task that quantifies a trade-off between the schedule-length and the degree of parallelism, The schedule is found to minimize either the schedule len gth dr the number of required processors and it satisfies: A feasibili ty, condition which guarantees that the schedule delay of a task from its earliest start time is below the threshold, and An optimality cond ition which uses a merit function to decide the best task-processor ma tch for a set of tasks competing for a given processor. At run time, t he tasks re merged producing a schedule for a smaller number of availa ble processors,This allows the program to be scaled down to the proces sors actually available at run time, Usefulness of this scheduling heu ristic has been demonstrated by. incorporating the scheduler in the co mpiler backend for targeting Sisal (Streams and Iterations in a Single Assignment Language) on iPSC/860.