article

Free access

Optimal VLSI circuits for sorting

Authors:

Richard Cole,

Alan SiegelAuthors Info & Claims

Journal of the ACM (JACM), Volume 35, Issue 4

Pages 777 - 809

https://doi.org/10.1145/48014.48017

Published: 01 October 1988 Publication History

PDF eReader

Abstract

This work describes a large number of constructions for sorting N integers in the range [0, M - 1], for N ≤ M ≤ N², for the standard VLSI bit model. Among other results, we attain:

VLSI sorter constructions that are within a constant factor of optimal size, for all M and almost all running times T.

a fundamentally new merging network for sorting numbers in a bit model.

new organizational approaches for optimal tuning of merging networks and the proper management of data flow.

References

[1]

BILARDI, G. The area time complexity of sorting. Ph.D. Dissertation, Comput. Sci. Dept., Univ. of illinois at Urbana-Champaign, Urbana, ill., i 984.

Crossref

Google Scholar

[2]

BILARDI, G., AND PREPARATA, F. An architecture for bitonic sorting with optimal VLSI performance. IEEE Trans. Comput. C-33, 7 (July 1984), 646-651.

Google Scholar

[3]

BILARDI, G., AND PREPARATA, F. The influence of key length on the area-time complexity of sorting. In Proceedings of the 12th International Colloquium on Automata, Languages, and Programming. Springer-Verlag, New York, 1985, pp. 53-62.

Crossref

Google Scholar

[4]

BiLAKDI, ~J., AND PREPARATA, F. 1 li;~l~ll;4tlCIIl tct;nlulquc~ lo} ~tlcu-tilztc 1 1-uuuxlua.4 .. :,k ^__1: cations to sorting. In Proceedings of the 19th Annual Conference on Information Sciences and Systems. Johns Hopkins Univ., Baltimore, Md., 1985, pp. 7-9.

Google Scholar

[5]

BILARDI G., AND PREPARATA, F. The VLSI optimality of hte aks sortinmg network INF.Process Lett. 20 (1985), 55-59.

Crossref

Google Scholar

[6]

B}LARDZ, G., AND PREPARATA, F. A minimum area VLSI network for O(logn) sorting. Special Idssue on sorting. IEEE Trans. Comput.C-34, 4(Apr., 1985), 336-343.

Crossref

Google Scholar

[7]

BILARDI, G., AND PREPARATA, F. Area-time lower bound techniques with applications to sorting. Algorithmica 1, I (1986) 65-91.

Crossref

Google Scholar

[8]

CARTER, L. Floyd, R., Gill, J., Markowsky, G., AND WEGMAN, M. Exact and approximate membership testers. In Proceedings of the lOth Annual ACM Symposium on the Theory of Computing (San Diego, Calif., May 1-3). ACM, New York, 1978, pp. 59-65.

Crossref

Google Scholar

[9]

Cony R., AND ~Ir:C.FI., Ao Optima! VLS! sorters~ Courant Institute Tech. Rep. No. 172. Courant Institute of Mathematics, New York Univ., New York, 1985.

Google Scholar

[10]

COLE, R., AND SIEGEL, A. On information flow and sorting: New upper and lower bounds for VLSI circuits. In Proceedings of the 26th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1985, pp. 208-221.

Google Scholar

[11]

COLE, R., AND SIEGEL, m. Lower bounds on communication complexity in VLSI. Courant Institute Tech. Rep. No. 192. Courant Institute of Mathematics, New York Univ., New York, 1985.

Google Scholar

[12]

DURIS, P., SYKORA, O., THOMPSON, C. D., AND VRTO, I. Tight chip area lower bounds for discrete Fourier and Walsh-Hadamard transformations. Inf. Proc. Lett. 21 (Nov. 1985), 245-247.

Google Scholar

[13]

HOCHSCHILD, P.M. Ph.D. Dissertation. Computer Science Department, Stanford Univ., Stanford, Calif., 1985.

Google Scholar

[14]

HOCHSCHILD, P. M., MAYR, E. W., AND SIEGEL, A.R. Techniques for solving graph problems in parallel. In Proceedings of the 23rd Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1983, pp. 351-359.

Google Scholar

[15]

LEXGHTON, F.T. Tight bounds on the complexity of parallel sorting. Special Issue on Sorting, IEEE Trans. Comput. C-34, 4 (Apr. 1985), 344-354.

Crossref

Google Scholar

[16]

LIN, F.-C., AND WU, I-CHEN "Lower bounds for VLSI sorting," manuscript.

Google Scholar

[17]

LouI, M.C. The complexity of sorting on distributed systems. Inf. Control 60 (Jan/Feb/Mar 1984), 70-85.

Crossref

Google Scholar

[18]

S}WG~L, A.R. Tight area bounds and provably good A T2 bounds for sorting circuits, Tech. Rep. 122. Computer Science Department, New York Univ., New York, June 1984.

Google Scholar

[19]

SIEGEL, A.R. "VLSI sorters: Techniques for comprehensive AT2 lower bounds and problems of minimal storage. Extended abstract.

Google Scholar

[20]

SEIGEL, A.R. Minimal storage sorting circuits. Special Issue on Sorting. IEEE Trans. Comput. C-34, 4 (Apr. 1985), 355-361.

Google Scholar

[21]

Seigl, A.R, Minimal storage sorting circuits special IOssue on sorting.IEEE Trans. Comput. ACM Symposium on the Theory of Computing (Berkeley, Calif., May 28-30). ACM, New York, 1986, 448-459.

Crossref

Google Scholar

[22]

THOMPSON, C. D. Area-time complexity for VLSI. In Proceedings of the 1 lth Annual ACM Symposium on the Theory of Computing (Atlanta, Ga., Apr. 30-May 2). ACM, New York, 1979, pp. 81-88.

Crossref

Google Scholar

[23]

THOMPSON, C.D. A complexity theory for VLSI. Ph.D. dissertation. Computer Science Department. Carnegie-Mellon Univ., Pittsburgh, Pa., 1980.

Crossref

Google Scholar

[24]

THOMPSON, C.D. The VLSI complexity of sorting. IEEE Trans. Comput. C-32, 12 (Dec. 1983), 1171-1183.

Google Scholar

[25]

ULLMAN, J.D. ComputationalAspects of VLSI. Computer Science Press, Rockville, Md., 1984.

Crossref

Google Scholar

[26]

YAO, A.C. The entropic limitations on VLSI computations. In Proceedings of the 13th Annual ACM Symposium on the Theory of Computing (Milwaukee, Wis., May 11-13). ACM, New York, 1981, pp. 308-311.

Crossref

Google Scholar

Cited By

View all

Wu YChang CHung JYang C(2017)A 135-mW Fully Integrated Data Processor for Next-Generation SequencingIEEE Transactions on Biomedical Circuits and Systems10.1109/TBCAS.2017.276010911:6(1216-1225)Online publication date: Dec-2017
https://doi.org/10.1109/TBCAS.2017.2760109
Grover P(2015)Information Friction and Its Implications on Minimum Energy Required for CommunicationIEEE Transactions on Information Theory10.1109/TIT.2014.236577761:2(895-907)Online publication date: 16-Jan-2015
https://dl.acm.org/doi/10.1109/TIT.2014.2365777
Bilardi GFantozzi C(2011)New area-time lower bounds for the multidimensional DFTProceedings of the Seventeenth Computing on The Australasian Theory Symposium - Volume 11910.5555/2483191.2483205(111-120)Online publication date: 17-Jan-2011
https://dl.acm.org/doi/10.5555/2483191.2483205
Show More Cited By

Index Terms

Optimal VLSI circuits for sorting

Recommendations

A New Class of Optimal Bounded-Degree VLSI Sorting Networks

Minimum-area very large scale integration (VLSI) networks have been proposed for sorting N elements in O(log,N) time. However, most of such networks proposed have complex structures, and no explicit network construction is given in others. New designs ...
Time-Space Optimal Parallel Merging and Sorting

The authors present a parallel merging algorithm that, on an exclusive-read exclusive-write (EREW) parallel random-access machine (PRAM) with k processors merges two sorted lists of total length n in O(n/k+log n) time and constant extra space per ...
Optimal time-space trade-offs for non-comparison-based sorting
SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

We study the problem of sorting n integers of w bits on a unit-cost RAM with word size w, and in particular consider the time-space trade-off (product of time and space in bits) for this problem. For comparison-based algorithms, the time-space ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 35, Issue 4

Oct. 1988

242 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/48014

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1988

Published in JACM Volume 35, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
756
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)12

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wu YChang CHung JYang C(2017)A 135-mW Fully Integrated Data Processor for Next-Generation SequencingIEEE Transactions on Biomedical Circuits and Systems10.1109/TBCAS.2017.276010911:6(1216-1225)Online publication date: Dec-2017
https://doi.org/10.1109/TBCAS.2017.2760109
Grover P(2015)Information Friction and Its Implications on Minimum Energy Required for CommunicationIEEE Transactions on Information Theory10.1109/TIT.2014.236577761:2(895-907)Online publication date: 16-Jan-2015
https://dl.acm.org/doi/10.1109/TIT.2014.2365777
Bilardi GFantozzi C(2011)New area-time lower bounds for the multidimensional DFTProceedings of the Seventeenth Computing on The Australasian Theory Symposium - Volume 11910.5555/2483191.2483205(111-120)Online publication date: 17-Jan-2011
https://dl.acm.org/doi/10.5555/2483191.2483205
Bilardi GFantozzi C(2011)New area-time lower bounds for the multidimensional DFTProceedings of the Seventeenth Computing: The Australasian Theory Symposium - Volume 11910.5555/2461196.2461210(111-120)Online publication date: 17-Jan-2011
https://dl.acm.org/doi/10.5555/2461196.2461210
Grover PWoyach KSahai A(2011)Towards a Communication-Theoretic Understanding of System-Level Power ConsumptionIEEE Journal on Selected Areas in Communications10.1109/JSAC.2011.11092229:8(1744-1755)Online publication date: Sep-2011
https://doi.org/10.1109/JSAC.2011.110922
Power MTosi SConway T(2008)Reduced Complexity Path Selection Networks for M-Algorithm Read Channel DetectorsIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2008.92011055:9(2924-2933)Online publication date: Oct-2008
https://doi.org/10.1109/TCSI.2008.920110
Cheng SYasuura H(2003)Arbitrary long digit integer sorter HW/SW co-designProceedings of the 2003 Asia and South Pacific Design Automation Conference10.1145/1119772.1119884(538-543)Online publication date: 21-Jan-2003
https://dl.acm.org/doi/10.1145/1119772.1119884
Colavita ACicuttin AFratnik FCapello G(2003)SORTCHIP: A VLSI implementation of a hardware algorithm for continuous data sortingIEEE Journal of Solid-State Circuits10.1109/JSSC.2003.81198238:6(1076-1079)Online publication date: Jun-2003
https://doi.org/10.1109/JSSC.2003.811982
Shun-Wen Cheng (2003)Arbitrary long digit integer sorter HW/SW co-designProceedings of the ASP-DAC Asia and South Pacific Design Automation Conference, 2003.10.1109/ASPDAC.2003.1195075(538-543)Online publication date: 2003
https://doi.org/10.1109/ASPDAC.2003.1195075
Gu Lin Bingxue Shi (1999)A expansible current-mode sorting integrated circuit for pattern recognitionIJCNN'99. International Joint Conference on Neural Networks. Proceedings (Cat. No.99CH36339)10.1109/IJCNN.1999.836150(3123-3127)Online publication date: 1999
https://doi.org/10.1109/IJCNN.1999.836150
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

A New Class of Optimal Bounded-Degree VLSI Sorting Networks

Time-Space Optimal Parallel Merging and Sorting

Optimal time-space trade-offs for non-comparison-based sorting

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations