Study Of Routing Algorithms On Honeycomb Mesh

It is well known that the performance and reliability of a parallel computing system depend heavily on the effectiveness of the interconnection network built in the system, and the topology of an interconnection network can be represented as a graph. Up to date, interconnection network has become a hot spot in parallel processing community, and tens kinds of graphs have been proposed as candidates for the underlying topology of an interconnection networks.An ideal interconnection network should have a fixed-degree topology. Honeycomb meshes are a class of fixed-degree graphs. As compared with a 2-dimensional mesh, a honeycomb mesh has one-less node degree and hence lower implementation cost. As a result, honeycomb meshes are regarded as promising structures of interconnection networks.These networks were widely studied and applied into real parallel systems. In the interconnection network, the effective of the communication among nodes is dependent to the routing strategy. It is known that the effectiveness of an interconnection network is measured by the efficiency of the group of message transmission strategies developed for this network. This dissertation aims at developing efficient routing algorithms for honeycomb networks.First, the deadlock-free unicast routing mechanism on honeycomb networks is investigated. We describe two deadlock-free wormhole routing algorithms. The first algorithm is based on the assumption that a channel cannot be divided into sub-channels. The second algorithm, named as Double-XY Route, takes the virtual channel technique. It is proved that Double-XY Route is a shortest path routing strategy, and simulation results show the utility of Double-XY Route.Second, a fault-tolerant wormhole routing algorithm for honeycomb networks, named as HFT-Route, is presented. This algorithm is designed by combining four virtual channels and the dimension-order routing strategy. Theoretical analysis and simulation experiment indicate that the proposed algorithm is deadlock-free and can route a packet to the destination in the presence of convex faults.Finally, a multi-routing algorithm on honeycomb networks is proposed by using the multicast-tree technique, and an example is given to illustrate the execution of this algorithm.