Title :
An optimal sorting algorithm on reconfigurable mesh
Author :
Jang, Ju-wook ; Prasanna, Viktor K.
Author_Institution :
Dept. of Electr. Eng.-Syst., Univ. of Southern California, Los Angeles, CA, USA
Abstract :
An optimal sorting algorithm on the reconfigurable mesh is proposed. The algorithm sorts n numbers in constant time using n×n processors. The best known previous result uses O(n×nlog2n) processors. The presented algorithm satisfies the AT2 lower bound of Ω(n2) for sorting n numbers in the word model of VLSI. Modification to the algorithm for area-time trade-off is shown, to achieve AT2 optimality over 1⩽T⩽√n. Previously, the bound was achieved over log n⩽T⩽√n
Keywords :
computational complexity; multiprocessor interconnection networks; parallel algorithms; sorting; AT2 lower bound; VLSI; area-time trade-off; constant time; optimal sorting algorithm; reconfigurable mesh; word model; Arithmetic; Computer architecture; Concurrent computing; Contracts; Sorting;
Conference_Titel :
Parallel Processing Symposium, 1992. Proceedings., Sixth International
Conference_Location :
Beverly Hills, CA
Print_ISBN :
0-8186-2672-0
DOI :
10.1109/IPPS.1992.223059
