English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  Toward Better Computation Models for Modern Machines

Jurkiewicz, T. (2013). Toward Better Computation Models for Modern Machines. PhD Thesis, Universität des Saarlandes, Saarbrücken.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0018-4A9C-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0028-1241-9
Genre: Thesis

Files

show Files

Locators

show
hide
Locator:
http://scidok.sulb.uni-saarland.de/volltexte/2013/5540/ (Any fulltext)
Description:
-
OA-Status:
Green
Locator:
http://scidok.sulb.uni-saarland.de/doku/lic_ohne_pod.php?la=de (Copyright transfer agreement)
Description:
-
OA-Status:
Not specified

Creators

show
hide
 Creators:
Jurkiewicz, Tomasz1, 2, Author           
Mehlhorn, Kurt1, Advisor           
Meyer, Ulrich3, Referee           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551              
3External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and a virtual memory. We address the computational cost of the address translation in the virtual memory and difficulties in design of parallel algorithms on modern many-core machines. Starting point for our work on virtual memory is the observation that the analysis of some simple algorithms (random scan of an array, binary search, heapsort) in either the RAM model or the EM model (external memory model) does not correctly predict growth rates of actual running times. We propose the VAT model (virtual address translation) to account for the cost of address translations and analyze the algorithms mentioned above and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms. In the second part of the paper we present a case study of the design of an efficient 2D convex hull algorithm for GPUs. The algorithm is based on \emphthe ultimate planar convex hull algorithm} of Kirkpatrick and Seidel, and it has been referred to as \emph{the first successful implementation of the QuickHull algorithm on the GPU by Gao et al. in their 2012 paper on the 3D convex hull. Our motivation for work on modern many-core machines is the general belief of the engineering community that the theory does not produce applicable results, and that the theoretical researchers are not aware of the difficulties that arise while adapting algorithms for practical use. We concentrate on showing how the high degree of parallelism available on GPUs can be applied to problems that do not readily decompose into many independent tasks.

Details

show
hide
Language(s): eng - English
 Dates: 2013-10-3020132013
 Publication Status: Issued
 Pages: 94 p.
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: Jurkiewicz2013
URN: urn:nbn:de:bsz:291-scidok-55407
 Degree: PhD

Event

show

Legal Case

show

Project information

show

Source

show