Abstract

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.