Fast data selection and broadcast on the Butterfly Network.

A quadtree communication structure is presented, along with two associated procedures for efficient, contention-free data selection and broadcast on the BBN Butterfly parallel processor and its family. The proposed structure suggests a general approach to mapping a class of parallel algorithms with intensive communication requirements for performing two primitive operations: selecting data from many different sources and distributing data from a single source. While performing these two operations through the quadtree structure, the two procedures, ascend and descend, incur no link conflicts in the Butterfly network. By properly merging messages and efficiently replicating data, they can complete required communications in O(log₄ M) parallel steps, where M is the size of a Butterfly parallel processor. Contraction and stretch of the quadtree communication structure while retaining the conflict-free property, is considered. The contracted and stretched tree structures allow the adaptive balance of computations and communication requirements for various algorithms with different computation/communication ratios.