Estimating a scaled cost of implementing an operation unit graph on a reconfigurable processor
A cost estimation tool in a system for implementing an operation unit graph on a reconfigurable processor is presented as well as a method of operating a cost estimation tool for determining scaled logical edge bandwidths in an operation unit graph in preparation of placing and routing the operation unit graph onto a reconfigurable processor. The cost estimation tool may be configured to receive the operation unit graph, divide the operation unit graph in first and second subgraphs, determine maximum latencies of the first and second subgraphs, and determine a scaled logical edge bandwidth of a logical edge that couples a first logical unit of M logical units in the first subgraph with a second logical unit of N logical units in the first subgraph based on M, N, and scaled bandwidth limits of the M and N logical units.
1. A method of operating a compiler that is executable in one or more processors coupled to a storage medium, comprising:
receiving an operation unit graph comprising logical units and logical edges that couple the logical units, wherein each one of the logical units is associated with a data operation;
dividing the operation unit graph into first and second subgraphs, wherein latencies of the first and second subgraphs are independent from each other, wherein M logical units of the logical units in the first subgraph transmit data to N logical units of the logical units in the first subgraph, where M and N are integers greater than zero;
determining a first maximum latency of the first subgraph and a second maximum latency of the second subgraph;
determining first upper bandwidth limits of each one of the M logical units based on the data operation associated with the respective one of the M logical units;
determining second upper bandwidth limits of each one of the N logical units based on the data operation associated with the respective one of the N logical units;
determining first scaled bandwidth limits of each one of the M logical units based on the first upper bandwidth limits, the first maximum latency, and a maximum of the first and second maximum latencies;
determining second scaled bandwidth limits of the N logical units based on the second upper bandwidth limits, the first maximum latency, and the maximum of the first and second maximum latencies;
determining a scaled logical edge bandwidth of a logical edge that couples a first logical unit of the M logical units with a second logical unit of the N logical units based on M, N, the first scaled bandwidth limits, and the second scaled bandwidth limits;
receiving a hardware description describing an arrangement of interconnects, physical compute units and/or physical memory units on the reconfigurable processor;
using the hardware description and the scaled logical edge bandwidth to determine an assignment of the logical units and the logical edges onto the interconnects, the physical compute units and/or the physical memory units of the reconfigurable processor during placement and routing of the operation unit graph; and
generating a configuration file that is adapted for being applied to the reconfigurable processor for configuring the interconnects, the physical compute units and/or the physical memory units with the assignment of the logical units and the logical edges.
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 the first logical unit comprises a compute unit or a memory unit.
4. The method of claim 1 , wherein the first logical unit comprises assembler code that is associated with the data operation of the first logical unit, and wherein determining the first upper bandwidth limits of each one of the M logical units based on the data operation associated with the respective one of the M logical units further comprises:
determining a pattern in the assembler code of the first logical unit.
5. The method of claim 4 , 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 logical unit based on a depth of an input first-in first-out (FIFO) buffer of a first port divided by a number of arithmetic logic unit (ALU) stages used for address calculation;
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 logical unit 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;
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 logical unit 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;
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 logical unit based on one divided by a number of enable signals that flow through a number of arithmetic logic unit (ALU) stages; and
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 logical unit based on a number of vectors being processed by the compute unit divided by a sum of a constant and a duration for consuming the vectors.
6. The method of claim 1 , wherein the first subgraph includes a start stage buffer and an end stage buffer, and wherein determining the first maximum latency of the first subgraph further comprises:
determining K latencies for K paths in the first subgraph, where K is an integer greater than zero, and wherein each one of the K latencies is associated with a different one of the K paths in the first subgraph and begins with a start stage buffer read start operation and ends with an end stage buffer write done operation.
7. The method of claim 6 , wherein a path of the K paths includes a plurality of template nodes having template node latencies, and wherein determining the K latencies for the K paths in the first subgraph further comprises:
determining a latency for the path as a sum of the template node latencies of the plurality of template nodes of the path.
8. The method of claim 6 , wherein determining the first maximum latency of the first subgraph further comprises:
determining the first maximum latency of the first subgraph as a maximum of the K latencies of the K paths in the first subgraph.
9. The method of claim 1 , wherein determining the first scaled bandwidth limits of the M logical units based on the first upper bandwidth limits, the first maximum latency, and the maximum of the first and second maximum latencies further comprises:
determining the first scaled bandwidths limits by multiplying the first upper bandwidth limits with the first maximum latency divided by the maximum of the first and second maximum latencies.
10. The method of claim 1 , wherein determining the scaled logical edge bandwidth of the logical edge that couples the first logical unit of the M logical units with the second logical unit of the N logical units based on M, N, the first scaled bandwidth limits, and the second scaled bandwidth limits further comprises:
in response to M and N being equal to one, determining the scaled logical edge bandwidth of the logical edge based on the minimum of the first scaled bandwidth limit and the second scaled bandwidth limit.
11. The method of claim 1 , wherein determining the scaled logical edge bandwidth of the logical edge that couples the first logical unit of the M logical units with the second logical unit of the N logical units based on M, N, the first scaled bandwidth limits, and the second scaled bandwidth limits further comprises:
in response to M being greater than one and N being equal to one, determining the scaled logical edge bandwidth of the logical edge based on the minimum of the second scaled bandwidth limit divided by M and the first scaled bandwidth limits.
12. The method of claim 1 , wherein determining the scaled logical edge bandwidth of the logical edge that couples the first logical unit of the M logical units with the second logical unit of the N logical units based on M, N, the first scaled bandwidth limits, and the second scaled bandwidth limits further comprises:
in response to M being equal to one and N being greater than one, determining the scaled logical edge bandwidth of the logical edge based on the minimum of the first scaled bandwidth limit and the minimum of all the second scaled bandwidth limits.
13. The method of claim 1 , wherein determining the scaled logical edge bandwidth of the logical edge that couples the first logical unit of the M logical units with the second logical unit of the N logical units based on M, N, the first scaled bandwidth limits, and the second scaled bandwidth limits further comprises:
in response to M being greater than one and N being greater than one, determining the scaled logical edge bandwidth of the logical edge based on the minimum of the minimum of the second scaled bandwidth limits divided by M and the first scaled bandwidth limits and the minimum of the first scaled bandwidth limits and the minimum of all the second scaled bandwidth limits.
14. A system for implementing an operation unit graph on a reconfigurable processor having interconnects, physical compute units and/or physical memory units, comprising:
one or more host processors coupled to a storage medium; and
a compiler executable in any of the one or more host processors wherein the compiler, is configured to:
receive the operation unit graph comprising logical units and logical edges that couple the logical units, wherein each one of the logical units is associated with a data operation,
divide the operation unit graph into first and second subgraphs, wherein latencies of the first and second subgraphs are independent from each other, wherein M logical units of the logical units in the first subgraph transmit data to N logical units of the logical units in the first subgraph, where M and N are integers greater than zero,
determine a first maximum latency of the first subgraph and a second maximum latency of the second subgraph,
determine first upper bandwidth limits of each one of the M logical units based on the data operation associated with the respective one of the M logical units,
determine second upper bandwidth limits of each one of the N logical units based on the data operation associated with the respective one of the N logical units,
determine first scaled bandwidth limits of each one of the M logical units based on the first upper bandwidth limits, the first maximum latency, and a maximum of the first and second maximum latencies,
determine second scaled bandwidth limits of the N logical units based on the second upper bandwidth limits, the first maximum latency, and the maximum of the first and second maximum latencies,
determine a scaled logical edge bandwidth of a logical edge that couples a first logical unit of the M logical units with a second logical unit of the N logical units based on M, N, the first scaled bandwidth limits, and the second scaled bandwidth limits;
receive a hardware description describing an arrangement of the interconnects, the physical compute units, and/or the physical memory units on the reconfigurable processor;
use the hardware description and the scaled logical edge bandwidth to determine an assignment of the logical units and the logical edges onto the interconnects, the physical compute units and/or the physical memory units during placement and routing of the operation unit graph; and
generate a configuration file that is adapted for being applied to the reconfigurable processor for configuring the interconnects, the physical compute units and/or the physical memory units with the assignment of the logical units and the logical edges.
15. The system of claim 14 , wherein the first subgraph includes a start stage buffer and an end stage buffer, and wherein the compiler, for determining the first maximum latency of the first subgraph, is further configured to:
determine K latencies for K paths in the first subgraph, where K is an integer greater than zero, and wherein each one of the K latencies is associated with a different one of the K paths in the first subgraph and begins with a start stage buffer read start operation and ends with an end stage buffer write done operation.
16. The system of claim 15 , wherein a path of the K paths includes a plurality of template nodes having template node latencies, and wherein the compiler, for determining the K latencies for the K paths in the first subgraph, is further configured to:
determine a latency for the path as a sum of the template node latencies of the plurality of template nodes of the path.
17. The system of claim 15 , wherein the compiler, for determining the first maximum latency of the first subgraph, is further configured to:
determine the first maximum latency of the first subgraph as a maximum of the K latencies of the K paths in the first subgraph.
18. The system of claim 14 , wherein the compiler, for determining the first scaled bandwidth limits of the M logical units based on the first upper bandwidth limits, the first maximum latency, and the maximum of the first and second maximum latencies, is further configured to:
determine the first scaled bandwidths limits by multiplying the first upper bandwidth limits with the first maximum latency divided by the maximum of the first and second maximum latencies.
19. The system of claim 14 , wherein the compiler, for determining the scaled logical edge bandwidth of the logical edge that couples the first logical unit of the M logical units with the second logical unit of the N logical units based on M, N, the first scaled bandwidth limits, and the second scaled bandwidth limits, is further configured to:
in response to M and N being equal to one, determine the scaled logical edge bandwidth of the logical edge based on the minimum of the first scaled bandwidth limit and the second scaled bandwidth limit;
in response to M being greater than one and N being equal to one, determine the scaled logical edge bandwidth of the logical edge based on the minimum of the second scaled bandwidth limit divided by M and the first scaled bandwidth limits;
in response to M being equal to one and N being greater than one, determine the scaled logical edge bandwidth of the logical edge based on the minimum of the first scaled bandwidth limit and the minimum of all the second scaled bandwidth limits; and
in response to M being greater than one and N being greater than one, determine the scaled logical edge bandwidth of the logical edge based on the minimum of the minimum of the second scaled bandwidth limits divided by M and the first scaled bandwidth limits and the minimum of the first scaled bandwidth limits and the minimum of all the second scaled bandwidth limits.
20. A non-transitory computer-readable storage medium including instructions that, when executed by a processing unit, cause the processing unit to operate a compiler, the instructions comprising:
receiving an operation unit graph comprising logical units and logical edges that couple the logical units, wherein each one of the logical units is associated with a data operation;
dividing the operation unit graph into first and second subgraphs, wherein latencies of the first and second subgraphs are independent from each other, wherein M logical units of the logical units in the first subgraph transmit data to N logical units of the logical units in the first subgraph, where M and N are integers greater than zero;
determining a first maximum latency of the first subgraph and a second maximum latency of the second subgraph;
determining first upper bandwidth limits of each one of the M logical units based on the data operation associated with the respective one of the M logical units;
determining second upper bandwidth limits of each one of the N logical units based on the data operation associated with the respective one of the N logical units;
determining first scaled bandwidth limits of each one of the M logical units based on the first upper bandwidth limits, the first maximum latency, and a maximum of the first and second maximum latencies;
determining second scaled bandwidth limits of the N logical units based on the second upper bandwidth limits, the first maximum latency, and the maximum of the first and second maximum latencies;
determining a scaled logical edge bandwidth of a logical edge that couples a first logical unit of the M logical units with a second logical unit of the N logical units based on M, N, the first scaled bandwidth limits, and the second scaled bandwidth limits;
receiving a hardware description describing an arrangement of interconnects, physical compute units and/or physical memory units on the reconfigurable processor;
using the hardware description and the scaled logical edge bandwidth to determine an assignment of the logical units and the logical edges onto the interconnects, the physical compute units and/or the physical memory units of the reconfigurable processor during placement and routing of the operation unit graph; and
generating a configuration file that is adapted for being applied to the reconfigurable processor for configuring the interconnects, the physical compute units and/or the physical memory units with the assignment of the logical units and the logical edges.