Operating a cost estimation tool for placing and routing an operation unit graph on a reconfigurable processor

Abstract

A system with a cost estimation tool for estimating a realized bandwidth consumption of a logical edge between a logical producer unit and a logical consumer unit of an operation unit graph during placement and routing of the logical producer unit, the logical consumer unit, and the logical edge onto a reconfigurable processor is presented as well as a method of operating such a cost estimation tool and a non-transitory computer-readable storage medium including instructions that, when executed by a processing unit, cause the processing unit to operate such a cost estimation tool The cost estimation tool may be configured to determine the realized bandwidth consumption of the tentative assignment based on an upper bandwidth limit of the logical edge, an end-to-end bandwidth, a scaling factor of a realized bandwidth, and a congestion estimation of the physical link.

What is claimed is: 
     
       1. A method of operating a cost estimation tool for estimating a realized bandwidth consumption of a logical edge between a logical producer unit and a logical consumer unit of an operation unit graph during placement and routing of the logical producer unit, the logical consumer unit, and the logical edge onto a reconfigurable processor, comprising:
 receiving the operation unit graph comprising the logical producer unit, the logical consumer unit, and the logical edge; 
 determining an upper output bandwidth limit of the logical producer unit, an upper input bandwidth limit of the logical consumer unit, and an upper bandwidth limit of the logical edge based on the upper output bandwidth limit and the upper input bandwidth limit; 
 determining a scaling factor of a realized bandwidth; 
 receiving a tentative assignment of the logical edge, the logical producer unit, and the logical consumer unit to a physical link, a physical producer unit, and a physical consumer unit; 
 determining an end-to-end bandwidth between the physical producer unit and the physical consumer unit; 
 determining a congestion estimation of the physical link; 
 determining the realized bandwidth consumption of the tentative assignment based on the upper bandwidth limit of the logical edge, the end-to-end bandwidth, the scaling factor of the realized bandwidth, and the congestion estimation of the physical link; and 
 providing the realized bandwidth consumption of the tentative assignment as a cost estimation to a placement and routing tool. 
 
     
     
       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 logical consumer unit comprises a compute unit or a memory unit. 
     
     
       4. The method of  claim 1 , wherein determining the end-to-end bandwidth between the physical producer unit and the physical consumer unit further comprises:
 in response to determining that the physical consumer unit is not end-to-end credit-controlled, determining the end-to-end bandwidth to be 1.0. 
 
     
     
       5. The method of  claim 1 , wherein determining the end-to-end bandwidth between the physical producer unit and the physical consumer unit further comprises:
 in response to determining that the physical consumer unit is end-to-end credit-controlled and that each credit represents one vector: 
 determining a number of hops between the physical producer unit and the physical consumer unit, and 
 determining a maximum Manhattan distance between the physical producer unit and the physical consumer unit and between the physical producer unit and any other placed physical consumer unit. 
 
     
     
       6. The method of  claim 5 , wherein determining the end-to-end bandwidth between the physical producer unit and the physical consumer unit further comprises:
 determining a first latency based on multiplying the number of hops with a hop-to-hop latency; and 
 determining a second latency based on multiplying the maximum Manhattan distance with a predetermined barrier latency. 
 
     
     
       7. The method of  claim 6 , wherein determining the end-to-end bandwidth between the physical producer unit and the physical consumer unit further comprises:
 determining the end-to-end bandwidth between the physical producer unit and the physical consumer unit based on dividing a predetermined first-in first-out buffer depth with a sum of the first and second latencies. 
 
     
     
       8. The method of  claim 1 , wherein determining the scaling factor of the realized bandwidth further comprises:
 determining a number of active cycles of the logical edge; 
 determining a number of stage cycles; and 
 determining the scaling factor of the realized bandwidth based on a division of the number of active cycles by the number of stage cycles. 
 
     
     
       9. The method of  claim 8 , wherein determining the number of active cycles further comprises:
 determining all paths that pass through the logical edge; 
 determining an accumulated active cycle for each one of all the paths that pass through the logical edge; and 
 determining the number of active cycles as a maximum accumulated active cycle of the accumulated active cycle for each one of all the paths that pass through the logical edge. 
 
     
     
       10. The method of  claim 1 , wherein determining the congestion estimation of the physical link further comprises:
 determining all logical edges of the operation unit graph that are assigned to use the physical link. 
 
     
     
       11. The method of  claim 10 , wherein determining the congestion estimation of the physical link further comprises:
 determining a sum of realized average bandwidths of all the logical edges that are assigned to use the physical link. 
 
     
     
       12. A system, comprising:
 a cost estimation tool for estimating a realized bandwidth consumption of a logical edge between a logical producer unit and a logical consumer unit of an operation unit graph during placement and routing of the logical producer unit, the logical consumer unit, and the logical edge onto a reconfigurable processor, wherein the cost estimation tool is configured to: 
 receive the operation unit graph comprising the logical producer unit, the logical consumer unit, and the logical edge; 
 determine an upper output bandwidth limit of the logical producer unit, an upper input bandwidth limit of the logical consumer unit, and an upper bandwidth limit of the logical edge based on the upper output bandwidth limit and the upper input bandwidth limit; 
 determine a scaling factor of a realized bandwidth; 
 receive a tentative assignment of the logical edge, the logical producer unit, and the logical consumer unit to a physical link, a physical producer unit, and a physical consumer unit; 
 determine an end-to-end bandwidth between the physical producer unit and the physical consumer unit; 
 determine a congestion estimation of the physical link; 
 determine the realized bandwidth consumption of the tentative assignment based on the upper bandwidth limit of the logical edge, the end-to-end bandwidth, the scaling factor of the realized bandwidth, and the congestion estimation of the physical link; and 
 provide the realized bandwidth consumption of the tentative assignment as a cost estimation to a placement and routing tool. 
 
     
     
       13. The system of  claim 12 , wherein, for determining the end-to-end bandwidth between the physical producer unit and the physical consumer unit, the cost estimation tool is further configured to:
 in response to determining that the physical consumer unit is end-to-end credit-controlled, determine the end-to-end bandwidth to be 100 percent. 
 
     
     
       14. The system of  claim 12 , wherein, for determining the end-to-end bandwidth between the physical producer unit and the physical consumer unit, the cost estimation tool is further configured to:
 in response to determining that the physical consumer unit is end-to-end credit-controlled and that each credit represents one vector: 
 determine a number of hops between the physical producer unit and the physical consumer unit, and 
 determine a maximum Manhattan distance between the physical producer unit and the physical consumer unit and between the physical producer unit and any other placed physical consumer unit. 
 
     
     
       15. The system of  claim 14 , wherein, for determining the end-to-end bandwidth between the physical producer unit and the physical consumer unit, the cost estimation tool is further configured to:
 determine a first latency based on multiplying the number of hops with a hop-to-hop latency; 
 determine a second latency based on multiplying the maximum Manhattan distance with a predetermined barrier latency; and 
 determine the end-to-end bandwidth between the physical producer unit and the physical consumer unit based on dividing a predetermined first-in first-out buffer depth with a sum of the first and second latencies. 
 
     
     
       16. The system of  claim 12 , wherein, for determining the scaling factor of the realized bandwidth, the cost estimation tool is further configured to:
 determine a number of active cycles of the logical edge; 
 determine a number of stage cycles; and 
 determine the scaling factor of the realized bandwidth based on a division of the number of active cycles by the number of stage cycles. 
 
     
     
       17. The system of  claim 16 , wherein, for determining the number of active cycles, the cost estimation tool is further configured to:
 determine all paths that pass through the logical edge; 
 determine an accumulated active cycle for each one of all the paths that pass through the logical edge; and 
 determine the number of active cycles as a maximum accumulated active cycle of the accumulated active cycle for each one of all the paths that pass through the logical edge. 
 
     
     
       18. The system of  claim 12 , wherein, for determining the congestion estimation of the physical link, the cost estimation tool is further configured to:
 determine all logical edges of the operation unit graph that are assigned to use the physical link; and 
 determine a sum of realized average bandwidths of all the logical edges that are assigned to use the physical link. 
 
     
     
       19. 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 realized bandwidth consumption of a logical edge between a logical producer unit and a logical consumer unit of an operation unit graph during placement and routing of the logical producer unit, the logical consumer unit, and the logical edge onto a reconfigurable processor, the instructions comprising:
 receiving the operation unit graph comprising the logical producer unit, the logical consumer unit, and the logical edge; 
 determining an upper output bandwidth limit of the logical producer unit, an upper input bandwidth limit of the logical consumer unit, and an upper bandwidth limit of the logical edge based on the upper output bandwidth limit and the upper input bandwidth limit; 
 determining a scaling factor of a realized bandwidth; 
 receiving a tentative assignment of the logical edge, the logical producer unit, and the logical consumer unit to a physical link, a physical producer unit, and a physical consumer unit; 
 determining an end-to-end bandwidth between the physical producer unit and the physical consumer unit; 
 determining a congestion estimation of the physical link; 
 determining the realized bandwidth consumption of the tentative assignment based on the upper bandwidth limit of the logical edge, the end-to-end bandwidth, the scaling factor of the realized bandwidth, and the congestion estimation of the physical link 
 providing the realized bandwidth consumption of the tentative assignment as a cost estimation to a placement and routing tool.