Concurrency enhancement through program unification: Design, techniques, and experiments

In this dissertation, we introduce a source-to-source transformation technique called program unification. It attempts to exploit parallelism across programs and improve the performance of poorly-parallelized programs. This technique is applicable to programs that satisfy two criteria, poor parallelism and the need for repeated executions. The program unification method transforms a poorly-parallelized program into a unified program that contains multiple instances of a program and its data. A single instance of a program and its data is called a component. Parallelism is exploited by executing the multiple components within a unified program simultaneously. The program unification technique we describe can be used on various machines. We focus on vector machines and SIMD machines. As a precursor to the development of a tool for program unification, we present a systematic way to transform a given program into a unified program for vector machines and SIMD machines. Each component of the transformed or unified program retains the same execution path and gives the same output as its sequential version. We present results of experiment with the program unification method on vector machines such as the Alliant FX series and the Cray Y-MP, and on SIMD machines such as the CM2 and the CM5. Application programs used include priority queue implementations, a single-server queueing system, and a Rayleigh problem. Since different application programs behave differently, the speedups obtained varied. However, the program unification method resulted in speedups in most cases. In one application, we obtained a speedup of 9, using a single processor on the Cray Y-MP