Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms |
| |
Authors: | Dehne Dittrich and Hutchinson |
| |
Affiliation: | (1) A preliminary version of this paper was presented at the 9th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '97), Newport, RI, June 22—25, 1997. The research by the first author was partially supported by the Natural Sciences and Engineering Research Council of Canada. The second author's research was partially supported by DFG-Sonderforschungsbereich 376 ``Massive Parallelit?t' and by EU ESPRIT Long Term Research Project 20244 (ALCOM-IT), and was started while he was visiting Carleton University. The research by the third author was partially supported by Almerco, Inc. and by the Natural Sciences and Engineering Research Council of Canada., CA;(2) School of Computer Science, Carleton University, Ottawa, Ontario, Canada K1S 5B6. frank@dehne.net, http://www.dehne.net., CA;(3) Bosch Telecom GmbH, Backnang, Germany., DE;(4) Department of Systems and Computer Engineering, Carleton University, Ottawa, Ontario, Canada K1S 5B6., CA |
| |
Abstract: | Abstract. External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory
of the computer is only a small fraction of the problem size. Typical EM algorithms are specially crafted for the EM situation.
In the past, several attempts have been made to relate the large body of work on parallel algorithms to EM, but with limited
success. The combination of EM computing, on multiple disks, with multiprocessor parallelism has been posted as a challenge
by the ACM Working Group on Storage I/ O for Large-Scale Computing.
In this paper we provide a simulation technique which produces efficient parallel EM algorithms from efficient BSP-like parallel algorithms. The techniques obtained can accommodate one or multiple processors
on the EM target machine, each with one or more disks, and they also adapt to the disk blocking factor of the target machine.
When applied to existing BSP-like algorithms, our simulation technique produces improved parallel EM algorithms for a large number of problems. |
| |
Keywords: | , Parallel algorithms, Coarse grained parallel computing, External memory algorithms, Parallel I/ O, |
本文献已被 SpringerLink 等数据库收录! |
|