Apparatus and method for performing a stable and short latency sorting operation

Abstract

Apparatus and method for stable and short latency sorting. For example, one embodiment of a processor comprises: an input circuit to receive a set of N input values to be sorted into a sorted order; comparison circuitry to compare each input value with all other input values in parallel to generate at least N*(N−1)/2 comparison result values; matrix generation circuitry and/or logic to generate a result matrix having a row associated with each input value, a plurality of bits in each row comprising comparison result values indicating results of comparisons with other input values, wherein a first region of the result matrix is to store a first set of bits comprising the N*(N−1)/2 comparison result values and a second region of the result matrix, opposite the first region, is to store a second set of bits comprising an inverse of the N*(N−1)/2 comparison result values; a parallel adder circuit to perform parallel additions of the bits in each row to generate N unique result values; and sorting circuitry to index into the N unique result values to return the sorted order.

What is claimed is: 
     
       1. A processor comprising:
 an input circuit to receive a set of N input values to be sorted into a sorted order, the set of N input values are obtained with in a graphics pipeline stage; 
 comparison circuitry to compare each input value with all other input values in parallel to generate at least N*(N−1)/2 comparison result values; 
 matrix generation circuitry and/or logic to generate a result matrix having a row associated with each input value, a plurality of bits in each row comprising comparison result values indicating results of comparisons with other input values, wherein a first region of the result matrix is to store a first set of bits comprising the N*(N−1)/2 comparison result values and a second region of the result matrix, opposite the first region, is to store a second set of bits comprising an inverse of the N*(N−1)/2 comparison result values; 
 a parallel adder circuit to perform parallel additions of the bits in each row to generate N unique result values; and 
 sorting circuitry to index into the N unique result values to return the sorted order to the graphics pipeline stage. 
 
     
     
       2. The processor of  claim 1  wherein the comparison circuitry comprises N*(N−1)/2 comparators to perform N*(N−1)/2 parallel comparisons to generate the at least N*(N−1)/2 comparison result values. 
     
     
       3. The processor of  claim 2  wherein the N*(N−1)/2 comparisons comprise greater than or equal to comparisons and wherein each comparison result value comprises a bit set to 1 if a first input value is greater than or equal to a second input value or set to 0 if the first input value is not greater than or equal to the second input value. 
     
     
       4. The processor of  claim 1  wherein each of the N input values comprises distance values associated with N bounding volume hierarchy (BVH) nodes, wherein the sorting circuitry is to generate a sorted order of the BVH nodes based on the comparison result values. 
     
     
       5. The processor of  claim 4  further comprising:
 stack management circuitry and/or logic to push the N BVH nodes to a stack in the sorted order. 
 
     
     
       6. The processor of  claim 1  wherein the first region of the result matrix comprises an upper right region and the second region of the result matrix comprises a lower left region, the first region and second region of the result matrix separated by a diagonal set of bit locations in the matrix connecting the upper left corner of the result matrix with the lower right corner of the result matrix. 
     
     
       7. The processor of  claim 1  wherein the first region of the result matrix comprises an upper left region and the second region of the result matrix comprises a lower right region, the first region and second region of the result matrix separated by a diagonal set of bit locations in the matrix connecting the lower left corner of the result matrix with the upper right corner of the result matrix. 
     
     
       8. The processor of  claim 1  wherein the value of N for the set of N input values is variable up to a threshold, and wherein the comparison circuitry is to generate the comparison result values and the matrix generation circuitry is to generate the result matrix in the same number of processor cycles, regardless of the value of N up to the threshold. 
     
     
       9. A method comprising:
 receiving a set of N input values to be sorted into a sorted order, the set of N input values are obtained with in a graphics pipeline stage; 
 comparing each input value with all other input values in parallel to generate at least N*(N−1)/2 comparison result values; 
 generating a result matrix having a row associated with each input value, a plurality of bits in each row comprising comparison result values indicating results of comparisons with other input values, wherein a first region of the result matrix is to store a first set of bits comprising the N*(N−1)/2 comparison result values and a second region of the result matrix, opposite the first region, is to store a second set of bits comprising an inverse of the N*(N−1)/2 comparison result values; 
 performing parallel additions of the bits in each row to generate N unique result values; and 
 indexing into the N unique result values to return the sorted order to the graphics pipeline stage. 
 
     
     
       10. The method of  claim 9  wherein the N*(N−1)/2 parallel comparisons are performed by N*(N−1)/2 comparators to generate the at least N*(N−1)/2 comparison result values. 
     
     
       11. The method of  claim 10  wherein the N*(N−1)/2 comparisons comprise greater than or equal to (GTE) comparisons and wherein each comparison result value comprises a bit set to 1 if a first input value is greater than or equal to a second input value or set to O if the first input value is not greater than or equal to the second input value. 
     
     
       12. The method of  claim 9  wherein each of the N input values comprises distance values associated with N bounding volume hierarchy (BVH) nodes, wherein a sorted order of the BVH nodes is generated based on the comparison result values. 
     
     
       13. The method of  claim 12  further comprising:
 pushing the N BVH nodes to a stack in the sorted order. 
 
     
     
       14. The method of  claim 9  wherein the first region of the result matrix comprises an upper right region and the second region of the result matrix comprises a lower left region, the first region and second region of the result matrix separated by a diagonal set of bit locations in the matrix connecting the upper left corner of the result matrix with the lower right corner of the result matrix. 
     
     
       15. The method of  claim 9  wherein the first region of the result matrix comprises an upper left region and the second region of the result matrix comprises a lower right region, the first region and second region of the result matrix separated by a diagonal set of bit locations in the matrix connecting the lower left corner of the result matrix with the upper right corner of the result matrix. 
     
     
       16. The method of  claim 9  wherein the value of N for the set of N input values is variable up to a threshold, and wherein the comparison result values and the result matrix are generated in the same number of processor cycles, regardless of the value of N up to the threshold. 
     
     
       17. A non-transitory machine-readable medium having program code stored thereon which, when executed by a machine, causes the machine to perform the operations of:
 receiving a set of N input values to be sorted into a sorted order; 
 comparing each input value with all other input values in parallel to generate at least N*(N−1)/2 comparison result values; 
 generating a result matrix having a row associated with each input value, a plurality of bits in each row comprising comparison result values indicating results of comparisons with other input values, wherein a first region of the result matrix is to store a first set of bits comprising the N*(N−1)/2 comparison result values and a second region of the result matrix, opposite the first region, is to store a second set of bits comprising an inverse of the N*(N−1)/2 comparison result values; 
 performing parallel additions of the bits in each row to generate N unique result values; and 
 indexing into the N unique result values to return the sorted order. 
 
     
     
       18. The non-transitory machine-readable medium of  claim 17  wherein the N*(N−1)/2 parallel comparisons are performed by N*(N−1)/2 comparators to generate the at least N*(N−1)/2 comparison result values. 
     
     
       19. The non-transitory machine-readable medium of  claim 18  wherein the N*(N−1)/2 comparisons comprise greater than or equal to (GTE) comparisons and wherein each comparison result value comprises a bit set to 1 if a first input value is greater than or equal to a second input value or set to 0 if the first input value is not greater than or equal to the second input value. 
     
     
       20. The non-transitory machine-readable medium of  claim 17  wherein each of the N input values comprises distance values associated with N bounding volume hierarchy (BVH) nodes, wherein a sorted order of the BVH nodes is generated based on the comparison result values. 
     
     
       21. The non-transitory machine-readable medium of  claim 20  further comprising program code to cause the machine to perform the operations of:
 pushing the N BVH nodes to a stack in the sorted order. 
 
     
     
       22. The non-transitory machine-readable medium of  claim 17  wherein the first region of the result matrix comprises an upper right region and the second region of the result matrix comprises a lower left region, the first region and second region of the result matrix separated by a diagonal set of bit locations in the matrix connecting the upper left corner of the result matrix with the lower right corner of the result matrix. 
     
     
       23. The non-transitory machine-readable medium of  claim 17  wherein the first region of the result matrix comprises an upper left region and the second region of the result matrix comprises a lower right region, the first region and second region of the result matrix separated by a diagonal set of bit locations in the matrix connecting the lower left corner of the result matrix with the upper right corner of the result matrix. 
     
     
       24. The non-transitory machine-readable medium of  claim 17  wherein the value of N for the set of N input values is variable up to a threshold, and wherein the comparison result values and the result matrix are generated in the same number of processor cycles, regardless of the value of N up to the threshold.