On a deadlock and performance analysis of ALBR and DAR algorithm on X-Torus topology by optimal utilization of Cross Links and minimal lookups

摘要

Interconnection networks play a major role in differentiating modern multiprocessor architectures. They can be categorized according to a number of criteria such as topology, routing strategy and switching technique. They are built up of switching elements; the topology is packaged such that it is cost effective along with its ability to achieve good performance. In this paper, we have studied an existing X-Torus topology (Gu et al. in ICCSA, LNCS, vol. 3984, pp. 149-157, 2006) which is an enhancement of a Torus network by adding Cross Links, and hence contributes to shorter diameter, shorter average distance and larger bisection bandwidth. Furthermore, we proposed the Adaptive Load Balanced Routing (ALBR) algorithm and Dual Adaptive Routing (DAR) algorithm. The ALBR algorithm can manage traffic during congestion by sensing the same through Channel Queues. The strength of the Algorithm lies in the fact that using backtracking, the number of lookups to reach destination through Cross Link decreases, thereby making optimal use of them. The Performance aspects for both Odd and Even forms of X-Torus are tested on Network Simulator-2 (NS-2) using Perl and Gawk for analyzing text of trace files generated during simulation. The DAR reduces the number of lookups by optimal utilization of Cross Links but also helps to curb the problem of packet congestion, which could be a major issue in X-Torus due to the presence of Cross Links. In order to improve its rooting performance we have provided a new approach to handle the problem of deadlock detection and recovery mechanism in the case of X-Torus. The proposed progressive deadlock recovery mechanism takes advantage of the high path diversity of X-Torus. We also present a low cost and simple mechanism for deadlock detection as against many conservative mechanisms.