LATIN SQUARES FOR PARALLEL ARRAY ACCESS

We propose a new parallel memory system for efficient parallel array a ccess. New latin squares called perfect latin squares are introduced t o be used as skewing functions. Simple construction methods are shown for building perfect latin squares. The resulting skewing scheme provi des conflict free access to several important subsets of an array. The address generation can be performed in constant time with simple circ uitry. The skewing scheme is the first skewing scheme that can provide constant time access to rows, columns, diagonals, and N1/2 x N1/2 sub arrays of an N x 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 s kewing schemes to provide conflict free access to three-dimensional ar rays. Combined with self-routing Benes networks, these schemes provide efficient access to frequently used subsets of three-dimensional arra ys.