A quadtree communication structure for fast data searching and distribution

Presents a quadtree communication structure and two associated procedures for efficient, contention-free data searching and distribution on the BBN Butterfly parallel processor and its family. The proposed quadtree 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 `ascend´ and `descend´ procedures incur no link conflicts in the Butterfly network. A concrete example of mapping the linear programming algorithm is given to show the effectiveness of the proposed quadtree communication structure