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

@article{citeulike:1639360, abstract = {Reshuffling elements of a multidimensional array according to an index operation traditionally requires an auxiliary buffer of the same size as the original array. We describe a new in-place algorithm using vacancy tracking cycles with minimum memory access which eliminates the buffer array and the related copy-back, speeding up the reshuffle significantly for large arrays. The algorithm can be parallelized using a multithread approach on shared-memory multiprocessor computers. On distributed-memory multiprocessor computers, the index reshuffle of distributed multidimensional arrays amounts to a remapping of processor domains and is carried out using the in-place local algorithm combined with a global exchange algorithm. Implementation and test results on CRAY T3E and IBM SP indicate the effectiveness of the algorithm}, author = {Ding, C. H. Q. }, booktitle = {Parallel and Distributed Systems, IEEE Transactions on}, citeulike-article-id = {1639360}, journal = {Parallel and Distributed Systems, IEEE Transactions on}, keywords = {algorithms}, number = {3}, pages = {306--315}, posted-at = {2007-09-09 18:20:49}, priority = {2}, title = {An optimal index reshuffle algorithm for multidimensional arrays and its applications for parallel architectures}, url = {http://ieeexplore.ieee.org/xpls/abs\_all.jsp?arnumber=914776}, volume = {12}, year = {2001} }

TY - JOUR ID - citeulike:1639360 L3 - citeulike-article-id:1639360 TI - An optimal index reshuffle algorithm for multidimensional arrays and its applications for parallel architectures T2 - Parallel and Distributed Systems, IEEE Transactions on JF - Parallel and Distributed Systems, IEEE Transactions on VL - 12 IS - 3 SP - 306 EP - 315 N2 - Reshuffling elements of a multidimensional array according to an index operation traditionally requires an auxiliary buffer of the same size as the original array. We describe a new in-place algorithm using vacancy tracking cycles with minimum memory access which eliminates the buffer array and the related copy-back, speeding up the reshuffle significantly for large arrays. The algorithm can be parallelized using a multithread approach on shared-memory multiprocessor computers. On distributed-memory multiprocessor computers, the index reshuffle of distributed multidimensional arrays amounts to a remapping of processor domains and is carried out using the in-place local algorithm combined with a global exchange algorithm. Implementation and test results on CRAY T3E and IBM SP indicate the effectiveness of the algorithm KW - algorithms AU - Ding, CHQ PY - 2001/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=914776 ER -