Granted Patent B2

US 12,332,837 · App. 18/225,856 · Granted Jun 17, 2025

Inventors: Hong Suh (Palo Alto, CA); Sumti Jairath (Palo Alto, CA)

Assignee: SambaNova Systems, Inc.

G06F15/80G06F9/30036G06F9/3836G06F15/7871

Abstract

Claims (99)

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 a set of unsorted nodes and edges that interconnect nodes in the set of unsorted nodes;

determining a first position of an ordered sequence of nodes as a current position of the ordered sequence of nodes;

repeating as long as the set of unsorted nodes comprises at least one unsorted node:

determining, from the set of unsorted nodes, a node-to-be-sorted in the operation unit graph;

adding the node-to-be-sorted to an ordered data structure; and

repeating until the ordered data structure is empty:

in order of the ordered data structure, removing a next node-to-be-sorted from the ordered data structure,

inserting the next node-to-be-sorted as the currently inserted node at the current position of the ordered sequence of nodes,

assigning a subsequent position of the ordered sequence of nodes as the current position of the ordered sequence of nodes,

determining neighboring nodes of the currently inserted node from the set of unsorted nodes, wherein each one of the neighboring nodes is separated from the currently inserted node by one of the edges,

adding each one of the neighboring nodes as a node-to-be-sorted to the ordered data structure, and

removing the currently inserted node from the set of unsorted nodes;

receiving a hardware description describing a reconfigurable processor having interconnects, physical compute units and/or physical memory units;

using the hardware description to determine an assignment of the edges and nodes of the ordered sequence of nodes 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 reconfigurable processor with the assignment of the edges and the nodes of the ordered sequence of nodes onto the interconnects, the physical compute units and/or the physical memory units.

2. The method of claim 1 , wherein determining, from the set of unsorted nodes, the node-to-be-sorted in the operation unit graph further comprises:

determining a set of input nodes in the set of unsorted nodes, wherein input nodes in the set of input nodes exclusively transmit data over the edges to other nodes in the set of unsorted nodes; and

determining a set of output nodes in the set of unsorted nodes, wherein output nodes in the set of output nodes exclusively receive data over the edges from other nodes in the set of unsorted nodes.

3. The method of claim 2 , wherein determining, from the set of unsorted nodes, the node-to-be-sorted in the operation unit graph further comprises:

determining a longest path in the operation unit graph, wherein the longest path starts from a first node in the set of input nodes and ends at a second node in the set of output nodes; and

selecting the first node or the second node as the node-to-be-sorted.

4. The method of claim 2 , wherein determining, from the set of unsorted nodes, the node-to-be-sorted in the operation unit graph further comprises:

determining a provisioned bandwidth for each edge of the edges that is connected to an input node of the input nodes; and

selecting as the node-to-be-sorted the input node among the input nodes that is connected to the edge of the edges with a greatest provisioned bandwidth.

5. The method of claim 2 , wherein determining, from the set of unsorted nodes, the node-to-be-sorted in the operation unit graph further comprises:

determining a provisioned bandwidth for each edge of the edges that is connected to an output node in the set of output nodes; and

selecting as the node-to-be-sorted the output node among the output nodes that is connected to the edge of the edges with a greatest provisioned bandwidth.

6. The method of claim 1 , wherein the ordered data structure comprises at least one of a linked list, a queue, a stack, a tree, or a heap.

7. The method of claim 1 , wherein adding each one of the neighboring nodes as a node-to-be-sorted to the ordered data structure further comprises:

determining a ranking of nodes-to-be-ranked, wherein the nodes-to-be-ranked comprise the neighboring nodes and each node-to-be-sorted in the ordered data structure;

rearranging each node-to-be-sorted in the ordered data structure according to the ranking; and

inserting each one of the neighboring nodes as a node-to-be-sorted according to the ranking into the ordered data structure.

8. The method of claim 7 , wherein determining the ranking of the nodes-to-be-ranked further comprises:

determining a series of keys for each one of the nodes-to-be-ranked, wherein the ranking of the nodes-to-be-ranked is based on the series of keys.

9. The method of claim 8 , wherein determining the ranking of the nodes-to-be-ranked further comprises:

determining the ranking of the nodes-to-be-ranked based on a first key in the series of keys.

10. The method of claim 9 , wherein determining the ranking of the nodes-to-be-ranked further comprises:

determining whether nodes of the nodes-to-be-ranked have the same first key; and

in response to determining that nodes of the nodes-to-be-ranked have the same first key, ranking the nodes of the nodes-to-be-ranked with the same first key among themselves based on subsequent keys in the series of keys.

11. The method of claim 8 , wherein determining the series of keys for each one of the nodes-to-be-ranked further comprises:

determining a key of the series of keys for a current node of the nodes-to-be-ranked based on a cost function of the current node of the nodes-to-be-ranked.

12. The method of claim 11 , wherein the cost function of the current node is determined based on at least one criterion.

13. The method of claim 12 , wherein the cost function of the current node is based on a weighted sum of the at least one criterion and at least one additional criterion.

14. The method of claim 12 , wherein a criterion of the at least one criterion comprises at least one of

a number of nodes in the ordered sequence of nodes that is connected to the current node,

a maximum bandwidth of all edges connected to the current node,

a maximum bandwidth of any edge connected to the current node and another node in the ordered sequence of nodes,

a minimum bandwidth of all edges connected to the current node,

a minimum bandwidth of any edge connected to the current node and another node in the ordered sequence of nodes,

a maximum fanout of the current node,

a number of edges that are connected to the current node and part of a virtual channel, or

a number of iterations that the current node has been in the ordered data structure while the next node-to-be-sorted has been removed from the ordered data structure.

15. A system, comprising:

one or more host processors coupled to a storage medium; and

a compiler executable in any one of the one or more host processors, wherein the compiler is configured to:

receive an operation unit graph comprising a set of unsorted nodes and edges that interconnect nodes in the set of unsorted nodes;

determine a first position of an ordered sequence of nodes as a current position of the ordered sequence of nodes;

repeat as long as the set of unsorted nodes comprises at least one unsorted node:

determine, from the set of unsorted nodes, a node-to-be-sorted in the operation unit graph;

add the node-to-be-sorted to an ordered data structure; and

repeat until the ordered data structure is empty:

in order of the ordered data structure, remove a next node-to-be-sorted from the ordered data structure,

insert the next node-to-be-sorted as the currently inserted node at the current position of the ordered sequence of nodes,

assign a subsequent position of the ordered sequence of nodes as the current position of the ordered sequence of nodes,

determine neighboring nodes of the currently inserted node from the set of unsorted nodes, wherein each one of the neighboring nodes is separated from the currently inserted node by one of the edges,

add each one of the neighboring nodes as a node-to-be-sorted to the ordered data structure, and

remove the currently inserted node from the set of unsorted nodes;

receive a hardware description describing a reconfigurable processor having interconnects, physical compute units and/or physical memory units;

use the hardware description and the ordered sequence of nodes to determine an assignment of the edges and nodes of the ordered sequence of nodes onto the interconnects, the physical compute units and/or the physical memory units 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 reconfigurable processor with the assignment of the edges and the nodes of the ordered sequence of nodes onto the interconnects, the physical compute units and/or the physical memory units.

16. The system of claim 15 , wherein the compiler, for adding each one of the neighboring nodes as a node-to-be-sorted to the ordered data structure, is further configured to:

determine a ranking of nodes-to-be-ranked, wherein the nodes-to-be-ranked comprise the neighboring nodes and each node-to-be-sorted in the ordered data structure;

rearrange each node-to-be-sorted in the ordered data structure according to the ranking; and

insert each one of the neighboring nodes as a node-to-be-sorted according to the ranking into the ordered data structure.

17. The system of claim 16 , wherein the compiler, for determining the ranking of the nodes-to-be-ranked, is further configured to:

determine a series of keys for each one of the nodes-to-be-ranked, wherein the ranking of the nodes-to-be-ranked is based on the series of keys.

18. The sorting tool system of claim 17 , wherein the compiler, for determining the ranking of the nodes-to-be-ranked, is further configured to:

determine the ranking of the nodes-to-be-ranked based on a first key in the series of keys;

determine whether nodes of the nodes-to-be-ranked have the same first key; and

in response to determining that nodes of the nodes-to-be-ranked have the same first key, rank the nodes of the nodes-to-be-ranked with the same first key among themselves based on subsequent keys in the series of keys.

19. The system of claim 17 , wherein the compiler, for determining the series of keys for each one of the nodes-to-be-ranked, is further configured to:

determine a key of the series of keys for a current node of the nodes-to-be-ranked based on a cost function of the current node of the nodes-to-be-ranked.

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 a set of unsorted nodes and edges that interconnect nodes in the set of unsorted nodes;

determining a first position of an ordered sequence of nodes as a current position of the ordered sequence of nodes;

repeating as long as the set of unsorted nodes comprises at least one unsorted node:

determining, from the set of unsorted nodes, a node-to-be-sorted in the operation unit graph;

adding the node-to-be-sorted to an ordered data structure; and

repeating until the ordered data structure is empty:

in order of the ordered data structure, removing a next node-to-be-sorted from the ordered data structure,

inserting the next node-to-be-sorted as the currently inserted node at the current position of the ordered sequence of nodes,

assigning a subsequent position of the ordered sequence of nodes as the current position of the ordered sequence of nodes,

determining neighboring nodes of the currently inserted node from the set of unsorted nodes, wherein each one of the neighboring nodes is separated from the currently inserted node by one of the edges,

adding each one of the neighboring nodes as a node-to-be-sorted to the ordered data structure, and

removing the currently inserted node from the set of unsorted nodes; and

receiving a hardware description describing a reconfigurable processor having interconnects, physical compute units and/or physical memory units;

using the hardware description to determine an assignment of the edges and nodes of the ordered sequence of nodes 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 reconfigurable processor with the assignment of the edges and the nodes of the ordered sequence of nodes onto the interconnects, the physical compute units and/or the physical memory units.

Assignments (2)

Continuity (4)

References Cited (18)