Rendergraph compilation method and use thereof for low-latency execution

A graph is compiled that defines a data flow from input(s) to output(s) for images. The data flow includes one or more filters to be applied to the images. Compiling the graph includes forming an assemblage of kernel invocations for the data flow and forming a mapping between kernel invocations in code for the one or more filters and the assemblage of kernel invocations. For multiple ones of a number of frames of images, code in the one or more filters is executed, data is passed into the assemblage to indicate which execution path in the assemblage should be chosen from among a plurality of possible execution paths for one of the filters, wherein the data is determined using at least the mapping and the executing code, and kernel invocations in the indicated execution path are executed. Methods, apparatus, and computer program products are disclosed.

TECHNICAL FIELD

Various embodiments relate generally to the field of image processing and in particular to software frameworks that support image processing operations.

BACKGROUND

Some operating systems have an abstraction layer that hides the complexity of graphics hardware from those exploiting that hardware. These abstraction layers may use various constructs to make programming easier. A render graph (referred to herein as a RenderGraph) is a data structure designed to aid in the computation of image processing operations. It is a graph structure whose nodes, called render actions, each represent one operation executed by the underlying graphics library. These actions are executed by traversing the graph, producing the contents of the frame buffer that is then displayed to the user.

In order to be performant when miming on a GPU (Graphics Processing Unit), the RenderGraph is typically compiled into a single GPU shader. Such a GPU shader may be called an uberKernel. A RenderGraph may also be compiled to run on a CPU, and in this case the uberKernel is a CPU shader or CPU code. In the instant context, the term uberKernel means, e.g., an assemblage of kernel invocations, where “uber” means “over” as this is the controlling code that calls other code. With regard to a GPU shader example, the uberKernel contains kernel code to invoke the image processing filters that the RenderGraph invokes from the framework.

A difficulty arises because the execution sequence within the uberKernel can change from frame to frame as a result of changes to, e.g., image filter parameters. For a concrete example, consider a HighlightAndShadow filter that reduces shadows and increases highlights. This filter takes two parameters, shadows and highlights, with values from 0.0 to 1.0. Depending on the values of these parameters, two (both shadows and highlights), one (either shadows or highlights) or zero (neither shadows nor highlights) invocations of filter processing kernels may be invoked by the RenderGraph. As a result, the uberKernel may need to invoke different kernel code on different frames. A problem that needs to be solved is how to allow different uberKernel control flow on different frames without burdening the runtime execution with unacceptable overhead.

BRIEF SUMMARY

This summary is merely exemplary and is not intended to be limiting.

An exemplary embodiment is a method, comprising: compiling a graph that defines a data flow from one or more inputs to one or more outputs for images, wherein the data flow includes one or more filters to be applied to the images, and wherein compiling the graph comprises forming an assemblage of kernel invocations for the data flow and forming a mapping between kernel invocations in code for the one or more filters and the assemblage of kernel invocations; and for multiple ones of a plurality of frames of images, executing code in the one or more filters, passing data into the assemblage to indicate which execution path in the assemblage should be chosen from among a plurality of possible execution paths for one of the filters, wherein the data is determined using at least the mapping and the executing code, and executing kernel invocations in the indicated execution path.

An exemplary apparatus includes one or more processors and one or more memories including computer program code. The one or more memories and the computer program code are configured to, with the one or more processors, cause the apparatus to perform at least the following: compiling a graph that defines a data flow from one or more inputs to one or more outputs for images, wherein the data flow includes one or more filters to be applied to the images, and wherein compiling the graph comprises forming an assemblage of kernel invocations for the data flow and forming a mapping between kernel invocations in code for the one or more filters and the assemblage of kernel invocations; and for multiple ones of a plurality of frames of images, executing code in the one or more filters, passing data into the assemblage to indicate which execution path in the assemblage should be chosen from among a plurality of possible execution paths for one of the filters, wherein the data is determined using at least the mapping and the executing code, and executing kernel invocations in the indicated execution path.

An exemplary computer program product includes a computer-readable storage medium bearing computer program code embodied therein for use with a computer. The computer program code includes: code for compiling a graph that defines a data flow from one or more inputs to one or more outputs for images, wherein the data flow includes one or more filters to be applied to the images, and wherein compiling the graph comprises forming an assemblage of kernel invocations for the data flow and forming a mapping between kernel invocations in code for the one or more filters and the assemblage of kernel invocations; and code, for multiple ones of a plurality of frames of images, for executing code in the one or more filters, for passing data into the assemblage to indicate which execution path in the assemblage should be chosen from among a plurality of possible execution paths for one of the filters, wherein the data is determined using at least the mapping and the executing code, and for executing kernel invocations in the indicated execution path.

A further exemplary embodiment is an apparatus, comprising: means for compiling a graph that defines a data flow from one or more inputs to one or more outputs for images, wherein the data flow includes one or more filters to be applied to the images, and wherein the means for compiling the graph comprises means for forming an assemblage of kernel invocations for the data flow and means for forming a mapping between kernel invocations in code for the one or more filters and the assemblage of kernel invocations; and means for executing code in the one or more filters, means for passing data into the assemblage to indicate which execution path in the assemblage should be chosen from among a plurality of possible execution paths for one of the filters, wherein the data is determined using at least the mapping and the executing code, and means for executing kernel invocations in the indicated execution path, wherein the means for executing code, means for passing data, and means for executing kernel invocations are used for multiple ones of a plurality of frames of images.

DETAILED DESCRIPTION OF THE DRAWINGS

For ease of reference, the present disclosure is divided into sections.

Before proceeding with additional description of problems with conventional systems, reference is made toFIG. 1, which shows a block diagram of an exemplary system in which the exemplary embodiments may be practiced. InFIG. 1, a UE110is in wireless communication with a network100. The user equipment110includes one or more processors120, one or more memories125, and one or more transceivers130interconnected through one or more buses127. The one or more transceivers130are connected to one or more antennas128. The one or more memories125include computer program code123. The UE110communicates with eNB170via a wireless link111.

The UE also includes an operating system135. As part of the operating system135, an image framework136is included, and this image framework136may be considered to implement the exemplary embodiments herein. The image framework136can be separate from the operating system135, but typically is not. In an exemplary embodiment, the one or more memories125and the computer program code123are configured to, with the one or more processors120, cause the user equipment110to perform one or more of the operations as described herein. For instance, the operating system135and the image framework136would be computer program code123and the one or more processors120would execute portions of these in order to perform operations as described herein. In another exemplary embodiment, the image framework136(e.g., and the operating system135) may be implemented by hardware such as an integrated circuit or a programmable gate array. Additionally, the exemplary embodiments can be implemented in part by using computer program code123(executed by a hardware processor120) and in part through hardware.

An application137is also shown in the UE110. The application uses the image framework136in order to cause the UE110to display images on a display. A display is shown inFIG. 2.

The eNB170includes one or more processors150, one or more memories155, one or more network interfaces (N/W I/F(s))161, and one or more transceivers160interconnected through one or more buses157. The one or more transceivers160are connected to one or more antennas158. The one or more memories155include computer program code153. The one or more memories155and the computer program code153are configured to, with the one or more processors150, cause a corresponding one of the eNBs170to perform one or more of the operations as described herein. The one or more network interfaces161communicate over a network such as by using the interfaces172and131. Two or more eNBs170communicate using, e.g., interface172. The interface172may be wired or wireless or both and may implement, e.g., an X2 interface. The eNB170may communicate with a core network via the interface131.

The computer readable memories125and155may be of any type suitable to the local technical environment and may be implemented using any suitable data storage technology, such as semiconductor based memory devices, flash memory, magnetic memory devices and systems, optical memory devices and systems, fixed memory and removable memory. The processors120and150may be of any type suitable to the local technical environment, and may include one or more of general purpose computers, special purpose computers, microprocessors, digital signal processors (DSPs) and processors based on a multi-core processor architecture, as non-limiting examples.

In general, the various embodiments of the user equipment110can include, but are not limited to, cellular telephones such as smart phones, tablets, computers, personal digital assistants (PDAs), portable computers, image capture devices such as digital cameras, gaming devices, music storage and playback appliances, Internet appliances permitting wireless Internet access and browsing, as well as portable units or terminals that incorporate combinations of such functions. Basically, the user equipment110may be any electronic device that displays images. Additionally, although the user equipment110is shown operating wirelessly, the user equipment110may operate using a wired network or with no network.

FIG. 2illustrates further detail of an exemplary UE110in both plan view (left) and sectional view (right). As shown inFIG. 2, the UE110includes a graphical display interface (e.g., touchscreen)20and a user interface that comprises a microphone24and speaker(s)34and touch-screen technology at the graphical display interface20and/or voice-recognition technology for audio signals received at the microphone24. A power actuator26controls the UE110being turned on and/or off by the user. The UE110may include a camera28A, which is shown as forward facing (e.g., for video calls) but may alternatively or additionally be rearward facing28B (e.g., for capturing images and video for local storage). The camera(s)28A and28B (called camera(s)28collectively) may be controlled by a shutter actuator30and optionally by a zoom actuator32, which may alternatively function as a volume adjustment for the speaker(s)34when the camera28is not in an active mode. These actuators may also be implemented using touch-screen technology.

Within the sectional view ofFIG. 2are seen multiple transmit/receive antennas128that are typically used for wireless communication (e.g., cellular communication). The antennas128may be multi-band for use with other radios in the UE. The operable ground plane for the antennas128may span the entire space enclosed by the UE housing, though in some embodiments the ground plane may be limited to a smaller area, such as disposed on a printed wiring board on which a power chip38is formed. The power chip38controls power amplification on the channels being transmitted on and/or across the antennas that transmit simultaneously, where spatial diversity is used, and amplifies received signals. The power chip38outputs the amplified received signal to the radio frequency (RF) chip40, which demodulates and downconverts the signal for baseband processing. The baseband (BB) chip42detects the signal, which is then converted to a bit-stream and finally decoded. Similar processing occurs in reverse for signals generated in the UE110and transmitted from the UE.

Signals to and from the camera(s)28pass through an image/video processor (video)44, which encodes and decodes the image data (e.g., image frames). A separate audio processor46may also be present to control signals to and from the speakers (spkr)34and the microphone24. The graphical display interface20is refreshed from a frame memory (frame mem)48as controlled by a user GFU50, which may process signals to and from the display interface20.

Certain exemplary embodiments of the UE110may also include one or more secondary radios such as a wireless local area network radio (WLAN)37and/or a Bluetooth radio (BT)39, which may incorporate one or more on-chip antennas or be coupled to one or more off-chip antennas. Throughout the UE110are various memories125, such as a random access memory (RAM)43, a read only memory (ROM)45, and, in some exemplary embodiments, a removable memory such as the illustrated memory card47. In some exemplary embodiments, various programs (as computer program code123) are stored on the memory card47. The components within the UE110may be powered by a portable power supply such as a battery49.

The aforesaid processors10,38,40,42,44,46, and50are examples of processors120. If such processors38,40,42,44,46, and50are embodied as separate entities in the UE110, these may operate in a master-slave relationship with respect to the main/master processor10. Exemplary embodiments need not be disposed in a central location, but may instead be disposed across various chips and memories as shown or disposed within another processor that combines some of the functions described above forFIG. 2. Any or all of these various processors ofFIG. 2may access one or more of the various memories, which may be on-chip with the processor or separate therefrom.

Note that the various processors (e.g.,38,40,42, etc.) described above may be combined into a fewer number of such processors and/or chips and, in a most compact case, may be embodied physically within a single processor or chip. For instance, the main/master processor10and the GPU50may be a single unit (i.e., on one piece of silicon), as illustrated by processor10-1.

2. Additional Description of Problems with Conventional Systems

As noted above a problem that needs to be solved is how to allow different single GPU shaders (called “uberKernels”) on different image frames without burdening the runtime execution with unacceptable overhead. The least performant solution to this problem is to assume that the uberKernel must be completely regenerated on every frame. The result of this choice has been that a system implementing this choice is relatively slow. U.S. patent Ser. No. 13/533,364 “Render Tree Caching”, U.S. Publication No. 2013/0328898 improves upon this by, e.g., the following (see the Abstract):

“GPU fragment programs can be used to render images in a computer system. These fragment programs are generated from render trees, which specify one or more filters or functions to be applied to an input image to render an output image. It is not uncommon for successive frames to require application of substantially the same filters. Therefore, rather than regenerate and recompile new fragment programs for successive corresponding render trees, the render trees are substantially uniquely identified and cached. Thus, when a render tree is received, it can be identified, and this identifier (such as a hash) can be used to determine whether a corresponding fragment program has already been generated, compiled and cached. If so, the corresponding cached fragment program is retrieved and executed. If not, a fragment program for the newly received render tree is generated and cached.”

The U.S. patent Ser. No. 13/533,364 had to perform compilation every frame for a fragment program, and an idea of U.S. patent Ser. No. 13/533,364 was to use previously compiled and stored fragment programs of render graphs for individual frames instead of recompiling the fragment programs.

By contrast, for the instant disclosure, a render graph is compiled once and then used for multiple frames. As described above, the RenderGraph is typically compiled into a single GPU or CPU kernel that is called the uberKernel herein. The uberKernel used for multiple frames, but the RenderGraph is only compiled once.

Turning to the exemplary embodiments herein, broadly exemplary embodiments include an algorithm to pre-generate all of the possible uberKernel execution sequences in a compact way, combined with an efficient mechanism to match each frame to its corresponding execution sequence. In an exemplary embodiment, the pre-generation step occurs at the time the RenderGraph is compiled prior to execution. It is shown that this can be done without an unreasonable increase in code size. At execution time, the only overhead is the cost of associating the current sequence of kernel invocations with the corresponding execution sequence. This is an O(n) operation with a solution based on hashing, and finite state automata (FSA).

In more detail, the context of various embodiments is a framework for image processing operations. A developer defines a RenderGraph that defines a data flow from inputs to outputs. At each node of the RenderGraph, a filter is applied to the inputs to produce the outputs.FIG. 3illustrates a simple example of a RenderGraph300-1with an image source310(NativeCamera) providing images to an Exposure filter320that provides images to an image sink330(NativeDisplay). RenderGraph300-1is one example of a RenderGraph300, and additional examples of these graphs are described below.

OpenCL is used as an example herein. OpenCL (Open Computing Language) is a standard for cross-platform, parallel programming of modern processors found in personal computers, servers and handheld/embedded devices. More generally, OpenCL is a framework for writing programs that execute across heterogeneous platforms including central processing units (CPUs), graphics processing units (GPUs), digital signal processors (DSPs), field-programmable gate arrays (FPGAs) and other processors. OpenCL includes a language for writing kernels (functions that execute on OpenCL devices), plus application programming interfaces (APIs) that are used to define and then control the platforms.

In OpenCL, the requirements for a filter are as follows:An image-valued function of one or more source images and filter parameters;A host-side execute( ) method in C++ that schedules OpenCL functions for subsequent execution;CPU- or GPU-side OpenCL functions compute the filter;unction parameters may be uniforms, pixels or images; and/orHost-side methods include: execute, getParameters, getColorSpace, get/set parameters, num Inputs/Outputs, domainOfDefinition, regionOfInterest.

FIG. 4Ashows a RenderGraph compiler430processing a more complex filter, a highlight shadow filter420, that generates multiple execution sequences. Code440for the highlight shadow filter420is shown inFIG. 4B. The code440has a file name HighlightShadow.cpp (where “.cpp” is an extension for a C++ program, although the exemplary embodiments are not limited to any language). This program conditionally invokes (via the “switch(index)” statement) one of three possible kernel functions depending on the values of the parameters getHighlight( ) and getShadow( ). The kernel functions are shown in part as “_ScheduleKernel”. The variable “index” will be assigned the value of one (if getShadow( ) is greater than 0.0), two (if getHightlight( ) is greater than zero; note that this Boolean result is shifted left by one bit), and three (if both getShadow( ) and getHightlight( ) are greater then 0.0).

This example is a useful illustration to illustrate many of the concepts used herein and is easy to understand. The program has simple flow control, limited to either invoking or not invoking any of a list of kernel functions. In this example, the host-side code440will only invoke one kernel function from the three possibilities, but in general there could be any number of invocations of kernel functions in a single host-side function.

The developer compiles the RenderGraph300-2before the RenderGraph300-2is executed. As previously described, the term RenderGraph refers to an entire data structure in host memory that defines the complete rendering operation. The RenderGraph is in the form of a DAG (Directed Acyclic Graph) with a filter associated with each node of the DAG. The RenderGraph is used during RenderGraph compilation and RenderGraph execution stages. The developer can invoke code (e.g., via application137) to cause the compilation. The RenderGraph300-2in this example has the image source, NativeCamera310, and image sink, NativeDisplay330, fromFIG. 3. However, the filter is HighlightShadow420filter that can perform highlighting, shadowing, or both highlighting and shadowing. A RenderGraph compiler430processes a RenderGraph300(300-2in the example ofFIG. 4A) to produce an uberKernel460and an associated FSA450. The uberKernel460includes execution sequences490. The FSA450is used to map a runtime sequence of kernel invocations to a single execution sequence in the uberKernel. Furthermore, the FSA450may map a hash sequence to an execution sequence as described below.

The exemplary execution sequences490in this example include the following statements470:

The RenderGraph compiler430uses the host-side filter code440, which is written by the filter designer and compiled as part of the filter compilation process. The filter compilation process is described in more detail below. The code440allows the compiler430to determine the different cases in statements470-2,470-3,470-4, and470-5. In particular, the statements470-2through470-5correspond with the statements in the switch selection statement as follows: Statement470-2of Case 0 corresponds to the default statement in the switch selection statement; statement470-3of Case 1 corresponds to case 1 of the switch selection statement; statement470-4of Case 2 corresponds to case 2 of the switch selection statement; and statement470-5of Case 3 corresponds to case 3 of the switch selection statement.

The example ofFIG. 4Aillustrates that a single filter may generate multiple execution sequences. At runtime on each frame, the image framework136selects one of these execution sequences. In order to support this, the compiler430generates in one embodiment an FSA450that maps hash-encoded kernel sequences in the code440to execution sequences490in the uberKernel. The compiler may rewrite the host-side filter code so that kernel invocations use hashed values of kernel names. This allows efficient matching of kernel names without the overhead of string processing.

When the RenderGraph300-2executes, the operations performed for each frame include a host-side filter execution followed by an uberKernel invocation. The host side code440contains calls to function “_ScheduleKernel_( )” that takes as its first argument the name of a kernel function to be schedule, followed by arguments to that kernel function. The name is a string but may be encoded internally as a hash function of the name Within _ScheduleKernel_( ) the kernel function arguments are marshaled for the call to the uberKernel, and the (hashed) kernel name is used to advance the state of the FSA450. When the FSA450reaches an accepting state, the value of a single execution sequence is known, as identified by the id of the accepting state. Once this is known, the uberKernel can be invoked with the specific execution sequence identified by passing the accepting state id (identification) as an argument.

Referring toFIG. 4C, this figure is a state-transition diagram for the FSA450inFIG. 4A. The diagram isFIG. 4Cmay be encoded as a table that is read by the FSA450. The table is generated by the RenderGraph compiler430. The states410include states410-0and410-1, the transition between which is caused by nativeCamera. From state410-1, there are three transitions, caused by highlights, shadows or highlightShadows, to states410-2,410-4, or410-6, respectively. From states410-2,410-4, or410-6there are three corresponding transitions caused by nativeDisplay to the states410-3,410-5, or410-7, respectively.

FIG. 4Dis a finite state automation flowchart for the FSA450inFIG. 4A. The initial state is state0410-0, as indicated by reference475. In block476, the FSA determines whether an input token has been received. Input tokens are received by execution of the code440, and more specifically by a rewritten version of the code440that uses hashed values of kernel names. If an input token has not been received (block496=No), in block496, the FSA waits for the next input token. Blocks476and496are performed until an input token is received. The FSA450receives (block476=Yes) an input token (e.g., the hash encoded representation of “highlights”) and changes its state based on the value of the input token. If the FSA450reaches a terminal state (states3410-3,5410-5, or7410-7in this example) (block480=Yes), the FSA450invokes (block485) the uberKernel and passes into the uberKernel the value of the terminal state. This allows conditional code inside the uberKernel to decide where to invoke kernels based on this state. If the state is not terminal (block480=No), the flow proceeds to block495, where the current state (“State”) is set to the next state using a current value of a state (“state”) and the input token (“token”), e.g., State=nextState(state, token).

Note that in many cases there will be a single execution sequence and so this mechanism can be disabled, resulting in code that runs as fast as hand-written code. For a simple example, suppose there is a single conditional statement in the host side code440that needs to be supported in the uberKernel. This support can be implemented by setting a Boolean variable in the host side code440and passing that into the uberKernel. Extend this to any number of conditional statements by creating an array of Boolean variables. Further compact this array by converting the array into a bit stream, since only one bit is needed per variable.

For instance, an alternative embodiment uses a conditional bit stream in place of an FSA. SeeFIG. 5. In this embodiment, successive bits in the bit stream are set to indicate whether specific invocations of _ScheduleKernel_ are executed within execute( ). The bit stream is passed into the uberKernel where the code examines the bit stream to conditionally invoke the specified kernels.

More specifically,FIG. 5shows exemplary mechanisms of another exemplary embodiment using a bit stream to represent conditional information. During RenderGraph execution, each call to filter::execute( ) makes some number of calls to _Schedule_Kernel_(name). See block510. This function sets a bit in the bit stream520by calling setBit(filterIndex,nameToBit(name)). The function setBit consults a table540that was produced by the RenderGraph compiler430to map filterIndex to a starting position in the bit stream520. The variable filterIndex is itself an index to filters in the code440. The index could be determined by setting an index to zero for the first filter in code440, setting the index to one for the second filter in code440, and the like. The function nameToBit returns a bit position based on the name. In this example, in terms of bit positions relative to the starting bit position, “highlights” corresponds to position 0, “shadows” corresponds to position 1, and “highlightshadows” corresponds to position 2. The function setBit sets the bit at the appropriate location in the bit stream520. In this example, the bit positions (and values) are 1 for highlights, 2 for shadows, and 4 for highlightshadows. Block530illustrates that the uberKernel contains conditional code that examines the bit stream520to make control flow decisions. The control flow decisions are as follows: If the bit stream has a value of 1, highlights( ) is to be executed; if the bit stream has a value of 2, shadows( ) is to be executed; and if the bit stream has a value of 4, highlightshadows( ) is to be executed.

Although the single filter of Highlight Shadow420is being illustrated inFIG. 5, there could be multiple filters of which Highlight Shadow420is only one. Thus, the bit stream520may be part of a larger bit stream550such that the starting bit position560could be non-zero. For instance, the starting bit position could be five, and the setBit sets bits relative to that starting location. The uberKernel conditional code in block530also would be modified to address additional filters.

FIG. 6shows a flowchart of events beginning with filter compilation and continuing through RenderGraph definition, compilation, and repeated frame executions. This figure is a logic flow diagram for a RenderGraph compilation method and use thereof for low-latency execution. This figure also illustrates the operation of an exemplary method, a result of execution of computer program instructions embodied on a computer readable memory, functions performed by logic implemented in hardware, and/or interconnected means for performing functions in accordance with exemplary embodiments. The blocks in the figure may be considered to be interconnected means for performing the functions in the blocks. The blocks are performed by a computer system such as a UE110, e.g., under control at least in part of the image framework136.

Each frame invocation includes host side execution with FSA traversal or bit stream generation followed by uberKernel invocation. In particular, a developer causes the filter(s) to be compiled (block605), then the developer invokes code to cause the RenderGraph to be defined and compiled, which is illustrated in blocks606as “define RenderGraph” and610as “Compile RenderGraph”. Block606generates a RenderGraph607, which is a graph that defines a data flow from one or more inputs to one or more outputs for images. Next the RenderGraph executes for one or more frames. During this the host side filter code440executes and the image framework136traverses the FSA (block620) or generates the bit stream (block620) for a corresponding filter in the executing filter code.

When the FSA reaches an accepting state, the FSA invokes (block630) the uberKernel with the identified execution sequence490. Alternatively, the generated bit stream (or a portion but not all thereof) is passed to the uberKernel. If there is another frame (block640=Yes), execution continues in block620. If there is no other frame (block640=No), the method ends in block650.

Turning toFIG. 7, another logic flow diagram is shown for a RenderGraph compilation method and use thereof for low-latency execution. This figure illustrates the operation of an exemplary method, a result of execution of computer program instructions embodied on a computer readable memory, functions performed by logic implemented in hardware, and/or interconnected means for performing functions in accordance with exemplary embodiments. The blocks in this figure may be considered to be interconnected means for performing the functions in the blocks.

Method700includes blocks705and710and blocks715-765are possible further exemplary embodiments of method700. The method700may be performed by a user equipment110, e.g., under control at least in part by the image framework136. In block705, the user equipment110performs the operation of compiling a graph607that defines a data flow from one or more inputs to one or more outputs for images. The data flow includes one or more filters320,420to be applied to the images. Compiling the graph comprises forming an assemblage of kernel invocations (e.g.,470-3,470-4,470-5) for the data flow and forming a mapping (e.g.,450,520) between kernel invocations in code440for the one or more filters320,420and the assemblage of kernel invocations. The operation of compiling may be performed by a means for compiling.

In block710, the user equipment110, for multiple ones of a plurality of frames of images, performs the operation of executing code in the one or more filters, and passing data into the assemblage to indicate which execution path in the assemblage should be chosen from among a plurality of possible execution paths for one of the filters. The data is determined using at least the mapping and the executing code. Block710also includes executing kernel invocations in the indicated execution path. The executing code may be performed by a means for executing code and the passing data may be performed by a means for passing data.

Block715illustrates another possible exemplary embodiment, where the mapping comprises a finite state automaton450. Blocks720and725are possible examples of block715. In block720, the compiling comprises rewriting code in the one or more filters prior to execution of the code440so that kernel invocations use hashed values of kernel names. Also, the finite state automaton450maps hash-encoded kernel sequences in the code440to execution sequences in the assemblage. In block725, the finite state automaton comprises a plurality of states, at least one of the states corresponds to a certain filter. Block730is a further example of block725, and in block730, the user equipment performs transitioning between states of the finite state automaton based on input tokens corresponding to the executing code. Also, passing data further comprises passing data corresponding to one of a plurality of kernel invocations and to a certain input token for the certain filter to the assemblage. Blocks735and740are examples of block730. In block735, passing data further comprises passing a state identification as an argument to the assemblage (e.g., see block495ofFIG. 4D), wherein the state identification corresponds at least to the certain filter. In block740, passing data further comprises passing the data in response to the finite state automaton reaching a terminal state (e.g.,410-3,410-5,410-7), see blocks480,485ofFIG. 4D.

Block745is another example of method700, where the mapping comprises a mapping from individual filters in the code for the one or more filters to one or more bits in a bit stream (e.g.,520or560). Blocks750,755, and760are examples of block745. In block750, the mapping further comprises a mapping from kernel invocations in the filters to bits in the bit stream. In block755, compiling the graph further comprises determining a table540that maps individual ones of the filters to a starting position (e.g.,560) in the bit stream and using the table to perform mapping from individual filters in the code to the one or more bits in the bit stream. In block760, passing data comprises passing a portion (e.g.,520) of the bit stream (e.g.,560) to the assemblage, the portion corresponding to one of the filters and to selected bits in the bit stream.

In block765, executing code further comprises causing display of one or more images on a display (e.g., 20) of a device (e.g., user equipment110) using at least one of the executed kernel invocations in the indicated execution path. Block765may apply to any of the blocks of method700and blocks715through760.

An apparatus may include means for performing any of the methods of blocks705-765. A communication system may include this apparatus. Another apparatus may include one or more processors and one or more memories including computer program code. The one or more memories and the computer program code are configured to, with the one or more processors, cause the apparatus to perform any of the methods of blocks705-765.

The exemplary embodiments can eliminate all execution-time overhead of selecting and generating the uberKernel at each frame, in exchange for a small cost to traverse the FSA in most cases. As a result, applications that use the imaging framework136can execute nearly as efficiently as if they were written and optimized manually. Thus one technical effect is a speed improvement over conventional techniques.

The cost of this improvement is twofold. First, there is a longer compilation step for the RenderGraph, but since this only occurs once during the run of an application, this is not a serious problem.

Second, there is an increase in the size of the code of the uberKernel. The extent of this increase is partly determined by whether kernel code uses inline functions or function calls. This implies that the effect can be mitigated at the expense of some performance, by making function calls rather than using inline functions.

This increase is also determined by the complexity of the control flow of the part of the image processing filter that runs on the host. In practice, this complexity can be restricted without impacting the ability to write real time image processing filters, and as a result this problem can be kept manageable. For instance, one can require that each kernel invocation be executed no more than once per filter execution without limiting the useful domain of filters that can be written. This allows the RenderGraph compiler to correctly analyze the possible runtime execution sequences for the uberKernel. As another example, one can also allow the developer to specify that every kernel invocation is executed exactly once per filter execution. This makes the problem even simpler and results in a single execution sequence for many RenderGraphs.

In summary, for most applications requiring real time image processing functions the increase in code size will be reasonable, but for some applications with extreme characteristics the code size might be unacceptable.

While described above in reference to processors, these components may generally be seen to correspond to one or more processors, data processors, processing devices, processing components, processing blocks, circuits, circuit devices, circuit components, circuit blocks, integrated circuits and/or chips (e.g., chips comprising one or more circuits or integrated circuits).

The various controllers/data processors, memories, programs, transceivers and antenna arrays depicted inFIGS. 1 and 2may all be considered to represent means for performing operations and functions that implement the several non-limiting aspects and embodiments of this invention.

Without in any way limiting the scope, interpretation, or application of the claims appearing below, a technical effect of one or more of the example embodiments disclosed herein is to improve a speed at which images may be rendered on a computer. Another technical effect of one or more of the example embodiments disclosed herein is lower latency operation for image rendering.

Embodiments of the present invention may be implemented in software or hardware or a combination of software and hardware. In an example embodiment, the application logic, software or an instruction set is maintained on any one of various conventional computer-readable media. In the context of this document, a “computer-readable medium” may be any media or means that can contain, store, communicate, propagate or transport the instructions for use by or in connection with an instruction execution system, apparatus, or device, such as a computer, with one example of a computer described and depicted inFIGS. 1 and 2. A computer-readable medium may comprise a computer-readable storage medium that may be any media or means that can contain or store the instructions for use by or in connection with an instruction execution system, apparatus, or device, such as a computer, but the computer-readable storage medium does not encompass propagating signals.

Although various embodiments of the invention are set out in the independent claims, other examples of the invention comprise other combinations of features from the described embodiments and/or the dependent claims with the features of the independent claims, and not solely the combinations explicitly set out in the claims.