Perfect Latin Squares And Parallel Array Access
- 24 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636897,p. 372-379
- https://doi.org/10.1109/isca.1989.714575
Abstract
A new nonlinear skewing scheme is proposed for parallel array access. We introduce a new Latin square(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 construction method for perfect Latin squares are presented. The resulting skewing scheme provides conflict free access to various subsets of an N x 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/ sup 1/2/ x N/sup 1/2/ subarrays of an N x N array using the minimum number of memory modules.Keywords
This publication has 17 references indexed in Scilit:
- Scrambled storage for parallel memory systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Partitioning: An Essential Step in Mapping Algorithms Into Systolic Array ProcessorsComputer, 1987
- An Efficient Memory System for Image ProcessingIEEE Transactions on Computers, 1986
- The Structure of Periodic Storage Schemes for Parallel MemoriesIEEE Transactions on Computers, 1985
- The Prime Memory System for Array AccessIEEE Transactions on Computers, 1982
- Conflict-free access of arrays — a counter exampleInformation Processing Letters, 1980
- Theoretical Limitations on the Efficient Use of Parallel MemoriesIEEE Transactions on Computers, 1978
- Memory Systems for Image ProcessingIEEE Transactions on Computers, 1978
- Access and Alignment of Data in an Array ProcessorIEEE Transactions on Computers, 1975
- ILLIAC IV Software and Application ProgrammingIEEE Transactions on Computers, 1968