Study Of Routing Algorithms On Honeycomb Networks

Interconnection networks provide an effective mechanism of transferring data between processors within a parallel computer. The performance and reliability of a parallel computing system depend heavily on the effectiveness of the built-in interconnection network. Before an interconnection network can be put in use, its properties should be fully understood. In particular, effective routing strategies must be proposed for this network. Due to lower node degree and lower cost of hardware implementation, honeycomb networks have been proposed as an attractive candidate for interconnection topology of parallel computers.This thesis aims at developing efficient routing algorithms for honeycomb networks. The main contributions of this thesis are presented below.First, based on the brick drawing of honeycomb meshes, two unicast routing algorithms are proposed, one of which is virtually a dimensional-order routing algorithm, combined with the virtual network technique; while the other bases itself on the turning model. It is also shown that both of these two algorithms are deadlock-free.Second, by combining a routing algorithm given previously and the one-to-all broadcast algorithm on linear array, a one-to-all broadcast strategy on honeycomb meshes is presented and is implemented. Through experimental comparison, it is found that, in terms of the communication overhead, our strategy outperforms some previous ones.Finally, we describe two all-to-all broadcasting algorithm on honeycomb tori. The first one yields a snake-like path, where each node carries out a personalized routing strategy. The second algorithm is designed by employing a Hamiltonian cycle existing in a honeycomb torus. As far as we know, it is the first time a broadcasting algorithm is advised for honeycomb torus networks.