Granted Patent B2

US 12,367,022 · App. 18/387,906 · Granted Jul 22, 2025

Inventors: Blaine Rister (San Francisco, CA); Qingjian Li (Berkeley, CA); Bowen Yang (Palo Alto, CA); Junjue Wang (Newark, CA); Chen Liu (Palo Alto, CA); Zhuo Chen (Palo Alto, CA); Arvind Sujeeth (Palo Alto, CA); Sumti Jairath (Palo Alto, CA)

Assignee: SambaNova Systems, Inc.

G06F8/433

Abstract

Claims (68)

1. A method, the method comprising:

selecting, by a computer-implemented efficiency analyzer, from an intermediate representation of a dataflow program, a set of operators of the dataflow program, the set of operators included in a first mapping of the set of operators to first hardware to execute the set of operators, the first mapping included in the intermediate representation, the first hardware included in a first computing system for executing the dataflow program;

computing, by the efficiency analyzer, based on a hardware description and the first mapping, a first predicted execution metric associated with executing the set of operators on the first hardware, the hardware description corresponding to hardware included in the first computing system;

determining, by the efficiency analyzer, based on the first predicted execution metric, a first inefficiency metric associated with the executing the set of operators on the first hardware;

determining, by the efficiency analyzer, based on the hardware description and the first inefficiency metric, a first inefficiency associated with the dataflow program; and,

outputting, by the efficiency analyzer, first inefficiency results comprising the first inefficiency.

2. The method of claim 1 , further comprising using, by a compiler, the first inefficiency results to compile the dataflow program to execute on the first computing system.

3. The method of claim 1 , wherein the first computing system comprises a coarse-grain reconfigurable computing system.

4. The method of claim 1 , wherein the method further comprises:

determining, by the efficiency analyzer, that the set of operators comprises a nested meta- pipe;

selecting, by the efficiency analyzer, from the intermediate representation, a second mapping comprising a mapping of the nested meta-pipe to second hardware to execute operators of the nested meta-pipe, the second hardware included in the first computing system;

computing, by the efficiency analyzer, based on the hardware description and the second mapping, a second predicted execution metric associated with executing the operators of the nested meta-pipe on the second hardware;

determining, by the efficiency analyzer, based on the second predicted execution metric, a second inefficiency metric associated with the executing the operators of the nested meta-pipe on the second hardware;

determining, by the efficiency analyzer, based on the hardware description and the second inefficiency metric, a second inefficiency associated with the dataflow program; and,

outputting, by the efficiency analyzer, second inefficiency results comprising the second inefficiency.

5. The method of claim 1 , wherein the first predicted execution metric comprises a predicted execution latency to execute an operator among the set of operators on the first hardware; and,

wherein the efficiency analyzer determining the first inefficiency metric comprises:

computing, by the efficiency analyzer, a theoretical minimum execution latency to execute the operator; and,

determining, by the efficiency analyzer, the first inefficiency metric based on a difference between the predicted execution latency and the theoretical minimum execution latency.

6. The method of claim 1 , wherein the method of the outputting, by the efficiency analyzer, the first inefficiency results comprises:

determining, by the efficiency analyzer, an inefficiency category associated with the first inefficiency; and,

outputting, by the efficiency analyzer, among the first inefficiency results, the inefficiency category.

7. The method of claim 1 , wherein the method of the outputting, by the efficiency analyzer, the first inefficiency results further comprises outputting, by the efficiency analyzer, the first inefficiency results to a component of a second computing system, the component selected from the group consisting of an application programming interface of a compiler; an application programming interface of the second computing system; a memory of the second computing system; a storage device of the second computing system; and, an analysis assistant program of the second computing system.

8. The method of claim 1 , wherein the first predicted execution metric is selected from the group consisting of a number of processors of the first computing system to execute the first mapping; a number of parallel computations to execute the first mapping; a latency of a first processor of the first computing system to execute the first mapping; a utilization of a second processor of the first computing system to execute the first mapping; a number of stage buffers of the first computing system required to execute the first mapping; an amount of a first memory of the first computing system required to execute the first mapping; a size of a second memory of the first computing system to execute the first mapping; a memory transfer latency of the first computing system to execute the first mapping; a utilization of a third memory of the first computing system to execute the first mapping; a utilization of a particular type of memory of the first computing system to execute the first mapping; and, a utilization of a particular memory of the first computing system to execute the first mapping.

9. The method of claim 1 , wherein an inefficiency metric included in the first inefficiency metric is selected from the group consisting of initialization of an operator, included in the set of operators, to execute on the first computing system; initialization of a first hardware pipeline of the first computing system to execute the operator; termination of a second hardware pipeline of the first computing system to execute the operator;

completing remaining computations of the operator by a processor of the first computing system; an inefficiency in a low level program for executing the operator on the first computing system; an inefficiency in a sequence of low level programs for executing the first mapping on the first computing system; and, a difference between an actual execution latency for executing the first mapping on the first computing system and a theoretical minimum execution latency for executing the first mapping on the first computing system.

10. A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the program instructions are executable by at least one processor to cause the at least one processor to:

select, from an intermediate representation of a dataflow program, a set of operators of the dataflow program, the set of operators included in a first mapping of the set of operators to first hardware to execute the set of operators, the first mapping included in the intermediate representation, the first hardware included in a first computing system for executing the dataflow program;

compute, based on a hardware description and the first mapping, first predicted execution metric associated with executing the set of operators on the first hardware, the hardware description corresponding to hardware included in the first computing system;

determine, based on the first predicted execution metric, first inefficiency metric associated with the executing the set of operators on the first hardware;

determine, based on the hardware description and the first inefficiency metric, a first inefficiency associated with the dataflow program; and,

output first inefficiency results comprising the first inefficiency.

11. The computer program product of claim 10 , wherein the program instructions are executable by the at least one processor to further cause the at least one processor to:

determine that the set of operators comprises a nested meta-pipe;

select, from the intermediate representation, a second mapping comprising a mapping of the nested meta-pipe to second hardware to execute operators of the nested meta-pipe, the second hardware included in the first computing system;

compute, based on the hardware description and the second mapping, a second predicted execution metric associated with executing the operators of the nested meta-pipe on the second hardware;

determine, based on the second predicted execution metric, a second inefficiency metric associated with the executing the operators of the nested meta-pipe on the second hardware;

determine, based on the hardware description and the second inefficiency metric, a second inefficiency associated with the dataflow program; and,

output second inefficiency results comprising the second inefficiency.

12. A first computing system, the first computing system comprising:

at least one processor included in the first computing system;

an intermediate representation of a dataflow program;

a hardware description corresponding to hardware included in a second computing system, the second computing system configurable to execute the dataflow program; and,

an efficiency analyzer configured to execute on the at least one processor to:

select, from the intermediate representation, a set of operators of the dataflow program, the set of operators included in a first mapping of the set of operators to first hardware to execute the set of operators, the first mapping included in the intermediate representation, the first hardware among the hardware included in the second computing system;

compute, based on the hardware description and the first mapping, a first predicted execution metric associated with executing the set of operators on the first hardware;

determine, based on the first predicted execution metric, a first inefficiency metric associated with the executing the set of operators on the first hardware;

determine, based on the hardware description and the first inefficiency metric, a first inefficiency associated with the dataflow program; and,

output first inefficiency results comprising the first inefficiency.

13. The first computing system of claim 12 , wherein the efficiency analyzer is further configured to execute on the at least one processor to:

determine that the set of operators comprises a nested meta-pipe;

select, from the intermediate representation, a second mapping comprising a mapping of the nested meta-pipe to second hardware to execute operators of the nested meta-pipe, the second hardware included in the first computing system;

compute, based on the hardware description and the second mapping, a second predicted execution metric associated with executing the operators of the nested meta-pipe on the second hardware;

determine, based on the second predicted execution metric, a second inefficiency metric associated with the executing the operators of the nested meta-pipe on the second hardware;

determine, based on the hardware description and the second inefficiency metric, a second inefficiency associated with the dataflow program; and,

output second inefficiency results comprising the second inefficiency.

14. The first computing system of claim 12 , wherein the first predicted execution metric comprises a predicted execution latency to execute an operator among the set of operators on the first hardware; and,

wherein the efficiency analyzer configured to execute on the at least one processor to determine the first inefficiency metric comprises the efficiency analyzer further configured to execute on the at least one processor to:

compute a theoretical minimum execution latency to execute the operator; and,

determine the first inefficiency metric based on a difference between the predicted execution latency and the theoretical minimum execution latency.

15. The first computing system of claim 12 , wherein the efficiency analyzer is further configured to execute on the at least one processor to:

determine an inefficiency category associated with the first inefficiency; and,

output, among the first inefficiency results, the inefficiency category.

16. The first computing system of claim 12 , wherein the efficiency analyzer configured to execute on the at least one processor to output the first inefficiency results comprises the efficiency analyzer further configured to execute on the at least one processor to output the first inefficiency results to a component of a third computing system, the component selected from the group consisting of an application programming interface of a compiler; an application programming interface of the third computing system; a memory of the third computing system; a storage device of the third computing system; and, an analysis assistant program of the third computing system.

17. The first computing system of claim 12 , wherein the first predicted execution metric is selected from the group consisting of a number of processors of the second computing system to execute the first mapping; a number of parallel computations to execute the first mapping; a latency of a first processor of the second computing system to execute the first mapping; a utilization of a second processor of the second computing system to execute the first mapping; a number of stage buffers of the second computing system required to execute the first mapping; an amount of a first memory of the second computing system required to execute the first mapping; a size of a second memory of the second computing system to execute the first mapping; a memory transfer latency of the second computing system to execute the first mapping; a utilization of a third memory of the second computing system to execute the first mapping; a utilization of a particular type of memory of the second computing system to execute the first mapping; and, a utilization of a particular memory of the second computing system to execute the first mapping.

18. The first computing system of claim 12 , wherein the first inefficiency metric is selected from the group consisting of initialization of an operator, included in the set of operators, to execute on the second computing system; initialization of a first hardware pipeline of the second computing system to execute the operator; termination of a second hardware pipeline of the second computing system to execute the operator; completing remaining computations of the operator by a processor of the second computing system; an inefficiency in a low level program for executing the operator on the second computing system; an inefficiency in a sequence of low level programs for executing the first mapping on the second computing system; and, a difference between an actual execution latency for executing the first mapping on the second computing system and a theoretical minimum execution latency for executing the first mapping on the second computing system.

19. The first computing system of claim 12 , wherein the efficiency analyzer is associated with a compiler for compiling the dataflow program to execute on the second computing system.

20. The first computing system of claim 12 , wherein the second computing system comprises a coarse-grain reconfigurable computing system.

Assignments (2)

Continuity (9)

References Cited (36)