Machine learning accelerator with decision tree interconnects

Patent metadata

Field	Value
Publication number	US-12112242-B2
Application number	US-202016986506-A
Country	US
Kind code	B2
Filing date	Aug 6, 2020
Priority date	Aug 6, 2020
Publication date	Oct 8, 2024
Grant date	Oct 8, 2024

Abstract

Techniques for performing improved machine learning using decision trees are disclosed. In one example, a system includes a plurality of decision tree structures, and configuration logic operatively coupled to the plurality of decision tree structures. The configuration logic selectively configures the plurality of decision tree structures to form at least one of: one or more combined decision tree structures, wherein a combined decision tree structure comprises multiple interconnected ones of the plurality of decision tree structures; and one or more individual decision tree structures, wherein an individual decision tree structure comprises a single one of the plurality of decision tree structures.

First claim

What is claimed is:

1. A system comprising:
a plurality of decision tree unit hardware modules;
a register;
a plurality of multiplexers, wherein each multiplexer is coupled to the register, and coupled to a respective decision tree unit hardware module of the plurality of decision tree unit hardware modules; and
a majority voter module coupled to the register and to the plurality of decision tree unit hardware modules;
wherein each decision tree unit hardware module comprises a plurality of decision tree structure, wherein each decision tree structure of the plurality of decision tree unit hardware modules comprises a balanced decision tree structure having a same number of nodes and a same depth, and hard-wired interconnects;
wherein the register is configured to output control data to the plurality of multiplexers to cause the plurality of multiplexers to selectively configure each of one or more of the decision tree unit hardware modules to function as an independent decision tree structure or to selectively configure at least two of the decision tree unit hardware modules to form a decision tree structure which comprises a combination of at least a first decision tree structure and a second decision tree structure of the plurality of decision tree unit hardware modules by selectively connecting at least one leaf node of the first decision tree structure to an internal node of the second decision tree structure; and
wherein the majority voter module is configured to receive output data from the decision tree unit hardware modules, and the control data from the register which indicates the configuration of the decision tree unit hardware modules, and generate a decision based on the received output data and the control data.

2. The system of claim 1 , wherein each of the decision tree structures of the plurality of decision tree unit hardware modules has a same depth of three or more.

3. The system of claim 2 , wherein at least one decision tree structure of the plurality of decision tree unit hardware modules comprises at least one filler node to make the at least one decision tree structure uniform in shape with respect to each other ones of the decision tree structures.

4. The system of claim 1 , wherein:
each multiplexer of the plurality of multiplexers comprises:
a selection input port coupled to the register;
a first input port, and second input port; and
an output port that is coupled to an input port of a respective decision tree unit hardware module of the plurality of decision tree unit hardware modules;

the control data output from the register comprises a plurality of control bits;
each control bit is applied to the selection input port of a respective multiplexer of the plurality of multiplexers;
in response to a control bit having a first logic level applied to the selection input port of a given multiplexer, the given multiplexer selects a first data input applied to the first input port thereof; and
in response to the control bit having a second logic level applied to the selection input port of the given multiplexer, the given multiplexer selects a second data input applied to the second input port thereof.

5. The system of claim 4 , wherein:
the first decision tree structure comprises a plurality of output ports, wherein each output port of the first decision tree structure is coupled to the majority voter module, and to a respective second input port of a respective multiplexer of the plurality of multiplexers; and
the logic levels of the control bits applied to respective selection input ports of the multiplexers are set to cause each given decision tree unit hardware module, which is coupled to an output port of a given multiplexer, to function (i) independently of other decision tree unit hardware modules, or (ii) as a sub-tree that is coupled to a given output port of the first decision tree structure by the given multiplexer.

6. The system of claim 4 , wherein the logic levels of the control bits are prestored in the register or dynamically set in the register to perform a classification process.

7. The system of claim 1 , wherein each one of the plurality of decision tree unit hardware modules comprises a plurality of nodes, wherein at least one node compares an input value to a threshold value and generates a result based on the comparison.

8. The system of claim 7 , wherein at least one node outputs a classification label.

9. The system of claim 1 , wherein the plurality of decision tree unit hardware modules is part of a random forest algorithm implementation.

10. The system of claim 1 , wherein the system is implemented as part of one or more integrated circuits.

11. An apparatus comprising:
at least one processor;
at least one memory including instruction code; and
control logic, wherein the control logic comprises:
a plurality of decision tree unit hardware modules;
a register;
a plurality of multiplexers, wherein each multiplexer is coupled to the register, and coupled to a respective decision tree unit hardware module of the plurality of decision tree unit hardware modules; and
a majority voter module coupled to the register and to the plurality of decision tree unit hardware modules;
wherein each decision tree unit hardware module comprises a decision tree structure, wherein each decision tree structure of the plurality of decision tree unit hardware modules comprises a balanced decision tree structure having a same number of nodes and a same depth, and hard-wired interconnects;

wherein the at least one memory and the instruction code are configured to, with the at least one processor, to instruct the control logic to:
cause the register to output control data to the plurality of multiplexers to cause the plurality of multiplexers to selectively configure each of one or more of the decision tree unit hardware modules to function as an independent decision tree structure or to selectively configure at least two of the decision tree unit hardware modules to form a decision tree structure which comprises a combination of at least a first decision tree structure and a second decision tree structure of the plurality of decision tree unit hardware modules by selectively connecting at least one leaf node of the first decision tree structure to an internal node of the second decision tree structure; and
cause the majority voter module to receive output data from the decision tree unit hardware modules, and the control data from the register which indicates the configuration of the decision tree unit hardware modules, and generate a decision based on the received output data and the control data.

12. The apparatus of claim 11 , wherein each of the decision tree structures of the plurality of decision tree unit hardware modules has a same depth of three or more.

13. The apparatus of claim 11 , wherein:
each multiplexer of the plurality of multiplexers comprises:
a selection input port coupled to the register;
a first input port, and second input port; and
an output port that is coupled to an input port of a respective decision tree unit hardware module of the plurality of decision tree unit hardware modules;

the control data output from the register comprises a plurality of control bits;
each control bit is applied to the selection input port of a respective multiplexer of the plurality of multiplexers;
in response to a control bit having a first logic level applied to the selection input port of a given multiplexer, the given multiplexer selects a first data input applied to the first input port thereof; and
in response to the control bit having a second logic level applied to the sele

Assignees

• IBM

Inventors

• Kang Mingu
• Woo Seonghoon
• Lee Eun Kyung
• Chey Sukjay

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N20/00 Primary

  Machine learning · CPC title