Abstract:
F. Dehne, W. Dittrich, D. Hutchinson,
A. Maheshwari, “Bulk synchronous parallel algorithms for the external
memory model”, Theory of Computing Systems, Vol. 35 Issue 6, 2002,
pp. 567-598.
Blockwise access to data is a central theme in the design of
efficient external memory (EM) algorithms.Asecond important issue, when
more than one disk is present, is fully parallel disk I/O. In this paper
we present a simple, deterministic simulation technique which transforms
certain Bulk Synchronous Parallel (BSP) algorithms into efficient parallel EM
algorithms. It optimizes blockwise data access
and parallel disk I/O and,
at the same time, utilizes multiple processors connected via a
communication network or shared memory. We obtain new improved parallel EM
algorithms for a large number of problems including sorting, permutation, matrix
transpose, several geometric and
show that certain parallel
algorithms known for the BSP model can be used to obtain EM algorithms that
meet well known I/O complexity lower bounds for various problems,
including sorting.