Granted Patent B2

US 12,436,915 · App. 18/221,685 · Granted Oct 7, 2025

Inventors: Yue Fu (Palo Alto, CA); Kin Hing Leung (Cupertino, CA); Likun Hao (Palo Alto, CA); Arvind Krishna Sujeeth (Palo Alto, CA); Sumti Jairath (Palo Alto, CA); Andrew Deng (San Jose, CA); Raghu Prabhakar (San Jose, CA)

Assignee: SambaNova Systems, Inc.

G06F15/7871G06F9/5044G06F13/4063

Abstract

Claims (74)

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.

Assignments (2)

Continuity (2)

References Cited (37)