D. Hutchinson, Parallel Algorithms in External Memory (research summary), Carleton Journal of Computer Science, No. 3, 1999, pp. 49-56.

External memory (EM) algorithms are designed for computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. In this work we develop simulation techniques which produce efficient EM algorithms from efficient algorithms developed under BSP-like parallel computing models. Our techniques 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. We propose a more comprehensive cost model for EM algorithms, which considers the total costs incurred by the algorithm including computation, input/output (I/O) and communication costs. We obtain parallel external memory algorithms for a large number of problems including sorting, permutation, matrix transpose, several geometric and GIS problems including 3D convex hulls (2D Voronoi diagrams), and various graph problems. All of the algorithms obtained via simulation are analyzed with respect to the computation time, communication time and I/O time. Our results answer to a challenge posed by the ACM working group on storage I/O for large-scale computing.