# US 2024/0405968 A1 · Executing complex computations using split graphs

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

- Number: US 2024/0405968 A1
- Document ID: US20240405968A1
- Status: Published application
- Kind: A1
- Application number: 18/329,001
- Filed: 2023-06-05
- Published: 2024-12-05
- Earliest claimed: 2023-06-05
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Nir DRUCKER; Ehud AHARONI; Hayim SHAUL
- Web page: https://patentgrep.com/patent/US20240405968A1

## CPC

- H04L 9/008: {involving homomorphic encryption}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

An example system includes a processor to split a graph of operations on tensors into even and odd vertical layers. In response to detecting even-even or odd-odd connections, the processor can fill the even-even or odd-odd connections using a reshape operation. The processor can also initialize outputs on a same layer type with a random packing data structure shape from a first group. The processor can then execute a breadth-first search backward based on a minimum number of shapes per layer.

## Claims

### Claim 1

A system, comprising a processor to:
split a graph of operations on tensors into even and odd vertical layers;
in response to detecting even-even or odd-odd connections, fill the even-even or odd-odd connections using a reshape operation;
initialize outputs on a same layer type with a random packing data structure shape from a group of compatible shapes; and
execute a breadth-first search backward based on a minimum number of shapes per layer.

### Claim 2 (depends on 1)

The system of claim 1, wherein the processor is to output a graph of operations having maximal numbers of shapes prior to stopping points.

### Claim 3 (depends on 1)

The system of claim 1, wherein the processor is to stop executing the bread-first search in response to detecting that all nodes of a layer are assigned with three shapes.

### Claim 4 (depends on 1)

The system of claim 1, wherein the graph is associated with a flow of simple operations to perform a complex operation.

### Claim 5 (depends on 4)

The system of claim 4, wherein the processor is to generate a plurality of graphs based on a received input complex computation, execute a fast tile tensor matrix multiplication on each of the plurality of graphs to calculate a final cost for each of the plurality of graphs, and return a graph of the plurality of graphs that minimizes a final cost.

### Claim 6 (depends on 1)

The system of claim 1, wherein the processor is to split six matrix shapes into two groups comprising the first group, wherein the even vertical layers comprise shapes from one of the two groups and the odd vertical layers comprise shapes from the other of the two groups.

### Claim 7 (depends on 1)

The system of claim 1, wherein the reshape operation comprises a multiplication by an identity element.

### Claim 8

A computer-implemented method, comprising:
splitting, via a processor, a graph of operations on tensors into even and odd vertical layers;
in response to detecting even-even or odd-odd connections, filling, via the processor, the even-even or odd-odd connections using a reshape operation;
initializing, via the processor, outputs on a same layer type with a random packing data structure shape from a group of compatible shapes; and
executing, via the processor, a breadth-first search backward based on a minimum number of shapes per layer.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein executing the breadth-first search comprises stopping in response to detecting an input.

### Claim 10 (depends on 8)

The computer-implemented method of claim 8, wherein executing the breadth-first search comprises stopping in response to detecting that all nodes of a layer are assigned with three shapes.

### Claim 11 (depends on 8)

The computer-implemented method of claim 8, comprising generating, via the processor, a plurality of graphs based on a received input complex computation.

### Claim 12 (depends on 11)

The computer-implemented method of claim 11, comprising executing, via the processor, a fast tile tensor matrix multiplication on each of the plurality of graphs to calculate a final cost for each of the plurality of graphs, and returning, via the processor, a graph of the plurality of graphs that minimizes a final cost.

### Claim 13 (depends on 8)

The computer-implemented method of claim 8, wherein splitting the graph comprises splitting six matrix shapes into two groups comprising the first group, wherein the even vertical layers comprise shapes from one of the two groups and the odd vertical layers comprise shapes from the other of the two groups.

### Claim 14 (depends on 8)

The computer-implemented method of claim 8, wherein filling the even-even or odd-odd connections comprises using a representation of a multiplication by an identity matrix.

### Claim 15

A computer program product for executing complex computations, the computer program product comprising a computer-readable storage medium having program code embodied therewith, the program code executable by a processor to cause the processor to:
split a graph of operations on tensors into even and odd vertical layers;
in response to detecting even-even or odd-odd connections, fill the even-even or odd-odd connections using a reshape operation;
initialize outputs on a same layer type with a random packing data structure shape from a group of compatible shapes; and
execute a breadth-first search backward based on a minimum number of shapes per layer.

### Claim 16 (depends on 15)

The computer program product of claim 15, further comprising program code executable by the processor to stop executing the bread-first search in response to detecting an input.

### Claim 17 (depends on 15)

The computer program product of claim 15, further comprising program code executable by the processor to stop executing the bread-first search in response to detecting that all nodes of a layer are assigned with three shapes.

### Claim 18 (depends on 15)

The computer program product of claim 15, further comprising program code executable by the processor to generate a plurality of graphs based on a received input complex computation.

### Claim 19 (depends on 15)

The computer program product of claim 15, further comprising program code executable by the processor to execute a fast tile tensor matrix multiplication on each of the plurality of graphs to calculate a final cost for each of the plurality of graphs, and return a graph of the plurality of graphs that minimizes a final cost.

### Claim 20 (depends on 15)

The computer program product of claim 15, further comprising program code executable by the processor to split six matrix shapes into two groups comprising the first group, wherein the even vertical layers comprise shapes from one of the two groups and the odd vertical layers comprise shapes from the other of the two groups.
