Report Number: CS-TR-73-388
Institution: Stanford University, Department of Computer Science
Title: Interconnections for parallel memories to unscramble
Author: Swanson, Roger C.
Date: May 1973
Abstract: Several methods are being considered for storing arrays in a
parallel memory system so that various useful partitions of
an array can be fetched from the memory with a single access.
Some of these methods fetch vectors in an order scrambled
from that required for a computation. This paper considers
the problem of unscrambling such vectors when the vectors
belong to a class called p-ordered vectors and the memory
system consists of a prime number of modules.
Pairs of interconnections are described that can unscramble
p-ordered vectors in a number of steps that grows as the
square root of the number of memories. Lower and upper bounds
are given for the number of steps to unscramble the worst
case vector. The upper bound calculation that is derived also
provides an upper bound on the minimum diameter of a star
polygon with a fixed number of nodes and two
interconnections. An algorithm is given that has produced
optimal pairs of interconnections for all sizes of memory
that have been tried. The algorithm appears to find optimal
pairs for all memory sizes, but no proof has yet been found.