Informatics Report Series


Report   

EDI-INF-RR-0398


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm
Authors: Marcelo Cintra ; Diego R. Llanos ; Belen Palop
Date:May 2004
Publication Title:Procs of CGA'04
Page Nos:188-197
Abstract:
Finding the fastest algorithm to solve a problem is one of the main issues in Computational Geometry. Focusing only on worst case analysis or asymptotic computations leads to the development of complex data structures or hard to implement algorithms. Randomized algorithms appear in this scenario as a very useful tool in order to obtain easier implementations within a good expected time bound. However, parallel implementations of these algorithms are hard to develop and require an in-depth understanding of the language, the compiler and the underlying parallel computer architecture. In this paper we show how we can use speculative parallelization techniques to execute in parallel iterative algorithms such as randomized incremental constructions. In this paper we focus on the convex hull problem, and show that, using our speculative parallelization engine, the sequential algorithm can be automatically executed in parallel, obtaining speedups with as little as four processors, and reaching 5.15x speedup with 28 processors.
Links To Paper
1st Link
Bibtex format
@Misc{EDI-INF-RR-0398,
author = { Marcelo Cintra and Diego R. Llanos and Belen Palop },
title = {Speculative Parallelization of a Randomized Incremental Convex Hull Algorithm},
year = 2004,
month = {May},
pages = {188-197},
url = {http://homepages.inf.ed.ac.uk/mc/Publications/cga04.pdf},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh