MATRIX TRANSPOSE FOR BLOCK ALLOCATIONS ON TORUS AND DEBRUIJN NETWORKS

We present in this paper fast algorithms for the matrix transpose prob lem on distributed-memory parallel machines for block allocations of t he matrix. We propose a general methodology based on a partitioning of the communication networks into paths or cycles for which we develop optimal algorithms for elementary pairwise exchanges, It leads to effi cient algorithms for torus and de Bruijn networks. We study the lower bounds for the linear model of time for both store-and-forward and wor mhole commutation modes, and we compare the execution time of our algo rithms with these lower bounds. (C) 1996 Academic Press, Inc.