Hardware random forest: low latency, fully reconfigurable ensemble classification

Systems, methods, computer program products, and apparatuses for low latency, fully reconfigurable hardware logic for ensemble classification methods, such as random forests. An apparatus may comprise circuitry for an interconnect and circuitry for a random forest implemented in hardware. The random forest comprising a plurality of decision trees connected via the interconnect, each decision tree comprising a plurality of nodes connected via the interconnect. A first decision tree of the plurality of decision trees comprising a first node of the plurality of nodes to: receive a plurality of elements of feature data via the interconnect, select a first element of feature data, of the plurality of elements of feature data, based on a configuration of the first node, and generate an output based on the first element of feature data, an operation, and a reference value, the operation and reference value specified in the configuration of the first node.

BACKGROUND

Systems such as autonomous vehicles demand agile and retrainable classification mechanisms, such as random forests. Doing so may allow these systems to detect different types of behavior, which may improve overall safety and performance. However, these classification systems often change over time. Therefore, implementing classification mechanisms in hardware require the flexibility to allow the hardware to reflect the changing classification mechanisms.

DETAILED DESCRIPTION

Embodiments disclosed herein provide low latency, fully reconfigurable hardware logic for ensemble classification methods, such as random forests. Generally, embodiments disclosed herein may provide reconfigurable logic that can quickly adapt to mutating tree structures. For example, a random forest may comprise a plurality of decision trees, each tree comprising a plurality of nodes. Embodiments disclosed herein may allow the reconfiguration of the trees, nodes, and/or associated interconnects to provide full parallel hardware execution with efficient routing of feature data to the nodes. By dynamically interconnecting configurable tree nodes and providing the feature data in an optimized order, embodiments disclosed herein achieve fully reconfigurable parallelized execution and allow for classification based on a subset of feature data.

Generally, a configuration file may specify the configuration for a random forest and its components. The configuration file may generally specify all parameters for the random forest, including the trees, nodes, interconnect(s), label translations, and optimal orderings of feature data. Whenever the configuration changes, the underlying hardware may be modified based on the configuration file. For example, a tree node may compare a first element of feature data to a reference value. If the reference value changes, the node configuration may be updated to reflect the changed reference value. Doing so allows for efficient reconfiguration of the underlying hardware by reprogramming only a portion of the hardware rather than reprogramming the hardware in its entirety.

Advantageously, embodiments disclosed herein provide techniques to improve the processing performance of random forests implemented at least partly in hardware. For example, by providing reconfigurable components, embodiments disclosed herein may improve the parallel processing performance of the random forest hardware. Furthermore, by improving the parallel processing performance of the random forest hardware, embodiments disclosed herein allow for faster decision making. For example, when embodied in an autonomous vehicle, the random forest hardware may enhance the safety of the operation of the autonomous vehicle, e.g., by detecting collisions, detecting malicious attacks to computing components of the autonomous vehicles, and the like, more quickly and/or accurately than conventional solutions.

FIG. 1illustrates an embodiment of a system100. As shown, the system100includes at least one apparatus101and a plurality of data sources120. As shown, the apparatus101includes circuitry130and a memory131. The circuitry130of the apparatus101comprises any type of circuitry, such as field programmable gate arrays (FPGAs), processors, microprocessors, microcontrollers, circuits, circuit elements (e.g., transistors, resistors, capacitors, inductors, and so forth), integrated circuits, application specific integrated circuits (ASIC), system on a chip (SoC), programmable logic array (PLA), complex programmable logic device (CPLD), programmable logic devices (PLD), digital signal processors (DSP), processor circuits, memory units, logic gates, registers, semiconductor device, chips, microchips, chip sets, and so forth.

In various embodiments, the system100including the apparatus101(or multiple apparatuses101) may be implemented in an autonomous vehicle. Generally, the apparatus101provides low latency fully reconfigurable ensemble classifications. In such embodiments, the autonomous vehicle includes one or more of the data sources120. The data sources120are representative of any type of data source that provides feature data121and/or configuration data122. For example, the data sources120may be hardware, software, and/or a combination of hardware and software. In one example, the data sources120include electronic control units (ECUs) of an autonomous vehicle. In other examples, the data sources120may be storage devices, memory devices, sensors, cameras or other image capture devices, applications, databases, streaming data sources, and/or other programmable logic. Although depicted as being provided by the same data sources120, in some embodiments, the feature data121and the configuration data122may be provided by different data sources120.

The feature data121is representative of any type of data describing one or more features (or attributes). For example, the feature data121may include data describing attributes of an autonomous vehicle, such as current speed of the vehicle, engine temperature, fuel reserve, etc. In some embodiments, the feature data121is generated by one or more processing algorithms (e.g., a machine learning algorithm, etc.). Generally, each type of feature in the feature data121may have a unique feature identifier (ID) (e.g., a unique ID for current speed, a unique ID for the engine temperature, a unique ID for fuel reserve, etc.). The configuration data122is representative of any type of data defining configuration parameters for the apparatus101. For example, the configuration data122may include configuration parameters for the random forest104, one or more trees105of the random forest104, the nodes106of each tree105, the node interconnect107of each tree105, the tree interconnect112of the random forest104, the voting engine108, the configuration interconnect109, and/or the feature interconnect110. Generally, each element of configuration data122may include a unique ID for each associated entity of the apparatus102, e.g., a random forest ID, tree ID, node ID, etc. Doing so allows the relevant components of the apparatus101to consume the correct configuration data122when streamed by the configuration streamer102.

As shown, the circuitry130of the apparatus101includes a configuration streamer102, a feature streamer103, one or more random forests104, a voting engine108, a configuration interconnect109, and a feature interconnect110. The random forest104includes a plurality of decision trees105and a tree interconnect112. Each tree105includes a plurality of nodes106and a node interconnect107. Although depicted as separate interconnects, the interconnects107,109,110,112may be part of a single interconnect (also referred to as a bus or a communications network).

As described in greater detail herein, the configuration streamer102is configured to stream the configuration data122to the various components of the apparatus101via the configuration interconnect109. The random forest104is an example of an ensemble classification structure for classification tasks, regression tasks, and other tasks based on the trees105. The trees105may be generated during a training phase. The output of the random forest104is generally based on the output of each tree105, such as the most common classification of the trees105and/or the mean prediction of the trees105. For example, for an image classification task, each tree105may generate an output classifying an object depicted in the image as a type of animal, e.g. a dog, a cat, a bird, etc. In such an example, the final output of the random forest104is the mode of the outputs all trees105. Therefore, if three of the trees105classify the animal as a cat, two of the trees105classify the animal as a dog, and one tree105classifies the animal as a bird, the output of the random forest104is the cat classification.

As described in greater detail herein, the node interconnect107generally interconnects the nodes106of each tree105to facilitate fully parallel processing by each node106in each tree105. Doing so improves processing performance relative to conventional software-based trees which have a conventional software tree structure (e.g., a root node and one or more child nodes on different tree levels) that does not allow for parallel processing. The voting engine108is configured to efficiently compute votes based on the output of each tree105in the random forest104. The label translator111of the voting engine108provides techniques to translate decisions generated by each tree105to a corresponding label. The tree interconnect112connects the plurality of trees105of the random forest104. The feature streamer103receives the feature data121from the data sources120. The feature interconnect110is an interconnect over which the feature streamer103streams the feature data121to the random forest104.

As stated, the system100may be implemented in an autonomous vehicle. In such embodiments, the apparatus101may analyze the feature data121for any number of purposes. For example, the feature data121may be analyzed to detect attacks to components of the autonomous vehicle, such as masquerading attacks, flooding attacks, and/or suspension attacks to one or more ECUs of the autonomous vehicle. If the output of the random forest104indicates an ECU is subject to an attack, one or more operations may be performed in response to the attack. For example, an alert may be generated, the impacted ECU may be taken offline, the impacted ECU may be replaced with a standby ECU, and/or messages generated by the impacted ECU may be modified to prevent consumption by other ECUs in the autonomous vehicle. For example, if the impacted ECU may cause the autonomous vehicle to travel at an unsafe speed, messages generated by the impacted ECU may be modified such that the autonomous vehicle does not travel at the unsafe speed. As another example, the speed of the autonomous vehicle may be modified from the unsafe speed to a slower speed (e.g., the speed limit where the vehicle is traveling).

FIG. 2is a schematic200depicting components of the configuration streamer102in greater detail. As shown, a configuration file220may be provided as input to the configuration streamer102. In some embodiments, the configuration file220may be received as configuration data122from the data sources120. The configuration file220may be generated during a training of the random forest104. The configuration file220may generally specify a plurality of configuration parameters for the random forest104. The configuration parameters include configurations for the interconnects107,109,110,112, the random forest104, the trees105, the nodes106, the voting engine108, and/or the label translator111. Once received, the configuration streamer102may store various portions of the configuration file220as the forest configuration201. The forest configuration201includes a node configuration202for configuration of each node106in each tree105, a tree configuration203for configuration of each tree105, an interconnect configuration204for configuration of the interconnects107,109,110,112, and a label configuration205for configuration of the label translator111. Generally, each tree105may be associated a unique tree identifier in the tree configuration203and each node106may be associated with a unique node identifier in the node configuration202. Doing so allows the trees105and nodes106to apply the tree configuration203and node configuration202, e.g., by selecting configuration data that is associated with the correct tree and/or node identifiers.

When a new forest configuration201is generated based on the configuration file220, a configuration sequencer210of the configuration streamer102may transmit the relevant portions of the forest configuration201via the configuration interconnect109. Advantageously, rather than reprogramming the apparatus101in its entirety, the configuration streamer102may reprogram only those portions of the apparatus101having an updated configuration. For example, when receiving node configuration data202, a nodes106may apply updates associated with the node ID assigned to the given node in the configuration data202. Similarly, when receiving tree configuration data203, the trees105may apply updates associated with the tree ID assigned to the tree105in the configuration data203.

FIG. 3is a schematic300depicting components of the feature streamer103in greater detail. As shown, the feature streamer103includes a feature list301. The feature list301generally specifies each feature of a plurality of features, where each feature is associated with a respective feature ID, an indication of whether the feature data is valid (e.g., available to be streamed), and a corresponding value. For example, as shown, feature data121-0may correspond to the entry having an ID of 0 in the feature list301, which is associated with an example “Feature 0”. Similarly, feature data121-1may correspond to the entry having an ID of 1 in the feature list301, which is associated with an example “Feature 1”. Further still, feature data121-N (where N is a positive integer greater than 1) may correspond to the entry having an ID of N in the feature list301, which is associated with an example “Feature N”. Generally, the values of Feature 0 . . . Feature N may take any relevant value (e.g., integers, binary values, etc.). As described in greater detail below, the node configuration202for each node106specifies one or more feature IDs that the node106is to select for processing (or consideration).

As shown, the feature streamer103includes a feature sequencer310which streams the received feature data121according to a feature order311. The feature order311may be specified in the configuration file220and determined during training. The feature order311may generally specify an ordering of the most important, or relevant features in the feature data121. The feature order311may be determined based on the number of nodes106in the trees105and/or forest104that consider (or process) a given feature. For example, if the node configuration202of 1,000 nodes106in the forest104specify to process feature “X” while the node configuration202of 500 nodes106in the forest specify to process feature “Y”, the feature order311may specify to stream feature X prior to streaming feature Y. Therefore, in such examples, if feature data121for features X and Y are available, the feature sequencer310may transmit the feature data121for feature X prior to transmitting the feature data for feature Y.

Additionally and/or alternatively, the feature order311may be determined based on the paths in each tree105that include each feature. Generally, if a feature is included in a shorter path and/or a path that allows for more quickly reaching a decision based on the feature, the feature may have a relatively higher position in the feature order311than other features. Therefore, if feature “Z” is in the shortest path to a decision in a tree105(or multiple paths of one or more trees105) than a feature “A”, feature Z may have a higher position in the feature order311relative to feature A. Therefore, in such examples, if feature data121for features A and Z are available, the feature sequencer310may transmit the feature data121for feature Z prior to transmitting the feature data for feature A. In some embodiments, a path score may be computed for each feature, where the path score is based on the path lengths of each tree path the feature is included in. For example, the path score may be the average path length of all paths the feature is included in. The path score may be used to rank each feature for the feature order. Additionally and/or alternatively the position of nodes106in the tree105that consider a given feature may be used to determine the feature order311, where features that are considered earlier than other features have a higher relative ordering in the feature order311. For example, if a node106-1processes feature X before a node106-2processes feature Y, feature X may have a higher relative ordering in the feature order311.

FIG. 4is a schematic400depicting an example tree105-1of the random forest104, according to one embodiment. As shown, the tree105-1includes example nodes106-1through106-N, where106-N is a positive integer greater than 6. The number of nodes depicted in the tree105-1is for illustrative purposes only, as the tree105-1may include any positive number of nodes106. Generally, each node106is configured to receive feature data via the feature interconnect110, select one or more features from the received feature data, and apply an operation to the selected feature data to a reference value to generate an output. For example, as shown, node106-1selects feature data “F0” and determines whether the value of F0is less than or equal to a reference value α. Doing so may generate an output R0reflecting whether the value of F0is less than or equal to α.

As described in greater detail herein, the output of each node106-1through106-N may be routed through the node interconnect107. For example, as shown, the logic gates401-1through401-N (where401-N is any positive integer greater than 3) may consider certain outputs of each node based on a configuration for the node interconnect107. Doing so allows the logic gates401-1through401-N to generate a binary decision for a given output label, e.g., label1, label2, etc. The binary label decisions may then be translated to final labels by the label translator111, which outputs a tree result402.

FIG. 5is a schematic500depicting an example node106-1in greater detail. As shown, the node106-1may receive feature data121as input. As shown, the feature data121may be transmitted in batches. For a given element of feature data121, a feature ID511and a feature value512may be specified. For example, as shown, feature ID511-1may have an associated feature value512-1, while feature ID511-2has an associated feature value512-2, and feature ID511-N has an associated feature value of512-N. In such an example, the feature ordering311of the feature streamer103may specify an ordering that causes feature ID511-1to be streamed before feature ID511-2and causes feature ID511-2to be streamed before feature ID511-N. Therefore, in the depicted example, feature ID511-1has a higher relative priority than feature ID511-2and feature ID511-N, while feature ID511-2has a higher relative priority than feature ID511-N. Furthermore, for example, feature ID511-1may be the feature ID of “0” while the associated feature value512-1has the value for the feature, such as 0.9.

As shown, the node106-1includes the node configuration202-1, which may be at least a portion of the node configuration202ofFIG. 2for the node106-1. Generally, the node configuration202-1specifies which feature ID(s) the node106-1should select for processing, an operation ID, and a reference value. Generally, when receiving the feature data121, the node ID502(which uniquely identifies the node106-1) may be used as an index into the node configuration202-1. Doing so returns a feature ID503, an operation ID504, and a reference value505from the node configuration202-1. The node106-1may use the feature ID503to select one or more of the elements of feature data from the feature data121. For example, if the feature ID503is511-1, the node106-1may select the feature511-1and corresponding value512-1as the selected features506. In doing so, the node106-1may ignore or otherwise refrain from processing other elements of feature data, such as the feature511-2and corresponding value512-2and/or feature511-N and corresponding value512-N.

In processing block507, the node106-1may process the selected features506based on the corresponding operation ID504and reference value505. In some embodiments, the operation ID504may be associated with a type of operation (e.g., an operation ID of 0 may be associated with the less than operation, an operation ID of 1 may be associated with the greater than operation, and so on). The reference value505may be a value that the value512-N of the selected feature506is compared to. For example, if feature511-1is the selected feature506, the feature value512-N is 10, the operation ID504is 0, and the reference value505is 20, the processing block507may determine whether 10 is less than 20. Doing so generates a result which is the output of the node106-1(e.g., an evaluation of true in the previous example of 10 being less than 20).

FIG. 6is a schematic600depicting components of the node interconnect107in greater detail. As shown, the evaluation outputs E0through En generated by the nodes106are received by the node interconnect107. Registers604-1through604-M may generally store binary values indicating whether the evaluation output E0-En should be considered when making a decision. For example, register604-1corresponds to whether E0is considered or not considered, while register604-2corresponds to whether the inverse of E0is considered or not considered. Generally, only one register of a pair of left/right registers (e.g., register604-1or register604-2) may be enabled, as each corresponds to an output branch of a node (e.g., the decision tree only flows to one branch based on the evaluation output of the node, such as to the left if E0is true, or to the right if E0is false). The values in the registers604-1through604-M may be programmed by the configuration engine601based on the interconnect configuration204. The configuration engine601may receive the interconnect configuration204from the configuration streamer102and apply the configuration matching a corresponding tree ID602. Each register Lmnor RmninFIG. 6may store a corresponding value as specified by the interconnect configuration204. Similarly, the configuration engine601may program the values in the enable decision registers605-1through605-M based on the interconnect configuration204received from the configuration streamer102.

The data stored in the registers604may be provided as input to one or more logic gates606, which may comprise OR gates or any other type of logic gate. Doing so provides efficient processing, as the values of the evaluation results E0through En may not need to be considered. Instead, the values in the registers604indicate whether the evaluation is true or false. For example, if the value in register604-1is “1”, the output607-1of OR gate606-1is “1”, or true (in other words, E0is not considered). If the value in register604-1is “0”, the output607-1of OR gate606-1is “1”, or true, only when E0is true, in other words, E0is taken into account in the construction of output607-1. If E0is “1”, the output607-1is “1”. Similarly, if E0is “0”, the output607-1is “0”.

The enable decision registers605-1through605-M, labeled “ED0” through “EDm”, are used to determine whether to enable the corresponding AND decision gate610-0through610-M. For example, if ED0605-1has a value of 0, decision gate610-0is disabled. Similarly, if EDm605-M has a value of 1, decision gate610-mis enabled. Generally, an enable decision register ED0through EDmis set based on whether all registers604connected to a given decision gate610are set to “1”. Otherwise, if one or more registers604connected to a given decision gate610are set to “0”, the corresponding evaluation result (e.g., E0through En) is relevant, and the decision gate610is not disabled. If enabled, each of the decision gates610-0through610-M generate a decision as output. Generally, each decision gate610-0through610-M operates independently. Therefore, for example, decision gate610-0may be independently enabled based on the values of registers604-1,604-2,604-3, and604-4(e.g., all registers604connected to decision gate610-0). Similarly, decision gate decision gate610-M may be independently disabled based on the values of registers604-5,604-6,604-7, and604-M (e.g., all registers604connected to decision gate610-M).

Advantageously, the configuration depicted inFIG. 6is an optimization relative to conventional solutions. More specifically, by configuring the enable decision registers605-1through605-M, embodiments disclosed herein may forego the need to stream data into some of the registers604that drive the decision gates610, thereby optimizing system performance. In other embodiments, the enable decision registers605-1through605-M may be removed. In such embodiments, the registers604need to be set to determine whether the corresponding decision gates610are activated. Doing so may save resources by not including the enable decision registers605-1through605-M, but may require additional configuration parameters to be specified in the configuration data for the node interconnect107.

FIG. 7is a schematic700illustrating the label translator111in greater detail. As shown, a label table701and a label array702may be programmed based on the label configuration205. In some embodiments, the label table701may include a subset of a plurality of possible decision labels that can be outputted by a tree105. Stated differently, the label table701may include less than all of the plurality of possible decision labels that the tree105can output. In other embodiments, the label table701may include all possible decision labels that can be outputted by a tree105. The label array702includes all possible decision labels that can be outputted by the random forest104, which includes all decision labels in the label table701and additional labels not present in the label table701. Therefore, when a decision is received from a tree105, the decision is used to index into the label table701. Doing so may return an index value which is used to index into the label array702. The corresponding entry of the label array702may then be returned as the classification result for the tree105. The entries in the label array702are mutually exclusive, as only one classification result can be returned for a given tree105.

FIG. 8is a schematic800illustrating the voting engine108in greater detail. As shown, the voting engine108receives the classification results for a plurality of trees105(e.g., a label array702-1through702-N for trees105-1through105-N). The voting engine108may compute a label count801which is an array reflecting the values in each label array702-1through702-N. In one embodiment, the voting engine108performs a Hamming weight computation to efficiently sum the values in the label arrays702-1through702-N. Generally, the label count801reflects a count of trees105generating the corresponding label (or result) as a final output. For example, as shown, the first entry in the label count801is a value of 1, indicating a single tree105returned the corresponding label as a result (e.g., classifying a fruit depicted in an image as an apple). The majority voter802may select the greatest value in the label count801as the final classification result of the random forest104. For example, the fourth entry in the label count801has the greatest depicted value of 5 (which may correspond to classifying the fruit as an orange). Therefore, the classification corresponding to the fourth entry (e.g., an orange) may be returned as the classification result for the random forest104, as the most common classification generated by the trees105in the random forest104was the orange.

In some embodiments, a classification result for the random forest104may be returned if a majority decision is detected prior to one or more trees105generating a classification result. For example, if there are ten trees105in the random forest104and six of the trees105return the same classification (e.g., classify the fruit as an orange), a majority decision has been reached. Therefore, the majority voter802may return the majority decision (e.g., the orange) as the final classification result for the random forest104without waiting for the remaining four trees105to generate a classification result.

In some examples, a tie may exist (e.g., 5 of the trees105may classify the fruit as an orange, while the remaining 5 trees105may classify the fruit as an apple). In such examples, the voting engine108may define one or more policies to resolve the tie. One example policy may specify to select one of the labels (e.g., select orange or apple as the classification result). Another example policy would output both labels (e.g., return both orange and apple as the classification result). Yet another example policy outputs no result and indicate that a tie has occurred. In some embodiments, the number of trees105in the forest104may be defined to avoid ties (e.g., by including an odd number of trees105, including a greater number of trees105than possible classification results, etc.).

Operations for the disclosed embodiments may be further described with reference to the following figures. Some of the figures may include a logic flow. Although such figures presented herein may include a particular logic flow, it can be appreciated that the logic flow merely provides an example of how the general functionality as described herein can be implemented. Further, a given logic flow does not necessarily have to be executed in the order presented unless otherwise indicated. In addition, the given logic flow may be implemented by a hardware element, a software element executed by a processor, or any combination thereof. The embodiments are not limited in this context.

FIG. 9illustrates an embodiment of a logic flow900. The logic flow900may be representative of some or all of the operations executed by one or more embodiments described herein. For example, the logic flow900may represent some or all of the operations performed by the apparatus101and/or another computing system to determine the feature order311during training. Embodiments are not limited in this context.

As shown, the logic flow900begins at block910, where a count of nodes106having a configuration202specifying to select (or process) a feature is determined for each of a plurality of features. The count for each feature may be based on each node106of each tree105in the random forest104. For example, the feature ID for feature “C” may be specified as a selected feature503in the node configuration202for 500 nodes, while the feature ID for feature “D” may be specified as a selected feature503in the node configuration202for 100 nodes. Generally, such counts would cause the feature order311to place feature C in a higher relative position than feature D.

At block920, an average path length is determined for each path that includes a given feature. For example, the average path length of all paths of all trees105that include feature C may be 5.5 nodes. Similarly, the average path length of all paths of all trees105that include feature D may be 3.3 nodes. Therefore, based on average path length, feature D may have a higher relative ordering in the feature order311. At block930, the average node position of each node that selects a given feature is determined for each feature. For example, the nodes106in each tree may be ordered based on processing flow. Therefore, features that are considered by nodes106that are earlier in the processing flow may cause the average node position to be lower for the feature. For example, the average node position for feature C may be 10 and 20 for feature D. Therefore, based on node position, feature C may have a higher relative ordering than feature D in the feature order311.

At block940, the feature order311is determined based on one or more of the feature count, average path length, and/or average node positions determined at blocks910-930respectively. For example, the feature order311may rank feature C higher than feature D, indicating feature C has greater relative importance. Doing so may cause the feature streamer103to stream features according to the feature order311at block950.

FIG. 10illustrates an embodiment of a logic flow1000. The logic flow1000may be representative of some or all of the operations executed by one or more embodiments described herein. For example, the logic flow1000may be representative of some or all of the operations executed by a node106. Embodiments are not limited in this context.

As shown, the logic flow1000begins at block1010, where an example node106receives a plurality of elements of feature data121. The plurality of elements of feature data121may be a batch that is ordered according to the feature order311. Each element of feature data121may have a corresponding feature ID. At block1020, the node106selects a first feature of the plurality of features based on the configuration202for the node106. For example, the feature IDs received at block1010may include ID values of 100, 200, and 300. If the node configuration202for the node106specifies the feature ID of 200, the node106selects the feature ID200and corresponding value (e.g., 0.25) as the first feature, while ignoring the remaining elements of feature data. At block1030, the node106performs an operation (e.g., less than) specified by an operation ID in the node configuration202. The operation may be applied to the value of the first element of feature data and a reference value (e.g., 0.1). At block1040, the result of the operation performed at block1030is outputted via the node interconnect107. For example, the result of the operation may be false based on the operation determining whether 0.25 is less than 0.1.

FIG. 11illustrates an embodiment of a logic flow1100. The logic flow1100may be representative of some or all of the operations executed by one or more embodiments described herein. For example, the logic flow1100may be representative of some or all of the operations executed by the node interconnect107. Embodiments are not limited in this context.

As shown, the logic flow1100begins at block1110, where the node interconnect107receives a respective output generated by each of a plurality of nodes106-1through106-N. At block1120, the node interconnect107determines to consider an output of a first node of the plurality of nodes based on the configuration204for the node interconnect107. At block1130, the node interconnect107determines to refrain from considering an output of a second node of the plurality of nodes based on the configuration204for the node interconnect107. At block1140, the tree105generates a decision based at least in part on the output of the first node and without considering the output of the second node.

FIG. 12illustrates an embodiment of a logic flow1200. The logic flow1200may be representative of some or all of the operations executed by one or more embodiments described herein. For example, the logic flow1200may be representative of some or all of the operations executed to translate decisions generated by trees105to labels by the label translator111. Embodiments are not limited in this context.

As shown, at block1210, the label translator111receives a decision from a first tree105-1. At block1220, the label translator111references the label table701to return an index value corresponding to the decision received from the first tree105-1. At block1230, the label translator111references the label array702using the index value returned at block1220to determine a label for the decision of the tree105-1. The index value may generally correspond to a position in the label array702. The label in the corresponding position of the label array702may be returned as the classification result for the tree105-1at block1240.

FIG. 13illustrates an embodiment of a storage medium1300. Storage medium1300may comprise any non-transitory computer-readable storage medium or machine-readable storage medium, such as an optical, magnetic or semiconductor storage medium. In various embodiments, storage medium1300may comprise an article of manufacture. In some embodiments, storage medium1300may store computer-executable instructions, such as computer-executable instructions to implement one or more of logic flows or operations described herein, such as instructions1301for the apparatus101(and all components thereof). The storage medium1300may store computer-executable instructions1302-1305for logic flows900,1000,1100, and1200ofFIGS. 9-12respectively. Examples of a computer-readable storage medium or machine-readable storage medium may include any tangible media capable of storing electronic data, including volatile memory or non-volatile memory, removable or non-removable memory, erasable or non-erasable memory, writeable or re-writeable memory, and so forth. Examples of computer-executable instructions may include any suitable type of code, such as source code, compiled code, interpreted code, executable code, static code, dynamic code, object-oriented code, visual code, and the like. The embodiments are not limited in this context.

FIG. 14illustrates an embodiment of an exemplary computing architecture1400comprising a computing system1402that may be suitable for implementing various embodiments as previously described. In various embodiments, the computing architecture1400may comprise or be implemented as part of an electronic device. In some embodiments, the computing architecture1400may be representative, for example, of a system that implements one or more components of the system100. In some embodiments, computing system1402may be representative, for example, of the apparatus101of the system100. The embodiments are not limited in this context. More generally, the computing architecture1400is configured to implement all logic, applications, systems, methods, apparatuses, and functionality described herein with reference toFIGS. 1-13.

As shown inFIG. 14, the computing system1402comprises a processor1404, a system memory1406and a system bus1408. The processor1404can be any of various commercially available computer processors, including without limitation an AMD® Athlon®, Duron® and Opteron® processors; ARM® application, embedded and secure processors; IBM® and Motorola® DragonBall® and PowerPC® processors; IBM and Sony® Cell processors; Intel® Celeron®, Core®, Core (2) Duo®, Itanium®, Pentium®, Xeon®, and XScale® processors; and similar processors. Dual microprocessors, multi-core processors, and other multi processor architectures may also be employed as the processor1404.

The system bus1408provides an interface for system components including, but not limited to, the system memory1406to the processor1404. The system bus1408can be any of several types of bus structure that may further interconnect to a memory bus (with or without a memory controller), a peripheral bus, and a local bus using any of a variety of commercially available bus architectures. In one embodiment, the bus1408comprises the interconnects107,109,110, and/or112ofFIG. 1. Interface adapters may connect to the system bus1408via a slot architecture. Example slot architectures may include without limitation Accelerated Graphics Port (AGP), Card Bus, (Extended) Industry Standard Architecture ((E)ISA), Micro Channel Architecture (MCA), NuBus, Peripheral Component Interconnect (Extended) (PCI(X)), PCI Express, Personal Computer Memory Card International Association (PCMCIA), and the like.

The computing system1402may include various types of computer-readable storage media in the form of one or more lower speed memory units, including an internal (or external) hard disk drive (HDD)1414, a magnetic floppy disk drive (FDD)1416to read from or write to a removable magnetic disk1418, and an optical disk drive1420to read from or write to a removable optical disk1422(e.g., a CD-ROM or DVD). The HDD1414, FDD1416and optical disk drive1420can be connected to the system bus1408by a HDD interface1424, an FDD interface1426and an optical drive interface1428, respectively. The HDD interface1424for external drive implementations can include at least one or both of Universal Serial Bus (USB) and IEEE 1394 interface technologies. The computing system1402is generally is configured to implement all logic, systems, methods, apparatuses, and functionality described herein with reference toFIGS. 1-10.

The drives and associated computer-readable media provide volatile and/or nonvolatile storage of data, data structures, computer-readable instructions, computer-executable instructions, and so forth. For example, a number of program modules can be stored in the drives and memory units1410,1412, including an operating system1430, one or more application programs1432, other program modules1434, and program data1436. In one embodiment, the one or more application programs1432, other program modules1434, and program data1436can include, for example, the various applications and/or components of the system100, such as the apparatus101, data sources120, the feature data121, and/or the configuration data122.

A user can enter commands and information into the computing system1402through one or more wire/wireless input devices, for example, a keyboard1438and a pointing device, such as a mouse1440. Other input devices may include microphones, infra-red (IR) remote controls, radio-frequency (RF) remote controls, game pads, stylus pens, card readers, dongles, finger print readers, gloves, graphics tablets, joysticks, keyboards, retina readers, touch screens (e.g., capacitive, resistive, etc.), trackballs, trackpads, sensors, styluses, and the like. These and other input devices are often connected to the processor1404through an input device interface1442that is coupled to the system bus1408, but can be connected by other interfaces such as a parallel port, IEEE 1394 serial port, a game port, a USB port, an IR interface, and so forth.

A monitor1444or other type of display device is also connected to the system bus1408via an interface, such as a video adaptor1446. The monitor1444may be internal or external to the computing system1402. In addition to the monitor1444, a computer typically includes other peripheral output devices, such as speakers, printers, and so forth.

The computing system1402may operate in a networked environment using logical connections via wire and/or wireless communications to one or more remote computers, such as a remote computer1448. The remote computer1448can be a workstation, a server computer, a router, a personal computer, portable computer, microprocessor-based entertainment appliance, a peer device or other common network node, and typically includes many or all of the elements described relative to the computing system1402, although, for purposes of brevity, only a memory/storage device1450is illustrated. The logical connections depicted include wire/wireless connectivity to a local area network (LAN)1452and/or larger networks, for example, a wide area network (WAN)1454. Such LAN and WAN networking environments are commonplace in offices and companies, and facilitate enterprise-wide computer networks, such as intranets, all of which may connect to a global communications network, for example, the Internet.

When used in a LAN networking environment, the computing system1402is connected to the LAN1452through a wire and/or wireless communication network interface or adaptor1456. The adaptor1456can facilitate wire and/or wireless communications to the LAN1452, which may also include a wireless access point disposed thereon for communicating with the wireless functionality of the adaptor1456.

When used in a WAN networking environment, the computing system1402can include a modem1458, or is connected to a communications server on the WAN1454, or has other means for establishing communications over the WAN1454, such as by way of the Internet. The modem1458, which can be internal or external and a wire and/or wireless device, connects to the system bus1408via the input device interface1442. In a networked environment, program modules depicted relative to the computing system1402, or portions thereof, can be stored in the remote memory/storage device1450. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers can be used.

The computing system1402is operable to communicate with wired and wireless devices or entities using the IEEE 802 family of standards, such as wireless devices operatively disposed in wireless communication (e.g., IEEE 802.16 over-the-air modulation techniques). This includes at least Wi-Fi (or Wireless Fidelity), WiMax, and Bluetooth™ wireless technologies, among others. Thus, the communication can be a predefined structure as with a conventional network or simply an ad hoc communication between at least two devices. Wi-Fi networks use radio technologies called IEEE 802.14x (a, b, g, n, etc.) to provide secure, reliable, fast wireless connectivity. A Wi-Fi network can be used to connect computers to each other, to the Internet, and to wire networks (which use IEEE 802.3-related media and functions).

Example 1 is an apparatus, comprising: circuitry for an interconnect; and circuitry for a random forest implemented in hardware, the random forest to comprise a plurality of decision trees connected via the interconnect, each decision tree to comprise a plurality of nodes connected via the interconnect, a first decision tree of the plurality of decision trees to comprise a first node of the plurality of nodes to: receive a plurality of elements of feature data via the interconnect select a first element of feature data, of the plurality of elements of feature data, based on a configuration of the first node; and generate an output based on the first element of feature data, an operation, and a reference value, the operation and reference value specified in the configuration of the first node.

Example 2 includes the subject matter of example 1, comprising the first node to: receive an updated configuration specifying a second element of feature data of the plurality of elements of feature data, an updated operation, and an updated reference value; and update the configuration of the first node based on the updated configuration, wherein the first and second elements of feature data correspond to different features.

Example 3 includes the subject matter of example 2, comprising the first node to: receive a second plurality of elements of feature data via the interconnect select the second element of feature data of the second plurality of elements of feature data based on the updated configuration of the first node; and generate a second output based on the second element of feature data, the updated operation, and the updated reference value.

Example 4 includes the subject matter of example 1, comprising the circuitry for the interconnect to: receive the output generated by the first node determine, based on a configuration of the interconnect, to use the output generated by the first node to generate a decision for the first decision tree; and cause the decision for the first decision tree to be generated based at least in part on the output generated by the first node.

Example 5 includes the subject matter of example 4, comprising the circuitry for the interconnect to: receive an updated configuration for the interconnect, the updated configuration specifying to not use the output generated by the first node to generate the decision for the first decision tree; and update the configuration of the interconnect based on the updated configuration for the interconnect.

Example 6 includes the subject matter of example 5, comprising the circuitry for the interconnect to: receive a second output generated by the first node; and cause a second decision to be generated for the first decision tree without using the second output generated by the first node.

Example 7 includes the subject matter of example 4, comprising the circuitry for the random forest to: receive the decision for the first decision tree; and determine a label for the decision of the first decision tree based on a lookup table indexed using the decision from the first decision tree.

Example 8 includes the subject matter of example 7, the circuitry for the random forest to: determine the label is returned by a majority of the decision trees; and determine the label as a final output of the random forest without receiving a decision from each of the decision trees.

Example 9 includes the subject matter of example 8, the circuitry for the random forest implemented in an autonomous vehicle, the autonomous vehicle to modify an operational parameter of the autonomous vehicle based on the final output of the random forest.

Example 10 includes the subject matter of example 1, the plurality of elements of feature data to be received by the first node according to an ordering of the plurality of elements of feature data, the ordering to be determined based a respective count for each element of feature data, each count to be determined based on a count of nodes in each decision tree having a configuration specifying to select the corresponding element of feature data.

Example 11 is a method, comprising: receiving, by a first node via an interconnect, a plurality of elements of feature data, wherein circuitry for a random forest implemented in hardware comprises a plurality of decision trees connected via the interconnect, wherein each decision tree comprises a plurality of nodes connected via the interconnect, a first decision tree of the plurality of decision trees comprising the first node selecting, by the first node, a first element of feature data, of the plurality of elements of feature data, based on a configuration of the first node; and generating, by the first node, an output based on the first element of feature data, an operation, and a reference value, the operation and reference value specified in the configuration of the first node.

Example 12 includes the subject matter of example 11, further comprising: receiving, by the first node, an updated configuration specifying a second element of feature data of the plurality of elements of feature data, an updated operation, and an updated reference value; and updating, by the first node, the configuration of the first node based on the updated configuration, wherein the first and second elements of feature data correspond to different features.

Example 13 includes the subject matter of example 12, further comprising: receiving, by the first node, a second plurality of elements of feature data via the interconnect selecting, by the first node, the second element of feature data of the second plurality of elements of feature data based on the updated configuration of the first node; and generating, by the first node, a second output based on the second element of feature data, the updated operation, and the updated reference value.

Example 14 includes the subject matter of example 11, further comprising: receiving, by the interconnect, the output generated by the first node determining, by the interconnect based on a configuration of the interconnect, to use the output generated by the first node to generate a decision for the first decision tree; and causing, by the interconnect, the decision for the first decision tree to be generated based at least in part on the output generated by the first node.

Example 15 includes the subject matter of example 14, further comprising: receiving, by the interconnect, an updated configuration for the interconnect, the updated configuration specifying to not use the output generated by the first node to generate the decision for the first decision tree; and updating the configuration of the interconnect based on the updated configuration for the interconnect.

Example 16 includes the subject matter of example 15, further comprising: receiving, by the interconnect, a second output generated by the first node; and causing, by the interconnect, a second decision to be generated for the first decision tree without using the second output generated by the first node.

Example 17 includes the subject matter of example 14, further comprising: receiving the decision for the first decision tree; and determining a label for the decision of the first decision tree based on a lookup table indexed using the decision from the first decision tree.

Example 18 includes the subject matter of example 17, further comprising: determining the label is returned by a majority of the decision trees; and determining the label as a final output of the random forest without receiving a decision from each of the decision trees.

Example 19 includes the subject matter of example 18, the circuitry for the random forest implemented in an autonomous vehicle, the autonomous vehicle to modify an operational parameter of the autonomous vehicle based on the final output of the random forest.

Example 20 includes the subject matter of example 11, the plurality of elements of feature data to be received by the first node according to an ordering of the plurality of elements of feature data, the ordering to be determined based a respective count for each element of feature data, each count to be determined based on a count of nodes in each decision tree having a configuration specifying to select the corresponding element of feature data.

Example 21 is an autonomous vehicle, comprising: circuitry for an interconnect; and circuitry for a random forest implemented in hardware, the random forest to comprise a plurality of decision trees connected via the interconnect, each decision tree to comprise a plurality of nodes connected via the interconnect, a first decision tree of the plurality of decision trees to comprise a first node of the plurality of nodes to: receive a plurality of elements of feature data via the interconnect select a first element of feature data, of the plurality of elements of feature data, based on a configuration of the first node; and generate an output based on the first element of feature data, an operation, and a reference value, the operation and reference value specified in the configuration of the first node.

Example 22 includes the subject matter of example 21, comprising the first node to: receive an updated configuration specifying a second element of feature data of the plurality of elements of feature data, an updated operation, and an updated reference value; and update the configuration of the first node based on the updated configuration, wherein the first and second elements of feature data correspond to different features.

Example 23 includes the subject matter of example 22, comprising the first node to: receive a second plurality of elements of feature data via the interconnect select the second element of feature data of the second plurality of elements of feature data based on the updated configuration of the first node; and generate a second output based on the second element of feature data, the updated operation, and the updated reference value.

Example 24 includes the subject matter of example 21, comprising the circuitry for the interconnect to: receive the output generated by the first node determine, based on a configuration of the interconnect, to use the output generated by the first node to generate a decision for the first decision tree; and cause the decision for the first decision tree to be generated based at least in part on the output generated by the first node.

Example 25 includes the subject matter of example 24, comprising the circuitry for the interconnect to: receive an updated configuration for the interconnect, the updated configuration specifying to not use the output generated by the first node to generate the decision for the first decision tree; and update the configuration of the interconnect based on the updated configuration for the interconnect.

Example 26 includes the subject matter of example 25, comprising the circuitry for the interconnect to: receive a second output generated by the first node; and cause a second decision to be generated for the first decision tree without using the second output generated by the first node.

Example 27 includes the subject matter of example 24, comprising the circuitry for the random forest to: receive the decision for the first decision tree; and determine a label for the decision of the first decision tree based on a lookup table indexed using the decision from the first decision tree.

Example 28 includes the subject matter of example 27, the circuitry for the random forest to: determine the label is returned by a majority of the decision trees; and determine the label as a final output of the random forest without receiving a decision from each of the decision trees.

Example 29 includes the subject matter of example 28, the autonomous vehicle to modify an operational parameter of the autonomous vehicle based on the final output of the random forest.

Example 30 includes the subject matter of example 21, the plurality of elements of feature data to be received by the first node according to an ordering of the plurality of elements of feature data, the ordering to be determined based a respective count for each element of feature data, each count to be determined based on a count of nodes in each decision tree having a configuration specifying to select the corresponding element of feature data.

Example 31 is an apparatus, comprising: means for receiving, by a first node via an interconnect, a plurality of elements of feature data, wherein circuitry for a random forest implemented in hardware is to comprise a plurality of decision trees connected via the interconnect, wherein each decision tree is to comprise a plurality of nodes connected via the interconnect, a first decision tree of the plurality of decision trees comprising the first node means for selecting, by the first node, a first element of feature data, of the plurality of elements of feature data, based on a configuration of the first node; and means for generating, by the first node, an output based on the first element of feature data, an operation, and a reference value, the operation and reference value specified in the configuration of the first node.

Example 32 includes the subject matter of example 31, further comprising: means for receiving, by the first node, an updated configuration specifying a second element of feature data of the plurality of elements of feature data, an updated operation, and an updated reference value; and means for updating, by the first node, the configuration of the first node based on the updated configuration, wherein the first and second elements of feature data correspond to different features.

Example 33 includes the subject matter of example 32, further comprising: means for receiving, by the first node, a second plurality of elements of feature data via the interconnect means for selecting, by the first node, the second element of feature data of the second plurality of elements of feature data based on the updated configuration of the first node; and means for generating, by the first node, a second output based on the second element of feature data, the updated operation, and the updated reference value.

Example 34 includes the subject matter of example 31, further comprising: means for receiving, by the interconnect, the output generated by the first node means for determining, by the interconnect based on a configuration of the interconnect, to use the output generated by the first node to generate a decision for the first decision tree; and means for causing, by the interconnect, the decision for the first decision tree to be generated based at least in part on the output generated by the first node.

Example 35 includes the subject matter of example 34, further comprising: means for receiving, by the interconnect, an updated configuration for the interconnect, the updated configuration specifying to not use the output generated by the first node to generate the decision for the first decision tree; and means for updating the configuration of the interconnect based on the updated configuration for the interconnect.

Example 36 includes the subject matter of example 35, further comprising: means for receiving, by the interconnect, a second output generated by the first node; and means for causing, by the interconnect, a second decision to be generated for the first decision tree without using the second output generated by the first node.

Example 37 includes the subject matter of example 34, further comprising: means for receiving the decision for the first decision tree; and means for determining a label for the decision of the first decision tree based on a lookup table indexed using the decision from the first decision tree.

Example 38 includes the subject matter of example 37, further comprising: means for determining the label is returned by a majority of the decision trees; and means for determining the label as a final output of the random forest without receiving a decision from each of the decision trees.

Example 39 includes the subject matter of example 38, the circuitry for the random forest implemented in an autonomous vehicle, the autonomous vehicle to modify an operational parameter of the autonomous vehicle based on the final output of the random forest.

Example 40 includes the subject matter of example 31, the plurality of elements of feature data to be received by the first node according to an ordering of the plurality of elements of feature data, the ordering to be determined based a respective count for each element of feature data, each count to be determined based on a count of nodes in each decision tree having a configuration specifying to select the corresponding element of feature data.

A data processing system suitable for storing and/or executing program code will include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code to reduce the number of times code must be retrieved from bulk storage during execution. The term “code” covers a broad range of software components and constructs, including applications, drivers, processes, routines, methods, modules, firmware, microcode, and subprograms. Thus, the term “code” may be used to refer to any collection of instructions which, when executed by a processing system, perform a desired operation or operations.

Logic circuitry, devices, and interfaces herein described may perform functions implemented in hardware and implemented with code executed on one or more processors. Logic circuitry refers to the hardware or the hardware and code that implements one or more logical functions. Circuitry is hardware and may refer to one or more circuits. Each circuit may perform a particular function. A circuit of the circuitry may comprise discrete electrical components interconnected with one or more conductors, an integrated circuit, a chip package, a chip set, memory, or the like. Integrated circuits include circuits created on a substrate such as a silicon wafer and may comprise components. And integrated circuits, processor packages, chip packages, and chipsets may comprise one or more processors.

Processors may receive signals such as instructions and/or data at the input(s) and process the signals to generate the at least one output. While executing code, the code changes the physical states and characteristics of transistors that make up a processor pipeline. The physical states of the transistors translate into logical bits of ones and zeros stored in registers within the processor. The processor can transfer the physical states of the transistors into registers and transfer the physical states of the transistors to another storage medium.

A processor may comprise circuits to perform one or more sub-functions implemented to perform the overall function of the processor. One example of a processor is a state machine or an application-specific integrated circuit (ASIC) that includes at least one input and at least one output. A state machine may manipulate the at least one input to generate the at least one output by performing a predetermined series of serial and/or parallel manipulations or transformations on the at least one input.