An optimal index reshuffle algorithm for multidimensional arrays and its applications for parallel architectures

Reshuffling elements of a multidimensional array according to an index oper ation traditionally requires an auxiliary buffer of the same size as the or iginal array. Here, we describe a new in-place algorithm using vacancy trac king cycles with minimum memory access which eliminates the buffer array an d the related copy-back, speeding up the reshuffle significantly for large arrays. The algorithm can be paralleiized using a multithread approach on s hared-memory multiprocessor computers. On distributed-memory multiprocessor computers, the index reshuffle of distributed multidimensional arrays amou nts to a remapping of processor domains and is carried out using the in-pla ce local algorithm combined with a global exchange algorithm. Implementatio n and test results on GRAY T3E and IBM SP indicate the effectiveness of the algorithm.