Unpublished, Draft, To Appear
@UnPublished
Unveröffentlicht, Entwurf


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









Author, Editor

Author(s):

Jurkiewicz, Tomasz
Danilewski, Piotr

dblp
dblp



BibTeX citekey*:

JurkiewiczDanilewski2011

Title, Booktitle

Title*:

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

Vol, No, pp., Year

Month:

November

Year:

2011

Language:

English

Pages:

20

Abstract, Links, ©

Note:


LaTeX Abstract:

In recent years CUDA became 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, and admits easy reuse of theory of parallel and multicore algorithms when 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 \cite{RandomizedQCH}, \cite{SimpleCH}, and \cite{UltimateCH}. Our implementation of the Convex Hull algorithm on CUDA exercise this approach in practice, and prove its appropriateness.

\keywords{convex hull, multicore algorithms, parallel algorithms, CUDA, GPGPU}
%In this paper we concentrate mostly on practical aspects of the problem, more detailed theoretical analysis and follow up research will appear in the extended version.
%please refer to the companion paper \cite{???}.

Categories / Keywords:

convex hull, multicore algorithms, parallel algorithms, CUDA, MSIMD, SIMD, MIMD

HyperLinks / References / URLs:

http://www.mpi-inf.mpg.de/~tojot/

Personal Comments:


File Upload:




Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

MPG Subsubunit:

Foundations and Discrete Mathematics

External Affiliations:

Universität des Saarlandes

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
@UNPUBLISHED{JurkiewiczDanilewski2011,
AUTHOR = {Jurkiewicz, Tomasz and Danilewski, Piotr},
TITLE = {Efficient Quicksort and 2D Convex Hull for CUDA, and MSIMD as a Realistic Model of Massively Parallel Computations.},
YEAR = {2011},
PAGES = {20},
MONTH = {November},
}


Entry last modified by Tomasz Jurkiewicz, 03/08/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Tomasz Jurkiewicz
Created
12/09/2010 03:04:39 PM
Revision
1.
0.


Editor
Tomasz Jurkiewicz
Tomasz Jurkiewicz


Edit Date
03/08/2011 05:05:39 PM
12/09/2010 03:04:39 PM


Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section