Access and Alignment of Data in an Array Processor
Duncan H. Lawrie · IEEE Transactions on Computers · 1975
This paper discusses the design of a primary memory system for an array processor which allows parallel, conflict-free access to various slices of data (e.g., rows, columns, diagonals, etc.), and subsequent alignment of these data for processing. Memory access requirements for an array processor are discussed in general terms and a set of common requirements are defined. The ability to meet these requirements is shown to depend on the number of independent memory units and on the mapping of the data in these memories. Next, the need to align these data for processing is demonstrated and various alignment requirements are defined. Hardware which can perform this alignment function is discussed, e.g., permutation, indexing, switching or sorting networks, and a network (the omega network) based on Stone's shuffle-exchange operation [1] is presented. Construction of this network is described and many of its useful properties are proven. Finally, as an example of these ideas, an array processor is shown which allows conflict-free access and alignment of rows, columns, diagonals, backward diagonals, and square blocks in row or column major order, as well as certain other special operations.
Cited by 1,120 works. doi:10.1109/t-c.1975.224157
Authors
References
- Sorting networks and their applications
- Parallel Processing with the Perfect Shuffle
- Mathematical Theory of Connecting Networks and Telephone Traffic
- An Adaptation of the Fast Fourier Transform for Parallel Processing
- A Permutation Network
- ILLIAC IV Software and Application Programming
- Parallelism exposure and exploitation in programs
- The Organization and Use of Parallel Memories
- On a Class of Rearrangeable Switching Networks Part I: Control Algorithm
- Cellular Interconnection Arrays