Compile Time Partitioning And Scheduling Of Parallel Programs Extended Summary

One of the biggest challenges facing language designers and implementors is to develop languages that will be suitable for use on multiprocessors. A wide variety of multiprocessor architectures are currently being built and that variety is expected to increase. Very little software is available to exploit parallelism and speed-up the execution of individual programs. What little work has been done, has focused largely on special-purpose parallelism (e.g. vectorization) or very limited classes of architectures. To understand the issues involved in taking advantage of parallelism and to evaluate architectures, we need to find compilation techniques for fairly general-purpose languages; these techniques need to be adapted to a wide variety of architectures. Only then will it be possible to compare various languages, alternative architectures, and their interaction with different applications. To compile and execute a program in a parallel fashion on a multiprocessor, there are three fundamental problems to be solved: 1) Identification of potential parallelism - discovering parallel computations in the program. 2) Partitioning the program into tasks - each task represents a serially-executed component that can execute in parallel with other tasks. 3) Scheduling the execution of tasks - the tasks must be scheduled for execution on multiple processors.