Scheduling processing in a ray tracing system
A method of scheduling processing in a ray tracing system gathers child rays into a child task, assigns priority to the child task on the basis that one or more child rays of the child task are derived from a task to which priority has been assigned, and schedules the child task for processing in preference to one or more other tasks to be scheduled to which priority has not been assigned.
1 . A method of scheduling processing in a ray tracing system, the method comprising:
assigning primary priority to a first parent task;
processing the first parent task so as to emit at least one child ray;
processing a second parent task to which primary priority has not been assigned so as to emit at least one child ray;
gathering child rays into a child task, wherein said gathering comprises gathering, into the child task:
one or more child rays emitted by the first parent task to which primary priority has been assigned; and
one or more child rays emitted by the second parent task to which primary priority has not been assigned;
assigning primary priority to the child task on the basis that one or more child rays of the child task are derived from the first parent task to which primary priority has been assigned;
determining whether to allocate a flag to any of the child rays of the child task, wherein flag is allocated to each of one or more child rays of the child task on the basis that they are derived from the second parent task to which primary priority has not been assigned, wherein the flag allocated to each of said one or more child rays of the child task is for subsequent use in determining whether to assign a secondary priority to one or more grandchild tasks into which one or more grandchild rays derived from the child task are gathered; and
scheduling the child task for processing in preference to one or more other tasks to be scheduled to which primary priority has not been assigned.
2 . The method of claim 1 , further comprising scheduling the first parent task for processing in preference to one or more other tasks to be scheduled to which primary priority has not been assigned.
3 . The method of claim 1 , wherein the first parent task is a primary task.
4 . The method of claim 1 , wherein one or more parent rays of the first parent task are derived from a primary task to which primary priority has been assigned.
5 . The method of claim 3 , wherein a plurality of primary tasks are active in the ray tracing system at a particular time.
6 . The method of claim 5 , further comprising assigning primary priority to one or more primary tasks of the plurality of primary tasks in dependence on the relative age of each of the primary tasks.
7 . The method of claim 5 , further comprising assigning primary priority to multiple primary tasks of the plurality of primary tasks, wherein the number of primary tasks that, at the particular time, are active in the ray tracing system to which primary priority can be assigned is limited to a predefined number.
8 . The method of claim 3 , wherein a primary task is a task that does not itself have a parent task.
9 . The method of claim 3 , wherein a primary task is a task implementing a ray generation shader so as to launch one or more primary rays.
10 . The method of claim 1 , further comprising:
processing the child task so as to emit one or more grandchild rays;
gathering one or more grandchild rays emitted by the child task in respect of said one or more child rays to which the flag has been allocated into a grandchild task, none of the rays gathered into the grandchild task being derived from a primary task to which primary priority has been assigned;
assigning a secondary priority to the grandchild task; and
scheduling the grandchild task for processing in preference to one or more other tasks to be scheduled to which neither primary priority, nor secondary priority, has been assigned.
11 . The method of claim 10 , wherein scheduling the grandchild task for processing comprises scheduling one or more other tasks to which primary priority has been assigned in advance of the grandchild task to which secondary priority has been assigned.
12 . The method of claim 1 , further comprising, prior to scheduling a task to which primary priority has not been assigned, delaying for a period of time without scheduling said task.
13 . The method of claim 12 , further comprising, if a task to which primary priority has been assigned becomes available for scheduling during the period of time, scheduling the task to which primary priority has been assigned in preference to the task to which primary priority has not been assigned.
14 . The method of claim 12 , wherein the period of time is adaptive in dependence on the amount of memory available to the ray tracing system for storage of intermediate data relating to tasks present in the ray tracing system.
15 . The method of claim 1 , further comprising:
providing a first queue for tasks to which primary priority has been assigned and a second queue for tasks to which primary priority has not been assigned; and
scheduling tasks for processing from the second queue only when no tasks are present in the first queue.
16 . The method of claim 1 , wherein each task comprises a plurality of instances of a shader program corresponding to a respective plurality of rays for which the shader program is to be executed.
17 . A ray tracing system configured to process rays, wherein:
the ray tracing system comprises task scheduling logic and processing logic, the ray tracing system being configured to: assign primary priority to a first parent task;
process the first parent task so as to emit a child ray;
process a second parent task to which primary priority has not been assigned so as to emit at least one child ray;
gather child rays into a child task, wherein gathering child rays into the child task comprises gathering, into the child task:
one or more child rays emitted by the first parent task to which primary priority has been assigned; and
one or more child rays emitted by the second parent task to which primary priority has not been assigned;
assign primary priority to the child task on the basis that one or more child rays of the child task are derived from the first parent task to which primary priority has been assigned;
determine whether to allocate a flag to any of the child rays of the child task, wherein a flag is allocated to each of one or more child rays of the child task on the basis that they are derived from the second parent task to which primary priority has not been assigned, and wherein the flag allocated to each of said one or more child rays of the child task is for subsequent use in determining whether to assign a secondary priority to one or more grandchild tasks into which one or more grandchild rays derived from the child task are gathered; and
schedule the child task for processing in preference to one or more other tasks to be scheduled to which primary priority has not been assigned.
18 . A non-transitory computer readable storage medium having stored thereon computer readable instructions that, when executed at a computer system, cause the computer system to perform a method of scheduling processing in a ray tracing system, the method comprising:
assigning primary priority to a first parent task;
processing the first parent task so as to emit at least one child ray;
processing a second parent task to which primary priority has not been assigned so as to emit at least one child ray;
gathering child rays into a child task, wherein said gathering comprises gathering, into the child task:
one or more child rays emitted by the first parent task to which primary priority has been assigned; and
one or more child rays emitted by the second parent task to which primary priority has not been assigned;
assigning primary priority to the child task on the basis that one or more child rays of the child task are derived from the first parent task to which primary priority has been assigned;
determining whether to allocate a flag to any of the child rays of the child task, wherein a flag is allocated to each of one or more child rays of the child task on the basis that they are derived from the second parent task to which primary priority has not been assigned, wherein the flag allocated to each of said one or more child rays of the child task is for subsequent use in determining whether to assign a secondary priority to one or more grandchild tasks into which one or more grandchild rays derived from the child task are gathered; and
scheduling the child task for processing in preference to one or more other tasks to be scheduled to which primary priority has not been assigned.