Minimization of Interprocessor Communication for Parallel Computations on an Simd Multicomputer.

Interprocessor communication is an important aspect of parallel processing. Studies have shown that data communication can be a major cause of performance degradation of a parallel algorithm. This thesis is concerned with minimization of delay due to interprocessor data communication during the execution of a parallel algorithm on an SIMD multicomputer interconnected with any multistage interconnection network from a class of functionally equivalent networks. The interprocessor communication cost minimization problem for the omega network in the equivalent class are presented. For the class of important permutations with which this thesis is concerned, a representation scheme is developed. This class of permutations includes the class of bit-permute-complement studied often in the literature. Based on the representation scheme and the omega network, algorithms are developed that determine, for a given parallel procedure, the mapping and remapping of data into physical memories so that the communication cost is minimized. Algorithms are also developed that determine, for every arithmetic expression of a given procedure, the alignment of oper and s for every binary operation so that the communication cost is minimized. For example, the communication costs of a lower triangular matrix inversion program and a fast Fourier transform program are minimized using both approaches. For each of the approaches, a saving of one-third of the original communication cost is achieved for the matrix inversion program while a saving of three-fifths is achieved for the fast Fourier transform program. The algorithms developed are proved to be applicable for any SIMD multicomputer interconnected with any network from the equivalent class.PhDComputer scienceUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/160073/1/8412286.pd