6198

Speculative Parallel Evaluation Of Classification Trees On GPGPU Compute Engines

Jason Spencer
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}

}

Download Download (PDF)   View View   Source Source   

858

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: