A unified approach to optimal multiprocessor implementations from non-parallel algorithm specifications (graph models, parallel processing)
Sae Hun Lee · 1986
The primary objective of this thesis is to develop a total system composed of four semi-independent elements: (1) the generation of a generic flow graph (GFG) BaSC83 from a serial specification of an algorithm; (2) the construction of a fully specified flow graph (FSFG) LeHB85 from a generic flow graph; (3) the generation of optimal (or suboptimal) schedules for synchronous multiprocessor systems BaH82a ; and (4) the generation of implementations for constrained communication architectures ScBH86 . The input to the first element is a serially defined algorithm specified using a subset of FORTRAN. The output of this element is a cyclic graphical representation of the algorithm, the GFG, with a collection of elementary operations (i.e. macro nodes) that gives maximum flexibility for the graph transformations to follow. The second element is the decomposition of the generated GFGs into fine-grain graphs for multiprocessor implementations. The FSFGs generated are specifically constrained to have maximum parallelism. The multiprocessor schedules generated are all constrained members of the class of cyclo-static implementations Schw85 which have been shown to be a powerful tool for implementing DSP algorithms. The solutions are constrained (in constrast to the unconstrained cyclo-static solutions in ScBa85 Schw85 ) in an attempt to reduce the required communications complexity of the multiprocessor realizations. Maximally fast, maximally efficient solutions are sought by sequentially searching for three different classes of solutions: Skewed Single Instruction Multiple Data (SSIMD); static parallel Skewed Single Instruction Multiple Data (static-PSSIMD); and balanced Parallel Skewed Single Instruction Multiple Data (balanced-PSSIMD). No explicit communications constraints are applied during the generation of SSIMD, static-PSSIMD, and balanced-PSSIMD schedules. The last element concerns the communications issue on synchronous multiprocessor systems which have constrained communication structures. Once again a limited class of cyclo-static methods are of interest, and the emphasis is on the realization of adjacent communications on a nearest-neighbor mesh network. Two subclasses of cyclo-static implementations, static-PSSIMD and balanced-PSSIMD ScBa85 LeBa86 are investigated in detail. (Abstract shortened with permission of author.)