Experiments with a Parallel External Memory System?

Abstract. The theory of bulk-synchronous parallel computing has pro-duced a large number of attractive algorithms, which are provably op-timal in some sense, but typically require that the aggregate random access memory (RAM) of the processors be sufficient to hold the entire data set of the parallel problem instance. In this work we investigate the performance of parallel algorithms for extremely large problem instances relative to the available RAM. We describe a system, Parallel Exter-nal Memory System (PEMS), which allows existing parallel programs designed for a large number of processors without disks to be adapted easily to smaller, realistic numbers of processors, each with its own disk system. Our experiments with PEMS show that this approach is practi-cal and promising and the run times scale predictable with the number of processors and with the problem size.