Interconnections for Parallel Memories to Unscramble p-Ordered Vectors.
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. The 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 grow 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1973
- Accession Number
- AD0770552
Entities
People
- Roger C. Swanson
Organizations
- Stanford University