Accelerated decision tree execution

Patent metadata

Field	Value
Publication number	US-10152674-B2
Application number	US-201313742355-A
Country	US
Kind code	B2
Filing date	Jan 16, 2013
Priority date	Jan 16, 2012
Publication date	Dec 11, 2018
Grant date	Dec 11, 2018

Abstract

A method for accelerated decision tree execution in a processor of a digital system is provided that includes receiving at least some attribute values of a plurality of attribute values of a query for the decision tree in a pre-processing component, evaluating the received attribute values in the pre-processing component according to first early termination conditions corresponding to a first decision to determine whether or not the received attribute values fulfill first early termination conditions, and querying the decision tree with the plurality of attribute values when the received attribute values do not fulfill the first early termination conditions.

First claim

What is claimed is:

1. A method for accelerated decision tree execution in a digital signal processor (DSP) of a system-on-a-chip (SoC), using single-instruction-multi-data (SIMD) instructions in an instruction set architecture (ISA) of the DSP, the method comprising:
receiving, by the DSP, at least some attribute values of a plurality of attribute values of a query for a decision tree in a pre-processing component;
evaluating, by the DSP, with a fixed program flow, the received attribute values in the pre-processing component according to an early termination condition and without querying the decision tree to determine whether or not the received attribute values fulfill the early termination condition, the early termination condition corresponding to multiple conditions that occur at different nodes in a condition path between a root node and a leaf node of the decision tree; and
querying, by the DSP, the decision tree with the plurality of attribute values in response to determining that the received attribute values do not fulfill the early termination condition.

2. The method of claim 1 , wherein the leaf node is a first leaf node, wherein the early termination condition is a first early termination condition corresponding to the first leaf node of the decision tree, and wherein evaluating the received attribute values includes evaluating the received attribute values according to a second early termination condition corresponding to a second leaf node of the decision tree to determine whether or not the received attribute values fulfill the second early termination condition.

3. The method of claim 1 , wherein the early termination condition corresponds to conditions that would be evaluated in the decision tree to reach the leaf node.

4. The method of claim 1 , wherein the leaf node corresponds to a first decision, and wherein the decision tree determines whether or not a pixel in a digital image is a feature point, the first decision is that the pixel is not a feature point, the received attribute values of the query include values of a set of neighboring pixels of the pixel, and the early termination condition considers relative brightness and darkness of a selected subset of the set of neighboring pixels as compared to the pixel.

5. The method of claim 4 , wherein early termination conditions are evaluated in parallel in the pre-processing component for a plurality of pixels in the digital image.

6. A non-transitory computer-readable storage medium storing a program for execution by a digital signal processor (DSP) of a system on-a-chip (SoC), the program for accelerated decision tree execution, the program including instructions to, using single-instruction-multi-data (SIMD) instructions in an instruction set architecture (ISA) of the DSP:
receive at least some attribute values of a plurality of attribute values of a query for a decision tree in a pre-processing component;
evaluate, with a fixed program flow, the received attribute values in the pre-processing component according to an early termination condition and without querying the decision tree to determine whether or not the received attribute values fulfill the early termination condition, the early termination condition corresponding to multiple conditions that occur at different nodes in a condition path between a root node and a leaf node of the decision tree ; and
query the decision tree with the plurality of attribute values in response to determining that the received attribute values do not fulfill the early termination condition.

7. The non-transitory computer-readable storage medium of claim 6 , wherein the leaf node is a first leaf node, wherein the early termination condition is a first early termination condition corresponding to the first leaf node of the decision tree, and wherein the instructions further comprise instructions to evaluate the received attribute values according to a second early termination condition corresponding to a second leaf node of the decision tree to determine whether or not the received attribute values fulfill the second early termination condition.

8. The non-transitory computer-readable storage medium of claim 6 , wherein the early termination condition corresponds to conditions that would be evaluated in the decision tree to reach the leaf node.

9. The non-transitory computer-readable storage medium of claim 6 , wherein the leaf node corresponds to a first decision, and wherein the decision tree determines whether or not a pixel in a digital image is a feature point, the first decision is that the pixel is not a feature point, the received attribute values of the query include values of a set of neighboring pixels of the pixel, and the early termination condition considers relative brightness and darkness of a selected subset of the set of neighboring pixels as compared to the pixel.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the multiple conditions are evaluated in parallel in the pre-processing component for a plurality of pixels in the digital image.

11. A system-on-a-chip (SoC) configured for accelerated decision tree execution, the SoC comprising:
a digital signal processor (DSP); and
a non-transitory computer readable storage medium storing a program for execution by the DSP, the program including instructions to, using single-instruction-multi-data (SIMD) instructions in an instruction set architecture (ISA) of the DSP:
receive at least some attribute values of a plurality of attribute values of a query for a decision tree in a pre-processing component;
evaluate, with a fixed program flow, the received attribute values in the pre-processing component according to an early termination condition and without querying the decision tree to determine whether or not the received attribute values fulfill the early termination condition, the early termination condition corresponding to multiple conditions that occur at different nodes in a condition path between a root node and a leaf node of the decision tree; and
query the decision tree with the plurality of attribute values in response to determining that the received attribute values do not fulfill the early termination condition.

12. The SoC of claim 11 , wherein the leaf node is a first leaf node, wherein the early termination condition is a first early termination condition corresponding to the first leaf node of the decision tree, and wherein the instructions further comprise instructions to evaluate the received attribute values according to a second early termination condition corresponding to a second leaf node of the decision tree to determine whether or not the received attribute values fulfill the second early termination condition.

13. The SoC of claim 11 , wherein the early termination condition corresponds to conditions that would be evaluated in the decision tree to reach the leaf node.

14. The SoC of claim 11 , wherein the leaf node corresponds to a first decision, and wherein the decision tree is configured to determine whether or not a pixel in a digital image is a feature point, the first decision is that the pixel is not a feature point, the received attribute values of the query include values of a set of neighboring pixels of the pixel, and the early termination condition considers relative brightness and darkness of a selected subset of the set of neighboring pixels as compared to the pixel.

15. The SoC of claim 14 , wherein the multiple conditions are evaluated in parallel in the pre-processing component for a plurality of pixels in the digital image.

Assignees

• Texas Instruments Inc

Inventors

• Dedeoglu Goksel
• Barnum Peter Charles

Classifications

• G06N5/01 Primary

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

• G06N5/02 Primary

  Knowledge representation; Symbolic representation · CPC title

• G06N5/003

  Physics · mapped topic