Method for programmable timeouts of tree traversal mechanisms in hardware

Patent metadata

Field	Value
Publication number	US-10885698-B2
Application number	US-201816101232-A
Country	US
Kind code	B2
Filing date	Aug 10, 2018
Priority date	Aug 10, 2018
Publication date	Jan 5, 2021
Grant date	Jan 5, 2021

Abstract

In a ray tracer, to prevent any long-running query from hanging the graphics processing unit, a traversal coprocessor provides a preemption mechanism that will allow rays to stop processing or time out early. The example non-limiting implementations described herein provide such a preemption mechanism, including a forward progress guarantee, and additional programmable timeout options that can be time or cycle based. Those programmable options provide a means for quality of service timing guarantees for applications such as virtual reality (VR) that have strict timing requirements.

First claim

The invention claimed is:

1. A ray tracing device comprising:
traversal hardware configured to receive, from a processor, a first query including first ray information and a second query including second ray information, in response to the first query, traverse an acceleration data structure to determine bounding volumes or geometric primitives that the first ray intersects and in response to the second query, traverse the acceleration data structure to determine bounding volumes and/or or geometric primitives that the second ray intersects; and
a programmable timeout circuit configured to:
(a) simultaneously monitor how much the traversal hardware is used to traverse the acceleration data structure for the first ray and how much the traversal hardware is used to traverse the acceleration data structure for the second ray,
(b) interrupt the traversal hardware in traversing the acceleration data structure for the first ray if an amount the traversal hardware is used in traversing the acceleration data structure for the first ray exceeds a first threshold value programmable for the first ray without interrupting the traversal hardware in traversing the acceleration data structure for the second ray, and
(c) interrupt the traversal hardware in traversing the acceleration data structure for the second ray if an amount the traversal hardware is used in traversing the acceleration data structure for the second ray exceeds a second threshold value programmable for the second ray without interrupting the traversal hardware in traversing the acceleration data structure for the first ray.

2. The ray tracing device of claim 1 wherein the programmable timeout circuit is work-based.

3. The ray tracing device of claim 1 wherein the programmable timeout circuit is cycle-based.

4. The ray tracing device of claim 1 wherein the programmable timeout circuit is time-based.

5. The ray tracing device of claim 1 wherein the programmable timeout circuit is epoch-based.

6. The ray tracing device of claim 1 wherein monitoring how much the traversal hardware is used comprises counting the number of certain traversal operations the hardware performs for the first or second ray.

7. The ray tracing device of claim 6 wherein the certain traversal operations comprise leaf node traversals.

8. The ray tracing device of claim 1 wherein the traversal hardware is configured to traverse the acceleration data structure to determine bounding volumes or geometric primitives that the first ray intersects at least partially in parallel with traversing the acceleration data structure to determine bounding volumes or geometric primitives that the second ray intersects.

9. A method implemented by a hardware-based traversal coprocessor coupled to a processor, the method comprising:
receiving from the processor a first query including first ray information and a second query including second ray information;
in response to receiving the first query, traversing an acceleration data structure to determine bounding volumes or geometric primitives that the first ray intersects;
in response to receiving the second query, traversing the acceleration data structure to determine bounding volumes or geometric primitives that second first ray intersects;
simultaneously monitoring how much the traversal coprocessor is used to traverse the acceleration data structure for the first ray and how much the traversal coprocessor is used to traverse the acceleration data structure for the second ray;
interrupting the traversal coprocessor in traversing the acceleration data structure for the first ray if an amount the traversal coprocessor is used in traversing the acceleration data structure for the first ray exceeds a first threshold value programmable for the first ray without interrupting the traversal hardware in traversing the acceleration data structure for the second ray; and
interrupting the traversal coprocessor in traversing the acceleration data structure for the second ray if an amount the traversal coprocessor is used in traversing the acceleration data structure for the second ray exceeds a second threshold value programmable for the second ray without interrupting the traversal hardware in traversing the acceleration data structure for the first ray.

10. The method of claim 9 wherein the amount the traversal coprocessor is used is work-based.

11. The method of claim 9 wherein the amount the traversal coprocessor is used is cycle-based.

12. The method of claim 9 wherein the amount the traversal coprocessor is used is time-based.

13. The method of claim 9 wherein the amount the traversal coprocessor is used is epoch-based.

14. The method of claim 9 wherein monitoring how much the traversal coprocessor is used comprises counting a number of certain traversal operations the coprocessor performs for the ray.

15. The method of claim 14 wherein the certain traversal operations comprise leaf node traversals.

Assignees

• Nvidia Corp

Inventors

• Muthler Greg
• Babich Jr Ronald Charles
• Newhall Jr William Parsons
• Nelson Peter
• Robertson James
• Burgess John

Classifications

• G06N3/045

  Combinations of networks · CPC title

• G06T17/005

  Tree description, e.g. octree, quadtree · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title

• G06T1/20 Primary

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

• G06T2210/12

  Bounding box · CPC title