Algorithmic redistribution methods for block cyclic decompositions

This research aims at creating and providing a framework to describe algo-rithmic redistribution methods for various block cyclic decompositions. To do so properties of this data distribution scheme are formally exhibited. The exami-nation of a number of basic dense linear algebra operations illustrates the appli-cation of those properties. This study analyzes the extent to which the general two-dimensional block cyclic data distribution allows for the expression of efficient as well as flexible matrix operations. This study also quantifies theoretically and practically how much of the efficiency of optimal block cyclic data layouts can be maintained. The general block cyclic decomposition scheme is shown to allow for the ex-pression of flexible basic matrix operations with little impact on the performance and efficiency delivered by optimal and restricted kernels available today. Second, block cyclic data layouts, such as the purely scattered distribution, which seem less promising as far as performance is concerned, are shown to be able to achieve optimal performance and efficiency for a given set of matrix operations. Conse-quently, this research not only demonstrates that the restrictions imposed by the optimal block cyclic data layouts can be alleviated, but also that efficiency and flexibility are not antagonistic features of the block cyclic mappings. These results are particularly relevant to the design of dense linear algebra software libraries as well as to data parallel compiler technology.