Method and system for providing a hardware sort for a large...

Details Method and system for providing a hardware sort for a large... Method and system for providing a hardware sort for a large...

2008-04-22

2008-04-22

Le, Uyen (Department: 2163)

Data processing: database and file management or data structures

Database design

Data structure types

C712S014000, C716S030000

Reexamination Certificate

active

07363304

ABSTRACT:
A method and system for sorting a number of items in a computer system. The sort is based on a plurality of values of a key. Each item has a value of the plurality of values. The method and system include providing plurality of stages, providing at least one switch coupled between the plurality of stages, and providing a final switch coupled with a last stage. Each of the plurality of stages has a pair of first-in-first-out buffers (FIFOs) that store twice as many of the items as the pair of FIFOs in a previous stage. Each switch is for merging and sorting a first portion of the number of items from the pair of FIFOs in the previous stage based on the key and for providing the first portion of the number plurality of items to a first FIFO of the pair of FIFOs of the stage in order. Each switch is also for merging and sorting a second portion of the number of items the pair of FIFOs in the previous stage based on the key and providing the second portion of the number plurality of items to a second FIFO of the pair of FIFOs of the stage in order. The last switch is for merging and sorting a third portion of the number of items to provide the number of items in order.

REFERENCES:
patent: 4030077 (1977-06-01), Florence et al.
patent: 4499555 (1985-02-01), Huang
patent: 5125074 (1992-06-01), Labeaute et al.
patent: 5621908 (1997-04-01), Akaboshi et al.
patent: 6035296 (2000-03-01), Fushimi
G. Liu et al., Parallel Merge Module for Combining Sorted Lists, IEEE Proceedings, May 1989, No. 3, part E, pp. 161-165.
G. Miranker et al., A “Zero-Time” VLSI Sorter, IBM Journal of Research and Development, vol. 27, No. 2, Mar. 1983, pp. 140-148.
V. Meyer et al., A Data-reducing Transform Codec with Variable Output Rate and Activity-controlled Channel Adaptation, Frequenz 44, No. 7-8, 1990 pp. 209-216.
T. Eldos et al.,A Functional Memory Based Architecture for Running Sorting,Fifth International Symposium on Signal Processing and Its Applications, ISSPA 1999, pp. 705-708.
S. Kamiya et al., A Hardware Pipeline Algorithm for Relational Database Operation and Its Implementation Using Dedicated Hardware, IEEE 1985, pp. 250-257.

Affiliated with

Also associated with

Rating

Method and system for providing a hardware sort for a large... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for providing a hardware sort for a large..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for providing a hardware sort for a large... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2783284