Automatic Mapping of Task and Data Parallel Programs for Efficient Execution on Multicomputers
Abstract
For a wide variety of applications, both task and data parallelism must be exploited to achieve the best possible performance on a multicomputer. Recent research has underlined the importance of exploiting task and data parallelism in a single compiler framework, and such a compiler can map a single source program in many different ways onto a parallel machine. There are several complex trade offs between task and data parallelism, depending on the characteristics of the program to be executed and the performance parameters of the target parallel machine. This makes it very difficult for a programmer to select a good mapping for a task and data parallel program. In this paper we isolate and examine specific characteristics of executing programs that determine the performance for different mappings on a parallel machine, and present an automatic system to obtain good mappings. The process consists of two steps: First, an instrumented input program is executed a fixed number of times with different mappings, to build an execution model of the program. Next, the model is analyzed to obtain a good final mapping of the program on to the processors of the parallel machine. The current implementation is static, feedback driven although the approach can be extended to a dynamic system. We demonstrate the system with an example program that is a model for many applications in the domains of signal processing and image processing.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1993
- Accession Number
- ADA274125
Entities
People
- Jaspal Subhlok
Organizations
- Carnegie Mellon University