Document Type
Article
Date
1995
Keywords
Communication-efficient algorithms, External data redistribution
Language
English
Disciplines
Computer Sciences
Description/Abstract
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.
Recommended Citation
Lee, Jang Sun; Ranka, Sanjay; and Shankar, Ravi V., "Communication-Efficient and Memory-Bounded External Redistribution" (1995). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 43.
https://surface.syr.edu/lcsmith_other/43
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
