Perfect Latin squares and parallel array access.

A nonlinear skewing scheme is proposed for parallel array access. The authors introduce perfect Latin square, which has several properties useful for parallel array access. A sufficient condition for the existence of perfect Latin squares and a simple method for their construction are presented. The resulting skewing scheme provides conflict free access to various subsets of an N × N array using N memory modules. When the number of memory modules is an even power of two, address generation is performed in constant time using a simple circuit. This scheme is the first memory scheme that achieves constant time access to rows, columns, diagonals, and N^1/2 subarrays of an N × N array using the minimum number of memory modules.