6149

Efficient Quicksort and 2D Convex Hull for CUDA, and MSIMD as a Realistic Model of Massively Parallel Computations

Tomasz Jurkiewicz, Piotr Danilewski
Max Planck Institute for Informatics, partially supported by IMPECS
2011

@article{jurkiewicz2011efficient,

   title={Efficient Quicksort and 2D Convex Hull for CUDA, and MSIMD as a Realistic Model of Massively Parallel Computations},

   author={Jurkiewicz, T. and Danilewski, P.},

   year={2011}

}

Download Download (PDF)   View View   Source Source   

1182

views

In recent years CUDA has become a major architecture for multithreaded computations. Unfortunately, its potential is not yet being commonly utilized because many fundamental problems have no practical solutions for such machines. Our goal is to establish a hybrid multicore/parallel theoretical model that represents well architectures like NVIDIA CUDA, Intel Larabee, and OpenCL as well as admits easy reuse of the theory of parallel and multicore algorithms whenever applicable. We call our model MSIMD, from multiple-SIMD. We apply our model to design Quicksort for MSIMD, and an output sensitive MSIMD 2D Convex Hull algorithm based on [Wenger, 1997], [Bhattacharya and Sen, 1997], and [Kirkpatrick and Seidel, 1986]. Our implementation of the Convex Hull algorithm on CUDA exercises this approach in practice and proves its appropriateness.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: