IEEE Transactions on Computers · 1982 · 63 citations · 12 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureInterconnection NetworksParallel AlgorithmsInterconnect DesignParallel SortingSorting AlgorithmsArray DesignParallel ProcessingParallel Sort AlgorithmsParallel Sorting AlgorithmsVlsi Implementation
We propose a new parallel sorting scheme, called the parallel enumeration sorting scheme, which is suitable for VLSI implementation. This scheme can be introduced to conventional computer systems without changing their architecture. In this scheme, sorting is divided into two stages, the ordering process and the rearranging one. The latter can be efficiently performed by central processing units or intelligent memory devices. For implementations of the ordering process by VLSI technology, we design a new hardware algorithm of parallel enumeration sorting circuits whose processing time is linearly proportional to the number of data for sorting. Data are serially transmitted between the sorting circuit and memory devices and the total communication between them is minimized. The basic structure used in the algorithm is called a bus connected cellular array structure with pipeline and parallel processing. The circuit consists of a linear array of one type of simple cell and two buses connecting all cells for efficient global communications in the circuit. The sorting circuit is simple, regular and small enough for realization by today's VLSI technology. We discuss several applications of the sorting circuit and evaluate its performance.
12
Sorting networks and their applications
Kenneth E. Batcher · 1968 · 2.4K citations
Sorting on a mesh-connected parallel computer
Clark D. Thompson, H. T. Kung · Communications of the ACM · 1977 · 476 citations · Full text
Bitonic Sort on a Mesh-Connected Parallel Computer
Nassimi, Sahni · IEEE Transactions on Computers · 1979 · 255 citations
The Design of Special-Purpose VLSI Chips
Kung · Computer · 1980 · 231 citations
Engineering, Computer Engineering, Electrical Engineering +16
Preparata · IEEE Transactions on Computers · 1978 · 160 citations · Full text