Associative broadcast communication in massively parallel SIMD machines: a practical approach

In massively parallel SIMD machines, communication bottlenecks have been a major problem due to the limitation of available topologies. Especially they are not well suited to broadcast-type communications. Some suggested approaches are not practical, even though they are asymptotically fast, because they incur large minimum latency. In this paper, a simple and practical linear broadcast-type communication algorithm which is based on associative computing and does not use interconnection networks at all, is presented