----------------------------------------------
|          TECHNICAL REPORT ECE-95-6           |
|                October 1995                  |
| Dept. of Electrical and Computer Engineering |
|           University of Victoria             |
 ----------------------------------------------

TITLE:   Leaf Communications in Complete Trees

AUTHORS: V. V. Dimakopoulos and N. J. Dimopoulos 

NOTE:    Expanded and revised version of TR-94-7
	 Submitted for publication

ABSTRACT

One  of  the  crucial  issues  associated   with  loosely-coupled
multiprocessors based on interconnection  networks is information
dissemination. A number of regular communication patterns seem to
cover a large portion of information  dissemination  requirements
in practice:   broadcasting,   scattering/gathering,    multinode
broadcasting and total exchange. In this work  we  consider  tree
networks where the processing nodes are confined to the leaves of
the tree. This type of hierarchical topology is also the basis of
fat tree networks. We present  and  analyze  algorithms and their
timing requirements  for the aforementioned  problems  under  two
models of communication capabilities.


KEYWORDS: collective communications, complete trees, fat trees, 
	  interconnection networks, packet-switched networks.