Systolic array based architecture for branch and bound algorithms
View Patent ↗Techniques and mechanisms implement a branch and bound algorithm using a systolic array based circuit architecture. For example, a systolic array may perform calculations associated with nodes of a tree data structure. Information associated with the nodes may be analyzed and stored by a controller. The controller may also provide data to the systolic array based on the information associated with the nodes.
1. A circuit for performing calculations associated with nodes of a tree data structure, the circuit comprising:
parallel processing circuitry, comprising a systolic array, the systolic array comprising a plurality of processing units that perform the calculations associated with the nodes of the tree data structure, the calculations including determining scores associated with the nodes, wherein at least a subset of the calculations are performed in parallel by at least a subset of the plurality of processing units;
a children memory that stores node information associated with the nodes of the tree data structure;
a best path memory that stores node information associated with selected nodes; and
a controller that:
receives the scores;
determines the selected nodes based on the scores; and
stores a path solution comprising the node information associated with the selected nodes in the best path memory.
2. The circuit of claim 1 , wherein the node information associated with the selected nodes includes the scores associated with the selected nodes.
3. The circuit of claim 2 , wherein the node information associated with the selected nodes further includes node identifiers associated with the selected nodes.
4. The circuit of claim 3 , wherein the node identifiers provide paths in the tree data structure associated with the selected nodes.
5. The circuit of claim 2 , wherein the node information associated with the selected nodes further includes systolic array state data associated with the selected nodes.
6. The circuit of claim 5 , wherein the controller provides systolic array state data associated with the selected node having a best score among the selected nodes to the systolic array.
7. The circuit of claim 1 , wherein a first node associated with a first score is determined to be a selected node upon determining the first score is better than a second score associated with a second node, the second node among the selected nodes.
8. The circuit of claim 1 , wherein the best path memory stores the selected nodes including a first node and a second node, the first node associated with a first level in the tree data structure, the second node associated with a second level in the tree data structure.
9. The circuit of claim 1 , wherein the controller further:
tracks a number of high scores for a plurality of paths;
selects a node on each of the plurality of paths based upon the number of high scores; and
stores a plurality of path solutions based upon selected node on each of the plurality of paths.
10. A method for performing calculations associated with nodes of a tree data structure, the method comprising:
performing, by a plurality of processing units of a systolic array of parallel processing circuitry, the calculations associated with the nodes of the tree data structure, the calculations including determining scores associated with the nodes, wherein at least a subset of the calculations are performed in parallel by at least a subset of the plurality of processing units;
storing, in a children memory, node information associated with the nodes of the tree data structure;
receiving, via the controller, the scores;
determining, by a controller, selected nodes based on the scores; and
storing, by the controller, a path solution comprising the node information associated with the selected nodes in the best path memory.
11. The method of claim 10 , wherein the node information associated with the selected nodes includes the scores associated with the selected nodes.
12. The method of claim 11 , wherein the node information associated with the selected nodes further includes node identifiers associated with the selected nodes.
13. The method of claim 12 , wherein the node identifiers provide paths in the tree data structure associated with the selected nodes.
14. The method of claim 11 , wherein the node information associated with the selected nodes further includes systolic array state data associated with the selected nodes.
15. The method of claim 14 , further comprising:
providing, by the controller, systolic array state data associated with the selected node having a best score among the selected nodes to the systolic array.
16. The method of claim 10 , wherein a first node associated with a first score is determined to be a selected node upon determining the first score is better than a second score associated with a second node, the second node among the selected nodes.
17. The method of claim 10 , wherein the selected nodes includes a first node and a second node, the first node associated with a first level in the tree data structure, the second node associated with a second level in the tree data structure.
18. The method of claim 10 , further comprising:
providing, by the controller, node information associated with one of the selected nodes to the systolic array.
19. A non-transitory machine-readable medium having instructions stored thereon, the instructions for generating configuration data for instantiating components in a parallel processing integrated circuitry device, the instructions executable by a processor to:
generate the configuration data for:
instantiating, in the device, a systolic array, comprising a plurality of processing units that perform calculations associated with nodes of the tree data structure, the calculations including determining scores associated with the nodes, wherein at least a subset of the calculations are performed in parallel by at least a subset of the plurality of processing units;
instantiating a child memory that stores node information associated with the nodes of the tree data structure;
instantiating a best path memory for storing node information associated with selected nodes; and
instantiating, in the device, a controller that executes instructions to:
receive the scores;
determine the selected nodes based on the scores; and
store the node information associated with the selected nodes in a memory.
20. The non-transitory machine-readable medium of claim 19 , wherein the node information associated with the selected nodes includes the scores associated with the selected nodes.
21. The non-transitory machine-readable medium of claim 20 , wherein the node information associated with the selected nodes further includes node identifiers associated with the selected nodes.
22. The non-transitory machine-readable medium of claim 21 , wherein the node identifiers provide paths in the tree data structure associated with the selected nodes.