Estimating a Cost of Implementing an Operation Unit Graph on a Reconfigurable Processor

1 . A method of operating a cost estimation tool for estimating a cost of implementing an operation unit graph on a reconfigurable processor, comprising:

receiving the operation unit graph comprising a first logical unit that performs a first data operation and has a first port, a second logical unit that performs a second data operation and has a second port, and a logical edge that connects the first port with the second port;

determining a timing group from a predetermined number of timing groups for the logical edge;

determining a first upper bandwidth limit of the first port based on the first data operation;

determining a second upper bandwidth limit of the second port based on the second data operation;

determining a logical edge bandwidth of the logical edge based on the first and second upper bandwidth limits; and

providing the logical edge bandwidth and the timing group as a cost estimation of implementing the operation unit graph on the reconfigurable processor.

2 . The method of claim 1 , wherein the reconfigurable processor comprises arrays of coarse-grained reconfigurable (CGR) units.

3 . The method of claim 1 , wherein one of the first and second logical units comprises a compute unit or a memory unit.

4 . The method of claim 1 , wherein determining the timing group from the predetermined number of timing groups for the logical edge further comprises:

determining whether the logical edge is active during a first execution phase of the operation unit graph or during a second execution phase of the operation unit graph, wherein the first and second execution phases are non-overlapping.

5 . The method of claim 4 , further comprising:

in response to determining that the logical edge is active during the first execution phase, assigning a first timing group of the predetermined number of timing groups to the logical edge; and

in response to determining that the logical edge is active during the second execution phase, assigning a second timing group of the predetermined number of timing groups to the logical edge.

6 . The method of claim 1 , wherein the first logical unit comprises assembler code that is associated with the first data operation.

7 . The method of claim 6 , wherein determining the first upper bandwidth limit of the first port based on the first data operation further comprises:

determining a pattern in the assembler code.

8 . The method of claim 7 , further comprising:

in response to determining that the pattern in the assembler code comprises a sequence-id based address calculation, determining the first upper bandwidth limit of the first port based on a length of an input first-in first-out (FIFO) buffer of the first port divided by a number of arithmetic logic unit (ALU) stages used for address calculation.

9 . The method of claim 7 , further comprising:

in response to determining that the pattern in the assembler code comprises bubbles in a pipeline of a memory unit, determining the first upper bandwidth limit of the first port based on a number of vectors processed by the memory unit to trigger a token generation divided by a sum of a constant that is based on the bubbles being inserted into the pipeline and the number of vectors processed by the memory unit to trigger the token generation.

10 . The method of claim 7 , further comprising:

in response to determining that the pattern in the assembler code comprises a dequeue operation of a memory unit, determining the first upper bandwidth limit of the first port based on one divided by a number of memory access operations that occur before the memory unit consumes one entry from an input FIFO buffer of the first port.

11 . The method of claim 7 , further comprising:

in response to determining that the pattern in the assembler code comprises a dequeue operation of a compute unit, determining the first upper bandwidth limit of the first port based on one divided by a number of enable signals that flow through a number of arithmetic logic unit (ALU) stages.

12 . The method of claim 7 , further comprising:

in response to determining that the pattern in the assembler code comprises a tail function of a compute unit or a systolic operation of a compute unit, determining the first upper bandwidth limit of the first port based on a number of vectors being processed by the compute unit divided by a sum of a constant and a latency of the compute unit.

13 . A system for implementing an operation unit graph on a reconfigurable processor, comprising:

a cost estimation tool for estimating a cost of implementing the operation unit graph on the reconfigurable processor, wherein the cost estimation tool is configured to:

receive the operation unit graph that comprises a first logical unit that performs a first data operation and has a first port, a second logical unit that performs a second data operation and has a second port, and a logical edge that connects the first port with the second port;

determine a timing group from a predetermined number of timing groups for the logical edge;

determine a first upper bandwidth limit of the first port based on the first data operation;

determine a second upper bandwidth limit of the second port based on the second data operation;

determine a logical edge bandwidth of the logical edge based on the first and second upper bandwidth limits; and

provide the logical edge bandwidth and the timing group as a cost estimation of implementing the operation unit graph on the reconfigurable processor.

14 . The system of claim 13 , wherein the reconfigurable processor comprises arrays of coarse-grained reconfigurable (CGR) units.

15 . The system of claim 13 , wherein one of the first and second logical units comprises a compute unit or a memory unit.

16 . The system of claim 13 , wherein the cost estimation tool, for determining the timing group from the predetermined number of timing groups for the logical edge, is further configured to:

determine whether the logical edge is active during a first execution phase of the operation unit graph or during a second execution phase of the operation unit graph, wherein the first and second execution phases are non-overlapping.

17 . The system of claim 16 , wherein the cost estimation tool is further configured to:

in response to determining that the logical edge is active during the first execution phase, assign a first timing group of the predetermined number of timing groups to the logical edge; and

in response to determining that the logical edge is active during the second execution phase, assign a second timing group of the predetermined number of timing groups to the logical edge.

18 . The system of claim 13 , wherein the first logical unit comprises assembler code that is associated with the first data operation.

19 . The system of claim 18 , wherein the cost estimation tool, for determining the first upper bandwidth limit of the first port based on the first data operation, is further configured to:

determine a pattern in the assembler code; and

determine the first upper bandwidth limit of the first port based on the pattern in the assembler code.

20 . A non-transitory computer-readable storage medium including instructions that, when executed by a processing unit, cause the processing unit to operate a cost estimation tool for estimating a cost of implementing an operation unit graph on a reconfigurable processor, the instructions comprising:

receiving the operation unit graph having logical edges, logical units, and ports at associated logical units, wherein the logical edges connect with the logical units at the ports, and wherein the logical units perform data operations;

determining timing groups from a predetermined number of timing groups for the logical edges;

determining upper bandwidth limits of the ports based on the data operations of the associated logical units;

determining logical edge bandwidths of the logical edges based on the upper bandwidth limits of the ports at which the logical edges connect with the logical units; and

providing the logical edge bandwidths and the timing groups of the logical edges as a cost estimation of implementing the operation unit graph on the reconfigurable processor.