Fast data selection and broadcast on the Butterfly Network.

Woei Lin, Tsang Ling Sheu, Chita R. Das, Tse Yun Feng, Chuan Lin Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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(log4 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.

Original languageEnglish (US)
Title of host publicationProc Workshop Future Trends Distrib Comput Syst 1990s
PublisherPubl by IEEE
Number of pages8
ISBN (Print)0818608978
StatePublished - Dec 1 1988

Publication series

NameProc Workshop Future Trends Distrib Comput Syst 1990s

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Fast data selection and broadcast on the Butterfly Network.'. Together they form a unique fingerprint.

Cite this