Optimizing the execution of media processing routines using a list of routine identifiers

• US 8,018,465 B2
• Filed: 03/31/2009
• Issued: 09/13/2011
• Est. Priority Date: 10/01/2003
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Graves, Eric, Carson, Kenneth M., Ubillos, Randy
• Primary Examiner(s): RICHER, JONI
• Application Number:
  US12/416,080
• Publication Number:
  US 20090244079A1
• Time in Patent Office: 896 Days
• Field of Search: 345/557, 345/530, 345/522, 345/501, 345/502
• US Class Current: 345/522
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G09G 2320/0252 Improving the response speed
• CPC Class Codes: G09G 2340/10 Mixing of images, i.e. displayed pixel being the result of an operation, e.g. adding, on the corresponding input pixels
• CPC Class Codes: G09G 2340/12 Overlay of images, i.e. displayed pixel being the result of switching between the corresponding input pixels
• CPC Class Codes: G09G 2340/125 wherein one of the images is motion video
• CPC Class Codes: G09G 5/026 Control of mixing and/or overlay of colours in general G09G5/022 and G09G5/024 take precedence
• CPC Class Codes: G09G 5/14 Display of multiple viewports

Abstract

Methods for analyzing a list of routine identifiers to optimize processing of routines identified in the list. Some embodiments execute a set of routines in multiple passes where each pass comprises each routine in the set processing a single band of its source. The band size of the sources of the set is related to the size of a cache used during execution of the set. A band size of sources of the set is determined so that all data processed by and produced by any routine in the set can be stored to the cache while the routine processes one band of its source. Some embodiments use the list to combine two or more routines into a single routine where the list is modified accordingly. Some embodiments use the list for grouping and re-ordering routines identified in the list to send particular routines to an alternative processor for processing.

Claims

1. A method for optimizing execution of a plurality of image processing routines on a processor using a particular cache, the method comprising:

receiving an ordered list of routine identifiers specifying a first order for the plurality of image processing routines, which when executed in the first order produce a particular effect, the ordered list specifying executing a first image processing routine after a second image processing routine and before a third image processing routine;

prior to execution of any of the routines by the processor, determining whether the third image processing routine will retrieve from the particular cache, as input data, output data produced by the second image processing routine and stored by the second image processing routine in the particular cache;

when the third image processing routine will retrieve from the particular cache output data produced by the second image processing routine, modifying said ordered list to create a modified list of routine identifiers that specifies a second order in which the third image processing routine is executed after execution of the second image processing routine and before execution of the first image processing routine, the second order optimizing processing time for execution of the image processing routines; and

executing the plurality of image processing routines in the second order to produce the particular effect.

2. The method of claim 1, wherein the second order specifies executing the third image processing routine immediately after executing the second image processing routine.

3. The method of claim 2, wherein said successive execution of the second and third image processing routines eliminates an access to main memory by reusing data from the particular cache.

4. The method of claim 1, wherein the modified ordered list optimizes processing time for the received ordered list by having fewer cache overflows when executing the modified ordered list than when executing the received ordered list.

5. The method of claim 1, wherein modifying said ordered list comprises repositioning the routine identifiers to specify a different order of execution for the image processing routines.

6. The method of claim 1, wherein the plurality of image processing routines comprise at least two of a color correction routine, a blend routine, an opacity routine, and a scale routine.

7. The method of claim 1, wherein modifying said ordered list comprises using a look-up table to identify image processing routines that use, as input data, output data produced by a different image processing routine.

8. The method of claim 1, wherein the second image processing routine produces a first sub-effect, wherein the third image processing routine converts the first sub-effect to a second sub-effect of the particular effect produced by the plurality of image processing routines.

9. A method for optimizing execution of a set of media editing routines on a processor using a particular cache, the method comprising:

receiving an ordering for the set of media editing routines which when executed produces a particular effect, each media editing routine for processing input data retrieved from the particular cache to produce output data that is stored to the particular cache, a plurality of media editing routines in the set of media editing routines specified by a user through a user interface in a particular order to transform one or more source media into an output media;

for each particular media editing routine in a subset of the set of media editing routines, repositioning the particular media editing routine after an identified media editing routine within the set of media editing routines when the identified media editing routine produces output data in the particular cache that is retrieved as input data of the particular media editing routine in order to create a repositioned ordering, wherein the repositioned ordering comprises (i) a first image processing routine for processing input data of a first frame and storing output data to the particular cache, (ii) a second image processing routine for processing input data of a second frame and storing output data to the particular cache without overwriting the output data of the first image processing routine stored to the particular cache, and (iii) a third image processing routine for processing the output data of the first image processing routine from the particular cache and the output data of the second image processing routine from the particular cache to produce output data of the third image processing routine that is stored to the particular cache; and

executing the set of media editing routines based on the repositioned ordering to produce the particular effect.

10. The method of claim 9, wherein the repositioned ordering optimizes processing time for the received ordering by having fewer cache overflows than when executing the received ordering.

11. The method of claim 9, wherein said receiving, repositioning, and executing are performed by a media application, the method further comprising providing a graphical user interface of the media application for users to specify the ordering for the set of media editing routines.

12. The method of claim 9, wherein said media editing routines process audio content.

13. The method of claim 9, wherein said media editing routines process video content.

14. A method for optimizing processing time for executing a plurality of image processing routines on a processor to produce a particular image processing effect, the method comprising:

receiving a plurality of identifiers in an initial order, each identifier identifying a corresponding image processing routine in the plurality of image processing routines;

replacing at least two identifiers with a single identifier to produce a modified ordering of the identifiers, wherein said single identifier identifies a single image processing routine that when executed by the processor produces a same sub-effect as when executing separately each of the image processing routines corresponding to the identifiers that are to be replaced; and

storing the modified ordering of the identifiers to a computer readable storage medium for later execution by the processor in order to produce the particular image processing effect.

15. The method of claim 14, wherein the modified ordering identifies fewer image processing routines to execute than the initial order of identifiers.

16. The method of claim 14, wherein replacing the at least two identifiers with a single identifier comprises using a look-up table to identify the single image processing routine that performs each of the image processing routines performed by the at least two identifiers that are to be replaced.

17. The method of claim 14, wherein said receiving, replacing, and storing are performed by a media application, wherein said identifiers comprise pointers used by the media application to reference image processing routines of the media application.

18. A method for optimizing execution of a plurality of image processing routines on a first processor and a second processor, the method comprising:

receiving an order for executing the plurality of image processing routines to produce a particular effect using the first processor, the plurality of image processing routines comprising a set of routines that modify at least one particular image to create an output image different from the particular image;

identifying sendable routines within the plurality of image processing routines that are able to be processed by the second processor, each sendable routine requiring a separate set of data transfers to the second processor for enabling the second processor to execute the sendable routine;

modifying said received order of the image processing routines by grouping said sendable routines into at least one set of successive sendable routines to send to the second processor, said set of successive sendable routines requiring fewer data transfers to the second processor than when sending each sendable routine separately to the second processor; and

executing the plurality of image processing routines according to the modified ordering using the first processor and the second processor to produce the particular effect, said executing comprising sending the set of successive sendable routines successively to the second processor and receiving from the second processor an output of the set of successive sendable routines without receiving intermediate output from routines within the set of sendable routines.

19. The method of claim 18 further comprising identifying nonsendable routines that are not able to be processed by the second processor, wherein the nonsendable routines are intermixed with the sendable routines within the plurality of image processing routines.

20. The method of claim 18, wherein the first processor is a general central processing unit and the second processor is a dedicated graphics processor.

21. The method of claim 18, wherein receiving said order comprises receiving an ordering of a plurality of identifiers, each identifier used to identify an image processing routine in the plurality of image processing routines, and wherein modifying said received order comprises replacing identifiers for sendable routines with an “

alternative processor”

routine identifier which identify routines that the first processor sends to the second processor for execution.

22. A non-transitory computer readable storage medium storing a computer program for optimizing execution of a plurality of image processing routines on a processor using a particular cache, the computer program comprising:

a set of instructions for receiving an ordered list of routine identifiers specifying a first order for the plurality of image processing routines, which when executed in the first order produces a particular effect, the ordered list specifying executing a first image processing routine after a second image processing routine and before a third image processing routine;

a set of instructions for, prior to execution of any of the image processing routines by the processor, determining whether the third image processing routine will retrieve from the particular cache, as input data, output data produced by the second image processing routine and stored by the second image processing routine in the particular cache;

a set of instructions for modifying, when it is determined that the third image processing routine will retrieve from the particular cache output data produced by the second image processing routine, said ordered list to create a modified list of routine identifiers that specifies a second order in which the third image processing routine is executed after execution of the second image processing routine and before execution of the first image processing routine, the second order optimizing processing time by minimizing cache misses when retrieving data from the particular cache; and

a set of instructions for executing the plurality of image processing routines in the second order to produce the particular effect.

23. The non-transitory computer readable storage medium of claim 22, wherein the second and third image processing routines are executed in at least two processing passes, the second and third image processing routines performed on a different band of a source image in each pass.

24. The non-transitory computer readable storage medium of claim 22, wherein the computer program further comprises a set of instructions for combining the second and third routines into a single image processing routine represented in the ordered list by a single routine identifier.

25. A non-transitory computer readable storage medium storing a computer program for optimizing processing time of a plurality of image processing routines, the computer program comprising:

a set of instructions for determining a plurality of identifiers for identifying an initial order for executing the plurality of image processing routines to produce a particular effect, each identifier identifying a corresponding image processing routine in the plurality of image processing routines;

a set of instructions for replacing at least two identifiers with a single identifier to produce a modified ordering of the identifiers, wherein said single identifier identifies a single image processing routine that when executed produces a same sub-effect as when executing separately each of the image processing routines corresponding to the identifiers that are to be replaced; and

a set of instructions for storing the modified ordering of the identifiers for later execution in order to produce the particular effect.

26. The non-transitory computer readable storage medium of claim 25, wherein the single image processing routine is for receiving only one set of parameters and outputting only one set of processed values.

27. The non-transitory computer readable storage medium of claim 25, wherein the at least two identifiers comprise first and second identifiers that are not successive in the initial order, wherein the set of instructions for replacing the identifiers comprises a set of instructions for moving the first identifier in the order such that the first identifier is directly after the second identifier in the order.

28. A non-transitory computer readable storage medium storing a computer program for optimizing execution of a plurality of image processing routines on a first processor and a second processor, the computer program comprising:

a set of instructions for receiving an order for executing the plurality of image processing routines to produce a particular effect using the first processor, the plurality of image processing routines comprising a set of routines that modify at least one particular image to create an output image different from the particular image;

a set of instructions for identifying sendable routines within the plurality of image processing routines that are able to be processed by the second processor, each sendable routine requiring a separate set of data transfers to the second processor for enabling the second processor to execute the sendable routine;

a set of instructions for modifying said received order of the image processing routines by grouping said sendable routines into at least one set of successive sendable routines to send to the second processor, said set of successive sendable routines requiring fewer data transfers to the second processor than when sending each sendable routine separately to the second processor;

a set of instructions for replacing, in said modified order, a particular set of successive sendable routines with a single alternative routine for performance by the second processor; and

a set of instructions for executing the plurality of image processing routines according to the modified ordering using the first processor and the second processor to produce the particular effect, said executing comprising sending the alternative routine to the second processor and receiving from the second processor an output of the alternative routine.

29. The non-transitory computer readable storage medium of claim 28, wherein the set of instructions for identifying sendable routines comprises a set of instructions for using a look-up table with listings of routine identifiers of routines that are able to be processed by the second processor.

30. The non-transitory computer readable storage medium of claim 28, wherein the set of instructions for modifying the received order comprises a set of instructions for moving a first sendable image processing routine in the order so that the first sendable image processing routine is executed directly after a second sendable image processing routine, wherein the first sendable image processing routine uses output of the second sendable image processing routine as input.

31. A non-transitory computer readable storage medium storing a computer program for optimizing execution of a set of media editing routines on a processor using a particular cache, the computer program comprising:

a set of instructions for receiving an ordering for the set of media editing routines which when executed produces a particular effect, each media editing routine for processing input data retrieved from the particular cache to produce output data that is stored to the particular cache, a plurality of media editing routines in the set of media editing routines specified by a user through a user interface in a particular order to transform one or more source media into an output media;

a set of instructions for repositioning, for each particular media editing routine in a subset of the set of media editing routines, the particular media editing routine after an identified media editing routine within the set of media editing routines when the identified media editing routine produces output data in the particular cache that is retrieved as input data of the particular media editing routine in order to create a repositioned ordering, wherein the repositioned ordering comprises (i) a first image processing routine for processing input data of a first frame and storing output data to the particular cache, (ii) a second image processing routine for processing input data of a second frame and storing output data to the particular cache without overwriting the output data of the first image processing routine stored to the particular cache, and (iii) a third image processing routine for processing the output data of the first image processing routine from the particular cache and the output data of the second image processing routine from the particular cache to produce output data of the third image processing routine that is stored to the particular cache; and

a set of instructions for executing the set of media editing routines based on the repositioned ordering to produce the particular effect.

32. The non-transitory computer readable storage medium of claim 31, wherein the repositioned ordering optimizes processing time for the received ordering by having fewer cache overflows than when executing the received ordering.

33. The non-transitory computer readable storage medium of claim 31, wherein the computer program further comprises a set of instructions for providing a graphical user interface of a media application for users to specify the ordering for the set of media editing routines.