Implementation of Permutation Functions in Illiac IV-Type Computers

Abstract

Much research has recently been done on processor interconnection schemes for parallel computers. These interconnection schemes allow certain permutations to be performed in less than linear time, typically 0(log N), 0(log²N), or 0(√N) for a vector of N elements and N processors. In this paper we show that many permutations can also be performed in less than linear time on a machine with an Illiac IV-type interconnection scheme, that is connections to processors at distances of ± 1 and ±√N. These reselts show that, for irregular permutations, these recently developed interconnection schemes yield a speedup of at most 0(√N) over the Illiac IV-type interconnections. These results are of current interest due to the present Illiac IV programming effort.