# US 2024/0202001 A1 · Sequence partition based schedule optimization

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

- Number: US 2024/0202001 A1
- Document ID: US20240202001A1
- Status: Published application
- Kind: A1
- Application number: 18/067,016
- Filed: 2022-12-16
- Published: 2024-06-20
- Earliest claimed: 2022-12-16
- Assignees: Edgecortix Inc.
- Applicants: Edgecortix Inc
- Inventors: Jens HUTHMANN; Sakyasingha DASGUPTA; Nikolay NEZ
- Web page: https://patentgrep.com/patent/US20240202001A1

## CPC

- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 9/3838: {Dependency mechanisms, e.g. register scoreboarding}
- G06F 5/01: for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)}
- G06F 7/32: Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence {merging methods in general}(G06F7/36 takes precedence)
- G06F 9/3856: {Reordering of instructions, e.g. using queues or age tags}
- G06F 9/3861: {Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Sequence partition based schedule optimization is performed by generating a sequence and a schedule based on the sequence, dividing the sequence into a plurality of sequence partitions based on the schedule and the data dependency graph, each sequence partition including a portion of the plurality of instructions and a portion of the plurality of buffers, performing, for each sequence partition, a plurality of partition optimizing iterations, and merging the plurality of sequence partitions to produce a merged schedule.

## Claims

### Claim 1

A non-transitory computer-readable medium including instructions executable by a processor to cause the processor to perform operations comprising:
assigning each instruction among a plurality of instructions of a data dependency graph to a corresponding computation unit among a plurality of computation units and each buffer among a plurality of buffers of the data dependency graph to a corresponding memory unit among a plurality of memory units;
ordering the plurality of instructions and the plurality of buffers to produce a sequence;
producing a schedule based on the sequence;
dividing the sequence into a plurality of sequence partitions based on the schedule and the data dependency graph, each sequence partition including a portion of the plurality of instructions and a portion of the plurality of buffers;
performing, for each sequence partition, a plurality of partition optimizing iterations of
allotting the instructions among the portion of the plurality of instructions and the buffers among the portion of the plurality of buffers in the sequence partition to intervals of time to produce a partition schedule,
restoring the sequence partition of a previous iteration in response to determining that a partition schedule of the previous iteration is more optimal than the partition schedule of a current iteration, and
mutating the sequence partition; and
merging the plurality of sequence partitions to produce a merged schedule.

### Claim 2 (depends on 1)

The computer-readable medium of claim 1, wherein the operations further comprise
merging the plurality of sequence partitions to produce a merged sequence after performing the plurality of partition optimizing iterations;
performing a plurality of merged schedule optimizing iterations of mutating the merged sequence,
allotting the instructions among the plurality of instructions and the buffers among the plurality of buffers in the merged sequence to intervals of time to reproduce the merged schedule, and
restoring the sequence of a previous iteration in response to determining that the merged schedule of the previous iteration is more optimal than the merged schedule of a current iteration.

### Claim 3 (depends on 1)

The computer-readable medium of claim 1, wherein the producing the schedule includes performing a plurality of schedule optimizing iterations of
allotting the instructions among the plurality of instructions and the buffers among the plurality of buffers in the sequence to intervals of time,
restoring the sequence of a previous iteration in response to determining that a schedule of the previous iteration is more optimal than the schedule of a current iteration, and
mutating the sequence.

### Claim 4 (depends on 1)

The computer-readable medium of claim 1, wherein the dividing the sequence includes:
drawing a plurality of initial boundaries in the schedule;
shifting, for each boundary, the initial boundary to intersect buffers among the plurality of buffers in the data dependency graph; and
duplicating each intersected buffer among the plurality of buffers.

### Claim 5 (depends on 4)

The computer-readable medium of claim 4, wherein the dividing the sequence further includes:
adding dummy instructions to each intersected buffer and each duplicated buffer.

### Claim 6 (depends on 1)

The computer-readable medium of claim 1, wherein the mutating includes performing at least one of:
reordering the instructions among the portion of the plurality of instructions in the sequence partition,
reassigning the instructions among the portion of the plurality of instructions in the sequence partition, or
reassigning the buffers among the portion of the plurality of buffers in the sequence partition.

### Claim 7 (depends on 1)

The computer-readable medium of claim 1, wherein the dividing the sequence includes dividing the sequence into a number of sequence partitions of no less than three.

### Claim 8 (depends on 1)

The computer-readable medium of claim 1, wherein the dividing the sequence includes dividing the sequence into a number of sequence partitions such that each sequence has no less than about one-hundred instructions.

### Claim 9

A method comprising:
assigning each instruction among a plurality of instructions of a data dependency graph to a corresponding computation unit among a plurality of computation units and each buffer among a plurality of buffers of the data dependency graph to a corresponding memory unit among a plurality of memory units;
ordering the plurality of instructions and the plurality of buffers to produce a sequence;
producing a schedule based on the sequence;
dividing the sequence into a plurality of sequence partitions based on the schedule and the data dependency graph, each sequence partition including a portion of the plurality of instructions and a portion of the plurality of buffers;
performing, for each sequence partition, a plurality of partition optimizing iterations of
allotting the instructions among the portion of the plurality of instructions and the buffers among the portion of the plurality of buffers in the sequence partition to intervals of time to produce a partition schedule,
restoring the sequence partition of a previous iteration in response to determining that a partition schedule of the previous iteration is more optimal than the partition schedule of a current iteration, and
mutating the sequence partition; and
merging the plurality of sequence partitions to produce a merged schedule.

### Claim 10 (depends on 9)

The method of claim 9, further comprising
merging the plurality of sequence partitions to produce a merged sequence after performing the plurality of partition optimizing iterations;
performing a plurality of merged schedule optimizing iterations of
mutating the merged sequence,
allotting the instructions among the plurality of instructions and the buffers among the plurality of buffers in the merged sequence to intervals of time to reproduce the merged schedule, and
restoring the sequence of a previous iteration in response to determining that the merged schedule of the previous iteration is more optimal than the merged schedule of a current iteration.

### Claim 11 (depends on 9)

The method of claim 9, wherein the producing the schedule includes performing a plurality of schedule optimizing iterations of
allotting the instructions among the plurality of instructions and the buffers among the plurality of buffers in the sequence to intervals of time,
restoring the sequence of a previous iteration in response to determining that a schedule of the previous iteration is more optimal than the schedule of a current iteration, and
mutating the sequence.

### Claim 12 (depends on 9)

The method of claim 9, wherein the dividing the sequence includes:
drawing a plurality of initial boundaries in the schedule;
shifting, for each boundary, the initial boundary to intersect buffers among the plurality of buffers in the data dependency graph; and
duplicating each intersected buffer among the plurality of buffers.

### Claim 13 (depends on 12)

The method of claim 12, wherein the dividing the sequence further includes:
adding dummy instructions to each intersected buffer and each duplicated buffer.

### Claim 14 (depends on 9)

The method of claim 9, wherein the mutating includes performing at least one of:
reordering the instructions among the portion of the plurality of instructions in the sequence partition,
reassigning the instructions among the portion of the plurality of instructions in the sequence partition, or
reassigning the buffers among the portion of the plurality of buffers in the sequence partition.

### Claim 15 (depends on 9)

The method of claim 9, wherein the dividing the sequence includes dividing the sequence into a number of sequence partitions of no less than three.

### Claim 16 (depends on 9)

The method of claim 9, wherein the dividing the sequence includes dividing the sequence into a number of sequence partitions such that each sequence has no less than about one-hundred instructions.

### Claim 17

An apparatus comprising:
a controller including circuitry configured to:
assign each instruction among a plurality of instructions of a data dependency graph to a corresponding computation unit among a plurality of computation units and each buffer among a plurality of buffers of the data dependency graph to a corresponding memory unit among a plurality of memory units;
order the plurality of instructions and the plurality of buffers to produce a sequence;
produce a schedule based on the sequence;
divide the sequence into a plurality of sequence partitions based on the schedule and the data dependency graph, each sequence partition including a portion of the plurality of instructions and a portion of the plurality of buffers;
perform, for each sequence partition, a plurality of partition optimizing iterations of
allotting the instructions among the portion of the plurality of instructions and the buffers among the portion of the plurality of buffers in the sequence partition to intervals of time to produce a partition schedule,
restoring the sequence partition of a previous iteration in response to determining that a partition schedule of the previous iteration is more optimal than the partition schedule of a current iteration, and
mutating the sequence partition;
merge the plurality of partition schedules produce a merged schedule.

### Claim 18 (depends on 17)

The apparatus of claim 17, wherein the circuitry is further configured to
merge the plurality of sequence partitions to produce a merged sequence after performing the plurality of partition optimizing iterations;
perform a plurality of merged schedule optimizing iterations of
mutating the merged sequence,
allotting the instructions among the plurality of instructions and the buffers among the plurality of buffers in the merged sequence to intervals of time to reproduce the merged schedule, and
restoring the sequence of a previous iteration in response to determining that the merged schedule of the previous iteration is more optimal than the merged schedule of a current iteration.

### Claim 19 (depends on 17)

The apparatus of claim 17, wherein the producing the schedule includes performing a plurality of schedule optimizing iterations of
allotting the instructions among the plurality of instructions and the buffers among the plurality of buffers in the sequence to intervals of time,
restoring the sequence of a previous iteration in response to determining that a schedule of the previous iteration is more optimal than the schedule of a current iteration, and
mutating the sequence.

### Claim 20 (depends on 17)

The apparatus of claim 17, wherein the dividing the sequence includes:
drawing a plurality of initial boundaries in the schedule;
shifting, for each boundary, the initial boundary to intersect buffers among the plurality of buffers in the data dependency graph; and
duplicating each intersected buffer among the plurality of buffers.