Title :
A quadtree communication structure for fast data searching and distribution
Author :
Lin, Woei ; Sheu, Tsang-Ling ; Das, Chita R.
Author_Institution :
Dept. of Electr. Eng., Pennsylvania State Univ., University Park, PA, USA
Abstract :
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
Keywords :
linear programming; parallel algorithms; parallel architectures; search problems; trees (mathematics); BBN Butterfly parallel processor; ascend procedure; contention-free data searching; data selection; descend procedure; intensive communication requirements; linear programming algorithm; mapping; parallel algorithms; post data distribution; primitive operations; quadtree communication structure; Broadcasting; Communication switching; Concurrent computing; Data engineering; Distributed computing; Hardware; Linear programming; Merging; Parallel algorithms; Switches;
Conference_Titel :
Computer Software and Applications Conference, 1988. COMPSAC 88. Proceedings., Twelfth International
Conference_Location :
Chicago, IL
Print_ISBN :
0-8186-0873-0
DOI :
10.1109/CMPSAC.1988.17193
