A Data Motion Algorithm

We desire to permute N items w 0 ... , w N - 1 , in an ultracomputer containing P processing elements (PEs), PE 0 ,... PE P - 1 . Under the assumpution that N+P and that w i e PE i , Schwartz gives the following worst case analyses: The static permutation algorithm requires 4 log P - 3 data communication steps. It is easily seen that for both algorithms the average case behavior closely approximates the worst case. Here we present a data motion algorithm oriented toward average case rather than worst case performance, and supply an argument suggesting that the following average number of data communication steps required is approximately 3 log P. 1. Introduction [UC] introduced the idea of an ultracomputer and reviewed algorithms for two permutation problems: The "static permutation problem", in which an algorithm is tailored to each specific permutation p (given in advance), and the "dynamic permutation problem", in which one algorithm must effect all permutations (i.e., the permuta..