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

Patent metadata

Field	Value
Publication number	US-11900498-B2
Application number	US-202016823741-A
Country	US
Kind code	B2
Filing date	Mar 19, 2020
Priority date	Mar 19, 2020
Publication date	Feb 13, 2024
Grant date	Feb 13, 2024

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.

First claim

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

Assignees

• Intel Corp

Inventors

• Mandal Saikat
• Surti Prasoonkumar
• Woop Sven

Classifications

• G06F9/30036

  Instructions to perform operations on packed data, e.g. vector, tile or matrix operations · CPC title

• G06F9/30038

  using a mask · CPC title

• G06T1/20 Primary

  Processor architectures; Processor configuration, e.g. pipelining · CPC title

• G06F7/02

  Comparing digital values (G06F7/06, {G06F7/22,} G06F7/38 take precedence) · CPC title

• G06F7/24

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title