Minimization of interprocessor communication in parallel computation
Kuo-Wei Herman Chen · Deep Blue (University of Michigan) · 1981
This thesis is concerned with the problem of minimizing the interprocessor data communication in parallel computations. A characterization of the SIMD computing system, including both hardware and software, is first developed. Based on this characterization, the interprocessor communication problem is formulated as a minimization problem. In this thesis, the minimization problem is solved for a class of parallel algorithms and SIMD computers. A special case of this minimization problem is termed the mapping problem, which is basically the problem of determining good storage schemes for those data in the given parallel algorithm which are involved in special types of data transfers. Through the use of special data mapping techniques, it is demonstrated that the capabilities of interconnection networks can be greatly enhanced. For a special class of SIMD machines, those which use circular connection networks, and a special class of parallel algorithms, the minimization problem is solved in two stages. First, at the logical level, the optimal alignment of oper and s for every binary operation in the given algorithm and the optimal computation order for every parallel expression are determined. In the second stage, data mapping schemes are obtained. Both static data mapping and data remapping are considered. While static mapping can often lead to great reduction in communication cost, data remapping can, in many cases, further reduce this cost significantly. Optimal remapping algorithms which always generate an optimal remapping schedule for the given data have been designed. This methodology is then applied to a numerical algorithm-the parallel Jacobi algorithm. It is shown that, using an optimal remapping schedule for the transformation matrix of the Jacobi algorithm, the communication complexity is reduced by a factor equal to the size of the matrix. In general, the methodology developed in this thesis is widely applicable to many parallel algorithms for reducing the communication complexity.