Sequence partition based schedule optimization

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.

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.