Method for forward progress and programmable timeouts of tree traversal mechanisms in hardware

Patent metadata

Field	Value
Publication number	US-2025292488-A1
Application number	US-202519223551-A
Country	US
Kind code	A1
Filing date	May 30, 2025
Priority date	Aug 10, 2018
Publication date	Sep 18, 2025
Grant date	—

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

1 . (canceled)

2 . A hardware-based traversal co-processor comprising:
traversal hardware configured to traverse, in parallel for each of a plurality of rays, an acceleration data structure to determine geometric primitives intersected by the rays; and a circuit configured to determine, for each of the plurality of rays, a number of traversals performed in traversing the acceleration data structure, and interrupt traversing the acceleration data for rays of the plurality of rays for which the determined number of traversals exceeds a threshold programmed for the respective ray.

3 . The hardware-based traversal co-processor of claim 2 , wherein the threshold programmed for the ray includes a number of leaf nodes traversals.

4 . The hardware-based traversal co-processor of claim 2 , wherein a threshold programmed for at least one of the rays is different from a threshold programmed for one or more other rays.

5 . A hardware-based traversal co-processor comprising:
traversal hardware configured to traverse, in parallel for each of a plurality of rays, an acceleration data structure to determine geometric primitives intersected by the rays; and a timeout circuit configured to determine, for each of the plurality of rays, an amount of time used in traversing the acceleration data structure, and interrupt traversing the acceleration data for rays of the plurality of rays for which the determined time exceeds a threshold programmed for the respective ray.

6 . The hardware-based traversal co-processor of claim 5 , wherein a threshold programmed for at least one of the rays is different from a threshold programmed for one or more other rays.

Assignees

• Nvidia Corp

Inventors

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

Classifications

• G06T17/005

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

• G06T1/20 Primary

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

• G06N5/046

  Forward inferencing; Production systems · CPC title

• G06T1/60

  Memory management · CPC title

• G06F9/3877

  using a secondary processor, e.g. coprocessor (peripheral processor G06F13/12) · CPC title