System for optimizing graphics operations

• US 8,134,561 B2
• Filed: 04/16/2004
• Issued: 03/13/2012
• Est. Priority Date: 04/16/2004
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Harper, John, Brunner, Ralph, Graffagnino, Peter, Zimmer, Mark
• Primary Examiner(s): Mengistu, Amare
• Assistant Examiner(s): Guertin, Aaron M
• Application Number:
  US10/825,694
• Publication Number:
  US 20050231514A1
• Time in Patent Office: 2,888 Days
• Field of Search: 345/339, 345/357, 345/358, 345/420, 345/440, 345/441, 345/501, 345/531, 345/557, 345/505, 345/771, 345/418
• US Class Current: 345/501
• CPC Class Codes: G06F 15/76 Architectures of general purpose stored program computers with program plugboard G06F15/08; multicomputers G06F15/16
• CPC Class Codes: G06F 15/80 comprising an array of processing units with common control, e.g. single instruction multiple data processors G06F15/82 takes precedence ; for correlation function computation G06F17/15
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G09G 5/02 characterised by the way in which colour is displayed details of colour display specific for CRTs G09G1/28; specific for flat matrix panels other than liquid crystal displays G09G3/2003; specific for liquid crystal displays G09G3/3607

Abstract

Disclosed is a system for producing images including techniques for reducing the memory and processing power required for such operations. The system provides techniques for programmatically representing a graphics problem. The system further provides techniques for reducing and optimizing graphics problems for rendering with consideration of the system resources, such as the availability of a compatible GPU.

Claims

1. A method of creating an image utilizing a central processing unit (CPU) and a graphics processing unit (GPU), the method comprising the steps of:

representing, in memory, an image by an image graph wherein the image graph comprises one or more GPU programs represented as nodes in the image graph, inputs to the one or more GPU programs and outputs from the one or more GPU programs wherein the inputs and outputs are represented as links in the image graph;

optimizing said image graph by running software on said CPU wherein optimizing comprises consolidating multiple GPU programs into one GPU program to create an optimized image graph;

wherein optimizing said image graph further comprises;

under control of said CPU, starting with the root GPU program, calling the following groups of objects for each GPU program that must be run in order that the root GPU program may run to render said image graph of GPU programs;

one or more objects for analyzing whether two GPU programs may be combined, and performing a combination if said analysis is positive wherein analyzing comprises analysis of inputs to the two GPU programs and outputs from the two GPU programs;

one or more objects for performing region of interest (ROI) and domain of definition (DOD) optimization, wherein the DOD comprises all places in an image that are explicitly defined and not transparent and the ROI comprises the portion of the input image that is necessary to compute the given output DOD; and

using the CPU to determine if GPU programs may be combined;

compiling said optimized image graph by running software on said CPU to create a compiled image graph; and

rendering said image graph by running said compiled image graph on a GPU, yielding a rendered image.

2. The method of claim 1, wherein the step of optimizing includes the step of using a cache look-up to see if at least a portion of said rendered image is already in cache.

3. The method of claim 2, wherein the step of optimizing includes the step of calculating an intersection, said intersection representing an area where said rendered image is both defined by said image graph and part of a region requested by a process running on said CPU that has requested creation of said image.

4. The method of claim 3 further comprising the step of, using said calculated intersection to limit the number of pixels that require calculation during said rendering on said GPU.

5. The method of claim 3 further comprising the step of, using said calculated intersection to limit the amount of memory necessary for storing said rendered image.

6. The method of claim 1 wherein the step of optimizing includes the step of using a cache look-up to see if at least a portion of said image graph has already been optimized and is in a memory.

7. The method of claim 6, wherein the step of optimizing includes the step of calculating an intersection, said intersection representing an area where said rendered image is both defined by said image graph and part of a region requested by a process running on said CPU that has requested creation of said image.

8. The method of claim 7 further comprising the step of, using said calculated intersection to limit the number of pixels that require calculation during said rendering on said GPU.

9. The method of claim 7 further comprising the step of, using said calculated intersection to limit the amount of memory necessary for storing said rendered image.

10. The method of claim 1, wherein the step of optimizing includes the step of calculating an intersection, said intersection representing an area where said rendered image is both defined by said image graph and part of a region requested by a process running on said CPU that has requested creation of said image.

11. The method of claim 10 further comprising the step of, using said calculated intersection to limit the number of pixels that require calculation during said rendering on said GPU.

12. The method of claim 10 further comprising the step of, using said calculated intersection to limit the amount of memory necessary for storing said rendered image.

13. The method of claim 1 wherein said act of optimizing further comprises

using the CPU to determine if said GPU is capable of running a program that has been created by combining two other programs.

14. A computer system configured for creating an image, the computer system comprising:

a central processing unit (CPU);

a graphics processing unit (GPU) communicatively coupled to the CPU; and

a memory communicatively coupled to the CPU and/or the GPU having, the memory storing computer executable instructions executable by the CPU and/or the GPU to configure the CPU and GPU to perform the method recited in claim 1.

15. A non-transitory computer-readable medium having computer executable instructions for performing the method recited in claim 1.

16. A method for creating a rendered polygon using an image graph based representation of graphics processing unit (GPU) programs, the method comprising the steps of:

under control of a CPU, receiving a request to render a polygon;

under control of said CPU, creating an image graph based representation of GPU programs to create said rendered polygon, the image graph based representation comprising a root GPU program and its relationship with other GPU programs, wherein said GPU programs are represented as nodes with their inputs and outputs represented as links;

under control of said CPU, starting with the root GPU program, calling the following groups of objects for each GPU program that must be run in order that the root GPU program may run to render said polygon;

one or more objects for analyzing whether two GPU programs may be combined, and performing a combination if said analysis is positive wherein analyzing comprises analysis of inputs to the two GPU programs and outputs from the two GPU programs;

one or more objects for performing region of interest (ROI) and domain of definition (DOD) optimization, wherein the DOD comprises all places in an image that are explicitly defined and not transparent and the ROI comprises the portion of the input image that is necessary to compute the given output DOD; and

one or more objects for creating a buffer and causing a GPU to render an image to that buffer by running a GPU program.

17. The method of claim 16 wherein said image graph based representation comprises a low-level image graph.

18. The method of claim 16 wherein said image graph based representation comprises a high-level image graph.

19. The method of claim 16 further wherein an application program under CPU control makes said request to render said polygon.

20. The method of claim 16 wherein said one or more objects for analyzing whether two GPU programs may be combined, and performing a combination if said analysis is positive, are recursively called until no more combinations are possible.

21. The method of claim 16 wherein DOD/ROI optimization comprises intersecting the ROI with the output DOD for a GPU program.

22. The method of claim 16 wherein a cache is used in order to find the result of running a particular GPU program, without running the particular GPU program.

23. A computer system configured for creating an image, the computer system comprising:

a central processing unit (CPU);

a graphics processing unit (GPU) communicatively coupled to the CPU; and

a memory communicatively coupled to the CPU and/or the GPU having, the memory storing computer executable instructions executable by the CPU and/or the GPU to configure the CPU and GPU to perform the method recited in claim 16.

24. A non-transitory computer-readable medium having computer executable instructions for performing the method recited in claim 16.

25. A method for creating a rendered image using an image graph based relationship of graphics processing unit (‘

GPU) programs, the method comprising the steps of;

under control of said CPU, creating an image graph representing said rendered image wherein said image graph comprises a representation of one or more GPU programs as nodes in the graph;

inputs to the one or more GPU programs and outputs from the one or more GPU programs as links in the image graph;

under control of said CPU, starting with a root node in said graph, calling the following groups of objects for each node that must be calculated in order that the root node may be calculated;

one or more objects for analyzing whether two GPU programs may be combined, and performing a combination if said analysis is positive wherein analyzing comprises analysis of inputs to the two GPU programs and outputs from the two GPU programs;

one or more domain of definition (DOD) and/or region of interest (ROI) objects for performing DOD/ROI optimization, wherein the DOD comprises all places in an image that are explicitly defined and not transparent and the ROI comprises the portion of the input image that is necessary to compute the given output DOD; and

one or more objects for creating a buffer and causing a GPU to render an image to that buffer by running a GPU program.

26. The method of claim 25 wherein said image graph is a low-level image graph.

27. The method of claim 25 wherein said image graph is a high-level image graph.

28. The method of claim 25 further comprising the step of receiving a request to render said image.

29. The method of claim 28 further comprising the step of an application program under CPU control making said request to render said image.

30. The method of claim 25 wherein said one or more objects for analyzing whether two GPU programs may be combined, and performing a combination if said analysis is positive, are recursively called until no more combinations are possible.

31. The method of claim 25 wherein DOD/ROI optimization comprises intersecting the ROI with the output DOD for a GPU program.

32. The method of claim 25 wherein a cache is used in order to find the result of computed particular node without computing the particular node.

33. A non-transitory computer-readable medium having computer executable instructions for performing the method recited in claim 25.

34. A computer system configured for creating an image, the computer system comprising:

a central processing unit (CPU);

a graphics processing unit (GPU) communicatively coupled to the CPU; and

a memory communicatively coupled to the CPU and/or the GPU having, the memory storing computer executable instructions executable by the CPU and/or the GPU to configure the CPU and GPU to perform the method recited in claim 25.