Communication-minimal Partitioning and Data Alignment of BLAS-like Algorithms

TitleCommunication-minimal Partitioning and Data Alignment of BLAS-like Algorithms
Publication TypeConference Paper
Year of Publication1995
AuthorsLee, HJ, Fortes, JAB
Conference Name1995 International Conference on Parallel Processing
Date Published08/1995
AbstractAutomatic data alignment and computation domain partitioning techniques have been widely investigated to reduce communication overheads in distributed memory systems. This paper considers how these two techniques can be combined and applied to BLAS-like algorithms. Current data alignment techniques focus on individual data entries and cannot be directly used for cases when blocks of entries should be aligned collectively. This paper shows that existing data alignment techniques can be applied to partitioned algorithms if the null space of the data array indexing matrix is a boundary of computation blocks or the intersection of some of the computation block boundaries. These conditions can be used to generate several different partitionings and time-space transformations from which the optimal ones can be chosen for a given target architecture. An example illustrates how it is possible to trade off the number of communications and memory space. Another example shows partitions of matrix...