JP5863426B2 - Information processing apparatus, information processing method, and program - Google Patents

Description

  The present invention relates to an information processing apparatus, an information processing method, and a program.

  A decision tree is also called a decision tree, and is a technique often used for machine learning and recently object recognition in addition to decision making in the field of decision theory. Executing a decision tree is simple. Starting from a single node called the root node, the input is judged and one of a plurality of child nodes is selected according to the result. By repeating this recursively, it finally reaches a node having no child nodes.

A node that does not have a child node is called a leaf node, and is associated with a decision tree result (here called a class). Here, a node having child nodes is referred to as a decision node. The determination node determines which of a plurality of child nodes is selected based on the input data. Thus, the decision tree is a method of selecting one of a plurality of class candidates based on input data. Assuming that all decision nodes have two child nodes and all child nodes have only one parent node, it is possible to classify into a maximum of 2 ⁿ classes with ⁿ judgments. It has been used as a classifier.

  On the other hand, a GPU (Graphics Processing Unit) is used as an execution environment of a computer. What uses GPU for calculations other than graphics drawing is called GPGPU (General Purpose computing on GPU). In GPGPU, the speed is usually improved by simultaneously moving several tens to over 1000 computational cores (parallel processing).

  However, many computation algorithms have a dependency on the execution of computation, and it is difficult to perform parallel processing. The same applies to the execution of decision trees. As a result, the number of calculation cores that do not participate in the calculation (referred to as idle cores) increases, and there is a problem that the processing speed cannot be increased. For example, Patent Document 1 discloses a configuration that performs decision tree processing at high speed.

Japanese Patent Laid-Open No. 11-184858

NVIDIA CUDATM NVIDIA CUDA C Programming Guide Version 3.2 11/9/2010 Whitepaper NVIDIA's Next Generation CUDATM Compute Architecture: FermiTM The OpenCL Specification Version: 1.1 Document Revision: 36 Programming Guide AMD Accelerated Parallel Processing OpenCLTM December 2010

  However, the technique of Patent Document 1 is a device that devises the memory arrangement of data, and when executing a decision tree, a result is obtained by repeating the determination while one thread walks over the determination nodes. In a situation where there are many computation cores (threads), it is important how many computation cores can participate in the computation at the same time and reduce idle cores. The conventional technique related to execution of a decision tree has a problem that the number of idle cores cannot be reduced, and the execution speed cannot be increased by parallelization.

  The present invention provides an information processing technique that can reduce idle cores and increase the processing speed.

The information processing apparatus according to one aspect of the present invention includes a root node that selected in accordance with the input data one of the child nodes of the plurality of child nodes accepts input data, one of the child nodes of the plurality of child nodes An information processing apparatus that processes the input data by a decision tree in which at least one of a determination node selected according to input data and a leaf node having no child nodes is hierarchically connected,
Setting means for setting identification information in binary notation to identify each of the root node, decision node, and leaf node;
A determination unit that performs a determination process on input data by each determination node, and outputs the identification information of a child node selected by the determination process as a selection result of each determination node;
A calculation means for performing a bitwise OR operation on the identification information of the child node obtained as a selection result of the determination node included in the same hierarchy;
A bitwise logical product operation is performed for all the hierarchies on the result of the bitwise logical OR operation, a leaf node having a binary notation obtained by the bitwise logical product operation as identification information is searched, and the search is performed. Determining means for determining a class associated with the designated leaf node as an execution result of a decision tree for the input data;
It is characterized by providing.

  According to the present invention, idle cores can be reduced and the processing speed can be increased.

The figure explaining the information processing method concerning a 1st embodiment using a decision tree. (A) The figure explaining the flow of the information processing method which concerns on 1st Embodiment using a decision tree, (b) The figure which shows the function structure of an information processing apparatus. The figure which illustrates the total result of step S4 of FIG. The figure which illustrates the decision tree applicable with the information processing method concerning an embodiment. FIG. 4 is a diagram illustrating thread assignment in the information processing method according to the embodiment.

(First embodiment)
An information processing method and a method for executing an information processing apparatus decision tree according to the first embodiment of the present invention using a decision tree will be described with reference to FIG. A child node is selected from the root node 11. The root node 11 receives input data, and determines which of the child nodes 121 and 122 should be selected as a determination result for the input data. A node that selects one of a plurality of child nodes is called a decision node. In FIG. 1, the decision nodes are indicated by thin circles. What the determination node determines based on the decision tree differs depending on the decision tree. For example, there are a plurality of values (variables) in the input data, and these values are determined by comparing them with predetermined values. A child node that matches the value obtained from the variable is selected based on the result of the comparison.

  In FIG. 1, a thick arrow coming out from the decision node indicates the selection result. In the root node 11, the child node 121 is selected from the child nodes 121 and 122. Similarly, the decision node 121 selects the child node 124 among the child nodes 123 and 124. In the decision node 124, the child node 130 is selected. In the decision node 130, the child node 141 is selected, but the node 141 is a leaf node having no child node. No selection is made at the leaf node, and the associated class is the result. In FIG. 1, the class “9” is the execution result of the decision tree.

  FIG. 2A is a diagram illustrating the flow of the information processing method according to the first embodiment using a decision tree, and FIG. 2B is a diagram illustrating the functional configuration of the information processing apparatus 20. The information processing apparatus 20 processes the input data using the decision tree. The decision tree includes a root node and at least one of a decision node that selects one of a plurality of child nodes according to input data and a leaf node that does not have a child node in a lower hierarchy in a hierarchical manner. It is connected.

  The setting unit 21 sets identification information in binary notation to identify each of the root node, the determination node, and the leaf node. The determination unit 22 performs a determination process on the input data by each determination node, and outputs identification information of the child node selected by the determination process as a selection result of each determination node. The calculation unit 23 performs a bitwise OR operation on the identification information of the child node obtained as a selection result of the determination nodes included in the same hierarchy.

  The determination unit 24 performs a bitwise logical product operation on the result of the bitwise logical sum operation, and searches for a leaf node having, as identification information, a binary notation obtained by the bitwise logical product operation. Then, the determination unit 24 determines the class associated with the searched leaf node as the execution result of the decision tree for the input data. The storage unit 25 holds input data for executing processing of each determination node in a single thread environment in which a thread executing a program is one thread or in a multi-thread environment in which a plurality of threads perform processing in parallel simultaneously. To do.

  The control unit 26 executes processing of input data by a decision tree on one work group (Open CL) on GPGPU (General-purpose computing on graphics processing units) that provides a multi-thread environment. The control unit 26 controls the execution timing of each thread in order to synchronize the processing of one thread and the processing of another thread in the multithread environment.

  The control unit 26 (FIG. 2B) of the information processing apparatus 20 controls the overall processing of the processing in FIG. In the node ID assignment step S1, node identification information (node ID) is set in each node of the decision tree to identify each node constituting the decision tree for internal processing. The setting unit 21 first assigns a node ID from a leaf node. The setting unit 21 appropriately assigns integer values so as not to overlap. In the case of FIG. 1, since the class of leaf nodes is 16 integer values of n (n is an integer) = 0-15, the value of the class associated with the leaf node is n = 0-15. Class associations are not specifically related to this value. The setting unit 21 finally sets identification information of n leaf nodes by n-bit binary notation. In FIG. 1, the node ID is written in the vicinity of each node as a 16-digit binary number based on the associated class.

  After giving the node ID of the leaf node, the setting unit 21 gives the node ID of the determination node. The node IDs of the decision nodes are assigned the node IDs of the leaf nodes of all the child nodes by bitwise OR (bitwise OR operation). For example, in the case of the determination node 127, there are two child nodes, which are “10000000 00000000” and “01000000 00000000”, respectively, in binary notation. When these OR (logical sum operations) are taken, “11000000 00000000” is obtained. This is the node ID. Similarly, node IDs are assigned to all judgment nodes. If the node IDs of leaf nodes are determined in this way, the node IDs of all judgment nodes can be automatically determined. The node ID of the root node can be obtained by performing a logical OR operation on the node IDs of the nodes (judgment node, leaf node) connected to the root node.

  Next, input data preparation step S2 is performed. The present invention can be executed on a computer (information processing apparatus 20) equipped with a multi-core CPU of Intel or AMD, a GPGPU of NVIDIA or AMD, but is not particularly limited thereto. The present invention can also be executed in a single thread environment in which there is one thread that is the execution subject of the program. The present invention can also be executed in a multi-thread environment in which a plurality of threads perform processing simultaneously and in parallel, and the processing speed can be increased by simultaneous and parallel processing.

  Each thread needs input data as a basis for making a determination in the subsequent determination step S3. In the input data preparation step S2, the input data necessary for this determination is set in a storage area accessible by each thread. Since the determination contents are different for each determination node, the input data required for each determination node is also different.

  In an SMP (Symmetric Multiprocessing) architecture represented by a multi-core CPU of Intel or AMD, a shared memory is used as an input data storage location for determination. Therefore, it is typically not necessary to set different input data for each thread in a data storage location dedicated to the thread. Therefore, this step can be omitted. On the other hand, in the case of a GPGPU of NVIDIA or AMD, a high-speed technique is used in which a value is set in a register that can be exclusively accessed by each thread.

  Subsequently, in the determination step S3, a predetermined determination process is performed on the input data set in the storage area in each determination node, and any one of a plurality of child nodes is selected and returned as a result. Is. The determination process is, for example, comparing a value of a certain variable included in input data with a predetermined value and selecting which child node is selected depending on whether or not they match. More specific examples include selecting one of two child nodes depending on whether or not the variable “weather” in the input data has a predetermined value “sunny”. It is done.

  In this way, the determination process may be performed by simply using the value of the variable, but there may be a determination that requires more complicated calculation. For example, the input image is given a luminance image and the coordinates of two points on this image, and an average value of pixel values in a 3 × 3 range centered on each coordinate is compared. Is used to determine the child node to select. In either case, one child node is selected, and the node ID of the selected child node is set as the selection result in the determination step S3.

  The process of determination step S3 can be executed in parallel. In a multi-thread environment, one thread is responsible for processing one or more decision nodes. In the determination step S3, the determination result of each determination node is held by many threads in a distributed manner. In the next OR step S4 and AND step S5, the results held by each thread are totaled, and the execution result of the decision tree is calculated.

  In the OR step S4, the calculation unit 23 adds up the results of the determination nodes in the same hierarchy. The “hierarchy” is the number of branches that pass from the root node 11 to the decision node. A branch is indicated by an arrow connecting a parent node and a child node in the decision tree. In FIG. 1, the root node 11 is the 0th hierarchy, the decision nodes 121 and 122 are the 1st hierarchy, the decision nodes 123, 124, 125, and 126 are the 2nd hierarchy, and the other decision nodes are the 3rd hierarchy. In the OR step S4, a bit-wise OR operation (bit-wise OR operation) is performed on the selection result (identification information of the child node in bit display) of the same hierarchy. FIG. 3 shows the total result of the OR step S4 in the case of FIG. The total results are summarized in binary notation for each hierarchy.

  Finally, in the AND step S5, the determination unit 24 performs a bitwise AND (bitwise AND operation) on the results of aggregation for the same layer in the OR step S4. In the case of FIG. 1, it is only necessary to perform a bitwise AND (bitwise AND) operation on all the aggregation results shown in FIG. As a result, “00000010 00000000” is obtained in binary notation. The class associated with the leaf node having this node ID is the execution result of the decision tree. In the case of FIG. 1, the leaf node 141 corresponds to this, and the resulting class is “9”.

In the case of FIG. 1, the single-thread processing of the conventional technique requires four determination processes, and it takes 4T _D + T _{α to} execute the decision tree. Here T _D is the time for one determination, T _alpha is the time for other processing branch or the like.

On the other hand, in the determination step S3 according to the embodiment of the present invention, when the determination process in each determination node is performed simultaneously in different threads, it takes time of T _D + T _T + T _β . T _T is the time required for data transfer between threads for aggregation, and T _β is the time required for other processing. When the determination process is sufficiently complicated and T _D >> _{T T} , T _α , T _β , the present embodiment can execute the decision tree execution process about four times faster than the conventional technique.

  In the case of FIG. 1, 15 threads are used, but this is a surplus computing resource that was not used as an idle core in the conventional technique. As described above, according to the embodiment of the present invention, it is possible to execute the decision tree at a higher speed than in the conventional technique by actively using the idle core.

(Second Embodiment)
Although the decision tree of the first embodiment described above is a balanced binary tree, the gist of the present invention is not limited to this example, and a decision tree structure as shown in FIG. Child nodes of the root node 41 include a determination node 421 and a leaf node 431, and child nodes of the determination node 421 include a determination node 423, a determination node 422, and a leaf node 432. In addition, the determination node 423 includes leaf nodes 435 and 434, and the determination node 422 includes leaf nodes 433 and 434.

The decision node 421 has three child nodes 422, 423, and 432, and the number of child nodes may be any number. Although the child nodes of the decision nodes 422 and 423 are the common node 434, the number of parent nodes may be any number. In this way, the decision tree structure is not limited as long as it is a decision tree having a single root node and no loop path. In the case of FIG. 4, if T _D >> _{T T} , T _α , T _β , the conventional technique takes about T _{D to} 3T _D depending on the input data. In this embodiment a T _D, it is possible to achieve three times the speed at the maximum as compared with the conventional techniques.

(Third embodiment)
In the case of T _D >> _{T T} , T _α , T _β , the decision tree can be executed at a high speed by simultaneously executing the decision step S3 for one decision node in one thread. By actively using n threads that were not used as idle cores in the conventional technique as computation resources, it is possible to execute a decision tree at a higher speed than in the conventional technique. When a balanced binary decision tree with 2 _n decision nodes is executed, the speed can be increased by about n times compared to the conventional technique.

  In the processing flow of the first embodiment, after the parallel execution process of the determination step S3, the selection results of the respective determination nodes are aggregated by the OR step S4 and the AND step S5. Since this aggregation process involves communication between threads, it may not be possible to sufficiently speed up the execution of the decision tree compared to the parallel execution process. If determination at each determination node in determination step S3 is time-consuming processing, speeding up by parallel processing is more effective than rate control by inter-thread communication. Conversely, if the determination at each decision node is simple and does not take much time, the rate-limiting effect due to inter-thread communication is greater than the speed-up due to parallelization.

Regarding T _D and T _T , if T _D >> _{T T} , speeding up by parallelizing processing step S3 to the maximum is effective. If this is not the case, it is effective to reduce T _T even if some parallelization is sacrificed.

  For this purpose, in the determination step S3, determination processing in a plurality of determination nodes is performed by one thread. Thereby, it is possible to reduce the influence of rate-limiting in inter-thread communication instead of lowering the processing parallelism.

  The number of decision nodes to perform the decision processing in one thread is a trade-off and greatly depends on the execution environment. Therefore, in many cases, it is experimentally obtained by repeating trials. Omitted because it is out of range.

In order to effectively reduce inter-thread communication, the processing at the decision node in the same hierarchy performed in the OR step S4 is performed with one thread, or the processing of totaling the results between the layers performed in the AND step S5 is performed with one thread. Good to do. However, the inter-thread communication in the AND step S5 involves only the nodes of the number of hierarchies in the determination step, and the effect is limited, and the flexibility when experimentally changing the parallelism is low. Therefore, the processing of the decision node in the same hierarchy is performed with one thread. FIG. 5 exemplifies which thread performs processing of which determination node in FIG. In Example 1 of FIG. 5, one thread or two determination nodes are assigned to one thread. In example 2, 3 to 4 decision nodes are assigned to one thread. In the example 2, the determination process of the determination node is assigned to the thread of the thread number 1 across the hierarchies, but the person in charge is assigned to perform the determination process of different hierarchies after performing the processing in the same hierarchy. Yes. In the case of Example 1, if the time required for communication between threads is half that of the previous embodiment, the time required for execution of the decision tree is approximately 2T _D + T _T / 2. When T _T = 2.5T _D , the speed of the embodiment is about 14% higher than that of the conventional technique, but a speed of about 23% can be achieved.

  In the example of FIG. 5, the number of threads used is 8, and the utilization rate of idle cores is reduced compared to the case where the number of threads used is 15. However, the speedup that actively uses idle cores is higher than the conventional technique. It becomes possible.

(Fourth embodiment)
In FIG. 1, the number of leaf nodes having no child nodes in the lower hierarchy is 16, and in FIG. 4, the number of leaf nodes is 5. In this embodiment, the node ID requires 1 bit per leaf node. Therefore, the size of the node ID is 16 bits in the case of FIG. 1 and 5 bits in the case of FIG.

  In the OR step S4 and the AND step S5, bit operation is used. Therefore, by setting the node ID to an integer value having a unit size that the information processing apparatus 20 can read and write at a time, the information processing apparatus 20 can perform processing efficiently. Currently, a multi-core CPU such as Intel or AMD, or NGDIA or AMD GPGPU can read / write data of a size of 8, 16, 32 bits at a time.

  Therefore, the decision tree of FIG. 1 is an integer having a 16-bit length and the decision tree of FIG. 4 is an 8-bit length. Depending on the information processing device 20, data of a plurality of sizes can be read and written at one time, but there may be a size that is most efficient among them. Assuming that the size is 32 bits, it is possible to efficiently read and write data by setting an integer of 32 bits in both cases of FIGS.

(Fifth embodiment)
CUDA, which is an NVIDIA general-purpose computing on graphics processing units (GPGPU) development environment, and OpenCL (Open Computing Language), which AMD adopts as a GPGPU development language, have a thread hierarchy that reflects the structure of the GPU. Since details are described in each document (Non-Patent Documents 1 to 4), they are omitted here, but a thread that is an execution subject is called a thread in CUDA and a work item in OpenCL. A group of these is called a block (CUDA) and a work group (OpenCL). In the following, the term OpenCL will be used. In the case of CUDA, the same explanation is obtained by appropriately replacing the reading. A work group is a collection of work items, and work items in the work group are logically simultaneously processed in parallel. Further, work items in the same work group can perform high-speed communication between work items via a local memory (shared memory in CUDA).

  It is not guaranteed that different workgroups are executed at the same time. Therefore, communication between work items across workgroups cannot be performed in principle.

  Therefore, by executing one decision tree on one work group, the execution result can be calculated by parallel processing while performing communication between work items.

(Sixth embodiment)
Considering the correspondence with a specific GPU (Graphics Processing Unit), there are more detailed rules. Basically, work items (threads) in the same work group can execute a program at high speed by executing instructions at the same position in the same program. Therefore, all the work items (threads) are wait-synchronized between the steps so that the work item corresponding to the determination node that has finished processing does not execute the next process in advance. The control unit 26 (FIG. 2B) controls the execution timing of each thread in order to synchronize the process of one work item (thread) and the process of another work item (thread). This makes it possible to synchronize the execution timing of each step, and at least at the beginning of each step, all work items can execute instructions at the same position in the same program.

(Other embodiments)
The present invention can also be realized by executing the following processing. That is, software (program) that realizes the functions of the above-described embodiments is supplied to a system or apparatus via a network or various storage media, and a computer (or CPU, MPU, or the like) of the system or apparatus reads the program. It is a process to be executed.

Claims (11)

Accepts input data have a root node that selected in accordance with the input data one of the child nodes of the plurality of child nodes, the decision node and child node selects according to the input data to one of the child nodes of the plurality of child nodes An information processing apparatus that processes the input data by a decision tree in which at least one of the non-leaf nodes is hierarchically connected,
Setting means for setting identification information in binary notation to identify each of the root node, decision node, and leaf node;
A determination unit that performs a determination process on input data by each determination node, and outputs the identification information of a child node selected by the determination process as a selection result of each determination node;
A calculation means for performing a bitwise OR operation on the identification information of the child node obtained as a selection result of the determination node included in the same hierarchy;
A bitwise logical product operation is performed for all the hierarchies on the result of the bitwise logical OR operation, a leaf node having a binary notation obtained by the bitwise logical product operation as identification information is searched, and the search is performed. Determining means for determining a class associated with the designated leaf node as an execution result of a decision tree for the input data;
An information processing apparatus comprising: The setting means sets identification information of n leaf nodes by n-bit binary notation,
The information processing apparatus according to claim 1, wherein a binary notation obtained by bitwise OR operation with respect to identification information of a leaf node included as a child node is set as identification information of the determination node. In order to execute the processing of each decision node in a single thread environment in which the thread that executes the program is one thread or in a multi-thread environment in which a plurality of threads perform processing simultaneously, the input to the storage area that can be accessed by each thread The information processing apparatus according to claim 1, further comprising storage means for holding data.   The information processing apparatus according to claim 3, wherein the determination unit executes a determination process in each determination node in the multithread environment.   The information processing apparatus according to claim 4, wherein the determination unit assigns one thread to one determination node.   The information processing apparatus according to claim 4, wherein the determination unit assigns one thread to a plurality of determination nodes included in the same hierarchy.   The information processing apparatus according to claim 4, wherein the determination unit assigns one thread to a plurality of determination nodes and a root node included in the same hierarchy.   8. The information processing according to claim 3, further comprising synchronization means for controlling execution timing of each thread in order to synchronize processing of one thread and processing of another thread. apparatus. Processing the input data by the decision tree is performed by the on GPGPU to provide a multi-threaded environment (General-purpose computing on graphics processing units), on one workgroup in Open CL (Open Computing Language) The information processing apparatus according to claim 3.   The program for functioning a computer as each means of the information processing apparatus of any one of Claims 1 thru | or 9. Accepts input data have a root node that selected in accordance with the input data one of the child nodes of the plurality of child nodes, the decision node and child node selects according to the input data to one of the child nodes of the plurality of child nodes An information processing method in an information processing apparatus that processes the input data by a decision tree in which at least one of the leaf nodes is hierarchically connected,
A setting step in which the setting means of the information processing apparatus sets identification information by binary notation in order to identify each of the root node, determination node, and leaf node;
A determination step in which a determination unit of the information processing apparatus performs a determination process on input data by each determination node, and outputs the identification information of the child node selected by the determination process as a selection result of each determination node; ,
A calculation step in which the calculation means of the information processing apparatus performs a bitwise OR operation on the identification information of the child node obtained as a selection result of the determination node included in the same hierarchy;
The determination unit of the information processing apparatus performs a bitwise logical product operation on all the hierarchies on the result of the bitwise logical sum operation, and uses a binary notation obtained by the bitwise logical product operation as identification information. A determination step of searching for a leaf node having, and determining a class associated with the searched leaf node as an execution result of a decision tree for the input data;
An information processing method characterized by comprising:

Images