Method for efficient grouping of cache requests for datapath scheduling
In a ray tracer, a cache for streaming workloads groups ray requests for coherent successive bounding volume hierarchy traversal operations by sending common data down an attached data path to all ray requests in the group at the same time or about the same time. Grouping the requests provides good performance with a smaller number of cache lines.
1 . A cache for use by a ray tracer that consumes an acceleration data structure stored in a memory, the cache comprising:
at least one cache line configured to store acceleration data retrieved from the memory;
a hit/miss detection circuit that determines whether memory access requests from ray tracing operations are hits or misses, the hit/miss detection circuit initiating acceleration data retrieval from the memory for caching by the at least one cache line in response to detected misses; and
a datapath that time-coherently serves acceleration data stored in the at least one cache line to ray tracing operations associated with groups of ray operations for plural rays that each request acceleration data stored in the at least one cache line,
wherein the datapath imposes on the ray tracer, a group execution order for ray tracing operations of plural rays time-coherently traversing the same or similar paths through the acceleration data structure.
2 . The cache of claim 1 wherein the ray tracer includes a stack manager configured to activate the plural rays in an order other than the group execution order.
3 . The cache of claim 2 wherein the stack manager is configured to activate the plural rays in a random order.
4 . The cache of claim 2 wherein the stack manager is configured to activate the plural rays in a round-robin order.
5 . The cache of claim 1 wherein the cache is configured to recognize opportunities to group randomly-selected rays with other rays that consume the same cached acceleration data.
6 . The cache of claim 1 wherein the cache is configured to coalesce rays behind specific blocks of cached acceleration data.
7 . The cache of claim 1 wherein the cache includes a pending request table and is configured to push new requests from plural rays for new data onto the pending request table and then time-coherently satisfy acceleration data needs of intersection testing of the plural rays, thereby controlling the ray tracer to operate on the plural rays in a repeating cadence.
8 . The cache of claim 1 wherein the cache is configured to retrieve acceleration data into the at least one cache line in response to a memory access request associated with a single ray, and the datapath is configured to serve the retrieved acceleration data to operations associated with the single ray and operations associated with additional rays in the group.
9 . The cache of claim 1 wherein the ray tracer activates rays independently of the group order, and the cache is configured to link or group a ray making a new request for first acceleration data with a ray that previously made an already pending request for the same first acceleration data.
10 . The cache of claim 1 wherein when the cache retrieves an acceleration data compressed treelet for caching in the at least one cache line, the cache serving at the same time or about the same time, ray-complet tests for all rays that have been waiting on the acceleration data compressed treelet, thereby scheduling ray-complet tests for all such rays.
11 . A cache method for use by a ray tracer that consumes an acceleration data structure stored in a memory, the cache method comprising:
storing acceleration data retrieved from the memory into at least one cache line;
detecting whether memory access requests from ray tracing operations are misses;
initiating acceleration data retrieval from the memory for caching into the at least one cache line in response to detected misses; and
time-coherently serving acceleration data stored in the at least one cache line to ray tracing operations associated with groups of ray operations for plural rays that request acceleration data stored in the at least one cache line, including imposing on the ray tracer, a group execution order for ray tracing operations of plural rays time-coherently traversing the same or similar paths through the acceleration data structure.
12 . The cache method of claim 11 further including activating the plural rays in an order other than group execution order.
13 . The cache method of claim 12 further including activating the plural rays in a random order.
14 . The cache method of claim 12 further including activating the plural rays in a round-robin order.
15 . The cache method of claim 11 further including recognizing opportunities to group randomly-selected rays with other rays that use the same cached acceleration data.
16 . The cache method of claim 11 further including coalescing rays behind specific blocks of cached acceleration data.
17 . The cache method of claim 11 further including pushing new requests from plural rays for new data onto a pending request table and then satisfying acceleration data needs of intersection testing of the plural rays at the same time, thereby controlling the ray tracer to operate on the plural rays in a repeating cadence.
18 . The cache method of claim 11 further including retrieving acceleration data into the at least one cache line for operation of a single ray, and serving the retrieved acceleration data to operations associated with the plural rays in the group.
19 . The cache method of claim 11 further including activating rays independently of group order, and linking or grouping a ray making a new request for acceleration data to a ray that previously made an already pending request for the same acceleration data.
20 . The cache method of claim 11 further including retrieving an acceleration data compressed treelet for caching in the at least one cache line, the cache scheduling ray-complet tests for all rays that have been waiting on the acceleration data compressed treelet by serving at the same time or about the same time, ray-complet tests for all rays waiting on the same acceleration data compressed treelet.