Liu, Xiaolin (2003) Multicasting algorithms for mesh and torus networks. Masters thesis, Concordia University.
Multicasting is an important interprocessor communication pattern existing in various parallel application algorithms. Mesh-connected topology is one of the most thoroughly investigated network topologies for parallel processing. The torus network has been proposed for metropolitan area networks (MAN). It can be divided into several mesh problems. Time and traffic are the main parameters considered in the multicasting communication environment. It is NP-complete in general to find an optimal multicasting algorithm which minimizes both time and traffic. This thesis proposes two kind of multicasting algorithms for torus/mesh networks, the VH algorithm with a time complexity of O(kD), and the DIST algorithm with a time complexity of O(kDN), where k is the number of destination nodes. D is the maximum distance, and N is the total number of nodes in the network. The VH algorithm guarantee that every destination node can receive the message from the source in a minimum multicasting time. The DIST algorithm generates less traffic compared to the VH algorithm, but at the price of an increased multicasting time.
|Divisions:||Concordia University > Faculty of Engineering and Computer Science > Computer Science and Software Engineering|
|Item Type:||Thesis (Masters)|
|Pagination:||xi, 103 leaves : ill. ; 29 cm.|
|Degree Name:||Theses (M.Comp.Sc.)|
|Program:||Computer Science and Software Engineering|
|Thesis Supervisor(s):||Harutyunyan, Hovhannes A|
|Deposited By:||Concordia University Libraries|
|Deposited On:||27 Aug 2009 13:24|
|Last Modified:||08 Dec 2010 10:24|
Repository Staff Only: item control page