Study Of Routing Algorithms On Locally Twisted Cube

Interconnection networks provide an effective mechanism of exchanging data between processors in multicomputer systems. The network topology determines how well the processors can work cooperatively. In an interconnection network, the communication is realized by performing various routing algorithms, which determine a path along which a packet or message is transferred to its destination. Wormhole switching technique is widely adopted in modern multicomputer systems, which may incur deadlock more frequently. Indeed, some packets may hold some resource while requesting others, which may lead to the result that some packets are not able to arrive at their destination. How to avoid the occurrence of deadlock is an important consideration while developing routing algorithms in wormhole networks.Locally twisted cube is a newly introduced interconnection network for parallel computing. As a variant of hypercube, the diameter of this network is only about half of the diameter of hypercube. The work of this thesis is focused on locally twisted cube.In this thesis, the router models and switching techniques are explained, accompanied with the introduction of a general deadlock-free theory. Then some popular unicast and multicast routing algorithms in hypercube and mesh are reviewed. After presenting the definition of the locally twisted cube, the following contributions are made:In the context of unicast routing, four routing algorithms are proposed. First, we illustrate that there exists deadlock in the minimal routing algorithm.Thus, a minimal routing algorithm based on the turn model is presented, which leads to a deadlock-free algorithm when incorporating the virtual network dividing technique. By exploring the property that one locally twisted cube consists of one subcube and one 2-twisted subcube, we apply the existing adaptive routing strategies for the subcubes to induce an adaptive routing scheme for locally twisted cube. Second, an improved algorithm is presented, which is more adaptive and deadlock-free. The using rate of channels is improved in this algorithm. Third, a non-minimal algorithm without virtual channel is given in this paper, which is also adaptive and deadlock-free without virtual channels. Finally, a minimal adaptive routing algorithm based on path is presented, which is also deadlock-free. In this algorithm, we determine the rout path by assigning a unique label to each node of a locally twisted cube.