Design of an Expandable VLSI Rebound Sorter


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 2, No. 3, pp. 433-442, Apr. 1995
10.3745/KIPSTE.1995.2.3.433,   PDF Download:

Abstract

This paper presents an improved VLSI implementation of a parallel sorter to achieve O(N) time complexity. Many fast VLSI sort algorithms have been proposed for sorting N elements in O(log N) time. However, most such algorithms proposed have complex network structure without considering data input and output time. They are also very difficult to expand or to use in real applications. After analyzing the chip area and time complexity of several parallel sort algorithms with overlapping data input and output time, the most effective algorithm, the rebound sort algorithm, is implemented in VLSI with some improvements. To achieve O(N) time complexity, an improved rebound sorter is able to sort 8 16-bits records on a chip. And it is possible to sort more than 8 records by connecting chips in a chain vertically.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
Y. J. Heon and A. B. Chul, "Design of an Expandable VLSI Rebound Sorter," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 2, no. 3, pp. 433-442, 1995. DOI: 10.3745/KIPSTE.1995.2.3.433.

[ACM Style]
Yun Ji Heon and Ahn Byoung Chul. 1995. Design of an Expandable VLSI Rebound Sorter. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 2, 3, (1995), 433-442. DOI: 10.3745/KIPSTE.1995.2.3.433.