Optimal algorithms for stable dimension permutations on Boolean cubes
C-T. Ho, Lennart Johnsson · 1988
In this paper we present algorithms optimal within a small constant factor for stable dimension permutations on Boolean cubes. A stable dimension permutation is a permutation such that element (wm-1wm-2 … w0) is relocated to the location of element (wd(m-1)wd(m-2)…wd(0) after the permutation, or i → d(i), where d(·) is a permutation function on {0,1,…, m - 1}. Depending on communication capability, message size, cube size, data transfer rate, and communication start-up time, different algorithms must be chosen for a communication time optimal within a small constant factor. The bandwidth of the Boolean cube is fully explored by dividing the data set to be communicated between a pair of processors into subsets, one for each path between the pair of processors. The k-shuffle permutation, the bit-reversal permutation, and matrix transposition, are special cases of stable dimension permutations. Experimental results on the Intel iPSC are also provided.