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

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.

What is claimed is:  
     
         1 . 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, 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.    
     
     
         2 . The system of  claim 1  wherein the comparator further provides a resultant, and wherein each of the plurality of sort cells further includes a controller coupled with the comparator and the storage, the controller for determining whether the corresponding item is to be retained based on the resultant and for allowing each sort cell further accept the new item or the item corresponding to the previous sort cell if the corresponding item is not to be retained.  
     
     
         3 . The system of  claim 2  wherein the output of each of the plurality of sort cells provides a signal to the next cell indicating that the corresponding item is to be accepted by the next cell if the corresponding item is not to be retained.  
     
     
         4 . The system of  claim 3  wherein the controller further determines that the corresponding item is to be retained when the comparator indicates the corresponding value is not greater than the new value.  
     
     
         5 . The system of  claim 4  wherein the controller determines that the new item is to be accepted when the corresponding value is greater than the new value and the previous cell has not provided a signal indicating that the item corresponding to the previous cell is to be accepted by the sort cell.  
     
     
         6 . The system of  claim 5  wherein the controller determines that the item corresponding to the previous cell is to be accepted when the corresponding value is greater than the new value and the previous cell has provided a signal indicating that the item corresponding to the previous cell is to be accepted by the sort cell.  
     
     
         7 . The system of  claim 6  wherein each of the plurality of items further has an identification associated with it and wherein the controller further allows the plurality of sort cells to sort the portion of the plurality of items having the same identification.  
     
     
         8 . The system of  claim 7  wherein each of the plurality of items has data associated with it and wherein each of the plurality of sort cells further has an associated data storage for storing the data associated with the corresponding item, the sort cell providing the data associated with the corresponding item over the output if the corresponding item is not to be retained, and the sort cell storing data associated with the new item or data associated with the item corresponding to the previous cell in the data storage if the corresponding item is not to be retained.  
     
     
         9 . The system of  claim 8  wherein the computer system is a computer graphics system including a display, wherein each of the plurality of items is a fragment, the key is a z value, and the data associated with the corresponding item includes color and blending data.  
     
     
         10 . The system of  claim 7  wherein each of the plurality of items has data associated with it, and wherein the system further comprises: 
 data storage for storing the data associated with the corresponding item for each of the plurality of sort cells.  
 
     
     
         11 . The system of  claim 10  wherein the computer system is a computer graphics system including a display, wherein each of the plurality of items is a fragment, the key is a z value, and the data associated with the corresponding item includes color and blending data.  
     
     
         12 . The system of  claim 7  wherein the key storage is located remote from each sort cell.  
     
     
         13 . The system of  claim 1  wherein the comparator further provides a resultant, and wherein the system further includes: 
 a controller coupled with the plurality of sort cells, the controller for determining whether the corresponding item for each of the plurality of sort cells is to be retained based on the resultant of each of the plurality of sort cells, the controller further instructing each sort cell to accept the new item or the item corresponding to the previous sort cell if the corresponding item is not retained.  
 
     
     
         14 . The system of  claim 13  wherein the controller further provides a signal to each of the plurality of sort cells indicating that the item corresponding to the previous sort cell is to be accepted if the corresponding item is not to be retained.  
     
     
         15 . The system of  claim 14  wherein the controller determines whether the corresponding item is to be retained when the comparator indicates the corresponding value is not greater than the new value.  
     
     
         16 . The system of  claim 15  wherein the controller determines that the new item is to be accepted when the corresponding value is greater than the new value and the previous cell has not provided a signal indicating that the item corresponding to the previous cell is to be accepted by the sort cell.  
     
     
         17 . The system of  claim 16  wherein the controller determines that the item corresponding to the previous cell is to be accepted when the corresponding value is greater than the new value and the previous cell has provided a signal indicating that the item corresponding to the previous cell is to be accepted by the sort cell.  
     
     
         18 . The system of  claim 17  wherein each of the plurality of items further has an identification associated with it and wherein the controller further allows the plurality of sort cells to sort the portion of the plurality of items having the same identification.  
     
     
         19 . The system of  claim 18  wherein each of the plurality of items further has an identification associated with it; and wherein the controller further allows the plurality of sort cells to sort the portion of the plurality of items having the same identification.  
     
     
         20 . The system of  claim 19  wherein each of the plurality of items has data associated with it and wherein each of the plurality of sort cells further includes: 
 data storage for storing the data associated with the corresponding item, the sort cell providing the data associated with the corresponding item over the output if the corresponding item is not to be retained, and the sort cell storing data associated with the new item or data associated with the item corresponding to the previous cell in the data storage if the corresponding item is not to be retained.  
 
     
     
         21 . The system of  claim 20  wherein the computer system is a computer graphics system including a display, wherein each of the plurality of items is a fragment, the key is a z value, and the data associated with the corresponding item includes color and blending data.  
     
     
         22 . The system of  claim 19  wherein each of the plurality of items has data associated with it and wherein the system further comprises: 
 data storage for storing the data associated with the corresponding item for each of the plurality of sort cells.  
 
     
     
         23 . The system of  claim 22  wherein the computer system is a computer graphics system including a display, wherein each of the plurality of items is a fragment, the key is a z value, and the data associated with the corresponding item includes color and blending data.  
     
     
         24 . The system of  claim 23  wherein the data storage is located remote from each sort cell.  
     
     
         25 . A method 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 cells, 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 the previous sort cell if the at least one corresponding item is not retained;    (e) if the at least one corresponding item is not to be retained, accepting the at least one new item or the item corresponding to the previous sort cell.    
     
     
         26 . The method of  claim 25  wherein the steps (a) through (e) are performed in one clock cycle.  
     
     
         27 . The method of  claim 26  wherein the at least one corresponding item further includes data associated with it, and wherein the method further comprises the step of: 
 (f) storing the data associated with the at least one corresponding item in a data storage, the data being retained if the at least one corresponding item is to be retained and being provided over the output if the at least one corresponding item is not to be retained.  
 
     
     
         28 . The method of  claim 27  wherein the computer system is a computer graphics system and the data associated with the at least one corresponding item further includes color and blending data for a particular fragment for a particular pixel on the display.  
     
     
         29 . The method of  claim 28  further comprising the steps of: 
 (g) providing an identification for each of the plurality of items; and  
 (h) sorting the portion of the plurality of items having the same identification.