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.