Compression using efficient multicasting
Micah Adler, Tom Leighton · 2000
Many multiprocessor systems have the ability to broadcast and/or multicast information efficiently.However, this ability is often overlooked when designing algorithms for these systems.In this paper, we introduce a new compression technique that uses efficient multicasting to significantly reduce the amount of information communicated during parallel and distributed computation, resulting in significantly faster algorithms for Fast Fourier Transforms and sorting on shared memory parallel models with limited bandwidth.These algorithms demonstrate the importance of taking advantage of efficient multicasting.The compression technique uses a new, natural variant of Ramsey theory, which may be of independent interest. gle point-to-point message must on average traverse p/2edges, but a data item can be multicast to any subset *A portion of this research was performed while the first author