Skewed Partition Method-Theory and Practice

[[abstract]]©1991 JISE-This paper studies strategies for partitioning programs on distributed-memory multicomputers. A technique called skewed partition is proposed. For certain applications the skewed partition method can reduce the amount of synchronization and provide greater control over the granularity than can the commonly used block partition method. To illustrate the idea, two examples¡Ðan image distance transformer and a linear equation solver¡Ðare examined. Results obtained from an Ncube-1 multicomputer show that the skewed partition method improves the performance of these programs more than 50¢H over the block partition method. Performance analysis of the skewed partition method is then studied. Expressions are derived to model and estimate the computation and communication costs resulting from a skewed partition. The expressions are based on loop-carried dependencies and take into account overlapping communications. From these analyses, the total execution time of parallel programs using the skewed partition method can be determined and the performance can be optimized.[[department]]資訊工程學