External Memory Computation Using Parallel Algorithms

External Memory Computation Using Parallel Algorithms

The RAM memory of a computer allows fine grained, random access to data without

significant performance impact. Many algorithms have been designed under this implicit

assumption. When problems grow far beyond the size of internal memory, however, the

assumption may no longer be valid, as virtual memory systems cannot deliver good

performance in the face of chaotic access patterns to a huge extended, disk-based

memory.

In contrast, external memory (EM) algorithms do not assume that every access to

memory is cheap. Loosely speaking, they ensure that accesses are clustered, i.e. localized,

and so most accesses do not incur the cost of an input/output operation. Deriving such

"smart'' algorithms is not easy, in general, and much research has been done in the past

few years on this issue. Identifying general techniques for creating EM algorithms is a

natural objective of these efforts.

In previous work [1,2,3] we have identified a correspondence between coarse grained

parallel algorithms and EM algorithms which allows a large number of problems to be

solved efficiently even when the problem size far exceeds the available internal memory.

Our techniques generate EM algorithms for machines with one or more processors, each

with one or more disks. Our theoretical results indicate that these new algorithms are

provably optimal by various criteria. Our cost models are based on principles of the Bulk

Synchronous Parallel (BSP) model of parallel computation due to Valiant and the Parallel

Disk Model (PDM) due to Vitter and Shriver, and address a challenge issued by the ACM

Working Group for I/O (ACM Computing Surveys 1996).

It remains to determine the usefulness of our techniques in practice. We have performed

some preliminary implementation experiments [4] with promising results. However, true

practicality remains an outstanding issue, and experimentation to confirm it is ongoing.

For more information, please send email to David Hutchinson hutchins@sce.carleton.ca

References (Other publications are here)

1. F. Dehne, W. Dittrich, D. Hutchinson, "Efficient external memory algorithms by

simulating coarse-grained parallel algorithms", Algorithmica, Vol. 36, 2003, pp. 97-122.

2. 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.

3. D. Hutchinson, “Parallel Algorithms in External Memory”, PhD Thesis, School of

Computer Science, Carleton University, May 1999.

4. K. Yogaratnam, " ", Fourth Year Project, School of Computer Science, Carleton

University, 1998.