Designing Parallel Programs of Parameterized Granularity

摘要

A method for designing fine grained programs is discussed. The design method isexplained by identifying five phases in the design of a parallel program. Each phase is addressed separately. A design decision made in one phase usually has impact on some next design phases. Two programs that serve as running examples throughout are derived. The implementation of parallel programs on processor networks is considered. A model to analyze an implementation's speedup is presented. A technique for transforming fine grained programs into programs of a coarser grain is discussed. This technique yields programs of parameterized granularity. The proposed technique is applied to two types of programs. The running examples are transformed into parallel programs of parameterized grain size. It is shown that the transformation technique is generally applicable to any fine grained program. Experimental results for both very large scale integration and processor network implementations of the running examples are presented.