# US 10,872,057 B1 · Partitioning in a compiler flow for a heterogeneous multi-core architecture

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

- Number: US 10,872,057 B1
- Document ID: US10872057B1
- Status: Granted
- Kind: B1
- Application number: 16/420,927
- Filed: 2019-05-23
- Granted: 2020-12-22
- Earliest claimed: 2019-05-23
- Assignees: Xilinx, Inc.
- Applicants: Xilinx, Inc.
- Inventors: Prashant S. Rawat; Shail Aditya Gupta
- Web page: https://patentgrep.com/patent/US10872057B1

## CPC

- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 15/7807: {System on chip, i.e. computer system on a single chip; System in package, i.e. computer system on one or more chips in a single package}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

An example method of placing kernels of an application in a data processing engine array (DPE) of a system on chip (SOC) includes obtaining a graph of the application having nodes representing the kernels and edges representing communication between the kernels, sorting the kernels based on runtime ratio associated with each of the kernels, processing the sorted kernels sequentially to place into partitions, determining an execution order of kernels in each of the partitions; and generating implementation data for the SOC for implementing the application therein based on the determined partitions and execution order for each of the partitions.

## Claims

### Claim 1

A method of placing kernels of an application in a data processing engine array (DPE) of a system on chip (SOC), comprising:
obtaining a graph of the application having nodes representing the kernels and edges representing communication between the kernels;
sorting the kernels based on runtime ratio associated with each of the kernels;
processing the sorted kernels sequentially to place into partitions;
determining an execution order of kernels in each of the partitions; and
generating implementation data for the SOC for implementing the application therein based on the determined partitions and execution order for each of the partitions.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
grouping a portion of the kernels into initial partitions based on user-defined constraints.

### Claim 3 (depends on 2)

The method of claim 2, wherein the portion of the kernels is grouped into the initial partitions based on at least one of an absolute constraint and a relative constraint in the user-defined constraints.

### Claim 4 (depends on 1)

The method of claim 1, wherein the step of processing the sorted kernels comprises:
maintaining a cumulative runtime ratio of each partition to be less than or equal to a threshold value.

### Claim 5 (depends on 1)

The method of claim 1, wherein the step of processing the sorted kernels comprises:
updating location constraints of each partition based on respective kernels assigned thereto.

### Claim 6 (depends on 5)

The method of claim 5, wherein the step of updating the location constraints of each partition comprises:
updating the location constraints of a first partition of the partitions based on at least one of an absolute constraint assigned to the kernel, a physical constraint of the data processing engine array, and a dynamic constraint resulting from the step of processing the sorted kernels.

### Claim 7 (depends on 1)

The method of claim 1, wherein the step of processing the sorted kernels comprises:
satisfying physical constraints of the DPE array.

### Claim 8 (depends on 7)

The method of claim 7, wherein the physical constraints comprise at least one of a defined number of input/output ports for each partition and a defined type of connection between kernels within each partition.

### Claim 9 (depends on 1)

The method of claim 1, wherein the step of processing the sorted kernels comprises:
satisfying one or more dynamic location constraints arising from placement of kernels into the partitions.

### Claim 10 (depends on 1)

The method of claim 1, wherein the step of processing the sorted kernels comprises:
placing a first kernel of the kernels into an existing partition of the partitions or a new partition added to the partitions, where selection of the existing partition or the new partition is based on constraints of the first kernel and constraints of one or more kernels in the existing partition.

### Claim 11 (depends on 1)

The method of claim 1, further comprising:
performing post-partitioning optimizations for communication minimization among the kernels.

### Claim 12

A computer system, comprising:
a memory configured to store program code; and
a processor configured to execute the program code to place kernels of an application in a data processing engine array (DPE) of a system on chip (SOC) by:
obtaining a graph of the application having nodes representing the kernels and edges representing communication between the kernels;
sorting the kernels based on runtime ratio associated with each of the kernels;
processing the sorted kernels sequentially to place into partitions;
determining an execution order of kernels in each of the partitions; and
generating implementation data for the SOC for implementing the application therein based on the determined partitions and execution order for each of the partitions.

### Claim 13 (depends on 12)

The computer system of claim 12, further comprising:
grouping a portion of the kernels into initial partitions based on user-defined constraints.

### Claim 14 (depends on 13)

The computer system of claim 13, wherein the portion of the kernels is grouped into the initial partitions based on at least one of an absolute constraint and a relative constraint in the user-defined constraints.

### Claim 15 (depends on 12)

The computer system of claim 12, wherein the processing the sorted kernels comprises:
maintaining a cumulative runtime ratio of each partition to be less than or equal to a threshold value.

### Claim 16 (depends on 12)

The computer system of claim 12, wherein the processing the sorted kernels comprises:
updating location constraints of each partition based on respective kernels assigned thereto.

### Claim 17 (depends on 16)

The computer system of claim 16, wherein the updating the location constraints of each partition comprises:
updating the location constraints of a first partition of the partitions based on at least one of an absolute constraint assigned to the kernel, a physical constraint of the data processing engine array, and a dynamic constraint resulting from the step of processing the sorted kernels.

### Claim 18 (depends on 12)

The computer system of claim 12, wherein the processing the sorted kernels comprises:
satisfying physical constraints of the DPE array.

### Claim 19 (depends on 18)

The computer system of claim 18, wherein the physical constraints comprise at least one of a defined number of input/output ports for each partition and a defined type of connection between kernels within each partition.

### Claim 20 (depends on 16)

The computer system of claim 16, wherein the processing the sorted kernels comprises:
satisfying one or more dynamic location constraints arising from placement of kernels into the partitions.