Publisher's Synopsis
A study into the questions posed by partitioning potential parallelism into useful parallelism, this work also attempts a general solution. Given that it is desirable for the partitioning and scheduling to be performed automatically, so that the same parallel program can execute efficiently on different multiprocessors, two approaches are presented. The first approach is based on a macro-dataflow model, where the program is partitioned into tasks at compile-time and the tasks are scheduled on processors at run-time; and the second is based on a compile-time scheduling model, where the partitioning of the program and the scheduling of tasks are both written at the same time.;Both approaches have been implemented to partition programs written in the single-assignment language SISAL. The inputs to the partitioning and scheduling algorithms are a graphical representation of the program and a list of parameters describing the target multiprocessor. Execution profile information is used to derive compile-time estimates of execution times and data sizes in the program. Both the macro-dataflow and compile-time scheduling problems are expressed as optimization problems, which are proved to be NP-complete in the strong sense. This work presents efficient approximation algorithms for these problems. The effectiveness of the partitioning and scheduling algorithms is studied by multiprocessor simulations of various SISAL benchmark programs for different target multiprocessor parameters.
