Bulk synchronous parallel algorithms for the external memory model
Blockwise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second 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 GIS problems including three-dimensional convex hulls (two-dimensional Voronoi diagrams), and various graph problems. We 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.
|Journal||Theory of Computing Systems|
Dehne, F, Dittrich, W. (Wolfgang), Hutchinson, D. (David), & Maheshwari, A. (2002). Bulk synchronous parallel algorithms for the external memory model. Theory of Computing Systems, 35(6), 567–597. doi:10.1007/s00224-002-1066-2