Premium
Parallel construction of classification trees on a GPU
Author(s) -
Strnad D.,
Nerat A.
Publication year - 2015
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.3660
Subject(s) - computer science , cuda , parallel computing , boosting (machine learning) , tree (set theory) , graphics processing unit , parallelism (grammar) , binary tree , architecture , general purpose computing on graphics processing units , graphics , task (project management) , artificial intelligence , algorithm , computer graphics (images) , mathematics , art , mathematical analysis , management , economics , visual arts
Summary Algorithms for constructing tree‐based classifiers are aimed at building an optimal set of rules implicitly described by some dataset of training samples. As the number of samples and/or attributes in the dataset increases, the required construction time becomes the limiting factor for interactive or even functional use. The problem is emphasized if tree derivation is part of an iterative optimization method, such as boosting. Attempts to parallelize the construction of classification trees have therefore been presented in the past. This paper describes a parallel method for binary classification tree construction implemented on a graphics processing unit (GPU) using compute unified device architecture (CUDA). By employing node‐level, attribute‐level, and split‐level parallelism, the task parallel and data parallel sections of tree induction are mapped to the architecture of a modern GPU. The GPU‐based solution is compared with the sequential and multi‐threaded CPU versions on public access datasets, and it is shown that an order of magnitude acceleration can be achieved on this data‐intensive task using inexpensive commodity hardware. The influence of dataset characteristics on the efficiency of parallel implementation is also analyzed. Copyright © 2015 John Wiley & Sons, Ltd.