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

Patent metadata

Field	Value
Publication number	US-12307547-B2
Application number	US-202418433823-A
Country	US
Kind code	B2
Filing date	Feb 6, 2024
Priority date	Mar 19, 2020
Publication date	May 20, 2025
Grant date	May 20, 2025

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. An apparatus comprising:
a processor and non-transitory machine-readable medium having program code stored thereon which, when executed by the processor, causes the processor to perform:
receiving a first plurality of input values to be sorted into a sorted order, wherein the first plurality of input values are obtained within a graphics pipeline stage,
comparing each input value within the first plurality of input values with all other input values within the first plurality of input values to generate a second plurality of comparison result values;
generating a result matrix with a row associated with each input value within the first plurality of input values, a plurality of bits in each row comprising comparison result values indicating results of comparisons the each input value with other input values within the first plurality of input values, wherein a first region of the result matrix is to store a first set of bits comprising the second plurality of 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 second plurality of comparison result values;
performing additions of the bits in each row of the result matrix to generate a corresponding first plurality of sum results; and
sorting the corresponding first plurality of sum results to return the sorted order to the graphics pipeline stage.

2. The apparatus of claim 1 , wherein the graphics pipeline stage comprises ray tracing operations, and wherein each input value within the first plurality of input values corresponds to a node in a bounding volume hierarchy (BVH).

3. The apparatus of claim 2 , wherein each input value within the first plurality of input values indicates a distance of a node in the BVH from a ray origin.

4. The apparatus of claim 2 , wherein the corresponding nodes in the BVH are to be pushed to a stack in the sorted order.

5. The apparatus of claim 1 , wherein the graphics pipeline stage comprises ray tracing operations, and wherein each input value within the first plurality of input values corresponds to a ray within a ray bank.

6. The apparatus 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 the 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 apparatus of claim 1 , wherein comparing each input value within the first plurality of input values with all other input values within the first plurality of input values comprises a greater than or equal to comparison, and each comparison result comprises a bit set to a first value if a first input value is greater than or equal to a second input value or set to a second value otherwise.

8. The apparatus of claim 1 , wherein comparing each input value within the first plurality of input values with all other input values within the first plurality of input values comprises one of a less than comparison, and a less than or equal to comparison.

9. A method comprising:
receiving a first plurality of input values to be sorted into a sorted order, wherein the first plurality of input values are obtained within a graphics pipeline stage,
comparing each input value within the first plurality of input values with all other input values within the first plurality of input values to generate a second plurality of comparison result values;
generating a result matrix with a row associated with each input value within the first plurality of input values, a plurality of bits in each row comprising comparison result values indicating results of comparisons the each input value with other input values within the first plurality of input values, wherein a first region of the result matrix is to store a first set of bits comprising the second plurality of 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 second plurality of comparison result values;
performing additions of the bits in each row of the result matrix to generate a corresponding first plurality of sum results; and
sorting the corresponding first plurality of sum results to return the sorted order to the graphics pipeline stage.

10. The method of claim 9 , wherein the graphics pipeline stage comprises ray tracing operations, and wherein each input value within the first plurality of input values corresponds to a node in a bounding volume hierarchy (BVH).

11. The method of claim 9 , wherein the graphics pipeline stage comprises ray tracing operations, and wherein each input value within the first plurality of input values corresponds to a ray within a ray bank.

12. 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 the 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.

13. The method of claim 9 , wherein comparing each input value within the first plurality of input values with all other input values within the first plurality of input values comprises a greater than or equal to comparison, and each comparison result comprises a bit set to a first value if a first input value is greater than or equal to a second input value or set to a second value otherwise.

14. A non-transitory machine-readable medium having program code stored thereon which, when executed by a processor, causes the processor to perform:
receiving a first plurality of input values to be sorted into a sorted order, wherein the first plurality of input values are obtained within a graphics pipeline stage,
comparing each input value within the first plurality of input values with all other input values within the first plurality of input values to generate a second plurality of comparison result values;
generating a result matrix with a row associated with each input value within the first plurality of input values, a plurality of bits in each row comprising comparison result values indicating results of comparisons the each input value with other input values within the first plurality of input values, wherein a first region of the result matrix is to store a first set of bits comprising the second plurality of 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 second plurality of comparison result values;
performing additions of the bits in each row of the result matrix to generate a corresponding first plurality of sum results; and
sorting the corresponding first plurality of sum results to return the sorted order to the graphics pipeline stage.

15. The non-transitory machine-readable medium of claim 14 , wherein the graphics pipeline stage comprises ray tracing operations, and wherein each input value within the first plurality of input values corresponds to a node in a bounding volume hierarchy (BVH).

16. The non-transitory machine-readable medium of claim 15 , wherein the corresponding nodes in the BVH are to be pushed to a stack in the sorted order.

17. The non-transitory machine-readable medium of claim 14 , wherein the graphic

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

• G06T15/08

  Volume rendering · CPC title

• G06F7/505

  in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination · CPC title

• G06F7/02

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