Compile Time Partitioning And Scheduling Of Parallel Programs

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.

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.

This book is one of the first to address the problem of forming useful parallelism from potential parallelism and to provide a general solution. The book presents two approaches to automatic partitioning and scheduling so that the same parallel program can be made to execute efficiently on widely different multiprocessors. The first approach is based on a macro dataflow model in which the program is partitioned into tasks at compile time and the tasks are scheduled on processors at run time. The second approach is based on a compile time scheduling model, where both the partitioning and scheduling are performed at compile time. Both approaches have been implemented in partition programs written in the single assignment language SISAL. The inputs to the partitioning and scheduling algorithms are a graphical representation of the parallel 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 and are shown to be NP complete in the strong sense. Efficient approximation algorithms for these problems are presented. Finally, the effectiveness of the partitioning and scheduling algorithms is studied by multiprocessor simulations of various SISAL benchmark programs for different target multiprocessor parameters. Vivek Sarkar is a Member of Research Staff at the IBM T. J. Watson Research Center. Partitioning and Scheduling Parallel Programs for Multiprocessing is included in the series Research Monographs in Parallel and Distributed Computing. Copublished with Pitman Publishing.

The second half of the 1970s was marked with impressive advances in array/vector architectures and vectorization techniques and compilers. This progress continued with a particular focus on vector machines until the middle of the 1980s. The major ity of supercomputers during this period were register-to-register (Cray 1) or memory-to-memory (CDC Cyber 205) vector (pipelined) machines. However, the increasing demand for higher computational rates lead naturally to parallel comput ers and software. Through the replication of autonomous processors in a coordinated system, one can skip over performance barriers due technology limitations. In princi ple, parallelism offers unlimited performance potential. Nevertheless, it is very difficult to realize this performance potential in practice. So far, we have seen only the tip of the iceberg called "parallel machines and parallel programming". Parallel programming in particular is a rapidly evolving art and, at present, highly empirical. In this book we discuss several aspects of parallel programming and parallelizing compilers. Instead of trying to develop parallel programming methodologies and paradigms, we often focus on more advanced topics assuming that the reader has an adequate background in parallel processing. The book is organized in three main parts. In the first part (Chapters 1 and 2) we set the stage and focus on program transformations and parallelizing compilers. The second part of this book (Chapters 3 and 4) discusses scheduling for parallel machines from the practical point of view macro and microtasking and supporting environments). Finally, the last part (Le.

This three-volume work presents a compendium of current and seminal papers on parallel/distributed processing offered at the 22nd International Conference on Parallel Processing, held August 16-20, 1993 in Chicago, Illinois. Topics include processor architectures; mapping algorithms to parallel systems, performance evaluations; fault diagnosis, recovery, and tolerance; cube networks; portable software; synchronization; compilers; hypercube computing; and image processing and graphics. Computer professionals in parallel processing, distributed systems, and software engineering will find this book essential to their complete computer reference library.

The Cray Research MPP Fortran Programming Model.- Resource Optimisation via Structured Parallel Programming.- SYNAPS/3 - An Extension of C for Scientific Computations.- The Pyramid Programming System.- Intelligent Algorithm Decomposition for Parallelism with Alfer.- Symbolic Array Data Flow Analysis and Pattern Recognition in Numerical Codes.- A GUI for Parallel Code Generation.- Formal Techniques Based on Nets, Object Orientation and Reusability for Rapid Prototyping of Complex Systems.- Adaptor - A Transformation Tool for HPF Programs.- A Parallel Framework for Unstructured Grid Solvers.- A Study of Software Development for High Performance Computing.- Parallel Computational Frames: An Approach to Parallel Application Development based on Message Passing Systems.- A Knowledge-Based Scientific Parallel Programming Environment.- Parallel Distributed Algorithm Design Through Specification Transformation: The Asynchronous Vision System.- Steps Towards Reusability and Portability in Parallel Programming.- An Environment for Portable Distributed Memory Parallel Programming.- Reuse, Portability and Parallel Libraries.- Assessing the Usability of Parallel Programming Systems: The Cowichan Problems.- Experimentally Assessing the Usability of Parallel Programming Systems.- Experiences with Parallel Programming Tools.- The MPI Message Passing Interface Standard.- An Efficient Implementation of MPI.- Post: A New Postal Delivery Model.- Asynchronous Backtrackable Communications in the SLOOP Object-Oriented Language.- A Parallel I/O System for High-Performance Distributed Computing.- Language and Compiler Support for Parallel I/O.- Locality in Scheduling Models of Parallel Computation.- A Load Balancing Algorithm for Massively Parallel Systems.- Static Performance Prediction in PCASE: A Programming Environment for Parallel Supercomputers.- A Performance Tool for High-Level Parallel Programming Languages.- Implementation of a Scalable Trace Analysis Tool.- The Design of a Tool for Parallel Program Performance Analysis and Tuning.- The MPP Apprentice Performance Tool: Delivering the Performance of the Cray T3D.- Optimized Record-Replay Mechanism for RPC-based Parallel Programming.- Abstract Debugging of Distributed Applications.- Design of a Parallel Object-Oriented Linear Algebra Library.- A Library for Coarse Grain Macro-Pipelining in Distributed Memory Architectures.- An Improved Massively Parallel Implementation of Colored Petri-Net Specifications.- A Tool for Parallel System Configuration and Program Mapping based on Genetic Algorithms.- Emulating a Paragon XP/S on a Network of Workstations.- Evaluating VLIW-in-the-large.- Implementing a N-Mixed Memory Model on a Distributed Memory System.- Working Group Report: Reducing the Complexity of Parallel Software Development.- Working Group Report: Usability of Parallel Programming System.- Working Group Report: Skeletons/Templates.

Proceedings -- Parallel Computing.