Communication-efficient algorithms, External data redistribution
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.
Lee, Jang Sun; Ranka, Sanjay; and Shankar, Ravi V., "Communication-Efficient and Memory-Bounded External Redistribution" (1995). L.C. Smith College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. Paper 43.
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.