Latin Squares for Parallel Array Access

We propose a new parallel memory system for efficient parallel array access. New latin squares called perfect latin squares are introduced to be used as skewing functions. Simple construction methods are shown for building perfect latin squares. The resulting skewing scheme provides conflict free access to several important subsets of an array. The address generation can be performed in constant time with simple cir-cuitry. The skewing scheme is the first skewing scheme that can provide constant time access to rows, columns, diagonals, and N1/2x iV1/2subarrays of an N × N array with maximum memory utilization. Self-routing Benes networks can be used to realize the permutations needed between the processing elements and the memory modules. We also propose two skewing schemes to provide conflict free access to three-dimensional arrays. Combined with self-routing Benes networks, these schemes provide efficient access to frequently used subsets of three-dimensional arrays.