Patent Description:
Aspects of the present disclosure relate to computer processor operation scheduling, and in particular to improved operation scheduling for memory-bound systems.

A large variety of computing processes today involve execution of a number of discrete operations sequentially or in parallel. Scheduling these operations should account for data dependencies (e.g., if particular operations must be completed before certain subsequent operations). Computing systems often utilize memory with fast access, such as caches, tightly-coupled memory (TCM), static random-access memory (SRAM) and the like, to store the associated data needed for execution by each operation. In memory-bound systems, however, there may be insufficient space in these fast-access memories to store the entire sequence of operations and the accompanying data.

Executing such processes on a memory-bound system can reduce performance in a variety of ways. Though some data can typically be stored in fast-access memory such as caches, memory-bound systems often need to rely on larger and slower memories to store the remaining data. Because the larger host memory typically incurs significantly more computational cost than fast-access memories such as SRAM, it is useful to reduce the number of such memory accesses in order to improve the execution of the process. Generally, accesses to the host memory increase power consumption and latency and reduce the overall bandwidth of the computer. An important aspect of scheduling such operations is therefore reduction of memory accesses to the slower memory (e.g., host processing system dynamic random access memory (DRAM)).

Some existing schedulers utilize greedy heuristics and local optimizations toward the goal of developing an optimal schedule that reduces power consumption, latency, and memory accesses. A variety of approaches exist for balancing the competing goals, but such approaches are inherently local and sub-optimal solutions to a problem which is driven by a global structure of the computing process and operations.

Accordingly, what are needed are systems and methods to improve process scheduling in order to perform computer processing more efficiently.

Certain embodiments provide a method for generating execution schedules, comprising receiving a data flow graph for a process, wherein data flow graph comprises a plurality of nodes and a plurality of edges; generating a topological ordering for the data flow graph based at least in part on memory utilization of the process; generating a first modified topological ordering by inserting, into the topological ordering, one or more new nodes corresponding to memory access based on a predefined memory capacity; allocating units of memory in the memory based on the first modified topological ordering; and generating a second modified topological ordering by rearranging one or more nodes in the first modified topological ordering, wherein the second modified topological ordering enables increased parallel utilization of a plurality of hardware components.

Other aspects provide processing systems configured to perform the aforementioned methods as well as those described herein; non-transitory, computer-readable media comprising instructions that, when executed by one or more processors of a processing system, cause the processing system to perform the aforementioned methods as well as those described herein; a computer program product embodied on a computer readable storage medium comprising code for performing the aforementioned methods as well as those further described herein; and a processing system comprising means for performing the aforementioned methods as well as those further described herein.

Accordingly, what are needed are systems and methods to improve process scheduling in order to perform computer processing more efficiently. Further reference is made to <CIT>, disclosing methods, systems, and apparatus, including computer programs encoded on computer storage media, for placement and scheduling of radio signal processing dataflow operations. An example method provides a primitive radio signal processing computational dataflow graph that comprises nodes representing operations and directed edges representing data flow. The nodes and directed edges of the primitive radio signal processing computational dataflow graph are partitioned to produce a set of software kernels that, when executed on processing units of a target hardware platform, achieve a specific optimization objective. Runtime resource scheduling, including data placement for individual software kernels in the set of software kernels to efficiently execute operations on the processing units of the target hardware platform. The resources of the processing units in the target hardware platform are then allocated according to the defined runtime resource scheduling.

In accordance with the present invention a method, and an apparatus is set forth in the independent claims, respectively. Certain embodiments provide a method for generating execution schedules, comprising receiving a data flow graph for a process, wherein data flow graph comprises a plurality of nodes and a plurality of edges; generating a topological ordering for the data flow graph based at least in part on memory utilization of the process; generating a first modified topological ordering by inserting, into the topological ordering, one or more new nodes corresponding to memory access based on a predefined memory capacity; allocating units of memory in the memory based on the first modified topological ordering; and generating a second modified topological ordering by rearranging one or more nodes in the first modified topological ordering, wherein the second modified topological ordering enables increased parallel utilization of a plurality of hardware components.

Aspects of the present disclosure provide apparatuses, methods, processing systems, and computer readable mediums for generating more efficient computer processing operation schedules using graph analysis to minimize memory utilization and improve the computational efficiency of executing the schedules.

Execution of many computing processes can be modeled using graphs where each node in the graph corresponds to a particular operation to be performed, and each edge corresponds to a flow of data among the operations.

For example, to execute a neural network, data can flow among any number of nodes for processing in order to generate a final output. In embodiments of the present disclosure, computing processes can be constructed as directed acyclic graphs (DAGs). A DAG is a directed graph that has no directed cycles (e.g., a graph with nodes and directed edges, where following the directed edges from node-to-node will never result in a closed loop). The "source" of a directed graph may generally refer to some upstream entity or component (just before the first node(s) of the graph) that provides any needed input data for the process, while the "target" is a downstream entity or component (just after the last node(s)) that receives any output from the process. To schedule execution of the process, embodiments of the present disclosure can generate a topological ordering (e.g., a linear ordering of nodes) based on the graph. Generally, a valid topological ordering must ensure that producer nodes (e.g., nodes that generate or otherwise output some data for downstream consumption) are scheduled and executed before any corresponding consumer nodes (e.g., nodes that receive, operate on, or are otherwise dependent on data generated by some upstream entity) begin execution. That is, if there is a directed edge from a first node (a producer) to a second node (a consumer), the first node must appear before the second node in the topological ordering. Notably, a given node may act as both a producer (for one or more downstream nodes) and a consumer (for one or more upstream nodes).

There are often a large number of valid topological orderings for any given graph. Finding an ordering to maximize any particular criteria or property is typically NP-hard. In some embodiments of the present disclosure, topological orderings are created to attempt to minimize storage accesses. By minimizing such storage accesses, the schedule can be executed with reduced latency and power consumption. In an embodiment, each node in the graph may output data that is consumed by zero or more subsequent nodes. Memory or storage is generally allocated (or used) when data is produced by a node, and freed (e.g., the memory space is made available) only when the last consumer completes its processing on the generated data. Thus, in some embodiments, a weighted directed graph is generated to reflect the node dependencies, where each edge corresponds to the units of memory required by the data.

For example, if a given (producer) node outputs <NUM> kilobytes of data to a consuming node, the edge between them may be assigned a weight of <NUM> kilobytes. This allows the system to quantify the total memory that will be needed at any given stage of execution.

Embodiments of the present disclosure provide techniques to generate and modify graphs using appropriate edge weighting to yield a valid topological ordering that seeks to minimize memory utilization in order to reduce the number of accesses to slower storage components. Additionally, embodiments of the present disclosure provide techniques to analyze and modify topological orderings to improve efficiency of the schedule.

In various embodiments, the efficiency gains can include, without limitation, reduced power consumption and latency, increased throughput of the system, and the like. In various embodiments, these scheduling improvements can be applied to improve the operations of a wide variety of processors and processes, including execution of machine learning models.

For a given graph, a cut is a set of edges that, if removed, disconnect the graph (e.g., partition the nodes into two disjoint subsets). As used herein, a minimum cut is a cut that minimizes the cost of the cut. In embodiments, the cost of a cut is defined as the sum of the weights of each edge that is severed or removed by the cut. Thus, a minimum cut is one that completely separates the graph into two disjoint subgraphs, while minimizing the total weight of the removed edges. For example, if a graph is partitioned by removing two edges, each with a weight of ten, the cost of the cut is twenty.

In the case of a directed graph, the cost of a given cut can be determined in part on the directionality of each removed edge and the directionality of the cut. Generally, edges that cross the cut in one direction (e.g., from left to right, in the case of a two dimensional graph) are included when computing the cost of the cut, while edges that cross the cut in the other direction are ignored.

A corollary to the concept of minimum cuts is maximum flow. The max-flow min-cut theorem states that the maximum amount of flow passing through a directed graph from the source to the target is equal to the total cost of the minimum cut. In some embodiments disclosed herein, edges in directed graphs are assigned weights based on the amount of data that flows across the edge. Any data that has been produced by a producer node but not yet consumed by a consumer node may be referred to as "in flight," and must be allocated space in memory. Thus, the weights of the edges in the graph indicate the amount of data that is "in flight" and therefore must have space allocated in memory for the producer/consumer set. Therefore, under the max-flow/min-cut theorem, by finding the minimum cut, the maximum amount of "in flight" data can be determined. That is, the cost of the minimum cut is the maximum amount of memory that will be needed at any one time to execute the operations in the graph.

<FIG> depicts an example workflow <NUM> for improved process scheduling to ensure efficient execution of the process. In the illustrated workflow <NUM>, a variety of components are depicted for conceptual clarity. In various embodiments, however, the functionality of each component may be combined or distributed across any number and variety of components. Additionally, the various components and operations may be performed in any order, including iteratively (e.g., a given component may be utilized multiple times in the workflow <NUM>). The illustrated workflow <NUM> includes an Ordering Component <NUM>, a Memory Component <NUM>, a Reordering Component <NUM>, and an Allocation Component <NUM>. Each of these components may generally be implemented as a software process on a general purpose processor, using hardware, or as a combination of hardware and software.

As illustrated, the workflow <NUM> begins when a Data Graph <NUM> is received by an Ordering Component <NUM>. In an embodiment, the Data Graph <NUM> is a directed graph reflecting the flow of data to accomplish a given process. In such an embodiment, each node in the Data Graph <NUM> may correspond to an operation (e.g., a transformation of data), while each edge may correspond to data being passed between operations.

For example, in one embodiment, the process corresponds to executing a machine learning model task, such as training or inferencing with an artificial neural network model. Although neural networks are used in some examples discussed herein, embodiments of the present disclosure are readily applicable to any data processing operation.

In an embodiment, each node in the Data Graph <NUM> may correspond to a neuron in a neural network, and the edges may correspond to the connections between such neurons. In order to process model input data (e.g., image data, sound data, sensor date, textual data, or other types of data) using the neural network, it is parsed and processed by the neurons sequentially, in parallel, or both. Thus, in an embodiment, the Data Graph <NUM> reflects this sequence of operations using a set of nodes with corresponding edges for the flow of data between neurons.

In some embodiments, the edges of the Data Graph <NUM> are weighted based on the data each edge corresponds to. In one embodiment, the weight of a given edge indicates the amount of data that is transmitted along the corresponding connection in the neural network. For example, if a first node passes ten kilobytes of data to a second node, the corresponding edge in the Data Graph <NUM> will have a weight of ten kilobytes. In this way, the Data Graph <NUM> quantifies the amount of data that is "in flight" at any given point during execution. In embodiments, when data is created or produced, space is required in memory to store it. This space is not freed until the last consumer of the data has finished its operations. Thus, the Data Graph <NUM> can be used to quantify the amount of memory needed at any given point in execution, by identifying producer-consumer sets that have begun (e.g., the producer has output data) but not yet terminated (e.g., the consumer(s) have not yet finished execution).

In the illustrated embodiment of <FIG>, the Ordering Component <NUM> generates a Topological Ordering 115A based on the Data Graph <NUM>. The Topological Ordering 115A is generally a linear sequence of operations (e.g., a sequence of nodes from the Data Graph <NUM>) that respects the dependencies reflected in the graph. Thus, if a given node in the Data Graph <NUM> is completed before a second node, the given node will precede the second node in the Topological Ordering 115A. By stepping along the Topological Ordering 115A (executing each node in the indicated sequence), one can perform the original process (e.g., processing data using a machine learning model, such as a neural network model).

As discussed above, in some embodiments, there is a limited amount of local and/or relatively faster memory available in the system (e.g., faster to access than a host system memory that requires moving data over a common data bus). For example, a tightly-coupled memory (TCM) may act as a fast, local memory that is tightly-coupled to a processor. In various embodiments, this fast memory may include cache space, SRAM, and the like. Although such memory can be accessed quickly (due to its tight coupling with the processor(s)), the size of such fast memory is often limited owing to physical constraints and other design considerations for a processing system. In contrast, a relatively large amount of storage or memory may be available elsewhere in the host system (e.g., in typical RAM, hard drive or solid state drive devices, and the like). Execution of typical computing operations can be memory intensive, often exceeding the space available in local faster memory. Thus, while it is desirable to store the needed data in the local fast memory, it is often not possible to store all of this data simultaneously (due to its small size), which requires reliance on remote memories such as host system memory (e.g., DRAM).

In an embodiment, the Topological Ordering 115A is configured to reduce the amount of data that is stored at any given point in the process. Beneficially, this reduces the overall memory utilization, latency, and power during the process. In some embodiments, the Ordering Component <NUM> is configured to generate a set of minimum cuts, in order to generate the Topological Ordering 115A.

Generally, computing a minimum cut includes finding the smallest aggregate edge weights that disconnect the source of the graph from the target. As discussed above, the source of a graph (or subgraph) is a node or component that provides the input to the graph, while a target is a node or component that acts as the final sink or destination for data traversing the graph. By iteratively finding such minimum cuts, the Ordering Component <NUM> can generate the Topological Ordering 115A. In embodiments, the Ordering Component <NUM> may utilize any number of techniques for finding minimum cuts, including the Ford-Fulkerson algorithm, the Edmonds-Karp algorithm, and the like.

In the illustrated workflow <NUM>, the Topological Ordering 115A is received by a Memory Component <NUM> that inserts memory operations into the ordering, as needed. In an embodiment, each memory operation corresponds to moving one or more units of data from the local memory (e.g., a TCM) into the remote memory or storage (e.g., DRAM), moving one or more units of data from the remote memory or storage into the local memory, or both. In some embodiments, such operations may be referred to as "spill/fill" operations. In other words, data may be spilled from a local memory to a remote memory, and later filled back into a local memory from the remote memory.

In an embodiment, the Memory Component <NUM> analyzes the Topological Ordering 115A to determine the amount of memory needed at each point in the ordering (e.g., at each node, or between each sequential node). In some embodiments, to do so, the Memory Component <NUM> determines the aggregate weight of all edges that are still "in flight" at each point (e.g., have left a producer node but not yet terminated at a consumer node).

For any points that exceed an available space in the local memory, the Memory Component <NUM> inserts one or more memory operations to move some data out of the faster memory into the remote memory. In this way, the Memory Component <NUM> generates a Modified Topological Ordering 115B, which is the original Topological Ordering 115A with zero or more memory operations inserted therein. Here it is zero or more because some Data Graphs <NUM> (e.g., those that require memory space that is smaller than or equal to the local memory) will not require any memory operations to the remote memory.

In the illustrated embodiment, this Modified Topological Ordering 115B is then provided to a Reordering Component <NUM>. In an embodiment, the Reordering Component <NUM> can move nodes in the Modified Topological Ordering 115B (while respecting the data dependencies) in an effort to improve the potential for parallel processing in execution. In an embodiment, respecting data dependencies includes ensuring that no consumer node is placed before any of its producers in the Modified Topological Ordering 115B. For example, if a consumer is placed immediately after its producer, the consumer cannot be moved earlier in the ordering. If one or more nodes are located between a consumer and its producer in the Topological Ordering 115A, the consumer may be moved earlier in the ordering to create the Modified Topological Ordering 115B.

For example, in one embodiment, the Reordering Component <NUM> can move direct memory access (DMA) operations to earlier positions in the ordering to allow for them to occur in the background, being performed by one or more processing units, while the execution of the operations continues on one or more other processing units. That is, rather than initiate DMA just before the data is needed (e.g., by the next node), if sufficient space is available in the local memory, the Reordering Component <NUM> may move the DMA operation earlier to allow it to begin loading the data into the memory before it is needed. This increases parallel utilization of hardware components (e.g., while one processing unit loads the data, others may continue to operate on other data).

As another example, the Reordering Component <NUM> can modify the ordering of the nodes to improve parallel execution on discrete hardware processing units. In some embodiments, the system can include a number of processing units (e.g., one or more central processing units (CPUs), one or more graphics processing units (GPUs), one or more machine learning accelerators, such as neural processing units (NPUs), and the like). In such an embodiment, the Reordering Component <NUM> may further modify the Modified Topological Ordering 115B to allow some operations to be performed in parallel on the separate processing units. This results in a second Modified Topological Ordering 115C.

In the illustrated workflow <NUM>, an Allocation Component <NUM> then processes the Modified Topological Ordering 115C to generate a Processing Schedule <NUM>. Although depicted as being used as the last processing step in the workflow <NUM> (resulting in the generation of the Processing Schedule <NUM>), in some embodiments, the Allocation Component <NUM> may be utilized at different steps in other workflows. Additionally, in some embodiments, one or more additional processes may be applied after the Allocation Component <NUM>.

For example, in some embodiments, the Memory Component <NUM> can insert memory operations before the Allocation Component <NUM> operates. In some embodiments, however, it is only during allocation that one or more memory operations need to be inserted. In such an embodiment, therefore, the Memory Component <NUM> may analyze (or re-analyze) the ordering after allocation is performed.

In one embodiment, the Allocation Component <NUM> allocates units of memory (e.g., in a TCM) based on the Topological Ordering 115C. In embodiments, as discussed above, the Data Graph <NUM> and Topological Orderings <NUM> each include a collection of operations that use input data to produce output data. This data requires working memory while in use. Because the local memory space may be limited, in some embodiments, some memory locations must be reused. This is possible because some units of data are needed only for some subset of the process. For example, if data is produced by a producer node and consumed by a consumer node, the data need only be stored from the time of production to the time of consumption. Thus, each producer-consumer set spans a portion of the Topological Ordering 115C, beginning at the producer node and ending at the (last) consumer node. The Allocation Component <NUM> may allocate physical locations in the memory at each point in time for the data that is "live" at that point in the ordering.

In embodiments, the Processing Schedule <NUM> can then be executed by one or more processing units of a processing system, such as described with respect to <FIG> and <FIG>, in order to perform the original process.

<FIG> depicts an example graph 200A including a set of operations and corresponding data flows involved in executing a process. For example, the process may include a machine learning task, such as training or inferencing based on a machine learning model.

In the illustrated embodiment, data flows from a Source <NUM> to a Target <NUM> via a set of Nodes <NUM>. In embodiments, each Node <NUM> performs some operation on incoming data, such as a mathematical operation, transformation, and the like. Further, each Node <NUM> may or may not output some data. In the illustrated embodiment, each edge is directed (indicated by the directionality of the arrow). Thus, each edge corresponds to data flowing from a producer node to a consumer node. In the depicted graph 200A, Node 210A receives two units of data from the Source <NUM>, performs some operation, and outputs four units of data to Node 210B and to Node 210C. Node 210B does not output data and thus may be referred to as a data sink or leaf node.

As illustrated, Node 210C receives <NUM> units of data and outputs one unit of data to Node 210E. For example, Node 210C may perform a layer operation in a machine learning model in which data is compressed, such as a convolution layer or pooling layer.

Node 210E additionally receives five units of data from Node 210D. Based on this input, Node 210E outputs four units of data to the Target <NUM>. Thus, in the illustrated embodiment, Node 210A is a "producer" node for two consumers: Nodes 210B and 210C. Node 210C is a producer for consumer Node 210E. Node 210D is also a producer for consumer Node 210E. In turn, Node 210E is a producer for the Target <NUM>.

Although the graph 200A depicts a simple example process for conceptual clarity, in various embodiments the graphs may be significantly more complex.

Notably, not all sets of minimum cuts for a given the graph yield a valid ordering. For example, a set of minimum cuts may create an ordering that does not respect the data dependencies (indicated by the directionality of the edges). Similarly, when a given producer has multiple consumers, only the node which completes last can free the allocated data. To address these issues, a set of pre-processing operations can be performed to transform the graph 200A of <FIG> into a modified representation prior to generating the topological ordering.

<FIG> depicts a reverse edge modification to create a modified graph 200B. In the illustrated embodiment, this modification is performed by transforming the graph 200A. In one embodiment, the modification is performed by the Ordering Component <NUM> of <FIG>. This graph 200B has one or more new edges inserted to ensure that the cuts yield a valid topological ordering. As discussed above, the concept of a minimum cut does not respect data dependencies, and will not necessarily result in a valid topological ordering (e.g., because the cut can curve back to cut an edge such that, from the perspective of the cut, the edge crosses backwards (e.g., from right to left) and therefore the weight is not included in the cost of the cut). In the illustrated embodiment, for each edge in the graph, a corresponding backwards or reverse edge (labeled <NUM>) has been inserted. This is illustrated in <FIG> using dashed arrows. In an embodiment, these reverse edges are assigned a weight that ensures they will not be cut during the subsequent operations, as discussed in more detail below with respect to <FIG> and <FIG>. That is, the backwards edges force the cut to respect data dependencies by being, in effect, uncuttable. For example, each backwards edge may be assigned an infinite weight.

Note that reverse edges are described in some examples herein as having "infinite" weights in order to ensure certain cuts will be prevented algorithmically. Generally, such edges may have arbitrarily high values. For example, because a truly infinite weight may be unworkable due to limitations of the physical hardware and software, the system may use a predefined value that significantly exceeds any realistic weight used in the system and is thus arbitrarily high. Generally, this predefined value may be selected to be larger than the costliest minimum cut, which ensures that it will never be included in a cut because cutting such a high weight, even alone, would incur more penalty than any alternative valid cut.

In some embodiments, this arbitrarily high predefined value is selected to be high enough that it exceeds reasonable or realistic weights, but low enough such that adding the weight of the infinite edge to weights of other edges would not cause integer overflow that could bring the weight back into the realm of reasonable weights. In other embodiments, the arbitrarily high value for reverse edges may be set based on one more values of forward edges in the graph, such as based on the largest forward edge weight, an average of forward edge weights, and the like, and such reference values may be modified by a coefficient or function to become arbitrarily high.

<FIG> depict cuts on a graph to partition the nodes into disjoint subsets.

<FIG> depicts the graph 200B with a Cut 217A. In embodiments, a minimum cut can be conceptualized as a directed line that crosses a set of one or more edges in the graph to separate the source from the target. In the illustrated embodiment, the Cut 217A slices from bottom to top across the page. For each edge that passes through the Cut 217A in one direction (e.g., from the left of the cut through to the right in the illustrated embodiment), the weight of the edge is added to the cost of the cut. For each edge that passes in the other direction (from the right of the cut through to the left in the illustrated embodiment), the weight of the edge is ignored.

In the illustrated embodiment, the edge from Node 210D to Node 210E and the edge from Node 210C to 210E both cross the Cut 217A in the same direction, from the left to the right. Their weights are therefore included in the cost of the Cut 217A. In contrast, the two reverse edges from Node 210E to 210C and Node 210E to 210D cross the Cut 217A from the right to the left, and their weights are therefore ignored. Thus, the cost of the Cut 217A is six.

<FIG> depicts another Cut 217B. The edge from Node 210C to Node 210E crosses the Cut 217B from left to right, and is therefore counted when computing the cost of the Cut 217B. The infinite reverse edge from Node 210E to Node 210C crosses from right to left, and is therefore ignored. As illustrated, the edge from Node 210A to Node 210C crosses the Cut 217B from the right of the Cut 217B to the left of the Cut 217B (determined based on the directionality of the Cut 217B, indicated by the arrow head). Thus, this edge is ignored. In contrast, the infinite reverse edge from Node 210C to Node 210A crosses the Cut 217B from the left of the Cut 217B to the right of the Cut 217B. Thus, the (infinite) weight of this edge is included in the cost of the Cut 217B. This gives the Cut 217B (which may violate the topology of the original graph) an infinite cost, ensuring it will not be used to partition the graph 200B.

Thus, if no infinite (or high weight) edges are inserted, the minimum cut techniques may result in graphs that cut "backwards" across an edge and violate the dependencies. Inserting reverse edges ensures that the subsequently-generated cuts do not violate the topology: such a cut would incur infinite cost.

<FIG> depicts a full connection modification to create a modified graph 200C. Specifically, the graph 200C reflects a modified version of the graph 200B, with additional edges inserted to enforce topological validity of the final ordering. A valid topological ordering (also referred to an ordering with topological validity) is one that respects the original dependencies of the graph, in that no consumer nodes are located before any of their producers. In the illustrated embodiment, this modification is performed to ensure that there is a path in the graph 200C from every Node <NUM> to the Target <NUM>, and from the Source <NUM> to every Node <NUM>. To do so, in the illustrated embodiment, zero-weight edges are inserted. Specifically, in graph 200B of <FIG>, no path existed to arrive at the Node 210D from the Source <NUM>. By contrast, in graph 200C of <FIG>, a zero-weight edge has been inserted directly from the Source <NUM> to the Node 210D (e.g., Ordering by Component <NUM> of <FIG>) and a corresponding infinite-weight reverse edge has been added.

Similarly, no path existed from the Node 210B to the Target <NUM> in graph 200B of <FIG>. To ensure topological validity, therefore, the Ordering Component <NUM> inserted a zero-weight edge connecting the Node 210B to the Target <NUM> (along with a corresponding infinite weight edge in reverse).

<FIG> depicts a deallocation modification to create a modified graph 200D. Graph 200D is based on the graph 200C of <FIG> and is configured to account for multiple consumer nodes. As discussed above, when a producer outputs data to one or more consumers, that data must be stored until all of the consumer(s) finish processing it. If a single consumer exists for the producer, the data can be deallocated as soon as the consumer completes. If multiple consumers exist, however, the data cannot be deallocated until all have completed their operations. In many embodiments, it may be difficult (or impossible) to know which consumer will complete last. Thus, in the illustrated embodiment, the Ordering Component <NUM> generates and inserts Deallocation Nodes <NUM> as needed. In embodiments, Deallocation Nodes <NUM> are placeholder nodes (e.g., nodes that do not perform any data operations or transformations, and exist to indicate when memory space can be deallocated or freed).

In one embodiment, the Ordering Component <NUM> inserts a Deallocation Node <NUM> for any producer node that has more than one consumer. Deallocation Nodes <NUM> are inserted to ensure that space in the local memory is not deallocated until all consumers of the data in that space have finished. If a producer node has a single consumer, the dependency reflected in the graph (e.g., the edge from the producer to the consumer) is sufficient to ensure that the consumer is scheduled after the producer. The space needed for the producer/consumer set is deallocated once the consumer finishes. However, if multiple consumers are present for a given producer, it is impossible to know when the space can be deallocated, as there is no dependency between the consumers that forces one to finish last. To ensure that the space is not deallocated prematurely, therefore, Deallocation Nodes <NUM> are used to signal when the space should be deallocated (only once all consumers have finished operating on the data).

In another embodiment, the Ordering Component <NUM> can simply insert a deallocation node for every producer, regardless of the number of consumers. As illustrated, inserting a Deallocation Node <NUM> for a given producer includes inserting an edge from each consumer of the producer to the Deallocation Node <NUM>. In the illustrated embodiment, therefore, for the producer Node 210A, zero-weight edges are inserted from each of the consumers Node 210B and 210C to the Deallocation Node <NUM>. As above, infinite-weight backwards edges are also added for each. This ensures that the Deallocation Node <NUM> is placed after both Nodes 210B and 210C in the topological ordering, and that the space is not deallocated until both have completed their operations.

In embodiments, the Ordering Component <NUM> also sets the weights of each original edge from the producer node to the consumers to zero. In the illustrated embodiment, this includes changing the weights of the edges from Node 210A to 210B and from Node 210A to 210C to zero. This is performed because if both edges retained their original weight, the data flowing on those edges would be "double counted" while computing minimum cuts, resulting in inaccuracies and inefficiencies in the final schedule.

To quantify the weight of these edges and ensure they are counted in the final ordering, the Ordering Component <NUM> can additionally insert an edge from the producer Node 210A to the Deallocation Node <NUM>. This edge is assigned a weight that corresponds to the original edges from the producer to the consumer(s). Additionally, as illustrated, this new edge is similarly accompanied by an infinite backwards edge to enforce topological validity.

In embodiments, the Ordering Component <NUM> can then process the graph 200D using maximum flow/minimum cut techniques in order to generate a valid topological ordering for the original graph 200A. Additionally, by utilizing the edge weights (corresponding to the amount of data needed for each producer/consumer set), the minimum cuts are computed based on memory utilization and attempt to use the minimum amount of memory at each stage of the execution.

<FIG> depict a sequence of evaluations and operations performed to generate a valid topological ordering of a data flow graph to improve scheduling of the corresponding process. Specifically, <FIG> depict a sequence of minimum cuts computed by an ordering component (e.g., Ordering Component <NUM> of <FIG>) in order to generate a topological ordering.

<FIG> depicts an initial graph 300A before cuts are generated. In the illustrated graph, data flows from a Source 305A to a Target 315A via a set of Nodes <NUM>. Specifically, Node 310A receives data from Source 305A and transmits data to Nodes 310B and 310C. Node 310B in turn provides data to Node 310D, and Node 310C provides data to Node 310E. Node 310F receives data from both Node 310D and Node 310E. Node 310F then provides data to the Target 315A.

<FIG> depicts a first Cut <NUM> in the graph 300A. In embodiments, the minimum cut technique yields a single cut for a graph. To generate a topological ordering, the ordering component can select a node to serve as an "index node" for a given cut, and constrain the cut to pass just after the index node. This allows the ordering component to exert some control over where the cut is placed, to help improve the efficiency and latency of the cutting process. For example, if the cuts are not constrained, the minimum cut for a given graph is likely to be a single edge near the beginning or end of the graph. Cutting here, however, is not useful in generating a topological ordering, because this portion of the graph is already linear. That is, if a single edge connects node A to node B, there is no possible ordering that places the node B before node A. Generating a cut at this point, therefore, is useless.

In some embodiments, to constrain the cut to an index node, the Ordering Component <NUM> selects an index node, computes a cut to divide the graph into two subgraphs, and then processes each sub-graph to compute another cut for each. By iteratively processing each sub-graph, a topological ordering is generated. In embodiments, a topological ordering is a linear sequence of nodes. There may be multiple valid topological orderings for a given graph. By iteratively processing each subgraph to subdivide each into additional subgraphs, the ordering component iteratively makes the overall graph more linear. That is, each cut effectively enforces some linearity by placing some nodes before the cut and some nodes after. By iteratively computing cuts, the graph becomes more linear.

In one embodiment, this process repeats until all subgraphs are linear (or all subgraphs include a single node). In another embodiment, rather than computing cuts until the subgraphs are linear (or contain a single node), the processing system can proceed until each subgraph has reached some predefined criteria relating to size or complexity (e.g., a number of nodes in the subgraph). These subgraphs may then be transformed using one or more techniques to generate topological orderings for the subgraph.

In an embodiment, the final topological ordering is created by reconnecting each subgraph, in the proper order, where the cuts were made (e.g., by adding or reconnecting the edges that were severed, while maintaining the linear sequence of nodes).

In the illustrated embodiment, the Ordering Component <NUM> has selected the Node 310B to serve as the index node for the first Cut <NUM>. In some embodiments, the Ordering Component <NUM> selects the index node randomly. In at least one embodiment, the Ordering Component <NUM> attempts to select an index node that is near the center of the graph 300A based on the depth of each node.

In one embodiment, the Ordering Component <NUM> determines the depth of each respective Node <NUM> based on its distance from both the Source 305A and the Target 315A. For example, for each respective Node <NUM>, the Ordering Component <NUM> may count the number of nodes or edges that precede it (e.g., that must be traversed to get from the source to the node) and the number of nodes or edges that are subsequent to it (e.g., that must be traversed to get from the node to the target). By aggregating these counts (e.g., through addition or multiplication), the Ordering Component <NUM> can identify the node (or set of nodes) located nearest to the center of the graph 300A. In an embodiment, the node with the highest aggregate depth from source and target is referred to as a "centroid" node. Although generally located near the center, in embodiments, the centroid node may of course not be precisely centered in the graph.

In one embodiment, if multiple nodes have the same depth score, the Ordering Component <NUM> can randomly select among them to select the index node. In at least one embodiment, if two nodes are at the same depth and have the same operation type, the Ordering Component <NUM> treats them as sibling nodes. Sibling nodes generally correspond to a single node which was split into a set of siblings, each performing the same operation. Sibling nodes may be generated to enhance processing parallelism. In an embodiment, to select among such siblings, the Ordering Component <NUM> constrains the cut after the middle node of the siblings, such that half of the siblings complete before the index node runs, and half complete after. In one embodiment, to identify the middle sibling, the ordering component traverses one edge upstream in the graph, then one edge back down to a sibling. This repeats until all siblings are found.

Typically, a minimum cut technique will place the cut to bisect the graph 300A in a location that minimizes the weight of the edges it cuts through. In order to constrain the cut to occur just after the selected index node (e.g., Node 310B), the Ordering Component <NUM> may add additional edges to the graph. In the illustrated embodiment, the Ordering Component <NUM> adds an edge with infinite weight from the Source 305A to the index Node 310B. The Ordering Component <NUM> additionally adds an edge with infinite weight from each consumer of the index node (Node 310D in the illustrated embodiment) to the Target 315A. This ensures that the computed cut will pass just after the index node and before any consumers of the index node.

In the illustrated embodiment, the resulting Cut <NUM> separates the index Node 310B and its consumer Node 310D. As illustrated, to bisect the graph 300A and disconnect the Source 305A from the Target 315A, the Cut <NUM> also cuts through the edge between Node 310A and Node 310C. Of course, in embodiments, the Cut <NUM> could instead have cut between Nodes 310C and 310E, between Nodes 310E and 310F, or between Node 310D and 310F (continuing through the edge between Node 310F and 315A).

In embodiments, the particular path of the cut (e.g., the edges it severs) is chosen to minimize the aggregate/accumulated weight of the severed edges. The Cut <NUM> must bifurcate the edge between Nodes 310B and 310D (because of the edges added by the Ordering Component <NUM>). The Ordering Component <NUM> will then route the Cut <NUM> through other edge(s) as needed to completely separate the graph 300A, while minimizing the total cost. Each time the Cut <NUM> passes through an edge, the weight of the edge is added to the total cost (also referred to as a penalty) of the cut. Notably, the total cost of the Cut <NUM> reflects the total amount of data that is maintained in memory at the corresponding point of the cut.

The Cut <NUM> bifurcates the graph 300A, such that some portion of the graph 300A is performed prior to the Cut <NUM>, and some portion occurs after the Cut <NUM>. In the illustrated embodiment, Nodes 310A and 310B precede the Cut <NUM> (along with the Source 305A), while Nodes 310C-F are subsequent to it (along with the Target 315A).

<FIG> depicts the result of the Cut <NUM>. Specifically, as illustrated, all elements on one side of the Cut <NUM> have been placed in a first subgraph 300B, while all elements on the other side belong to a second subgraph 300C. Additionally, as illustrated, a new Target 315B has been inserted into the subgraph 300B to provide a new target for the subgraph. In some embodiments, for each edge that was cut by the Cut <NUM>, a new edge is added to the new Target 315B, in order to preserve and enforce the dependencies in the original graph 300A.

Similarly, in the subgraph 300C, a new Source 305B has been added. Additionally, as illustrated, for each edge that the Cut <NUM> severed, a new edge has been added from the new Source 305B to enforce the dependencies of the original graph 300A.

<FIG> depicts additional Cuts <NUM> and <NUM> generated by the Ordering Component <NUM> for the subgraphs 300B and 300C, respectively. In the subgraph 300B, the Ordering Component <NUM> has selected the Node 310A as the index node. To constrain the Cut <NUM> to occur just after this Node 310A, as illustrated, the Ordering Component <NUM> inserts infinite-weight edges from the Source 305A to the index Node 310A, and from all consumers of the index node (e.g., from consumer Node 310B) to the new Target 315B.

Similarly, in subgraph 300C, the Ordering Component <NUM> has selected Node 310E to serve as the index node. To constrain the Cut <NUM>, the Ordering Component <NUM> has inserted an infinite edge from the new Source 305B to the index Node 310E, and an infinite edge from each consumer of the index node (here, Node 310F) to the Target 315A.

As discussed above, Cuts <NUM> and <NUM> bifurcate each subgraph 300B and 300C into two new subgraphs (yielding four subgraphs in total). In some embodiments, the Ordering Component <NUM> can perform similar processing for each subgraph iteratively until some terminating criteria (e.g., a maximum number of iterations, or a maximum time spent finding the cuts) has been satisfied. That is, the Ordering Component <NUM> may compute a cut to divide a graph into two subgraphs. For each subgraph, the Ordering Component <NUM> can then compute another cut to divide each subgraph into two more subgraphs (yielding four subgraphs total). For each of these four subgraphs, the Ordering Component <NUM> may similarly compute a cut to yield eight total subgraphs.

In one embodiment, the Ordering Component <NUM> selects the next subgraph to be divided based on the size of each subgraph. Although selecting a centroid node can help balance the subgraphs, the resulting cut can be significantly uneven (with more nodes on one side than the other). In some embodiments, the Ordering Component <NUM> selects the largest of the available subgraphs to compute the next cut. This iterative process repeats until the predefined criteria are met. By iteratively selecting and cutting the largest subgraph, the ordering component can compute minimum cuts at the denser or more complex regions of the graph first, followed by the less dense or complex regions. This results in a more efficient topological ordering, and reduces the time needed to find final the set of cuts.

In one embodiment, the terminating criteria relate to a full topological ordering. For example, the Ordering Component <NUM> may continue to iteratively cut each subgraph until the nodes in a given subgraph are linear. When a subgraph is linear, no additional cuts are required to yield a topological ordering. Once all subgraphs are linear, they may then be combined (e.g., by linking the subgraphs together at the places where they were cut) to form the full topological ordering. In some embodiments, the terminating criteria may include a number of iterations or cuts to be computed. Once the number of iterations has been reached, the process stops. In some embodiments, the terminating criteria includes a time bound. When the predefined amount of time has been spent, the cutting process stops.

<FIG> depicts a flow diagram illustrating a method <NUM> for improved scheduling of computer processing operations. In some embodiments, the method <NUM> is performed by a processing system, such as described with respect to <FIG>, including one or more components, such as an Ordering Component <NUM>, a Memory Component <NUM>, a Reordering Component <NUM>, an Allocation Component <NUM>, and the like.

The method <NUM> begins at block <NUM>, where a data flow graph is received for processing. In an embodiment, as discussed above, this data flow graph generally corresponds to some computing process, where each node corresponds to an operation performed during the process and each (directed) edge corresponds to data flow in the process. In some embodiments, the weight of each edge in the data flow graph corresponds to the amount of data that is passed along the dependency and is therefore required to be allocated space in memory.

At block <NUM>, the processing system generates a topological ordering for the received data flow graph. In one embodiment, this process includes some or all of the steps illustrated and discussed above with reference to <FIG> and 3A-3D.

The method <NUM> then proceeds to block <NUM>, where the processing system determines whether an available space in memory (e.g., in local memory) will be exceeded by the topological ordering at any point. That is, the processing system can determine whether the memory needed (indicated by the aggregate weight of the edges at any point in the ordering) exceeds the available space in the memory (e.g., in the TCM). If so, the method <NUM> continues to block <NUM>.

At block <NUM>, the processing system inserts one or more memory operations (e.g., spill/fill operations) into the topological ordering. In an embodiment, for each point where the needed space (indicated by the weight of the edges at each point) exceeds the available space in local memory, the processing system inserts memory operation(s) to move some data out of the local memory and into more remote memory to ensure the local memory capacity is not exceeded. The method <NUM> then continues to block <NUM>. The processing system may similarly insert operations to move the data back into memory when needed.

Additionally, at block <NUM>, if the processing system determines that no point in the ordering will require more space than is available in local memory, the method <NUM> continues to block <NUM>.

At block <NUM>, the processing system allocates units of memory based on the topological ordering. As discussed above, in some embodiments, this includes assigning addresses in the memory to each piece of data at each point in time.

<FIG> depicts a visualization of memory allocations, according to some embodiments disclosed herein. In the illustrated embodiment, allocations are plotted on a graph <NUM> where the horizontal axis is time and the vertical axis is units of memory in the local memory. In an embodiment, each Allocation <NUM> (e.g., to a producer-consumer or producer-consumers set) is depicted as a rectangle that spans horizontally from a time when the producer node produces the data to a time when the final consumer node consumes it. The height of each Allocation <NUM> corresponds to the amount of data needed for the producer-consumer set. In an embodiment, the processing system allocates memory by assigning units of memory in an effort to pack such rectangles as tightly as possible, without exceeding some predefined value on the vertical axis (corresponding to the available space of the local memory, indicated by the dashed line <NUM>). If any Allocations <NUM> pass this line <NUM>, some data must be moved to the remote (host) memory, and the corresponding space in the local memory is deallocated (allowing it to be reallocated to other producer/consumer sets).

In the illustrated embodiment, the allocations indicate the time when each producer and consumer can operate. For example, the producer associated with the Allocation 510F has space allocated after the consumer associated with the Allocation 510B has completed. Thus, the producer of Allocation 510F cannot begin until the consumer of Allocation 510B completes.

Returning to <FIG>, once the memory has been allocated, in the illustrated embodiment, the method <NUM> continues to block <NUM>, where the processing system modifies the ordering of the nodes in the topological ordering in order to increase parallel utilization of resources. In various embodiments, this can include, for example, moving load operations (e.g., moving data from storage to memory) to earlier positions in the ordering, rearranging nodes to allow for parallel execution on separate processing units, and the like.

<FIG> depicts a flow diagram illustrating a method <NUM> for generating topological orderings to improve process scheduling.

In one embodiment, the method <NUM> provides additional detail for block <NUM> in <FIG> (generating a topological ordering).

The method <NUM> begins at block <NUM>, where the processing system performs one or more operations to ensure that the cuts will result in a valid topological ordering (e.g., an ordering that respects the original dependencies). As discussed above, this may include, for example, adding reverse edges with high or infinite weights (to prevent the cut from crossing an edge backwards and violating a dependency).

The method <NUM> then continues to block <NUM>, where the processing system inserts zero or more deallocation nodes into the graph, as needed. In one embodiment, as discussed above, the deallocation nodes can be utilized to ensure that producers with multiple consumer nodes are processed correctly by the minimum cut algorithm(s).

At block <NUM>, a loop is initiated to generate a set of minimum cuts. At block <NUM>, the processing system determines whether predefined termination criteria are satisfied.

In one embodiment, the terminating criteria includes determining whether the graph (or each subgraph) is linear. If so, the method <NUM> continues to block <NUM>, where the processing system returns this linear topological ordering. In various embodiments, the termination criteria can include, for example, a maximum time, a maximum number of cuts or iterations, and the like.

If the terminating criteria are not satisfied, the method <NUM> continues to block <NUM>, where the processing system selects a subgraph. In an embodiment, during the first iteration of the loop, the processing system operates on the entire graph. In each subsequent iteration, block <NUM> can include selecting the next subgraph to be operated on. In one embodiment, the processing system selects the largest of the remaining (nonlinear) subgraphs.

The method <NUM> then continues to block <NUM>, where the processing system computes a minimum cut for the selected subgraph (or the original graph, for the first iteration). In some embodiments, to compute the cut, the processing system first selects an index node to constrain the cut. That is, the processing system ensure that the cut separates the index node from all of its consumers. Selecting index nodes near the center of the graph can allow the processing system to process the complex portions of the graph first, rather than cutting off single nodes, which ensures that the iterative process is rapid and efficient, and results in a final ordering that accounts for the global graph structure (as opposed to individual local portions thereof).

In some embodiments, computing the cut comprises selecting a set of edges to remove in order to completely separate the source and the target nodes while minimizing the total cost of the cut. The cost of any given cut is determined based on aggregating (e.g., adding) the individual weights of each edge that the cut crosses.

The method <NUM> then returns to block <NUM>. In this way, the processing system continues to iteratively evaluate and cut each subgraph until the terminating criteria are satisfied.

<FIG> depicts a flow diagram illustrating a method <NUM> for enforcing topological validity while generating efficient process schedules.

In one embodiment, the method <NUM> provides additional detail for block <NUM> in <FIG> (ensuring the cuts will yield a valid topological ordering).

In the illustrated embodiment, the method <NUM> begins at block <NUM>, where the processing system selects an edge in the graph. This initial selection may be accomplished in any number of ways, including randomly, as the processing system will iterate through all edges in the graph.

At block <NUM>, the processing system generates a corresponding reverse edge for the selected edge. That is, if the selected edge traverses from a first node to a second node, the reverse edge is from the second node to the first node. In embodiments, this reverse edge is assigned a predefined weight or other flag indicating that it cannot be cut by a minimum cut. For example, in one embodiment, the processing system assigns an infinite (or an arbitrarily high) weight that would cause an infinite (or arbitrarily high) penalty to be applied for any cut that crosses in the wrong direction (e.g., in a direction that would violate the data dependencies in the graph).

At block <NUM>, the processing system determines whether any additional edges remain to be evaluated. If so, the method <NUM> returns to block <NUM>. In this way, the processing system inserts reverse edges to enforce the data dependencies in the graph and ensure any minimum cut results in a valid topological ordering. The method <NUM> then continues to block <NUM>.

At block <NUM>, the processing system attempts to visit all nodes in the graph by traversing directed edges from the source. This may include utilizing a breadth-first search or a depth-first search, depending on the particular implementation. In an embodiment, the processing system notes which nodes have been visited during this search. The method <NUM> then proceeds to block <NUM>, where the processing system determines whether any nodes in the graph where not visited during this search. If so, the unvisited nodes are disconnected from the source, in that no valid path exists using directed edges to reach the node from the source. If all nodes were visited, the method <NUM> proceeds to block <NUM>. If at least one node was not traversed during the search, however, the method <NUM> continues to block <NUM>.

At block <NUM>, the processing system inserts edge(s) with zero weight from the source to any nodes that were not visited during the search. This ensures that the non-visited nodes are fully connected to the source, and enforces topological validity of any computed minimum cuts. In one embodiment, the processing system additionally inserts an infinite weight reverse edge from the non-visited node(s) to the source. The method <NUM> then continues to block <NUM>.

At block <NUM>, the processing system performs another search to attempt to visit all nodes by traversing the reverse edges from the target. The system may similarly note which nodes are found/traversed during this search. In embodiments, this search may be performed depth-first or breadth-first.

The method <NUM> then continues to block <NUM>, where the processing system determines whether all nodes were visited during this search from the target. If any nodes were not found, they are disconnected from the target and no valid path exists in the graph using the (forward) directed edges from the non-visited node to the target. If all nodes were found, the method <NUM> proceeds to block <NUM>. If at least one node was not visited, however, the method <NUM> continues to block <NUM>.

At block <NUM>, the processing system inserts edge(s) with zero weight from the non-visited node(s) to the target. This ensures that the node is fully connected to the target, and enforces topological validity of any computed minimum cuts. In one embodiment, the processing system additionally inserts an infinite weight reverse edge from the target to the non-visited node(s). The method <NUM> then continues to block <NUM>.

At block <NUM>, the processing system returns the modified graph. In this way, the processing system ensures that each node is connected via a valid path to both the source and the target, in order to enforce the data dependencies in the graph and ensure any minimum cut results in a valid topological ordering.

<FIG> depicts a flow diagram illustrating a method <NUM> for handling parallel data flows to accurately generate efficient process schedules.

In one embodiment, the method <NUM> provides additional detail for block <NUM> in <FIG> (inserting deallocation nodes as needed). The method <NUM> begins at block <NUM>, where the processing system selects a producer node in the graph. In embodiments, producer nodes are any nodes that output data to one or more subsequent nodes (or to the target node).

In some embodiments, at block <NUM>, the processing system selects a producer node from a subset of the producers in the graph. For example, in one embodiment, the method <NUM> is only applied to producer nodes that have more than one consumer. That is, because adding deallocation nodes for any producer with a single consumer is not needed and is potentially wasteful, the processing system may first identify all nodes that output to multiple consumers, and select from this identified subset. In another embodiment, the method <NUM> is applied to all producer nodes, regardless of the number of consumers each is associated with. In various embodiments, this initial selection may be accomplished in any number of ways, including randomly.

At block <NUM>, the processing system identifies the set of consumer node(s) for the selected producer.

The method <NUM> then proceeds to block <NUM>, where the processing system determines the amount of data that is output by the selected producer to the identified consumer(s). The amount of data produced will be used to set the weight of the edge to the deallocation node. For example, if the producer produces ten kilobyte of data (regardless of the number of consumers that use this data), the system will subsequently set the weight of the edge to the deallocation node to ten kilobytes. The method <NUM> then continues to block <NUM>.

At block <NUM>, the processing system generates a deallocation node for the selected producer. At block <NUM>, the processing system then inserts an edge from the selected producer to the deallocation node.

The method <NUM> then proceeds to block <NUM>, where the processing system assigns a weight to the newly-generated edge. In an embodiment, the weight of the edge is based on the (previously-determined) amount of data that is output by the producer node to the consumer(s). In some embodiments, the processing system also inserts a reverse edge with arbitrarily-high weight from the deallocation node to the selected producer node.

The method <NUM> then proceeds to block <NUM>, where the processing system creates edges from each identified consumer of the selected producer, connecting them to the newly-created deallocation node.

At block <NUM>, the processing system sets the weight of the edge to and from the identified consumers to zero. That is, the processing system sets the weight(s) of all edge(s) from the selected producer to the identified consumer(s) to zero. This ensures that the data for the producer-consumer(s) set is not counted multiple times in computing the minimum cuts. The system further sets the weight(s) of the newly-created edge(s) from each consumer to the deallocation node to zero.

At block <NUM>, the processing system determines whether there is at least one additional producer (or one additional producer in the subset of producers with multiple consumers) that has not been evaluated. If so, the method <NUM> returns to block <NUM>.

Otherwise, the method <NUM> continues to block <NUM>, where the processing system returns this modified graph with deallocation nodes inserted.

<FIG> depicts a flow diagram illustrating a method <NUM> for dividing data flow graphs to generate topological orderings to yield efficient process schedules.

In one embodiment, the method <NUM> provides additional detail for block <NUM> in <FIG> (generating a cut in a graph).

The method <NUM> begins at block <NUM>, where the processing system selects an index node from the graph. In one embodiment, as discussed above, the processing system selects the index node based on the depth of each of the nodes. For example, the processing system may generate a depth score for each node based on its distance from the start node and to the end node, where higher depth scores correspond to nodes that are closer to the center of the graph (or subgraph). The processing system may then select, as the index node, the node with the largest depth score.

At block <NUM>, the processing system inserts an infinite weight edge from the source node to the selected index node. This constrains the subsequent cut to occur after the index node.

Further, at block <NUM>, the processing system identifies the consumer(s) of the index node.

At block <NUM>, the processing system similarly inserts an infinite weight edge from each identified consumer to the target. This constrains the cut to occur before any of the identified consumers. In this way, the processing system can constrain the minimum cut techniques to cut immediately after the index node, separating it from its consumers.

The method <NUM> then continues to block <NUM>, where the processing system generates a minimum cut for the index node. In embodiments, the minimum cut is found by identifying a set of edges to sever that will separate the source from the target while incurring the minimum penalty (based on edge weight), as discussed above.

<FIG> depicts a flow diagram illustrating a method <NUM> for generating and modifying topological orderings to improve process scheduling.

The method <NUM> begins at block <NUM>, where a processing system receives a data flow graph for a process, wherein data flow graph comprises a plurality of nodes and a plurality of edges.

At block <NUM>, the processing system generates a topological ordering for the data flow graph based at least in part on memory utilization of the process.

In some aspects, the plurality of nodes in the data flow graph correspond to operations performed during the process, the plurality of edges in the data flow graph correspond to data passing among the operations, each respective edge of the plurality of edges is associated with a respective weight based on a size of the data associated with the respective edge, and generating the topological ordering comprises finding a set of minimum cuts in the data flow graph based on the weights.

In some aspects, finding the set of minimum cuts comprises modifying the data flow graph to enforce data dependencies by: for each respective edge of the plurality of edges, adding a respective backwards edge of infinite weight. In some aspects, finding the set of minimum cuts further comprises modifying the data flow graph to enforce data dependencies by ensuring that at least one valid path exists in the data flow graph from a source to each of the plurality of nodes and from each of the plurality of nodes to a sink.

In some aspects, finding the set of minimum cuts comprises assigning the weights to the plurality of edges by: identifying a producer node of the plurality of nodes that outputs data to at least one consumer node of the plurality of nodes; determining a size of the data output by the producer node; and inserting a deallocation node into the data flow graph by: creating a first edge with a weight corresponding to the size of the data output by the producer node, wherein the first edge is inserted from the producer node to the deallocation node; assigning weight of zero to an edge from the producer node to the at least one consumer node; and creating an edge from the at least one consumer node to the deallocation node, assigned a weight of zero.

In some aspects, finding the set of minimum cuts comprises, for a first index node of the plurality of nodes, constraining a first minimum cut to occur after the first index node by: creating a first edge with an infinite weight from a source to the first index node; identifying a set of consumer nodes, from the plurality of nodes, that receive data from the first index node; creating edges with an infinite weight from each consumer node in the set of consumer nodes to a sink; and computing the first minimum cut, wherein the first minimum cut places the first index node in a first portion of the data flow graph and all successors of the first index node in a second portion of the data flow graph.

In some aspects, finding the set of minimum cuts further comprises iteratively computing minimum cuts for index nodes in the first and second portions of the data flow graph and separating the first and second portions of the data flow graph based on the minimum cuts until a predefined stopping condition is satisfied.

In some aspects, the method <NUM> further includes selecting the first index node based on determining that the first index node is centered in the data flow graph.

In some aspects, the method <NUM> further includes determining that the first index node is one of a set of sibling nodes in the data flow graph; and computing the first minimum cut by constraining a first portion of the set of sibling nodes to the first portion of the data flow graph and a second portion of the set of sibling nodes to the second portion of the data flow graph.

At block <NUM>, the processing system generates a first modified topological ordering by inserting, into the topological ordering, one or more new nodes corresponding to memory access based on a predefined memory capacity.

At block <NUM>, the processing system allocates units of memory in the memory based on the first modified topological ordering.

At block <NUM>, the processing system generates a second modified topological ordering by rearranging one or more nodes in the first modified topological ordering, wherein the second modified topological ordering enables increased parallel utilization of a plurality of hardware components.

In some aspects, rearranging one or more nodes in the first modified topological ordering comprises moving one or more nodes corresponding to loading data from a host processing system memory into the memory to an earlier position in the topological ordering.

<FIG> depicts an example Processing System <NUM>, which may be configured to perform aspects of the various methods described herein, including, for example, the methods described with respect to <FIG> and <FIG>-<NUM>.

Processing System <NUM> includes a central processing unit (CPU) <NUM>, which in some examples may be a multi-core CPU. Instructions executed at the CPU <NUM> may be loaded, for example, from a program memory associated with the CPU <NUM> or may be loaded from a memory <NUM>.

Processing System <NUM> also includes additional processing components tailored to specific functions, such as a graphics processing unit (GPU) <NUM>, a digital signal processor (DSP) <NUM>, and a neural processing unit (NPU) <NUM>.

Though not depicted in <FIG>, NPU <NUM> may be implemented as a part of one or more of CPU <NUM>, GPU <NUM>, and/or DSP <NUM>.

Although not included in the illustrated embodiment, the Processing System <NUM> may also include one or more input and/or output devices, such as screens, physical buttons, speakers, microphones, and the like.

Processing System <NUM> also includes Memory <NUM>, which is representative of one or more static and/or dynamic memories, such as a dynamic random access memory, a flash-based static memory, and the like. In this example, Memory <NUM> includes computer-executable components, which may be executed by one or more of the aforementioned processors of Processing System <NUM>.

In this example, Memory <NUM> includes an Ordering Component <NUM>, Memory Component <NUM>, Reordering Component <NUM>, Allocation Component <NUM>, Data Graph(s) <NUM>, Topological Ordering(s) <NUM>, and Processing Schedule(s) <NUM>. The depicted components, and others not depicted, may be configured to perform various aspects of the methods described herein. For example, the Ordering Component <NUM>, Memory Component <NUM>, Reordering Component <NUM>, and Allocation Component <NUM> may analyze Data Graphs <NUM> to generate Topological Orderings <NUM> and Processing Schedules <NUM>. These Processing Schedules <NUM> may be executed by the Processing System <NUM>, or may be used by one or more other devices or systems.

In the illustrated example, the Processing System <NUM> also includes an Ordering Circuit <NUM>, a Memory Circuit <NUM>, a Reordering Circuit <NUM>, and an Allocation Circuit <NUM>. The depicted circuits, and others not depicted, may be configured to perform various aspects of the techniques described herein.

For example, the Ordering Circuit <NUM> may be configured to perform the functionality of the Ordering Component <NUM>, the Memory Circuit <NUM> may be configured to perform the functionality of the Memory Component <NUM>, the Reordering Circuit <NUM> may be configured to perform the functionality of the Reordering Component <NUM>, and the Allocation Circuit <NUM> may be configured to perform the functionality of the Allocation Component <NUM>.

Though depicted as separate components and circuits for clarity in <FIG>, Ordering Circuit <NUM>, Memory Circuit <NUM>, Reordering Circuit <NUM>, and Allocation Circuit <NUM> may collectively or individually be implemented in other processing devices of the Processing System <NUM>, such as within CPU <NUM>, GPU <NUM>, DSP <NUM>, NPU <NUM>, and the like.

<FIG> depicts an example multi-processor Processing System <NUM>, which may be configured to perform aspects of the various methods described herein.

Processing System <NUM> includes a central processing unit (CPU) <NUM>, which in some examples may be a multi-core CPU. Instructions executed at the CPU <NUM> may be loaded, for example, from a program memory associated with the CPU <NUM> or may be loaded from a Memory <NUM> or Host Memory <NUM>.

Processing System <NUM> also includes additional processing components tailored to specific functions, such as a graphics processing unit (GPU) <NUM>, a digital signal processor (DSP) <NUM>, and a neural processing unit (NPU) <NUM>. In some examples, one or more of the processors of Processing System <NUM> may be based on an ARM or RISC-V instruction set.

Processing System <NUM> includes a Local Memory <NUM>, which is representative of memory or storage situated close to the various processing units. For example, the Local Memory <NUM> may include tightly-coupled memory (TCM), SRAM, cache space, and the like. As illustrated, the Local Memory <NUM> includes some Data 1218A. In an embodiment, this Data 1218A in the Local Memory <NUM> may correspond to data that is currently being processed or used by the Processing System <NUM> (e.g., while executing a process using a Processing Schedule <NUM>).

Processing System <NUM> also includes Host Memory <NUM>, which is representative of one or more static and/or dynamic memories, such as a dynamic random access memory, a flash-based static memory, and the like. In this example, Host Memory <NUM> includes computer-executable Processing Schedule(s) <NUM>, which may be executed by one or more of the aforementioned processors of Processing System <NUM>. In the illustrated embodiment, the Host Memory <NUM> also includes Data 1218B. In some embodiments, this Data 1218B may be additional data for one or more ongoing operations (e.g., being executed according to a Processing Schedule <NUM>) that does not fit within the limited space available in the Local Memory 1218A.

In some embodiments, the Processing System <NUM> may move data back and forth between the Local Memory <NUM> and the Host Memory <NUM> while executing a Processing Schedule <NUM> using one or more processing units, as discussed above.

The preceding description is provided to enable any person skilled in the art to practice the various embodiments described herein. The examples discussed herein are not limiting of the scope, applicability, or embodiments set forth in the claims. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments. For example, changes may be made in the function and arrangement of elements discussed without departing from the scope of the disclosure. In addition, the scope of the disclosure is intended to cover such an apparatus or method that is practiced using other structure, functionality, or structure and functionality in addition to, or other than, the various aspects of the disclosure set forth herein.

Further, the various operations of methods described above may be performed by any suitable means capable of performing the corresponding functions.

Claim 1:
A method for a computer processing system (<NUM>), comprising:
Receiving (<NUM>) a data flow graph (<NUM>) for a process, wherein data flow graph comprises a plurality of nodes and a plurality of edges, wherein the plurality of nodes in the data flow graph correspond to operations performed during the process and the plurality of edges in the data flow graph correspond to data passing among the operations, and wherein each respective edge of the plurality of edges is associated with a respective weight based on a size of the data associated with the respective edge;
generating (<NUM>) a topological ordering (115A) for the data flow graph based at least in part on a memory utilization of the process, wherein generating the topological ordering (115A) comprises finding a set of minimum cuts in the data flow graph (<NUM>) based on the weights;
generating (<NUM>) a first modified topological ordering (115B) by inserting, into the topological ordering (115A), one or more new nodes corresponding to memory access based on a predefined memory capacity;
allocating (<NUM>) units of memory in a memory (<NUM>) of the computer processing system (<NUM>) based on the first modified topological ordering (115B); and
increasing the parallel utilization of a plurality of hardware components by generating (<NUM>) a second modified topological ordering(115C) by rearranging one or more nodes in the first modified topological ordering (115B) that one or more corresponding operations are performed in parallel.