Latin Squares for Parallel Array Access

Kichul Kim, Viktor K. Prasanna

Research output: Contribution to journalArticlepeer-review

49 Scopus citations


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.

Original languageEnglish
Pages (from-to)361-370
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number4
StatePublished - Apr 1993


  • Conflict free access
  • latin squares
  • memory systems
  • parallel array access
  • parallel memories
  • routing
  • shared memory systems
  • skewing functions


Dive into the research topics of 'Latin Squares for Parallel Array Access'. Together they form a unique fingerprint.

Cite this