Method and system for providing a hardware sort for a large number of items

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.

1. A system for sorting a number of 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 stages, each stage having first and second first-in-first-out buffers (FIFOs), the FIFOs in each stage storing twice as many of the items as the FIFOs in a previous stage of the plurality of stages; 
 at least one switch, each of the at least one switch coupled between two successive stages of the plurality of stages, each switch operable to merge and sort items stored in the pair of FIFOs in the previous stage based on the key to produce a sorted set of items, each of the at least one switch operable to provide successive sets of sorted items alternately to the first and second FIFOs in the next stage; and 
 a final switch coupled to a last stage of the plurality of stages, the final switch operable to merge and sort the items stored in the pair of FIFOs in the last stage to provide the number of items in order. 
 
   
   
     2. The system of  claim 1  further comprising:
 a distributor coupled to a first stage of the plurality of stages, the distributor providing sets of items alternately to the first and second FIFOs in the first stage. 
 
   
   
     3. The system of  claim 2  further comprising:
 an initial sorter coupled to the distributor, the initial sorter operable to sort the sets of items to be provided to the first stage. 
 
   
   
     4. The system of  claim 3  wherein the distributor is operable to provide sets of N items alternately to the first and second FIFOs in the first stage, and wherein each FIFO in an i th  stage of the plurality of stages is operable to store 2 (i−1) *N items. 
   
   
     5. The system of  claim 3  wherein the initial sorter is a hardware sorter. 
   
   
     6. The system of  claim 5  wherein the hardware sorter includes:
 a plurality of sort cells for sorting the sets of items to be provided to the first stage, 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, a first input, and an output, the first input of the each of the plurality of sort cells except a 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 if the corresponding item is not to be retained and provides the corresponding item over the output if the corresponding item is not retained. 
 
   
   
     7. The system of  claim 1  wherein the computer system further includes a display having a plurality of pixels and wherein the number of items include the number of fragments intersecting a pixel of the plurality of pixels. 
   
   
     8. The system of  claim 7  wherein each of the number of fragments include a label indicating a place in the number of fragments. 
   
   
     9. The system of  claim 8  wherein the label indicates that a fragment of the number of fragments is a next fragment in the number of fragments, a last fragment in the number of fragments, or a last fragment for the pixel. 
   
   
     10. The system of  claim 9  wherein the label indicates if the fragment is a last fragment of a portion of the plurality of fragments stored in a FIFO of the pair of FIFOs in a first stage of the plurality of stages. 
   
   
     11. A method for sorting a number of 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 the steps of:
 (a) providing sorted sets of items alternately to a first first-in-first-out buffer (FIFO) and a second FIFO of a pair of FIFOs in a stage of a plurality of stages, each of the plurality of stages having a pair of FIFOs, the pair of FIFOs in a stage of the plurality of stages storing twice as many of the items as the pair of FIFOs in a previous stage of the plurality of stages; 
 (b) merging and sorting the of items from the pair of FIFOs in the stage based on the key; 
 (c) repeating steps (a) through (b) through a last stage of the plurality of stages; and 
 (d) merging and sorting the number of items to provide the number of items from the last stage of the plurality of stages. 
 
   
   
     12. The method of  claim 11  further comprising the step of:
 (e) initially sorting sets of items prior to providing the sorted sets of items alternately to the first second FIFOs in the first stage of the plurality of stages. 
 
   
   
     13. The method of  claim 12  wherein sets of N items are alternately provided to the first and second FIFOs in the first stage of the plurality of stages, and wherein each FIFO in an i th  stage of the plurality of stages is operable to store 2 (i−1) *N items. 
   
   
     14. The method of  claim 12  wherein the initial sorting step (e) is performed by a hardware sorter. 
   
   
     15. The method of  claim 14  wherein the hardware sorter includes:
 a plurality of sort cells for sorting sets of items to be provided to the first stage, 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, a first input, and an output, the first input of the each of the plurality of sort cells except a 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 if the corresponding item is not to be retained and provides the corresponding item over the output if the corresponding item is not retained. 
 
   
   
     16. The method of  claim 11  wherein the computer system further includes a display having a plurality of pixels and wherein the number of items include the number of fragments intersecting a pixel of the plurality of pixels. 
   
   
     17. The method of  claim 16  wherein each of the number of fragments include a label indicating a place in the number of fragments. 
   
   
     18. The method of  claim 17  wherein the label indicates that a fragment of the number of fragments is a next fragment in the number of fragments, a last fragment in the number of fragments, or a last fragment for the pixel. 
   
   
     19. The method of  claim 18  wherein the label also indicates if the fragment is a last fragment of a portion of the plurality of fragments stored in a FIFO of the pair of FIFOs in a first stage of the plurality of stages.