# US 2022/0066834 A1 · Memory-bound scheduling

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0066834 A1
- Document ID: US20220066834A1
- Status: Published application
- Kind: A1
- Application number: 17/463,393
- Filed: 2021-08-31
- Published: 2022-03-03
- Earliest claimed: 2020-09-01
- Assignees: QUALCOMM Incorporated
- Applicants: QUALCOMM Incorporated
- Inventors: Jonathan DeWitt WOLFE; Erich PLONDKE
- Web page: https://patentgrep.com/patent/US20220066834A1

## CPC

- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 8/45: {Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions}
- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 8/445: {Exploiting fine grain parallelism, i.e. parallelism at instruction level (run-time instruction scheduling G06F9/3836)}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE

## Abstract

Certain aspects of the present disclosure provide techniques for generating execution schedules, comprising receiving a data flow graph for a process, where data flow graph comprises a plurality of nodes and a plurality of edge; 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, where the second modified topological ordering enables increased parallel utilization of a plurality of hardware components.

## Claims

### Claim 1

A method, 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 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.

### Claim 2 (depends on 1)

The method of claim 1, wherein 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.

### Claim 3 (depends on 1)

The method of claim 1, wherein:
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.

### Claim 4 (depends on 3)

The method of claim 3, wherein 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.

### Claim 5 (depends on 4)

The method of claim 4, wherein 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.

### Claim 6 (depends on 3)

The method of claim 3, wherein 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.

### Claim 7 (depends on 3)

The method of claim 3, wherein 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.

### Claim 8 (depends on 7)

The method of claim 7, wherein 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.

### Claim 9 (depends on 7)

The method of claim 7, further comprising selecting the first index node based on determining that the first index node is centered in the data flow graph.

### Claim 10 (depends on 9)

The method of claim 9, further comprising:
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.

### Claim 11

A processing system, comprising:
a memory comprising computer-executable instructions; and
one or more processors configured to execute the computer-executable instructions and cause the processing system to perform an operation 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 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.

### Claim 12 (depends on 11)

The processing system of claim 11, wherein 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.

### Claim 13 (depends on 11)

The processing system of claim 11, wherein:
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.

### Claim 14 (depends on 13)

The processing system of claim 13, wherein 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.

### Claim 15 (depends on 14)

The processing system of claim 14, wherein 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.

### Claim 16 (depends on 13)

The processing system of claim 13, wherein 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.

### Claim 17 (depends on 13)

The processing system of claim 13, wherein 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.

### Claim 18 (depends on 17)

The processing system of claim 17, wherein 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.

### Claim 19 (depends on 17)

The processing system of claim 17, further comprising selecting the first index node based on determining that the first index node is centered in the data flow graph.

### Claim 20 (depends on 19)

The processing system of claim 19, further comprising:
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.

### Claim 21 (depends on 11)

The processing system of claim 11, further comprising:
an ordering component configured to generate the topological ordering;
a memory component configured to generate the first modified topological ordering by inserting the one or more new nodes corresponding to memory access;
an allocation component configured to allocate the units of memory; and
a reordering component configured to generate the second topological ordering by rearranging one or more nodes in the first modified topological ordering.

### Claim 22

A non-transitory computer-readable medium comprising computer-executable instructions that, when executed by one or more processors of a processing system, cause the processing system to perform an operation 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 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.

### Claim 23 (depends on 22)

The non-transitory computer-readable medium of claim 22, wherein 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.

### Claim 24 (depends on 22)

The non-transitory computer-readable medium of claim 22, wherein:
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.

### Claim 25 (depends on 24)

The non-transitory computer-readable medium of claim 24, wherein 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; and
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.

### Claim 26 (depends on 24)

The non-transitory computer-readable medium of claim 24, wherein 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.

### Claim 27 (depends on 24)

The non-transitory computer-readable medium of claim 24, wherein 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.

### Claim 28 (depends on 27)

The non-transitory computer-readable medium of claim 27, wherein 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.

### Claim 29 (depends on 28)

The non-transitory computer-readable medium of claim 28, further comprising:
selecting the first index node based on determining that the first index node is centered in the data flow graph;
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.

### Claim 30

A processing system, comprising:
means for receiving a data flow graph for a process, wherein data flow graph comprises a plurality of nodes and a plurality of edges;
means for generating a topological ordering for the data flow graph based at least in part on memory utilization of the process;
means for 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;
means for allocating units of memory in memory based on the first modified topological ordering; and
means for 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.
