Bulk Synchronous Parallel Algorithms for the External Memory Model |
| |
Authors: | Dehne Dittrich Hutchinson and Maheshwari |
| |
Affiliation: | (1) School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6 dehne@scs.carleton.ca, maheshwa@scs.carleton.ca, CA;(2) Bosch Telecom GmbH, UC-ON/ERS, Gerberstraße 33, 71522 Backnang, Germany, DE;(3) Department of Computer Science, Duke University, Box 90129, Durham, NC 27708-0129, USA hutchins@cs.duke.edu, US |
| |
Abstract: | Abstract. 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|