Compile-Time Partitioning and Scheduling of Parallel Programs

Abstract
Partitioning and scheduling techniques are necessary to implement parallel languages on multiprocessors. Multiprocessor performance is maximized when parallelism between tasks is optimally traded off with communication and synchronization overhead. The authors present compile-time partitioning and scheduling techniques to achieve this tradeoff. One of the biggest challenges facing compiler writers is to efficiently implement programming languages on multiprocessors. We need to find compilation techniques for general-purpose parallel languages; these techniques should be adaptable to a wide range of multiprocessor architectures. There are three fundamental problems to be solved when compiling a program for parallel execution on a multiprocessor: 1) Identifying potential parallelism; 2) Partitioning the program into sequential tasks; and 3) Scheduling the concurrent execution of these tasks. This document addresses the latter two problems and suggest that these be solved at compile- time instead of run-time for applications with fairly predictable execution times.