Speculative Parallel Evaluation Of Classification Trees On GPGPU Compute Engines
School of Computing and Digital Media, DePaul University, Chicago, IL, USA
arXiv:1111.1373v1 [cs.DC] (6 Nov 2011)
@article{2011arXiv1111.1373S,
author={Spencer}, J.},
title={Speculative Parallel Evaluation Of Classification Trees On GPGPU Compute Engines},
journal={ArXiv e-prints},
archivePrefix={arXiv},
eprint={1111.1373},
primaryClass={cs.DC},
keywords={Computer Science – Distributed, Parallel, and Cluster Computing, Computer Science – Computer Vision and Pattern Recognition},
year={2011},
month={nov},
adsurl={http://adsabs.harvard.edu/abs/2011arXiv1111.1373S},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
We examine the problem of optimizing classification tree evaluation for on-line and real-time applications by using GPUs. Looking at trees with continuous attributes often used in image segmentation, we first put the existing algorithms for serial and data-parallel evaluation on solid footings. We then introduce a speculative parallel algorithm designed for single instruction, multiple data (SIMD) architectures commonly found in GPUs. A theoretical analysis shows how the run times of data and speculative decompositions compare assuming independent processors. To compare the algorithms in the SIMD environment, we implement both on a CUDA 2.0 architecture machine and compare timings to a serial CPU implementation. Various optimizations and their effects are discussed, and results are given for all algorithms. Our specific tests show a speculative algorithm improves run time by 25% compared to a data decomposition.
November 8, 2011 by hgpu
