Article

Arbitrary long digit integer sorter HW/SW co-design

Author:

Shun-Wen ChengAuthors Info & Claims

ASP-DAC '03: Proceedings of the 2003 Asia and South Pacific Design Automation Conference

Pages 538 - 543

https://doi.org/10.1145/1119772.1119884

Published: 21 January 2003 Publication History

Abstract

The coming of multimedia era and information security era indicates that must process longer digit integer data. Previous sort researches focus on pure performance of large amount of finite fixed digit/bit number. This paper discusses on effectively solving arbitrary long digit integer sorting problem by HW/SW co-design under the Area x Time² (AT²) price-performance constraint. The work proposes multi-level (two-level) sort architecture to attain the object: an accomplished fixed-digit (k-bit) hardware sorter implements the first or basic level sorting, software programmed radix 2^k sort implements the second or higher level sorting. By Super Radix Sorting HW/SW co-design and reuse techniques, the work makes fixed-digit HW sorters more flexible and useful.

References

[1]

M. Afghahi, "A 512 16-b Bit-serial Sorter Chip," IEEE J. Solid-State Circuits, vol. 26, pp. 1452--1457, Oct. 1991.

[2]

B. Ahn and J. M. Murray, "A Pipelined, Expandable VLSI Sorting Engine Implemented in CMOS Technology," in Proc. IEEE Int'l. Symp. on Circuits and Systems, 1989, pp. 134--137.

[3]

S. G. Akl, Parallel Sorting Algorithms. Reading, New York: Academic Press, 1985.

Digital Library

[4]

K. E. Batcher, "Sorting Networks and Their Applications," in Proc. AFIPS 1968 Spring Joint Computer Conference, pp. 307--314, Apr. 1968.

[5]

G. Baudet and D. Stevenson, "Optimal Sorting Algorithms for Parallel Computer," IEEE Trans. Computers, vol. 27, pp. 84--87, Jan. 1978.

Digital Library

[6]

R. Beigel and J. Gill, "Sorting n Objects with a k-sorter," IEEE Trans. Computers, vol. 39, pp. 714--716, May 1990.

Digital Library

[7]

G. Bilardi and F. P. Preparata, "A Minimum Area VLSI Network for O(log n) Time Sorting," IEEE Trans. Computers, vol. 34, pp. 336--343, May 1985.

Digital Library

[8]

T. C. Chen, Vincent Y. Lum, and C. Tung, "The Rebound Sorter: An Efficient Sort Engine for Large File," in IEEE Proc. 4th Int'l Conf. on Very Large Data Bases, pp. 312--318, Sep. 1978.

[9]

R. Cole and A. R. Seigel, "Optimal VLSI Circuits for Sorting," JACM, vol. 35, pp. 777--809, 1988.

Digital Library

[10]

Edward. H. Friend, "Sorting on Electronic Computer Systems," JACM, vol. 3, pp. 134--168, 1956.

Digital Library

[11]

C. A. R. Hoare, "Quicksort," Computing Journal, vol. 5, pp. 10--15, 1962.

[12]

M. Keating and P. Bricaud, Reuse Methodology Manual. Reading: Kluwer, 1998.

Digital Library

[13]

D. E. Knuth, The Art of Computer Programming, Vol 3: Sorting and Searching. Reading: Addison-Wesley, 1973.

[14]

J.-G. Lee and B.-G. Lee, "Realization of Large-scale Distributors Based on Batcher Sorters," IEEE Trans. Communications, vol. 47, pp. 1103--1110, July 1999.

[15]

T. Leighton, "Tight Bounds on The Complexity of Parallel Sorting," IEEE Trans. Computers, vol. 34, pp. 344--354, Apr. 1985.

Digital Library

[16]

G. S. Miranker, Luong Tang, and Chak-Kuen Wong, "A 'Zero-Time' VLSI Sorter," IBM J. Research & Development, vol. 27, pp. 140--148, Mar. 1983.

Digital Library

[17]

S. Olariu, M. C. Pinotti, and S. Q. Zheng, "How to Sort N Items Using a Sorting Network of Fixed I/O Size," IEEE Trans. Parallel and Distributed Sys., vol. 10, pp 487--499, May 1999.

Digital Library

[18]

B. Parhami and D.-M. Kwai, "Data-driven Control Scheme for Linear Arrays: Application to a Stable Insertion Sorter," IEEE Trans. Parallel and Distributed Sys., vol. 10, pp 23--28, Jan. 1999.

Digital Library

[19]

H. S. Stone, "Parallel Processing with the Perfect Shuffle," IEEE Trans. Computers, vol. 20, pp. 153--161, Feb. 1971.

Digital Library

[20]

C. D. Thompson, "Area-Time Complexity for VLSI," in Proc. 11th Annual ACM Symp. on Theory of Comp., pp. 81--88, Apr. 1979.

Digital Library

[21]

C. D. Thompson, "The VLSI Complexity of Sorting," IEEE Trans. Computers, vol. 32, pp. 1171--1184, Dec. 1983.

Digital Library

[22]

N. H. E. Weste and K. Eshraghian, Principle of CMOS VLSI Design, 2nd Ed., Reading: Addison-Wesley, 1993.

Digital Library

[23]

H. Yasuura, N. Takagi, and S. Yajima, "The Parallel Enumeration Sorting Scheme for VLSI," IEEE Trans. Computers, vol. 31, pp. 1192--1201, Dec. 1982.

Digital Library

[24]

S. Q. Zheng, S. Olariu, and M. C. Pinotti, "A Systolic Architecture for Sorting an Arbitrary Number of Elements," in Proc. 1997 3rd Int. Conf. Algorithms and Architectures for Parallel Processing, pp. 113--126, 1997.

Cited By

Ghosh SDasgupta SSaha Ray S(2019)A Comparison-free Hardware Sorting Engine2019 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI.2019.00110(586-591)Online publication date: Jul-2019
https://doi.org/10.1109/ISVLSI.2019.00110
Ghasemzadeh MNajafibisfar SAmini A(2018)Ultra Low-power, High-speed Digital Comparator2018 25th International Conference "Mixed Design of Integrated Circuits and System" (MIXDES)10.23919/MIXDES.2018.8436901(215-217)Online publication date: Jun-2018
https://doi.org/10.23919/MIXDES.2018.8436901
Frustaci FPerri SLanuzza MCorsonello P(2018)Energy-efficient single-clock-cycle binary comparatorInternational Journal of Circuit Theory and Applications10.1002/cta.72040:3(237-246)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1002/cta.720
Show More Cited By

Arbitrary long digit integer sorter HW/SW co-design
1. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis

Recommendations

HW/SW co-design for public-key cryptosystems on the 8051 micro-controller

It is a challenge to implement large word length public-key algorithms on embedded systems. Examples are smartcards, RF-ID tags and mobile terminals. This paper presents a HW/SW co-design solution for RSA and Elliptic Curve Cryptography (ECC) over GF(p) ...
Hw/Sw Co-Design technique for 2D fast fourier transform algorithm on Zynq SoC
Abstract
The Two-Dimensional Fast Fourier Transform (2D-FFT) algorithm is used for the study of many modern systems applied for security and biometrics. The adoption of this algorithm, which is a compute intensive task, is limited due to its ...
Highlights
- Underline the effect of the Hw/Sw co-design of the 2D-FFT algorithm for the reduction of the processing time and power consumption.
HW/SW partitioning and code generation of embedded control applications on a reconfigurable architecture platform
CODES '02: Proceedings of the tenth international symposium on Hardware/software codesign

This paper studies the use of a reconfigurable architecture platform for embedded control applications aimed at improving real time performance. The hw/sw codesign methodology from POLIS is used. It starts from high-level specifications, optimizes an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '03: Proceedings of the 2003 Asia and South Pacific Design Automation Conference

January 2003

865 pages

ISBN:0780376609

DOI:10.1145/1119772

General Chair:
Hiroto Yasuura

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IPSJ: Information Processing Society of Japan
IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEICE: Institute of Electronics, Information and Communication Engineers

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
152
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghosh SDasgupta SSaha Ray S(2019)A Comparison-free Hardware Sorting Engine2019 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI.2019.00110(586-591)Online publication date: Jul-2019
https://doi.org/10.1109/ISVLSI.2019.00110
Ghasemzadeh MNajafibisfar SAmini A(2018)Ultra Low-power, High-speed Digital Comparator2018 25th International Conference "Mixed Design of Integrated Circuits and System" (MIXDES)10.23919/MIXDES.2018.8436901(215-217)Online publication date: Jun-2018
https://doi.org/10.23919/MIXDES.2018.8436901
Frustaci FPerri SLanuzza MCorsonello P(2018)Energy-efficient single-clock-cycle binary comparatorInternational Journal of Circuit Theory and Applications10.1002/cta.72040:3(237-246)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1002/cta.720
Deb S(2012)A novel architecture for binary comparison using time division de-multiplexing technique2012 IEEE International Conference on Advanced Communication Control and Computing Technologies (ICACCCT)10.1109/ICACCCT.2012.6320826(478-482)Online publication date: Aug-2012
https://doi.org/10.1109/ICACCCT.2012.6320826
Deb SChaudhury S(2012)High-speed comparator architectures for fast binary comparison2012 Third International Conference on Emerging Applications of Information Technology10.1109/EAIT.2012.6408016(454-457)Online publication date: Nov-2012
https://doi.org/10.1109/EAIT.2012.6408016
Alaparthi SGulati KKhatri S(2009)Sorting binary numbers in hardware - A novel algorithm and its implementation2009 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.2009.5118240(2225-2228)Online publication date: May-2009
https://doi.org/10.1109/ISCAS.2009.5118240
Shun-Wen Cheng (2003)A high-speed magnitude comparator with small transistor count10th IEEE International Conference on Electronics, Circuits and Systems, 2003. ICECS 2003. Proceedings of the 200310.1109/ICECS.2003.1301720(1168-1171)Online publication date: 2003
https://doi.org/10.1109/ICECS.2003.1301720

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents