SYSTEM AND METHOD FOR PARALLEL PROCESSING OF A DECISION TREE

1 . A computing device comprising:

a bank of processing elements;

a controller interconnected with the bank of processing elements, the controller configured to:

obtain an input vector having a plurality of input attributes, the input vector to be processed by a decision tree to identify a determined outcome for the input vector;

control the bank of processing elements to process the input vector to obtain a result vector, wherein each input attribute is processed by one of the processing elements in the bank to obtain a result, and wherein the result vector comprises a combination of the results;

control the bank of processing elements to accumulate the result vector with an outcome vector for each potential outcome of the decision tree to obtain a respective outcome metric for each potential outcome; and

select one potential outcome as the determined outcome of the decision tree for the input vector based on the respective outcome metrics for each potential outcome.

2 . The computing device of claim 1 , wherein the decision tree comprises a plurality of nodes, each node configured to process a given input attribute of the input vector.

3 . The computing device of claim 2 , wherein the controller is further configured to: assign each node of the decision tree to one of the processing elements to process the given input attribute to obtain the result.

4 . The computing device of claim 1 , wherein to process the input attribute, the processing element is configured to compare the input attribute to a predefined threshold for the input attribute.

5 . The computing device of claim 4 , wherein the controller is further configured to initialize the bank of processing elements to store the predefined threshold for each input attribute in a respective corresponding memory cell of the processing element.

6 . The computing device of claim 1 , wherein the controller is configured to assign each respective outcome metric to be accumulated by one of the processing elements in the bank.

7 . The computing device of claim 1 , wherein the respective outcome metric comprises a dot product between the result vector and the respective outcome vector.

8 . The computing device of claim 7 , wherein the controller is configured to apply a generalized matrix-vector multiply between the result vector and an outcome matrix comprising the outcome vectors to accumulate the respective outcome metrics.

9 . The computing device of claim 8 , wherein the controller is configured to initialize the bank of processing elements to load the outcome matrix into memory cells associated with the processing elements.

10 . The computing device of claim 1 , wherein to select the determined outcome, the controller is configured to:

compare each outcome metric to a depth value for the potential outcome; and

normalize the outcome metrics;

multiply each normalized outcome metric by a respective outcome identifier; and

return the outcome identifier identifying the determined outcome.

11 . A method comprising:

obtaining an input vector having a plurality of input attributes, the input vector to be processed by a decision tree to identify a determined outcome for the input vector;

controlling a bank of processing elements to process the input vector to obtain a result vector, wherein each input attribute is processed by one of the processing elements in the bank to obtain a result, and wherein the result vector comprises a combination of the results;

controlling the bank of processing elements to accumulate the result vector with an outcome vector for each potential outcome of the decision tree to obtain a respective outcome metric for each potential outcome; and

selecting one potential outcome as the determined outcome of the decision tree for the input vector based on the respective outcome metrics for each potential outcome.

12 . The method of claim 11 , wherein the decision tree comprises a plurality of nodes, each node configured to process a given input attribute of the input vector.

13 . The method of claim 12 , further comprising: assigning each node of the decision tree to one of the processing elements to process the given input attribute to obtain the result.

14 . The method of claim 11 , wherein processing the input attribute comprises comparing the input attribute to a predefined threshold for the input attribute.

15 . The method of claim 14 , further comprising initializing the bank of processing elements to store the predefined threshold for each input attribute in a respective corresponding memory cell of the processing element.

16 . The method of claim 11 , further comprising assigning each respective outcome metric to be accumulated by one of the processing elements in the bank.

17 . The method of claim 11 , wherein the respective outcome metric comprises a dot product between the result vector and the respective outcome vector.

18 . The method of claim 17 , further comprising applying a generalized matrix-vector multiply between the result vector and an outcome matrix comprising the outcome vectors to accumulate the respective outcome metrics.

19 . The method of claim 18 , further comprising initializing the bank of processing elements to load the outcome matrix into memory cells associated with the processing elements.

20 . The method of claim 11 , wherein selecting the determined outcome comprises:

comparing each outcome metric to a depth value for the potential outcome; and

normalizing the outcome metrics;

multiplying each normalized outcome metric by a respective outcome identifier; and

returning the outcome identifier identifying the determined outcome.