Perfect Latin squares and parallel array access.

Kichul Kim, V. K.Prasanna Kumar

Research output: Contribution to journalConference articlepeer-review

24 Scopus citations


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 N1/2 subarrays of an N × N array using the minimum number of memory modules.

Original languageEnglish
Pages (from-to)372-379
Number of pages8
JournalConference Proceedings - Annual Symposium on Computer Architecture
Issue number16
StatePublished - 1989
Event16th Annual International Symposium on Computer Architecture - Jerusalem, Israel
Duration: 28 May 19891 Jun 1989


Dive into the research topics of 'Perfect Latin squares and parallel array access.'. Together they form a unique fingerprint.

Cite this