Updating frame divisions based on ray tracing image processing system performance

• US 8,089,481 B2
• Filed: 09/28/2006
• Issued: 01/03/2012
• Est. Priority Date: 09/28/2006
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Shearer, Robert A.
• Primary Examiner(s): Hsu, Joni
• Assistant Examiner(s): Sonners, Scott E
• Application Number:
  US11/536,179
• Publication Number:
  US 20080079734A1
• Time in Patent Office: 1,923 Days
• Field of Search: 345/421, 345/426, 345/505
• US Class Current: 345/426
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 2210/52 Parallel processing

Abstract

An image processing system may perform various tasks in an effort to evenly distribute workload amongst workload managers. According to one embodiment of the invention, the image processing system may divide a frame of pixels into different regions and assign responsibility for the regions to different workload managers in order to evenly distribute workload. The workload managers may be responsible for performing operations relating to determining or maintaining the color of the pixel within the region or regions which they are responsible. According to another embodiment of the invention, the image processing system may re-divide the frame into new regions based on relative workloads experienced by the processing elements to evenly distribute workload. Furthermore, according to another embodiment of the invention, the image processing system may re-partition a spatial index based on relative workloads experienced by the processing elements to evenly distribute workload amongst workload managers.

Claims

1. A method for distributing workload in a ray tracing image processing system, the method comprising:

dividing a two-dimensional frame of pixels into at least a first region of pixels and a second region of pixels, wherein the two-dimensional frame of pixels represents an image rendered from a three-dimensional scene;

partitioning a spatial index, wherein the spatial index represents the three-dimensional scene;

assigning to a first processing element a responsibility for initiating ray tracing for rays that traverse through the first region of pixels;

assigning to a second processing element a responsibility for initiating ray tracing for rays that traverse through the second region of pixels;

performing ray tracing with the first processing element and the second processing element to determine colors of pixels in the two-dimensional frame of pixels;

monitoring at least one of a workload experienced by the first processing element and a workload experienced by the second processing element;

re-dividing the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element; and

re-partitioning the spatial index based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

2. The method of claim 1, further comprising:

assigning to the first processing element a responsibility for maintaining colors of pixels located within the new first region of pixels; and

assigning to the second processing element a responsibility for maintaining colors of pixels located within the new second region of pixels.

3. The method of claim 1, wherein the size of at least one of the new first region of pixels and the new second region of pixels is based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

4. The method of claim 1, wherein re-dividing the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels comprises:

upon determining that the workload experienced by the first processing element is greater than the workload experienced by the second processing element, re-dividing the two-dimensional frame of pixels such that the new first region of pixels is smaller than the new second region of pixels; and

upon determining that the workload experienced by the second processing element is greater than the workload experienced by the first processing element, re-dividing the two-dimensional frame of pixels such that the new second region of pixels is smaller than the new first region of pixels.

5. The method of claim 1, wherein monitoring a workload comprises monitoring a performance counter for at least one of the first processing element and the second processing element.

6. The method of claim 1, wherein monitoring a workload comprises monitoring an inbox associated with at least one of the first processing element and the second processing element.

7. The method of claim 1, wherein the first processing element is located on a first processing core and the second processing element is located on a second processing core.

8. The method of claim 1, further comprising:

assigning to the first processing element a responsibility for initiating ray tracing for rays that traverse through the new first region of pixels; and

assigning to the second processing element a responsibility for initiating ray tracing for rays that traverse through the new second region of pixels.

9. The method of claim 1, wherein the spatial index is implemented as a tree type data structure.

10. A non-transitory computer readable storage medium containing a program which, when executed, performs operations comprising:

dividing a two-dimensional frame of pixels into at least a first region of pixels and a second region of pixels, wherein the two-dimensional frame of pixels represents an image rendered from a three-dimensional scene;

partitioning a spatial index, wherein the spatial index represents the three-dimensional scene;

assigning to a first processing element a responsibility for initiating ray tracing for rays that traverse through the first region of pixels;

assigning to a second processing element a responsibility for initiating ray tracing for rays that traverse through the second region of pixels;

performing ray tracing with the first processing element and the second processing element to determine colors of pixels in the two-dimensional frame of pixels;

monitoring at least one of a workload experienced by the first processing element and a workload experienced by the second processing element;

re-dividing the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element; and

re-partitioning the spatial index based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

11. The computer readable storage medium of claim 10, wherein re-dividing the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels comprises:

upon determining that the workload experienced by the first processing element is greater than the workload experienced by the second processing element, re-dividing the two-dimensional frame of pixels such that the new first region of pixels is smaller than the new second region of pixels; and

upon determining that the workload experienced by the second processing element is greater than the workload experienced by the first processing element, re-dividing the two-dimensional frame of pixels such that the new second region of pixels is smaller than the new first region of pixels.

12. The computer readable storage medium of claim 10 wherein monitoring a workload comprises monitoring a performance counter for at least one of the first processing element and the second processing element.

13. The computer readable storage medium of claim 10, wherein monitoring a workload comprises monitoring an inbox associated with at least one of the first processing element and the second processing element.

14. The computer readable storage medium of claim 10, wherein the operations further comprise:

assigning to the first processing element a responsibility for initiating ray tracing for rays that traverse through the new first region of pixels; and

assigning to the second processing element a responsibility for initiating ray tracing for rays that traverse through the new second region of pixels.

15. The computer readable storage medium of claim 10, wherein the spatial index is implemented as a tree type data structure.

16. The computer readable storage medium of claim 10, wherein the size of at least one of the new first region of pixels and the new second region of pixels is based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

17. An image processing system comprising:

a first processing element; and

a second processing element,

wherein the image processing system is configured to;

divide a two-dimensional frame of pixels into at least a first region of pixels and a second region of pixels, wherein the two-dimensional frame of pixels represents an image rendered from a three-dimensional scene,

partition a spatial index, wherein the spatial index represents the three-dimensional scene,

assign to the first processing element a responsibility for initiating ray tracing for rays that traverse through the first region of pixels,

assign to the second processing element a responsibility for initiating ray tracing for rays that traverse through the second region of pixels,

perform ray tracing with the first processing element and the second processing element to determine colors of pixels in the two-dimensional frame of pixels,

monitor at least one of a workload experienced by the first processing element and a workload experienced by the second processing element,

re-divide the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element, and

re-partition the spatial index based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

18. The image processing system of claim 17, wherein the image processing system is further configured to:

assign to the first processing element a responsibility for maintaining colors of pixels located within the new first region of pixels, and

assign to the second processing element a responsibility for maintaining colors of pixels located within the new second region of pixels.

19. The image processing system of claim 17, wherein the size of at least one of the new first region of pixels and the new second region of pixels is based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

20. The image processing system of claim 17, wherein re-dividing the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels comprises:

upon determining that the workload experienced by the first processing element is greater than the workload experienced by the second processing element, re-dividing the two-dimensional frame of pixels such that the new first region of pixels is smaller than the new second region of pixels; and

upon determining that the workload experienced by the second processing element is greater than the workload experienced by the first processing element, re-dividing the two-dimensional frame of pixels such that the new second region of pixels is smaller than the new first region of pixels.

21. The image processing system of claim 17, wherein monitoring the workload comprises monitoring a performance counter for at least one of the first processing element and the second processing element.

22. The image processing system of claim 17, wherein monitoring the workload comprises monitoring an inbox associated with at least one of the first processing element and the second processing element.

23. The image processing system of claim 17, further comprising:

a first processing core; and

a second processing core,

wherein the first processing element is located on the first processing core and the second processing element is located on the second processing core.

24. The image processing system of claim 17, wherein the image processing system is further configured to:

assign to the first processing element a responsibility for initiating ray tracing for rays that traverse through the new first region of pixels, and

assign to the second processing element a responsibility for initiating ray tracing for rays that traverse through the new second region of pixels.

25. The image processing system of claim 17, wherein the spatial index is implemented as a tree type data structure.