BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-73-388
       ENTRY:: September 25, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Interconnections for parallel memories to unscramble
               p-ordered vectors.
        TYPE:: Technical Report
      AUTHOR:: Swanson, Roger C.
        DATE:: May 1973
       PAGES:: 58
    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.
       NOTES:: [Adminitrivia V1/Prg/19950925]
         END:: STAN//CS-TR-73-388