Abstract
In this thesis, we proposed an efficient deadlock-free tree-based routing algorithm, the DOWN/UP routing, for irregular wormhole-routed networks based on the turn model. In a tree-based routing algorithm, hot spots around the root of a spanning tree and the uneven traffic distribution are the two main facts degrade the performance of the routing algorithm. To solve the hot spot and the uneven traffic distribution problems, in the DOWN/UP routing, it tries to push the traffic downward to the leaves of a spanning tree as much as possible and remove prohibited turn pairs with opposite directions in each node, respectively. Given an irregular network topology, the construction of the DOWN/UP routing consists of three phases. In the first phase, a communication graph based on the coordinated tree of the given topology is constructed. In a communication graph, tree links and cross links are considered as different links. This will make the prohibited turn selection more precisely. In this phase, we also proposed a better way to construct the coordinated tree such that a better throughput can be obtained when a routing algorithm is performed. In the second phase, based on the maximal direction graph and the turn model, we construct a maximal acyclic direction dependency graph to obtain the set of prohibited turns. In this phase, we careful select the set of prohibited turns such that the traffic can be pushed downward to leaves of a spanning tree as much as possible and a more even distribution of traffic load can be achieved. In the third phase, we apply the set of prohibited turns to each node in the communication graph and release unnecessary prohibited turns for each node. Then the DOWN/UP routing algorithm for the give irregular network can be derived based on the prohibited turns of each node. To evaluate the performance of DOWN/UP routing, the simulation is conducted. We have implemented the DOWN/UP routing along with the L-turn routing on the IRFlexSim0.5 simulator. Irregular networks that contain 128 switches with 4-port and 8-port configurations are simulated. The simulation results show that the proposed routing algorithm outperforms the L-turn routing for all test samples in terms of the degree of hot spots, the traffic load distribution, and throughput.