Parallel processing with macro-pipeline model

Current parallelization techniques, mostly based on data dependence analysis, are primarily used to generate vector and data-parallel programs. These techniques handle loop-carried dependency of array data fairly well, but not parallelism across the boundaries of loop and function modules. This thesis focuses on a parallelization technique for coarse-grain parallelism among the tasks of a sequential program. A new parallel programming model, called macro-pipeline model, is proposed to parallelize a sequential program into a linear sequence of communicating sequential processes which can be executed by a linear array of general-purpose processors. The main idea is to partition a sequential program by a functional decomposition approach rather than the domain decomposition approach in order to preserve the function coherency as well as the original sequence of the control flow and the data flow in the original sequential program. Based on this approach, this thesis first presents a systematic method to parallelizing a sequential program into a macro-pipelining program. Next, a performance model is defined to evaluate the efficiency and the effectiveness of the parallelized program fitting a specific parallel system. Using computer simulation on an application domain, the performance and limitations of the proposed macro-pipeline model are verified, and architectural requirements of a macro-pipeline machine are then proposed. To ease the programming job, a parallelizing compiler is proposed to translate a sequential program into a macro-pipelining program automatically. Based on the assumption of structured programs, a target iteration body can be expressed as a linear sequence of basic program segments (single-entry, single-exit), and the proposed techniques are used to perform program partitioning and data distribution. A data flow analysis technique is used to determine all the variables that are used across processes, and then determines where to position the send and receive statements appropriately in the parallelized program. The proposed parallelizing compiler based on these techniques can be applied to a few classes of application programs