A Minimum Area VLSI Architecture for O(logn) Time Sorting
Gianfranco Bilardi, F. P. Preparata · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1983
trade-off, combination sorting, bitonic merging, cube-connected-cycles, mesh, orthogonal trees, optimal algorithms, parallel computation j 19.A B S T R A C T (C o n tin u e on reverse if necessary an d id en tify by block n u m b e r) A generalization of a known class of parallel sorting algorithms is presented, together with a new architecture to execute them.A VLSI implementation is also proposed, and its area-time performance is discussed.It is shown that an algorithm in the class is jexecutable in 0(logn) time by a chip occupying 0(n2) area.The design is a typical instance of a "hybrid architecture", resulting from the combination of well-known VLSI arrays as the orthogonal-trees and the cube-connected-cycles; it is also the first known to meet the AT = ft(n log n) lower bound for sorters of n words of length (H-e)logn(e > 0), and working in minimum 0(logn) time.