DECISION TREE COMPUTATION IN HARDWARE

• US 20130179377A1
• Filed: 01/05/2012
• Published: 07/11/2013
• Est. Priority Date: 01/05/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Parthasarathy, Padma, Carrie, Susan, Forin, Alessandro, Oberg, Jason, Eguro, Ken, Tirva, Victor, Chow, Jonathan
• Granted Patent: US 9,292,767 B2
• Time in Patent Office: Days
• US Class Current: 706/45
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

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.

Claims

1. A computing device for use in decision tree computation, comprising:

a processor in communication with memory and mass storage via a communications interface;

a software program stored in the mass storage device and executed by the processor using portions of the memory, 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; and

a decision tree computation device implemented in hardware as a logic circuit distinct from the processor, and which is linked to the processor by the 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, and return a result to the software program via the communication interface.

2. The computing device of claim 1, wherein the hardware in which the decision tree computation device is implemented is an integrated circuit formed separate from the processor, the integrated circuit including on-chip memory formed separate from the memory of the computing device.

3. The computing device of claim 2, wherein the hardware in which the decision tree computation device is implemented is a field programmable gate array (FPGA), complex programmable logic device (CPLD), or application specific integrated circuit (ASIC).

4. The computing device of claim 2, wherein the hardware in which the decision tree computation device is implemented is a system-on-chip, and each of the processor and the decision tree computation devices are separate logic units within the system-on-chip.

5. The computing device of claim 2, wherein the on-chip memory include a prefetch cache, and the decision tree computation device is configured to prefetch decision tree database data from the memory of the computing device, and store it in the prefetch cache of the on-chip memory.

6. The computing device of claim 5, wherein the on-chip memory further includes a FIFO buffer, and the decision tree computation device is further configured to, in response to receiving the instruction to perform the decision tree computation, load the FIFO buffer with input data in memory of the computing device, for subsequent access and processing by on-chip computation logic.

7. The computing device of claim 1, wherein the decision tree computation device is configured to perform binning of decision tree data loaded from the memory of the computing device into an off-chip memory location in the memory of the computing device.

8. The computing device of claim 1, wherein the software program is further configured to display output on a display associated with the computing device, based directly or indirectly on the result received from the decision tree computation device.

9. The computing device of claim 8, wherein the computing device is configured as a game console, the user input device includes a depth camera configured to capture depth image information as the user input, and the software program is configured to classify the depth image information via the decision tree computation task, based on the result received from the decision tree computation device.

10. The computing device of claim 1, wherein, to perform the decision tree computation, the decision tree computation device is configured to retrieve a plurality of items of input data from memory of the computing device, retrieve decision tree database data including a decision tree having a plurality of node descriptors from the memory of the computing device, 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.

11. The computing device of claim 1, wherein the result of the decision tree computation task received from the decision tree computation device is used by the software program in speech recognition, image processing, or search query processing.

12. A method for use in decision tree computation, comprising:

at a software program, executed on a processor of a computing device using portions of memory and mass storage;

receiving user input from a user input device associated with a computing device;

in response to the user input, performing a decision tree task, the performing of the decision tree task including sending an instruction from the software program to a decision tree computation device implemented in hardware as a logic circuit distinct from the processor;

at the decision tree computation device;

receiving the instruction from the software program;

performing a decision tree computation; and

returning a result to the software program.

13. The method of claim 12,

wherein the hardware in which the decision tree computation device is implemented is an integrated circuit formed separate from the processor, the integrated circuit including on-chip memory formed separate from the memory of the computing device;

and

wherein the instruction is sent from the software program to the decision tree computation device via a hardware communications interface.

14. The method of claim 13, wherein the hardware in which the decision tree computation device is implemented is a field programmable gate array (FPGA), complex programmable logic device (CPLD), or application specific integrated circuit (ASIC).

15. The method of claim 12, wherein the hardware in which the decision tree computation device is implemented is a system-on-chip, and each of the processor and the decision tree computation devices are separate logic units within the system-on-chip, and the instruction and result are communicated via a communications interface formed on the system-on-chip.

16. The method of claim 12, wherein performing a decision tree computation at the decision tree computation device includes:

prefetching decision tree database data from the memory of the computing device;

storing the decision tree database data in a prefetch cache of the on-chip memory.

17. The method of claim 16, wherein performing a decision tree computation at the decision tree computation device further includes:

in response to receiving the instruction to perform the decision tree computation, loading a FIFO buffer of the decision tree computation device with the decision tree data from the decision tree database in memory of the computing device, for subsequent access and processing by on-chip computation logic.

18. The method of claim 16, wherein performing a decision tree computation at the decision tree computation device further includes:

in response to receiving the instruction to perform the decision tree computation, binning decision tree data loaded from the memory of the computing device into an off-chip memory location in the memory of the computing device during processing of the decision tree data by the on-chip computation logic, for subsequent retrieval and processing.

19. The method of claim 12, further comprising:

displaying output on a display associated with the computing device, based directly or indirectly on the result received from the decision tree computation device

20. A computing device for use in decision tree computation, comprising:

a processor in communication with memory and mass storage via a communications interface;

a software program stored in the mass storage device and executed by the processor using portions of the memory, 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;

a decision tree computation device implemented in hardware as a logic circuit distinct from the processor, and which is linked to the processor by the 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, and return a result to the software program via the communication interface, wherein the hardware in which the decision tree computation device is implemented is an integrated circuit formed separate from the processor, the integrated circuit including on-chip memory formed separate from the memory of the computing device; and

the software program being further configured to display output on a display associated with the computing device, based directly or indirectly on the result received from the decision tree computation device;

wherein the computing device is configured as a game console, the user input device includes a depth camera configured to capture depth image information as the user input, and the software program is configured to classify the depth image information via the decision tree computation task, based on the result received from the decision tree computation device.