US 6,556,993 B2Granted

Method and system for providing a hardware sort in a graphics system

AssigneeBroadcom Corporation

InventorMichael C. Lewis

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method for providing a sort in a computer system is disclosed. The sort is based on a plurality of values of a key. Each of the plurality of items has an associated value of the plurality of values. The method and system include providing a new item of the plurality of items to a plurality of sort cells. The new item includes a new value of the plurality of values. The plurality of sort cells is for sorting the plurality of items. Each sort cell is for sorting a corresponding item of the plurality of items. The corresponding item has a corresponding value of the plurality of values. The method and system further include comparing the new value to the corresponding value for each of the plurality of sort cells to determine whether to retain the corresponding item. Each of the plurality of sort cells retains the corresponding item if the corresponding item is to be retained. For each of the plurality of sort cells, the method and system determine whether to accept the new item or an item corresponding to the previous sort cell if the corresponding item is not to be retained. If the corresponding item is not to be retained, the method and system allow a sort cell to accept the new item or the item corresponding to the previous sort cell.

Claims30

Dependent claims

A system for sorting items in a computer system, the sort being based on a plurality of values of a key, each item having a value of the plurality of values, the system comprising:

a plurality of sort cells for sorting at least a portion of the plurality of items, the plurality of sort cells including a first sort cell, each sort cell of the plurality of sort cells being a hardware sort cell, each sort cell for sorting a corresponding item, the corresponding item having a corresponding value, each sort cell further having an associated key storage for storing the corresponding value, a comparator for comparing the corresponding value to a new value associated with a new item and an output, wherein each of the plurality of sort cells except the first sort cell further includes a first input, the first input of the each of the plurality of sort cells except the first sort cell being coupled with the output of a previous sort cell;
and
a second input coupled with each of the plurality of sort cells, the second input for providing the new item to the plurality of sort cells;
such that each of the plurality of sort cells compares the new value to the corresponding value to determine whether to retain the corresponding item and retains the corresponding item if it is determined that the corresponding item is to be retained;
and
such that each of the plurality of sort cells accepts either the new item or an item corresponding to the previous sort cell from the output of the previous sort cell if the corresponding item is not to be retained and provides the corresponding item over the output if the corresponding item is not retained.

3 more elements

A method for sorting a plurality of items in a computer system, the sort being based on a plurality of values of a key, each of the plurality of items having an associated value of the plurality of values, the method comprising the steps of:

(a) providing at least one new item of the plurality of items to a plurality of sort cell, each of the plurality of sort cells being a hardware sort cell, the at least one new item including at least one new value of the plurality of values, the plurality of sort cells for sorting the plurality of items, each sort cell for sorting at least one corresponding item of the plurality of items, the at least one corresponding item having at least one corresponding value of the plurality of values;
(b) for each of the plurality of sort cells, comparing the at least one new value to the at least one corresponding value to determine whether to retain the at least one corresponding item;
(c) for each of the plurality of sort cells, retaining the at least one corresponding item if the at least one corresponding item is to be retained;
(d) for each of the plurality of sort cells, determining whether to accept the at least one new item or at least one item corresponding to a previous sort cell if the at least one corresponding item is not retained;
(e) if the at least one item corresponding item is not to be retained, accepting the at least one new item or the item corresponding to the previous sort cell.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/003,784Filed 15 Nov 2001 · continuation
Priority: 30 May 2000
Published: US 2002/0040362 A14 Apr 2002
Granted: 29 Apr 2003
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 7/24
Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc: sorting, i.e. extracting data from one or…
Y10S 707/99937
Database or file accessing: sorting
G06F
Computing and data processing
Y10S
Technical subjects covered by former uspc cross-reference art collections [xracs] and digests