Updating Frame Divisions Based on Ray Tracing Image Processing System Performance

• US 20080079734A1
• Filed: 09/28/2006
• Published: 04/03/2008
• 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.
• Granted Patent: US 8,089,481 B2
• Time in Patent Office: Days
• US Class Current: 345/505
• 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 of distributing workload in a ray tracing image processing system, the method comprising:

dividing a frame of pixels into at least a first region of pixels and a second region of pixels;

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

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

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

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

re-dividing the frame of pixels into at least a new first region of pixels and a new second region of pixels.

2. The method of claim 1, further comprising:

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

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

3. The method of claim 2, further comprising:

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

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

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

5. The method of claim 4, wherein if the workload experienced by the first processing element is greater than the workload experienced by the second processing element, re-dividing the frame of pixels such that the new first region of pixels is smaller than the new second region of pixels;

and

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

6. The method of claim 1, wherein monitoring a workload comprises:

monitoring a performance counter for at least one of the first processing element or the second processing element.

7. The method of claim 1, wherein monitoring a workload comprises:

monitoring an inbox associated with at least one of the first processing element or the second processing element.

8. 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.

11. The computer readable medium of claim 7 wherein monitoring a workload comprises:

monitoring a performance counter for at least one of the first processing element or the second processing element.

9. A computer readable medium containing a program which, when executed, performs operations comprising:

dividing a frame of pixels into at least a first region of pixels and a second region of pixels;

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

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

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

monitoring at least a workload experienced by the first processing element or a workload experienced by the second processing element;

re-dividing the frame of pixels into at least a new first region of pixels and a new second region of pixels;

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

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

10. The computer readable medium of claim 9 wherein the size of at least one of the new first region of pixels or the size of the new second region of pixels is based on at least one of the workload experienced by the first processing element or the workload experienced by the second processing element;

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

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

12. The computer readable medium of claim 9, wherein monitoring a workload comprises:

monitoring an inbox associated with at least one of the first processing element or the second processing element.

13. An image processing system, comprising:

a first processing element; and

a second processing element, wherein the image processing system is configured to divide a frame of pixels into at least a first region of pixels and a second region of pixels;

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

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

perform ray tracing with the first processing element and the second processing element to determine colors of pixels in the frame of pixels;

monitor at least a workload experienced by the first processing element or a workload experienced by the second processing element; and

re-divide the frame of pixels into at least a new first region of pixels and a new second region of pixels.

14. The image processing system of claim 13, wherein the image processing system is further configured to assign the responsibility for maintaining colors of pixels located within the new first region of pixels to the first processing element;

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

15. The image processing system of claim 14, wherein the image processing system is further configured to:

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

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

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

17. The image processing system of claim 16, wherein if the workload experienced by the first processing element is greater than the workload experienced by the second processing element, re-dividing the frame of pixels such that the new first region of pixels is smaller than the new second region of pixels;

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

18. The image processing system of claim 13, wherein monitor a workload comprises monitoring a performance counter for at least one of the first processing element or the second processing element.

19. The image processing system of claim 13, wherein monitor a workload comprises monitoring an inbox associated with at least one of the first processing element or the second processing element.

20. The image processing system of claim 13, further comprising

a first processing core;

and

a second processing core; and

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