Image processing system and method employing a threaded scheduler

This application claims priority from U.S. Provisional Application 60/752,423 for an “Image Processing System and Method Employing a Threaded Scheduler,” by P. Emmett et al., filed Dec. 21, 2005, which is also hereby incorporated by reference in its entirety.

A methodology is disclosed for an image processing system, and more particularly, a threaded scheduler providing compact and efficient dataflow as a pipeline management and data flow layer for use with an image processing platform.

U.S. Pat. No. 6,286,026, for a “Method and Apparatus for Integrating Pull and Push Tasks in Pipeline Data Processing,” by D. L. Venable et al. (Sep. 4, 2001), hereby incorporated by reference in its entirety, teaches a device and method for processing data with a data processing string having push type and pull type tasks.

In a chunk-based image processing pipeline there needs to be a system to process each chunk of data by each processing step in an efficient manner. This system needs to control the flow of the chunks as well as the order of execution of the processing steps.

A threaded scheduler, as disclosed herein, breaks up an image processing pipeline into a collection of traces, which are a sequence of processing steps or “engines”. This collection of traces is processed by one or more threads as each trace's “engines” become scheduled for execution. At the execution of each “engine”, data chunks are taken from upstream “engines” and processed by the “engine”. Resulting data chunks are then passed to downstream “engines”. This taking/passing of chunks may schedule or block the execution of additional “engines” based on the arrival of data or the triggering of limits on links between “engines.”

The Engines platform provides many powerful image processing operations in a very modular and dataflow neutral system. Although the dataflow neutral aspect is powerful, by providing integration with various dataflows, it poses a problem if one doesn't have a dataflow. The disclosed system and method fills this void by providing a compact and efficient dataflow for use with the Engines platform.

One of the disclosed embodiments processes data in chunks and supports any type of data that Engine does, including such types as compressed data. It also supports the efficient buffer management of Engines by allowing chunks to migrate down a pipeline, reducing the need for copies and re-buffering of data. The disclosed embodiments can handle simple linear pipelines to more complex pipelines, described with Directed Acyclic Graphs or DAGs, with multiple branches and joins. In accordance with the embodiment, a DAG my be made dynamically or on the fly using calls to add nodes and lines or the DAG may be saved and loaded using an extensible markup language (XML) based description. The embodiment disclosed below also supports the concept of DAGs within DAGs, by providing the ability to encapsulate a sub-DAG within a node of a larger DAG. This powerful feature allows for “code reuse” at the DAG level by having a useful DAG reused in a larger operation.

Disclosed in embodiments herein is a method for processing image data, comprising: defining a multi-trace directed acyclic graph, including breaking a directed acyclic graph for processing image data into a plurality of traces, wherein each trace is a fragment of the directed acyclic graph; and executing the multi-trace directed acyclic graph wherein each trace is executed in a separate thread.

Also disclosed in embodiments herein is a system for processing image data in a networked computing environment, comprising: an image data source; a host system, connected to said image data source via the network, wherein said host system includes an image processing pipeline, said pipeline operating on chunks of image data from said source; and memory for storing said chunks of image data during and upon completion of the data by the pipeline.

Disclosed in a further embodiment herein is an image processing pipeline, comprising: a client layer; an dataflow layer, said dataflow layer including at least one interface and service to describe, run, and feed the image-processing pipeline; and an Engine layer, wherein said dataflow layer controls the operation of at least one node in said Engine layer.

FIG. 1 is a general illustration of a directed acyclic graph in accordance with an aspect of the disclosed system and method;

FIG. 2 is an partial illustration of a network architecture in an embodiment of the systems and methods disclosed herein;

FIG. 3 is a simple flow diagram illustrating a processing pipeline in accordance with embodiments of the systems and methods disclosed herein;

FIGS. 4A and 4B illustrate examples of the manner in which the dataflow scheduler manages traces and any associated chunks of image data;

FIGS. 5 and 6 are state diagrams illustrating the general operation of the scheduling and mapping operations for the disclosed system and method; and

FIG. 7 is an exemplary representation of a flow diagram illustrating stages of a buffer mapping operation in accordance with the disclosed system and method.

As used herein the term “DFlow” is employed to characterize a pipeline management and data flow layer for use with Engines. Prior to the creation of DFlow, the responsibility for connecting multiple Engines together fell to the client. With DFlow, any client may easily construct and execute Engine based image processing pipelines. The acronym DAG refers to a Directed Acyclic Graph, which is generally a graph of nodes linked together, typically where no output from one node is feed back into the node, directly or indirectly. The term “pipeline” refers to an executable DAG of Engines. A “scheduler” is an object capable of selecting tasks from a list and performing them in a reasonable order. A “chunk” is a portion of a data stream. A chunk may contain all or some of an entire stream object, and in accordance with an embodiment disclosed herein, a chunk contains an integral number of image scanlines. An Engine chunk (XEngChunk) is a structure that contains a description of a particular buffer and its contents. A “trace,” given an ordered set of tasks that may branch and join (a DAG), is one possible way to traverse the task list such that all tasks are given an opportunity to run before any task is repeated. A trace may be built with an execution order in which a source runs first, then the Engine using the output of the source, then a third Engine using the output of the second, etc. A single trace may represent an entire DAG or multiple traces may be created to divide the DAG into pieces. Each trace may be executed simultaneously and asynchronously in different threads.

As set forth above the system and method disclosed herein can handle simple linear pipelines to more complex pipelines, often referred to as DAGs, including DAGS with multiple branches and joins and those with DAGs within DAGs. In one embodiment, the methods described herein may be implemented in computer software (code) and may be used to operate a computer system such as a Linux, Windows, Solaris or a Mac OSX computer platform suitable for running Engines or the like.

An example of a DAG 100 is depicted in FIG. 1 , where a series of nodes 110 are employed to represent various operations. Referring also to FIG. 2 , at a more detailed level the system provides a monolithic dataflow layer 210 for Engines because the dataflow logic, and code, is not spread across individual processing nodes. Instead, the nodes do not talk to each other but to a single instance of the scheduler 220 . Also included within the dataflow layer 210 are a DAG Manager 250 and a Buffer manager 270 . DAG Manager 250 allows the client to describe the nodes and edges of a DAG, where the nodes represent the Engines and the edges represent the data flow links between them. The Buffer Manager 270 is responsible for handling the chunk buffers: migratable, non-migratable, and client-owned.

The scheduler 220 is responsible for dividing the DAG into executable traces and then creating threads to run the traces, and therefore has the job of communicating with the nodes 110 , moving data between them and determining when an Engine should be executed to process more data. In essence the scheduler 220 moves down the list of nodes, executing them when they have work to do and moving the resulting chunks (not shown) to other nodes based on where the links 230 point. This approach, of having the dataflow in one object, matches well with the modular nature of Engines.

The dataflow layer 210 provides a data flow package that resides between the client ( 208 ) and the Engine ( 212 ) layers. It contains all the necessary interfaces and services to describe, run, and feed an image-processing pipeline.

A client could use the dataflow layer 210 in a variety of ways, but there are some consistent steps. Every client must start by creating a new instance of the object and end by deleting that instance. An instance of the object may be reused any number of times before it is ultimately deleted.

One example of a client could be a DAG Editor. This type of client would use a DAG Manager API to create a DAG description and then have save the description to an XML file to be used later. Another example of a client could be a pipeline server 310 as generally illustrated by the operations depicted in FIG. 3 . The pipeline server would receive an XML 320 file from a remote user, load the XML 330 into an instance, run the pipeline 340 , and return the results 350 to the remote user. The system and method disclosed herein contemplate a client used by Engine and pipeline developers that would have many of these features combined. Such a system would allow the developer to edit the DAG, run the pipeline, perform pipeline debugging, and collect performance statistics.

While the disclosed system and method can execute a DAG as a complete unit, the disclosed systems and methods further contemplate a more powerful execution option—breaking a DAG 100 up into traces 120 . Each trace is merely a fragment of the complete DAG 100 . With a multi-trace DAG each trace is executed in a separate thread. This single DAG then has the ability to utilize more then one processor in a multi-processor system. It may also be useful on a single processor system where an Engine is waiting on a task to complete, such as an outside piece of hardware, disk, network, coprocessor, etc., and the host processor could be doing more work elsewhere on the DAG.

Currently there are two ways to fragment a DAG into traces. One is automatic and the other is manual. In the automatic embodiment, a new trace is created for each source Engine finds (readjpg, pattern, etc.), and then grows that trace by following the links out from that Engine. The manual embodiment requires the DAG developer to set a “threadbreak” on selected links (e.g., 230 ) in the DAG. This “threadbreak” will cause the DAG to fragment, and form a new trace, at this link.

Using the present system and method, it is possible to leverage the broad image processing available with Engines, providing an efficient and easy to use dataflow. With direct support for Engines, the full features of Engines can be exploited, without the need to handle the complex aspects of the dataflow.

In accordance with an embodiment of the present system and method, the threaded scheduler 220 breaks up an image processing pipeline into a collection of traces, which are a sequence of processing steps or “engines.” A trace is started at each source “engine” and continues to the downstream “engines” until no remaining “engines” are available. “Engines” that already belong to a trace or are past a thread break are not added and followed. Generally, a thread break is a user settable hint on the pipeline that indicates a desired break point.

Referring next to FIGS. 4A and 4B , which depict functionality of the dataflow scheduler 220 , the collection (waiting list 440 ) of traces 410 is processed by one or more threads 420 as each trace's “engines” become scheduled for execution by the scheduler. At most, there are as many threads as there are traces. The threads efficiently wait on the traces to be scheduled for execution. When a trace being waited on is scheduled for execution, counter 450 (nReady) is incremented. The counter indicates how many Engines are ready to execute. Subsequently, a thread awakens and takes the trace. The thread processes the trace's “engine” 460 sequence in order until the end and places the trace back into the waiting list 440 . The thread then returns to waiting on the trace list.

At the execution of each “engine”, data chunks 476 are taken from upstream “engines”. All output queues 480 that are below a user settable level are provided with an empty chunk, the others are “plugged” with a zero sized chunk to prevent output. These chunks are then processed by the “engine” 460 . Resulting data chunks are subsequently passed to downstream “engines” 460 . Any unprocessed input chunks 476 are returned to their respective input queue 480 (see also waiting list 440 in FIG. 4A ). If this “engine” consumed or produced any chunks then it is scheduled for execution. If the removal of the upstream chunk caused the output queue of the upstream “engine” to go below a user settable level then that “engine” will be scheduled for execution by marking its trace ready and adjusting the nReady counter accordingly. If the passing of the downstream chunk caused new data to arrive at the downstream “engine” then that “engine” will be scheduled for execution

To increase the efficiency of the chunk passing, the chunks are owned by the scheduler and can migrate down the pipeline without being copied. This also allows the chunks to queue up where necessary with no additional copying. If a chunk gets branched and sent to one or more “engines” it will be marked read only and sent along with its reference count increased accordingly. The scheduler tracks the references to the chunks and frees and/or reuses the chunks when needed.

Having described the general operation of the dataflow scheduler and several examples of functionality of a system or method employing the various elements described, attention is now turned to providing more detail relative to an embodiment of the system and method. As described herein, various aspects are implemented in an object oriented design in ANSI C to match the existing Engine design and language constraints.

The system and method give the client layer the ability to describe an image processing pipeline, save that description in memory (RAM, magnetic media, etc.), load a previously saved description from memory, run the currently loaded description, and extract performance statistics. The client may choose to run a pipeline using one of the following methods:

Non-interactive: Describe, Run, Wait for completion. This would be typical for a pipeline server that is handed a complete DAG and asked to execute it to completion. Interactive build: Run, Describe and test at each step, wait for completion. This method might be used by a client for a DAG that would change its shape depending on the type of image to be processed. For instance, an Engine that splits an image into its component channels doesn't know how many outputs it will have until it sees the actual image to be split. It could be RGB (3), CMYK (4), or have any number of additional tag channels (n). Chunked stream: Describe/Run, then Feed and Retrieve chunks interactively as indicated above relative to FIG. 4 . A client that receives the input image as a chunked stream (like a web server) may wish to begin processing and return output without having to buffer the entire image. This is particularly important when running on a limited memory system where the size of a single frame buffer may exceed the total available RAM.

The client may also choose to run the directed acyclic graph in one of three threading modes:

Client Thread: The client must call the DFlow_Process method to allow the DAG to execute. This would be necessary for an interactive pipeline debugger as well as on a platform that does not support threading. Limited Threads: The Scheduler will create up to a specified number of threads and run the DAG with those threads. This would be appropriate on a system with limited computing resources where the client wishes to prevent DFlow from monopolizing the CPU. This might also be a good idea for a pipeline server where many instances of DFlow may need to share the system resources. Unlimited Threads: The Scheduler will create as many threads as needed to have at least one thread per trace. This would be the normal mode of operation for a system requiring maximum performance. However, it is important to note that a DAG is most efficient with a few, well-selected traces.

There are several major classes employed in a system as described herein. The primary object is referred to as DFlow. A single DFlow can host a single DAG. If a client desires to have multiple concurrent DAGs, it may create multiple instances of DFlow. A DFlow object contains the collection of Engine instances, the links between them, and a scheduler object for running them. The methods of DFlow define the client API. They allow the client to create and edit a DAG description, run the pipeline, and retrieve performance and success statistics. Another class is XFEng, which represents a node in the pipeline graph. An XFEng contains the details of the node's name and parameters. Once the pipeline is running, it also holds the actual Engine instance, performance statistics, and buffer management structures. XFLink is an edge in the pipeline graph. An XFLink contains buffers that are in transition between Engines and in some cases between scheduler threads. XFBuf represents a buffer holding stream data. An XFBuf contains an XEngChunk along with enough information to chain XFBufs into a list and free them when they're done. An XFBuf may hold a chunk allocated by the DFlow layer, by an Engine, or by the client. The XFBufMgr is an XFBuf allocator class. An XFBufMgr can create XFBuf objects, free them and other tracking details. An example of the XBUf instance is the buffer manager 270 of FIG. 2 . The XFScheduler represents a class responsible for creating XFThreads for executing XFTraces. Threads are controlled based on the maxThreads value set by the client and the actual number of traces. Lastly, XFParams are a class responsible for managing parameter sets and translating parameter templates into actual parameter lists. A client that creates or loads a pipeline description containing macros (a parameter template) must also provide a macro substitution list at runtime.

DFlow is the top-level object and presents the client API. DFlow has many public methods, but no public data members. To enforce this restriction in ANSI C, DFlow is implemented as an opaque structure. The following table (Table A) characterizes the DFlow Data members:

Furthermore, the following tables provide further characterization of the DFlow structure: Table B characterizes the DFlow methods and objects, Table C characterizes the DAG Manager functionality; Table D characterizes the characterizes the Pipeline Runner function; Table E characterizes the Port Interface.

Having described the DFlow object in general, the Detailed Dynamic Model will now be set forth and described with reference to FIG. 5 . The DFlow object has five states: Idle ( 510 ), Run ( 520 ), Pause ( 530 ), Complete ( 540 ), and Error ( 550 ). DFlow is initialized to the Idle state 510 , and may be moved to the Run state 520 at any time by calling the DFlow_PipeRun method. DFlow will not return to the Idle state until DFlow_PipeCleanup is called.

When in the Run state 520 , DFlow will create new scheduler traces and start running. All sources will be initialized along with the Engines they feed. Data will begin flowing down the pipeline. The data flow will block if it reaches an unconnected output. The client may add new Engines to unconnected outputs at any time, thus allowing the dynamic construction of a pipeline. The client may not remove or alter an individual Engine once it has been initialized since the stream cannot be “rewound” and reprocessed with a new Engine. New sources may, however, be added at any time while in the Run state.

From the Run state 520 , DFlow may move to Idle 510 , Pause 530 , Complete 540 , or Error 550 . DFlow_PipeCleanup will cause a return to Idle. DFlow_PipePause will set the Pause state. The completion of all Engines will set the Complete state 540 . The error of any Engine will set the Error state 550 . DFlow will remain in Pause until the client calls DFlow_PipeRun to continue processing or DFlow_PipeCleanup to return to the Idle state 510 . DAG changes in the Pause state 530 have the same restrictions as in the Run state 520 . Lastly, DFlow will remain in Complete 540 , or Error 550 until DFlow_PipeCleanup is called. This allows the client to review the pipeline state if desired. (e.g. for a post-mortem.) All DAG changes are prohibited in the Complete and Error states, 540 and 550 , respectively.

From the functional perspective, when an Engine instance is added using the DFlow_DAGAddXEng method, it is placed in an instance array. If any links are specified as arguments on this call, they are added to the Link array and connected from the outputs of the specified Engine instance(s) to the inputs of the new Engine. When Links are added using the DFlow_DAGAddLink method, they are placed in the Link array. They are also connected to their respective source and destination Engine instances.

As mentioned in the dynamic model described above, new Engines and links may be added to unconnected outputs of the DAG even when DFlow is in the Run state 520 . If this occurs, the dataflow scheduler must regenerate its traces before continuing. Also, recall that an Engine or Link may not be removed once it has been initialized; DFlow_PipeCleanup must be called first.

One problem with dynamically building a pipeline arises when adding a branch to a partially initialized pipeline. Imagine a source feeding a single Engine (not a Sink). When run, the source and Engine will initialize and begin processing the stream. A portion of the stream will move out of the source and into the Engine where it will block due to the unconnected output. In this state, an attempt to add a new Engine that connects to the source (as a tee-branch) will fail because a portion of the stream has already moved out of the source and cannot be repeated.

Having described the dynamic and functional aspects of DFlow, attention is directed to the following information, which is related to the XFEng detailed design. Generally, an XFEng object represents an Engine in the DAG, hosts the Engine instance, and handles its execution state and data flow control.

In the following detailed object model: Table F characterizes the XFEng Data Members; and Table G characterizes the XFEng Methods.

As will be appreciated, the XFEngine employs various internal classes and operations. The XFEngineInfo class (Table H) is filled from information in the XFEng instance. The XFPerfStats class (Table I) is stored within the XFEng class and copied out on request from the client. Table J illustrates the XFStats in accordance with an embodiment of the system described herein.

The XFInput and XFOutput classes, Table K and Table L, respectively, are use to handle the mapping of Engine input and output ports into DFlow. In one embodiment there is exactly one XFInput or XFOutput instance for each input or output chunk on the Engine, although it may be conceivable that alternative arrangements may be useful. Each instance of XFInput holds a reference to an XFLink, a private header copy, an event to use instead of the trace event and a port name. Each instance of XFOutput holds a reference to an XFLink, a reference to the output header, an event to use instead of the trace event, a busy chunk and a port name.

In the detailed dynamic model, for example as depicted in FIG. 6 , the XFEng class has six states. The edges shown are for normal operation. It is also possible to return to Idle from any state by calling Cleanup. The states are as follow:

Idle ( 610 )—The initial state on creation. This is the state before Start and after Cleanup. To Init ( 620 )—The initial state after Start. The instance is ready to be initialized when all of its input headers are available. After initialization, the state will move to No Valid Outputs, Running, or Error as appropriate. No Valid Outputs ( 640 )—The instance has successfully initialized, but has set the “XENG_OUTPUTS_NOT_VALID_SFLAG” flag. It can accept input, but will not produce any output. It will stay in this state until it clears the flag or signals an error. Running ( 660 )—The instance has successfully initialized and cleared the “XENG_OUTPUTS_NOT_VALID_SFLAG” flag. The availability of output headers is determined by the “XENG_OUTPUT_NOT_VALID_OFLAG” flag on each output port. The instance can accept input and may produce output. It will stay in this state until it completes or flags an error. Complete ( 650 )—The instance has consumed the entire input stream and produced an entire output stream. Its process point shall not be called again, but its end point has not been called yet. It will remain in this state until Cleanup is called. Error ( 630 )—The instance has produced an error. Its process point shall not be called again, but its end point has not been called yet. It will remain in this state until Cleanup is called.

An XFEng, in the functional model, is responsible for hosting an Engine instance and managing its state and data flow. To do this, it provides methods to start, run, and cleanup the Engine. To manage the data flow for an Engine, an XFEng must handle the inbound and outbound motion of XFBufs. XFBufs as described below. When the XFEng_Start method is called and the XFEng is in the Idle state 610 , it is moved to the ToInit state 620 . Otherwise, the method returns XF_FAIL.

When the XFEng_Cleanup method is called, the XFEng is cleaned up and returned to the Idle state 610 . When the XFEng_Process method is called, the behavior depends on the current state. The Idle 610 , Complete 650 , and Error 630 states will return immediately. The other states will proceed as depicted, for example, in FIG. 7 .

Referring to FIG. 7 , several stages represent complex activities. The details of those steps are expanded in the following description. In the “Have Required Buffers?” stage 710 , the system analyzes the input and output arrays. If there is no pending input, the Engine did not do any work on its last Process call, and the Engine is not a Source, so it is skipped. If not skipping, and the Engine supports migratable buffers, then migratable buffers are allocated for each output that is not throttled (all downstream links do not want any more data). If an output is throttled, then allocate a NULL migratable buffer. If not skipping and the Engine does not support migratable buffers, then skip the Engine if any busy flags are set or any output is throttled.

Relative to the “Move and/or Free Buffers” stage 720 , an XEngChunk is a buffer descriptor that resides on each input and output “port” of an Engine. As a buffer passes through a port, the description of that buffer is copied into or out of the relevant XEngChunk. Since the descriptor is owned by the Engine, it cannot travel with the buffer. To allow buffer migration, and to track non-migratable buffers, DFlow creates an XFBuf wrapper for each buffer. During the call to the Process point 712 , a reference to the XFBuf is stored in the XEngChunk's User Data field.

After the Process call 712 returns, the inputs and outputs are scanned for buffers that need to be moved and/or freed. Depending on the XENG_MIGRATE_SFLAG, buffer chunks left on inputs may be released. In non-migrate mode, XFBuf_Done is called unless the buffer has been passed through to an output. In migrate mode, the XENG_FINISHED_CHUNK flag indicates that a buffer should be released, otherwise it is left alone.

Non-NULL buffer chunks left on outputs are moved to the output XFLink(s). If an output has multiple branches, then the buffer chunk must be duplicated and distributed appropriately. A further optimization may be implemented when a buffer is marked with the Read Only flag. These buffers may be shared on the downstream branches using a reference counting mechanism.

The held queue is scanned for buffers with their XENG_FINISHED_CHUNK flag set. Any buffers with the flag set are released.

Lastly, at various points, the XFEng needs to pass headers from the Engine's output to the downstream links where they may be read by the next Engine(s) in the pipeline. The actual header is not copied during this process, only a reference is copied.

In one embodiment of the disclosed system and method, an XFLink is the connection between two XFEng instances. The XFLink also contains a thread-safe FIFO (to hold any buffers passing down the pipeline) and references to the source and destination XFEng instances. Given that each XFEng is responsible for getting and putting buffers from/to its links, the source and destination references are used primarily for allowing a link to cleanly remove itself from the pipeline and also to help serialize the links to external storage. The following are more descriptive characterizations of aspects of the XFLink functionality: Table M is a characterization of the XFLink data members; Table N is a characterization of the XFLink methods; and Table O suggests that XFLink contains the XFLinkEnd class.

In the dynamic model of XFLink, when the FIFO contains no XFBufs, XFLink_IsEmpty will return XF_TRUE. When the FIFO contains fewer than wantsDataThreshold XFBufs, XFLink_WantsData will return XF_TRUE, and when there are XF_MAX_DEPTH XFBufs in the FIFO, XFLink_IsFull will return XF_TRUE.

Functionally, XFLink is intended to act as an intermediary between two XFEng instances, either in the same or in independent threads. Each call to query or modify the queue state is protected by a mutex. The PutBuf method will append a new Buf to the tail of the queue. The call will return XF_FAIL if the queue is already full. If the queue is going from empty to non-empty, the downstream Engine is signaled ready to run. The TakeBuf method will remove a Buf from the head of the queue. The call will return XF_FAIL if the queue is already empty. If the queue is going from not wanting to wanting data, the upstream Engine is signaled ready to run.

Considering the XFBuf functionality referred to above, attention is now turned to the detailed design of the XFBuf. An XFBuf is an XEngChunk descriptor with the added ability to be linked into lists and to be returned to a buffer manager. Since an Engine buffer is just a block of memory with no associated descriptor, an XFBuf is created to describe the buffer and travel with it between Engines. An XFBuf is created by an XFBufMgr. The following tables set forth the detailed object model for the XFBuf: Table P characterizes the XFBuf Data Members; and Table Q characterizes the XFBuf Methods.

The XFBuf class does not have any states or state transition events, and an XFBuf is created and owned by an XFBufMgr (see below). The XFBuf is passed around amongst the XFEng instances until it is not needed any more. At that time, the last XFEng will call XFBuf_Done and return the buffer to its owner.

The XFBufMgr is responsible for creating XFBufs and accepting them back when the XFBuf's Done method is called. What happens when Done is called depends on which XFBufMgr created the XFBuf. XFBufMgr is an abstract class. At least two concrete classes shall be derived from XFBufMgr, one for migratable and one for non-migratable buffers. The present system and method further contemplate an additional XFBufMgr that may be created to handle client owned buffers.

Table R, Table S, Table T, Table U, and Table V provide further information relative to the detailed object model for the XFBufMgr. Table R sets forth the data members. Table S indicates that XFMigratableBufMgr adds a data member, whereas XFNonMigratableBufMgr does not add any data members. In Table T, the XFBufMgr defines the indicated methods for the base class. Table U characterizes the virtual methods XFMigratableBufMgr implements, and adds two more, whereas Table V characterizes the virtual methods XFNonMigratableBufMgr implements and also adds two more.

The XFBufMgr class does not have any states or state transition events. Functionally, the two buffer managers will be used in slightly different ways.

If an Engine has set its migratable support flag, the Migratable buffer manager will be called before the Engine's process point in order to provide buffers for each of the Engine's outputs. When the Engine releases the buffer, it will be moved to the downstream link or discarded as appropriate. Alternatively, if an Engine does not set its migratable support flag, the Non-Migratable buffer manager may be called after the Engine's process point to provide an XFBuf wrapper for each new output buffer generated by the Engine. In the case where the buffer coming out the output was passed through from an input, the original XFBuf will be located on that input and reunited with the buffer before passing onto the XFLink.

Attention is now turned to the XFScheduler detailed design. The XFScheduler class is responsible for dividing the DAG into executable traces and then running those traces in zero or more threads depending on the client request. If the client specifies zero threads, then it must call DFlow_Process (which calls XFScheduler_Process) to execute the trace. The object model for the XFScheduler is set forth below in Table W (Members) and Table X (Methods).

The XFScheduler contains three internal classes, XFPerfMonitor, XFThread and XFTrace. Table Y through Table EE set forth the characteristics of these internal classes.

The XFScheduler has three states based on its control setting:

Stop—Stop and join all threads, delete all traces. Single Step—Create traces and threads, call XFTrace_Process with the Single Step flag set. This means that the trace can be rescheduled to a new thread after running only one Engine. It also means that the traces will respond to the stop condition quickly. One Loop—Create traces and threads, call XFTrace_Process with the Single Step flag clear. This means that the trace will run all of its Engines before being rescheduled or responding to the stop condition.

Functionally, when DFlow is placed in the Run state, one or more scheduler traces are created to execute portions of the DAG. A number of threads are created to execute the traces from the trace pool. The lesser of the number of traces and maxthreads determines the number of threads to create.

If maxThreads is 0 or 1, all Engines are placed in a single trace. To create scheduler traces, DFlow follows these steps:

1) Create a new trace object. 2) Search the Engine list for an unscheduled Source (an Engine with zero inputs). If there are no sources but still unscheduled Engines, then search for a ThreadBreak leading to an unscheduled Engine. Add the selected Engine to the current trace. If no unscheduled Engines can be located, then exit after discarding an empty trace object. 3) Follow the links from that Engine and add each Engine to the trace until hitting a Sink, ThreadBreak, or previously scheduled Engine. (Note: ThreadBreaks are only respected in the multi-thread case.) If any given Engine has multiple outputs, queue up the other outputs to be followed later on within this trace. Once all branches have been followed to completion, this trace is complete. 4) If this is the multi-trace mode, create a new trace object. Otherwise, reuse the current trace. 5) Go back to (2).

The method for executing traces differs between the client thread mode and the independent thread modes. In the client thread mode, since no threads are created, the scheduler cannot do anything independently. It must wait until the client calls DFlow_Process, which then calls XFScheduler_Process, which then calls XFTrace_Process. In the limited-thread mode, the scheduler creates up to maxThreads threads (but no more than there are traces). Those threads take the trace from the head of the list, execute it in the mode specified by the scheduler control (SingleStep or OneLoop), return it to the tail of the list, and repeat. And, in the unlimited-thread mode, the scheduler creates the same number of threads as there are traces. These threads each execute a single trace. Note that unlimited mode is simply the limited mode with no maxthreads restriction. The same thread-trace assignment model is used.

To kill traces, the control flag is set to Stop. The next time a thread returns to the scheduler to exchange its trace, it will exit. The thread that called XFScheduler_SetCtrl(Stop) will block until all threads have joined or a timeout occurs. It should be appreciated that the unusual selection of types for the head and tail pointers in the Trace queue is intended as an optimization. It eliminates all but one test from the append and remove operations.

Init (New):

head=NULL; tail=&head;

Append (PutTrace):

*tail=trace; tail= &trace->next; trace->next=NULL;

Remove (TakeTrace):

*pTrace=head; head=head->next; if (!head)

tail=&head;

(*pTrace)-&gt;next=NULL;</screen>

Lastly, XFParams is a class responsible for keeping track of an XFEng's parameter set as well as translating a parameter template into an argument list compatible with an Engine Init function. The XFParams class provides the methods for parsing the parameter template string, but the client must provide an ArgList containing the mappings between any value macro names and their actual values.

Using the XFParams class takes several steps:

1) Create a set of parameters or templates using XFParams_Add or by loading an XML pipeline description. The DFlow client will do this. 2) Create an instance of XFParamMap from an ArgList style macro substitution list. The DFlow client must supply the ArgList when calling DFlow_PipeRun, DFlow will convert it to an XFParamMap. 3) Call XFParams_CreateArgv to create the final ArgList to be handed to an Engine's Init method.

The following tables (Table FF-Table KK) characterize the detailed object model for the XFParams (e.g., XFParams is a renamed instance of XFArray, the array holds objects of type HXFParam):

The XFParams class does not have any states or state transition events. However, functionally XFParams provides two methods of parsing a parameter template set. CreateArgv takes a parameter set as an input and converts it to an Engine style ArgList. It also detects macros in the parameter set and inserts appropriate references to the actual values when building the ArgList. GetArgDesc takes a parameter set as an input and locates all the macros. The compiled set of macros is then exportable as an argument descriptor list.

It may also be noted that, from a data structure perspective, the disclosed method and system contemplate that the DFlow DAG may be serialized to an XML file. Further contemplated herein is the addition of a DAG “Expert”. For example, a callback system may be implemented where registered “Experts” will be given the opportunity to modify a DAG prior to it executing. Examples of possible “Experts” include: an auto-formatting module that will insert the correct engines to account for required image formats to other engines; and an auto-thread breaking module that will insert thread breaks such that the DAG executes more efficiently on the given platform (especially multi-CPU/core systems).

It will be appreciated that various of the above-disclosed and other features and functions, or alternatives thereof, may be desirably combined into many other different systems or applications. Also that various presently unforeseen or unanticipated alternatives, modifications, variations or improvements therein may be subsequently made by those skilled in the art which are also intended to be encompassed by the following claims.