Radix sort algorithm for graphics processing units

Data processing: database and file management or data structures – Database design – Data structure types

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C707S793000

Reexamination Certificate

active

07624107

ABSTRACT:
One embodiment of the present invention sets forth a technique for efficiently performing a radix sort operation on a graphics processing unit (GPU). The radix sort operation is conducted on an input list of data using one or more passes of a series of three processing phases. In each processing phase, thread groups are each associated with one segment of input data. In the first phase, occurrences of each radix symbol are counted and stored in a list of counters. In the second phase, the list of counters is processed by a parallel prefix sum operation to generate a list of offsets. In the third phase, the list of offsets is used to perform re-ordering on the list of data, according to the current radix symbol. To maintain sort stability, the one or more passes proceed from least significant data to most significant data in the sort key.

REFERENCES:
patent: 5434995 (1995-07-01), Oberlin et al.
patent: 5721921 (1998-02-01), Kessler et al.
patent: 5924091 (1999-07-01), Burkhard
patent: 5928351 (1999-07-01), Horie et al.
patent: 6085303 (2000-07-01), Thorson et al.
patent: 6216174 (2001-04-01), Scott et al.
patent: 6519593 (2003-02-01), Matias et al.
patent: 6897871 (2005-05-01), Morein et al.
patent: 7424467 (2008-09-01), Fontoura et al.
patent: 2005/0165838 (2005-07-01), Fontoura et al.
patent: 2007/0106876 (2007-05-01), Goswami
patent: 2007/0271268 (2007-11-01), Fontoura et al.
patent: 2008/0316214 (2008-12-01), Peeper
Eggers, et al. “Simultaneous Multithreading: A Platform for Next-Generation Processors”, IEEE Micro. Sep./Oct. 1997 (vol. 17, No. 5) pp. 12-19.
Johnson, et al. “A Distributed Hardware Mechanism for Process Synchronization on Shared-Bus Multiprocessors,”1994. IEE Computer Society; ICPP '94. pp. 268-275.
Eggers, et al., “Simultaneous Multithreading: A Platform for Next-Generation Processors,”IEEE Micro, vol. 17, No. 5, pp. 12-19, Sep./Oct. 1997.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Radix sort algorithm for graphics processing units does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Radix sort algorithm for graphics processing units, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Radix sort algorithm for graphics processing units will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-4136330

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.