Decision tree computation in hardware utilizing a physically distinct integrated circuit with on-chip memory and a reordering of data to be grouped

摘要

A computing device for use in decision tree computation is provided. The computing device may include a software program executed by a processor using portions of memory of the computing device, the software program being configured to receive user input from a user input device associated with the computing device, and in response, to perform a decision tree task. The computing device may further include a decision tree computation device implemented in hardware as a logic circuit distinct from the processor, and which is linked to the processor by a communications interface. The decision tree computation device may be configured to receive an instruction to perform a decision tree computation associated with the decision tree task from the software program, process the instruction, and return a result to the software program via the communication interface.

主权项

1. A computing device for use in decision tree computation, comprising:
a processor; a software program stored in a mass storage device and executed by the processor to perform a decision tree task; and a decision tree computation device implemented in hardware as a logic circuit physically distinct from the processor, and which is linked to the processor by a communications interface, the decision tree computation device being configured to receive an instruction to perform a decision tree computation associated with the decision tree task from the software program, process the instruction, retrieve a plurality of items of input data and decision tree database data including a decision tree having a plurality of node descriptors, perform the decision tree computation by applying the decision tree to the plurality of items of input data, and return a result to the software program via the communications interface, wherein the hardware in which the decision tree computation device is implemented includes on-chip memory and is a field programmable gate array (FPGA), complex programmable logic device (CPLD), or application specific integrated circuit (ASIC), and wherein the computing device further includes off-chip memory in direct communication with the processor, the off-chip memory being physically distinct from the on-chip memory of the decision tree computation device; and wherein, to perform the decision tree computation, the decision tree computation device is configured to retrieve the plurality of items of input data from the off-chip memory physically distinct from the hardware in which the decision tree computation device is implemented, retrieve decision tree database data including the decision tree having a plurality of node descriptors from the off-chip memory, initialize a current list containing the input data, evaluate each item of input data based on node descriptors at a current level in the decision tree, and reorder the evaluated input data to be grouped by node descriptor in a next list to be evaluated according to the node descriptors at a next level of the decision tree.