Physical Sciences and Mathematics Commons^™

Communication-Efficient And Memory-Bounded External Redistribution, Jang Sun Lee, Sanjay Ranka, Ravi V. Shankar

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents communication-efficient algorithms for the external data redistribution problem. Deterministic lower bounds and upper bounds are presented for the number of I/O operations, communication time and the memory requirements of external redistribution. Our algorithms differ from most other algorithms presented for out-of-core applications in that it is optimal (within a small constant factor) not only in the number of I/O operations, but also in the time taken for communication. A coarse-grained MIMD architecture with I/O subsystems attached to each processor is assumed, but the results are expected to be applicable over a wider variety of architectures.