# US 2022/0092247 A1 · Compile Time Logic for Detecting Streaming Compatible and Broadcast Compatible Data Access Patterns

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

- Number: US 2022/0092247 A1
- Document ID: US20220092247A1
- Status: Published application
- Kind: A1
- Application number: 17/031,679
- Filed: 2020-09-24
- Published: 2022-03-24
- Earliest claimed: 2020-09-24
- Assignees: SambaNova Systems, Inc.
- Applicants: SambaNova Systems, Inc.
- Inventors: David Alan KOEPLINGER; Weiwei CHEN; Kevin James BROWN; Xiaoming GU
- Web page: https://patentgrep.com/patent/US20220092247A1

## CPC

- G06F 8/443: {Optimisation}
- G06F 8/451: {Code distribution (considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083)}
- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 12/0842: for multiprocessing or multitasking
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A dataflow graph has operation units that are configured to be producer operation units to produce tensors for execution of the application, and to be consumer operation units to consume the tensors for execution of the application. Compile time logic is configured to process the dataflow graph to determine, for the tensors, expected producer memory layouts, expected consumer memory layouts, and current memory layouts. The expected producer memory layouts specify memory layouts required by the producer operation units that produce the tensors. The expected consumer memory layouts specify the memory layouts required by the consumer operation units that consume the tensors. The current memory layouts specify the memory layouts of the tensors. Each of the memory layouts includes a vector dimension and at least one of a vector ordering and a data alignment.

## Claims

### Claim 1

A system, comprising:
memory storing a dataflow graph for an application, the dataflow graph having operation units that are configured to be producer operation units to produce tensors for execution of the application, and to be consumer operation units to consume the tensors for execution of the application; and
compile time logic having access to the memory and configured to process the dataflow graph to
determine, for the tensors, expected producer memory layouts, expected consumer memory layouts, and current memory layouts,
wherein the expected producer memory layouts specify memory layouts required by the producer operation units that produce the tensors,
wherein the expected consumer memory layouts specify the memory layouts required by the consumer operation units that consume the tensors,
wherein the current memory layouts specify the memory layouts of the tensors, and
wherein each of the memory layouts includes a vector dimension and at least one of a vector ordering and a data alignment; and
store the expected producer memory layouts, the expected consumer memory layouts, and the current memory layouts in the memory for use in processing the tensors through the dataflow graph.

### Claim 2 (depends on 1)

The system of claim 1, wherein the memory stores memory layout functions that generate the expected producer memory layouts and the expected consumer memory layouts based on operation types implemented by the operation units.

### Claim 3 (depends on 2)

The system of claim 2, wherein the compile time logic is further configured to
process the dataflow graph in a forward traversal, starting from a first operation unit and progressing to successive operation units, to determine
the expected producer memory layouts using the memory layout functions, and
the current memory layouts based on the expected producer memory layouts; and
reprocess the dataflow graph in a backward traversal, starting from a last operation unit and progressing to preceding operation units, to determine
the expected consumer memory layouts using the memory layout functions, and
redetermine the current memory layouts based on the expected consumer memory layouts.

### Claim 4 (depends on 3)

The system of claim 3, wherein the compile time logic is further configured to determine the current memory layouts based on a redetermination in a prior backward traversal.

### Claim 5 (depends on 3)

The system of claim 3, wherein the compile time logic is further configured to determine the current memory layouts based on a determination in a prior forward traversal.

### Claim 6 (depends on 3)

The system of claim 3, wherein the compile time logic is further configured to redetermine the current memory layouts based on a majority vote between a plurality of the expected consumer memory layouts.

### Claim 7 (depends on 3)

The system of claim 3, wherein the compile time logic is further configured to iterate the processing and the reprocessing of the dataflow graph until convergence, wherein the convergence occurs when the expected producer memory layouts and the expected consumer memory layouts remain constant between iterations.

### Claim 8 (depends on 7)

The system of claim 7, wherein, upon the convergence, the compile time logic is further configured to further process the dataflow graph to detect undefined instances of the current memory layouts.

### Claim 9 (depends on 8)

The system of claim 8, wherein, the compile time logic is further configured to use a set of heuristics to assign the memory layouts to the undefined instances of the current memory layouts, wherein heuristics in the set of heuristics are based on tensor rank.

### Claim 10 (depends on 9)

The system of claim 9, wherein, upon the convergence, the compile time logic is further configured to detect a memory layout conflict, and to resolve the memory layout conflict by using memory layout conversion operations.

### Claim 11 (depends on 10)

The system of claim 10, wherein the compile time logic is further configured to detect the memory layout conflict when the expected consumer memory layouts are different from corresponding ones of the expected producer memory layouts, and to resolve the memory layout conflict by modifying the dataflow graph to cause the expected consumer memory layouts to match the corresponding ones of the expected producer memory layouts.

### Claim 12 (depends on 10)

The system of claim 10, wherein the compile time logic is further configured to detect the memory layout conflict when the expected consumer memory layouts are different from corresponding ones of the current memory layouts, and to resolve the memory layout conflict by modifying the dataflow graph to cause the expected consumer memory layouts to match the corresponding ones of the current memory layouts.

### Claim 13 (depends on 10)

The system of claim 10, wherein, upon the convergence, the compile time logic is further configured to detect multiple instances of the memory layout conflict, and to resolve the multiple instances of the memory layout conflict by using the memory layout conversion operations.

### Claim 14 (depends on 12)

The system of claim 12, wherein the memory layout conversion operations include a transpose operation that modifies the current memory layouts by changing the vector dimension of corresponding ones of the tensors.

### Claim 15 (depends on 12)

The system of claim 12, wherein the memory layout conversion operations include a shuffle operation that modifies the current memory layouts by changing the vector ordering of the corresponding ones of the tensors.

### Claim 16 (depends on 12)

The system of claim 12, wherein the memory layout conversion operations include a realignment operation that modifies the current memory layouts by changing the data alignment of the corresponding ones of the tensors.

### Claim 17 (depends on 10)

The system of claim 10, wherein the compile time logic is further configured to insert, in the dataflow graph, new operation units that implement the memory layout conversion operations, and to generate an updated version of the dataflow graph.

### Claim 18 (depends on 17)

The system of claim 17, wherein the compile time logic is further configured to iterate the processing and the reprocessing of the updated version of the dataflow graph as long as the undefined instances of the current memory layouts and the memory layout conflict are detected.

### Claim 19

A computer-implemented method, including:
storing a dataflow graph for an application, the dataflow graph having operation units that are configured to be producer operation units to produce tensors for execution of the application, and to be consumer operation units to consume the tensors for execution of the application;
processing the dataflow graph to determine, for the tensors, expected producer memory layouts, expected consumer memory layouts, and current memory layouts,
wherein the expected producer memory layouts specify memory layouts required by the producer operation units that produce the tensors,
wherein the expected consumer memory layouts specify the memory layouts required by the consumer operation units that consume the tensors,
wherein the current memory layouts specify the memory layouts of the tensors, and
wherein each of the memory layouts includes a vector dimension and at least one of a vector ordering and a data alignment; and
storing the expected producer memory layouts, the expected consumer memory layouts, and the current memory layouts for use in processing the tensors through the dataflow graph.

### Claim 20

A non-transitory computer readable storage medium impressed with computer program instructions, the instructions, when executed on a processor, implement a method comprising:
storing a dataflow graph for an application, the dataflow graph having operation units that are configured to be producer operation units to produce tensors for execution of the application, and to be consumer operation units to consume the tensors for execution of the application;
processing the dataflow graph to determine, for the tensors, expected producer memory layouts, expected consumer memory layouts, and current memory layouts,
wherein the expected producer memory layouts specify memory layouts required by the producer operation units that produce the tensors,
wherein the expected consumer memory layouts specify the memory layouts required by the consumer operation units that consume the tensors,
wherein the current memory layouts specify the memory layouts of the tensors, and
wherein each of the memory layouts includes a vector dimension and at least one of a vector ordering and a data alignment; and
storing the expected producer memory layouts, the expected consumer memory layouts, and the current memory layouts for use in processing the tensors through the dataflow graph.

### Claim 21

A system, comprising:
memory storing a dataflow graph for an application, the dataflow graph having operation units that are configured to be producer operation units to produce tensors for execution of the application, and to be consumer operation units to consume the tensors for execution of the application; and
compile time logic having access to the memory and configured to process the dataflow graph to
determine, for the tensors, expected producer memory layouts, expected consumer memory layouts, and current memory layouts,
wherein the expected producer memory layouts specify memory layouts required by the producer operation units that produce the tensors,
wherein the expected consumer memory layouts specify the memory layouts required by the consumer operation units that consume the tensors,
wherein the current memory layouts specify the memory layouts of the tensors, and
wherein each of the memory layouts includes a vector dimension and at least one of a vector ordering and a data alignment;
detect memory layout conflicts when the expected consumer memory layouts are different from corresponding ones of the expected producer memory layouts and/or when the expected consumer memory layouts are different from corresponding ones of the current memory layouts; and
resolve the memory layout conflicts by modifying the dataflow graph to cause the expected consumer memory layouts to match the corresponding ones of the expected producer memory layouts and/or to cause the expected consumer memory layouts to match the corresponding ones of the current memory layouts.
