Computer-Aided Parallelization of Applications

M. Mazzariol

Ph.D. dissertation by Marc Mazzariol, under the supervision of Prof. Roger D. Hersch, Thesis No 2431 presented at the Computer Science Department, Ecole Polytechnique Fédérale de Lausanne, July 2001

Within the scope of this thesis, we are interested in running high-performance parallel applications on clusters of commodity components, i.e. PCs or workstations. Creating parallel applications remains a difficult task. Moreover, creating efficient pipelined parallel schedules where communication, computation and I/O are carried out simultaneously is a real challenge.

We use the Computer-Aided Parallelization (CAP) framework developed at EPFL in order to facilitate the design and development of pipelined parallel applications. The CAP based parallelization approach differs from other parallelization approaches by freeing the programmer from low-level issues such as thread management, protocol management and synchronization. The programmer can concentrate his efforts on building efficient parallel schedules. Application programmers express separately the serial program parts and the parallel behavior of the program at a high level of abstraction, i.e. as a parallel schedule. The parallel schedule determines the flow of data and parameters between operations running on the same or on different processors. CAP offers asynchronous processing capabilities allowing to carry out simultaneously I/O operations, communications and computations.

In this thesis, we show how parallel applications from various domains can be developed by taking advantage of CAP: parallel linear algebra algorithms such as matrix multiplication and LU decomposition, parallel image filtering, parallel cellular automata and parallel discrete optimization algorithm such as Branch and Bound. We are also interested in the parallelization of industrial applications, such as the Radiocontrol application aiming at computing in parallel the listening quotes of radio stations.

The contributions of this thesis are (1) to validate the CAP C++ language extension by demonstrating its capability of synthesizing parallel programs, and (2) to show that the CAP based parallelization approach yields efficient parallel programs in different application fields.

The reader is introduced to the CAP philosophy and to the formulation of parallel schedules. We discuss flow-control and load balancing issues and propose appropriate CAP constructs. In several parallel applications, we demonstrate the compositionality of CAP and its benefits. In order to demonstrate the performance offered by CAP, we create for most applications a performance model and verify it by experimental measurements. Finally, we describe the perspectives and give ideas for pursuing this research.

Download the full paper: PDF 5.4 MB