The Experts below are selected from a list of 1041 Experts worldwide ranked by ideXlab platform
Hamid Sarbaziazad - One of the best experts on this subject based on the ideXlab platform.
-
an accurate performance model of Fully Adaptive Routing in wormhole switched two dimensional mesh multicomputers
Microprocessors and Microsystems, 2007Co-Authors: H Hasheminajafabadi, Hamid Sarbaziazad, P RajabzadehAbstract:Numerous analytical performance models have been proposed for deterministic wormhole-routed mesh networks while only a single model, to our best knowledge, has been suggested for Fully Adaptive wormhole Routing in mesh interconnection networks. This paper proposes a new and accurate analytical performance model for Fully Adaptive wormhole-routed mesh networks. Simulation results show that unlike the previously proposed model which is only accurate in light traffic loads, this model can be used for the performance analysis of almost all traffic loads.
-
analytical performance comparison of deterministic partially and Fully Adaptive Routing algorithms in binary n cubes
International Conference on Parallel and Distributed Systems, 2006Co-Authors: Ahmad Patooghy, Hamid SarbaziazadAbstract:In this paper, we study the effect of adaptivity of Routing algorithm on the overall performance in a hypercube multicomputer using wormhole switching. To this end, we use three accurate analytical models proposed for deterministic, Fully-Adaptive, and partially-Adaptive Routing algorithms in hypercube. Surprisingly, our analysis shows that under uniform traffic load, the partially-Adaptive Routing exhibits a lower performance compared to the deterministic Routing with less adaptivity.
-
analytic performance modeling of a Fully Adaptive Routing algorithm in the torus
International Symposium on Parallel and Distributed Processing and Applications, 2005Co-Authors: Mostafa Rezazad, Hamid SarbaziazadAbstract:Over the past decade, many Fully Adaptive Routing algorithms have been proposed in the literature, of which Duato’s Routing algorithm has gained considerable attention for analytical modeling. In this study we propose an analytical model to predict message latency in wormhole routed 2-dimensional torus networks in which Fully Adaptive Routing, based on Linder-Harden’s methodology [10], is employed. This methodology presents a framework in which Adaptive Routing algorithms can be developed for the k-ary n-cube network. Simulation experiments reveal that the latency results predicted by the proposed analytical model are in good agreement with those provided by simulation experiments.
-
performance evaluation of Fully Adaptive Routing under different workloads and constant node buffer size
International Conference on Parallel and Distributed Systems, 2005Co-Authors: Mostafa Rezazad, Hamid SarbaziazadAbstract:In this paper, the performance of some popular direct interconnection networks, namely the mesh, torus and hypercube, are studied with Adaptive wormhole Routing for different traffic patterns. We investigate the effect of the number of virtual channels and depth of their buffers on the performance of such strictly orthogonal topologies under uniform, hot-spot and matrix-transpose traffic patterns for generated messages, while the total buffer size associated to each physical channel is kept constant. In addition we analyze the effect of escape channel buffer length on the performance of a Fully Adaptive Routing algorithm. It is shown that the optimal number of virtual channels and buffer depth strongly depends on the assumed traffic pattern.
-
analytical modelling of wormhole routed k ary n cubes in the presence of matrix transpose traffic
Journal of Parallel and Distributed Computing, 2003Co-Authors: Hamid Sarbaziazad, M Ouldkhaoua, L M MackenzieAbstract:Several analytical models of Fully Adaptive Routing in wormhole-routed k-ary n-cubes under the uniform traffic pattern have recently been proposed in the literature. Although the uniform reference model has been widely used in the past, it is not always true in practice as there are many applications that exhibit non-uniform traffic patterns. There has not been so far any study that describes an analytical model of Fully Adaptive Routing under non-uniform traffic conditions. This paper describes a new analytical model of Fully Adaptive Routing in k-ary n-cubes in the presence of non-uniform traffic generated by matrix-transpose permutations, which is an important communication operation found in many matrix computation problems. Results obtained through simulation experiments confirm that the model predicts message latency with a high degree of accuracy under different working conditions.
M Ouldkhaoua - One of the best experts on this subject based on the ideXlab platform.
-
performance evaluation of Fully Adaptive Routing for the torus interconnect networks
International Conference on Computational Science, 2007Co-Authors: Farshad Safaei, Ahmad Khonsari, Mahmood Fathy, M OuldkhaouaAbstract:Adaptive Routing algorithms have been frequently suggested as a means of improving communication performance in parallel computer networks. These algorithms, unlike deterministic Routing, can utilize network state information to exploit the presence of multiple paths. Before such schemes can be successFully incorporated in networks, it is necessary to have a clear understanding of the factors which affect their performance potential. This paper proposes a new analytical model to obtain message latency in wormhole-switched 2-D torus interconnect networks. The analysis focuses on a Fully Adaptive Routing which has been shown to be one of the most effective in torus networks. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.
-
analytical modelling of wormhole routed k ary n cubes in the presence of matrix transpose traffic
Journal of Parallel and Distributed Computing, 2003Co-Authors: Hamid Sarbaziazad, M Ouldkhaoua, L M MackenzieAbstract:Several analytical models of Fully Adaptive Routing in wormhole-routed k-ary n-cubes under the uniform traffic pattern have recently been proposed in the literature. Although the uniform reference model has been widely used in the past, it is not always true in practice as there are many applications that exhibit non-uniform traffic patterns. There has not been so far any study that describes an analytical model of Fully Adaptive Routing under non-uniform traffic conditions. This paper describes a new analytical model of Fully Adaptive Routing in k-ary n-cubes in the presence of non-uniform traffic generated by matrix-transpose permutations, which is an important communication operation found in many matrix computation problems. Results obtained through simulation experiments confirm that the model predicts message latency with a high degree of accuracy under different working conditions.
-
disha a performance model of a true Fully Adaptive Routing algorithm in k ary n cubes
Modeling Analysis and Simulation On Computer and Telecommunication Systems, 2002Co-Authors: Ahmad Khonsari, A Farahani, M OuldkhaouaAbstract:A number of analytical models for predicting message latency in k-ary n-cubes have recently been reported in the literature. Most of these models, however, have been discussed for Adaptive Routing algorithms based on deadlock avoidance. Several research studies have empirically demonstrated that Routing algorithms based on deadlock recovery offer maximal adaptivity that can result in considerable improvement in network performance. Disha (see Anjan, K.V. and Pinkston, T.M., Proc. 22nd ACM/IEEE Int. Symp. on Computer Architecture, p.201-10, 1996; Pinkston, T.M., IEEE Trans. Computers, vol.7, no.48, p.649-69, 1999) is an example of a true Fully Adaptive Routing algorithm that uses minimal hardware to implement a simple and efficient progressive method to recover from potential deadlocks. The paper proposes a new analytical model of Disha in wormhole-routed k-ary n-cubes. Simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various networks sizes and under different traffic conditions.
-
performance modelling of a true Fully Adaptive Routing algorithm
International Conference on Parallel Processing, 2001Co-Authors: Ahmad Khonsari, Hamid Sarbaziazad, M OuldkhaouaAbstract:Several recent studies have revealed that deadlocks occur very infrequently in the network, especially when enough Routing freedom is provided. Routing algorithms based on deadlock avoidance reserve some virtual channels or Routing options to specifically deal with deadlocks, and as a result they are not utilized most of the time. Routing algorithms based on deadlock recovery allow messages to use all available virtual channels to cross the network, and efficiently handle infrequently occurred deadlocks. This paper describes a new analytical model of a true Fully Adaptive Routing (TFAR) algorithm with software-based deadlock recovery in k-ary n-cubes. Results obtained through simulation experiments confirm that the model predicts message latency with a good degree of accuracy under different working conditions.
-
a performance model of Adaptive Routing in k ary n cubes with matrix transpose traffic
International Conference on Parallel Processing, 2000Co-Authors: Hamid Sarbaziazad, L M Mackenzie, M OuldkhaouaAbstract:Several analytical models of Fully Adaptive Routing in wormhole-routed k-ary n-cubes under the uniform traffic pattern have recently been proposed in the literature. Although the uniform reference model has been widely used in the past, it is not always true in practice as there are many applications that exhibit non-uniform traffic patterns. There has not been so far any study that describes an analytical model of Fully Adaptive Routing under permutation traffic patterns. This paper describes a new analytical model of Fully Adaptive Routing in k-ary n-cubes in the presence of non-uniform traffic generated by matrix-transpose permutations, which is an important communication operation found in many matrix computation problems. Results obtained through simulation experiments confirm that the model predicts message latency with a reasonable degree of accuracy under different working conditions.
Jose Duato - One of the best experts on this subject based on the ideXlab platform.
-
A Routing methodology for achieving fault tolerance in direct networks
2015Co-Authors: Nils Agne Nordbotten, Jose Flich, Jose Duato, Tor Skeie, Ieee Computer Society, Antonio Robles, Olav LysneAbstract:Abstract—Massively parallel computing systems are being built with thousands of nodes. The interconnection network plays a key role for the performance of such systems. However, the high number of components significantly increases the probability of failure. Additionally, failures in the interconnection network may isolate a large fraction of the machine. It is therefore critical to provide an efficient fault-tolerant mechanism to keep the system running, even in the presence of faults. This paper presents a new fault-tolerant Routing methodology that does not degrade performance in the absence of faults and tolerates a reasonably large number of faults without disabling any healthy node. In order to avoid faults, for some source-destination pairs, packets are first sent to an intermediate node and then from this node to the destination node. Fully Adaptive Routing is used along both subpaths. The methodology assumes a static fault model and the use of a checkpoint/restart mechanism. However, there are scenarios where the faults cannot be avoided solely by using an intermediate node. Thus, we also provide some extensions to the methodology. Specifically, we propose disabling Adaptive Routing and/or using misRouting on a per-packet basis. We also propose the use of more than one intermediate node for some paths. The proposed fault-tolerant Routing methodology is extensively evaluated in terms of fault tolerance, complexity, and performance. Index Terms—Fault tolerance, direct networks, Adaptive Routing, virtual channels, bubble flow control.
-
achieving balanced buffer utilization with a proper co design of flow control and Routing algorithm
Networks-on-Chips, 2014Co-Authors: Miguel Gorgues, Dong Xiang, Jose Flich, Jose DuatoAbstract:Buffer resource minimization plays an important role to achieve power-efficient NoC designs. At the same time, advanced switching mechanisms like virtual cut-through (VCT) are appealing due to their inherited benefits (less network contention, higher throughput, and simpler broadcast implementations). Moreover, Adaptive Routing algorithms exploit the inherited bandwidth of the network providing higher throughput. In this paper, we propose a novel flow control mechanism, referred to as type-based flow control (TBFC), and a new Adaptive Routing algorithm for NoCs. First, the reduced flow control strategy allows using minimum buffer resources, while still allowing VCT. Then, on top of TBFC we implement the safe/unsafe Routing algorithm (SUR). This algorithm allows higher performance than previous proposals as it achieves a proper balanced utilization of input port buffers. Results show the same performance of Fully Adaptive Routing algorithms but using less resources. When resources are matched, SUR achieves up to 20% throughput improvement.
-
a Fully Adaptive fault tolerant Routing methodology based on intermediate nodes
Lecture Notes in Computer Science, 2004Co-Authors: Nils Agne Nordbotten, Jose Flich, A Robles, M E Gomez, Pedro Lopez, Tor Skeie, Olav Lysne, Jose DuatoAbstract:Massively parallel computing systems are being built with thousands of nodes. Because of the high number of components, it is critical to keep these systems running even in the presence of failures. Interconnection networks play a key-role in these systems, and this paper proposes a fault-tolerant Routing methodology for use in such networks. The methodology supports any minimal Routing function (including Fully Adaptive Routing), does not degrade performance in the absence of faults, does not disable any healthy node, and is easy to implement both in meshes and tori. In order to avoid network failures, the methodology uses a simple mechanism: for some source-destination pairs, packets are forwarded to the destination node through a set of intermediate nodes (without being ejected from the network). The methodology is shown to tolerate a large number of faults (e.g., five/nine faults when using two/three intermediate nodes in a 3D torus). Furthermore, the methodology offers a gracious performance degradation: in an 8 x 8 x 8 torus network with 14 faults the throughput is only decreased by 6.49%.
-
fc3d flow control based distributed deadlock detection mechanism for true Fully Adaptive Routing in wormhole networks
IEEE Transactions on Parallel and Distributed Systems, 2003Co-Authors: J M M Rubio, P Lopez, Jose DuatoAbstract:Two general approaches have been proposed for deadlock handling in wormhole networks. Traditionally, deadlock-avoidance strategies have been used. In this case, either Routing is restricted so that there are no cyclic dependencies between channels or cyclic dependencies between channels are allowed provided that there are some escape paths to avoid deadlock. More recently, deadlock recovery strategies have begun to gain acceptance. These strategies allow the use of unrestricted Fully Adaptive Routing, usually outperforming deadlock avoidance techniques. However, they require a deadlock detection mechanism and a deadlock recovery mechanism that is able to recover from deadlocks faster than they occur. In particular, progressive deadlock recovery techniques are very attractive because they allocate a few dedicated resources to quickly deliver deadlocked messages, instead of killing them. Unfortunately, distributed deadlock detection is usually based on crude time-outs, which detect many false deadlocks. As a consequence, messages detected as deadlocked may saturate the bandwidth offered by recovery resources, thus degrading performance. Additionally, the threshold required by the detection mechanism (the time-out) strongly depends on network load, which is not known in advance at the design stage. This limits the applicability of deadlock recovery on actual networks. We propose a novel distributed deadlock detection mechanism that uses only local information, detects all the deadlocks, considerably reduces the probability of false deadlock detection over previously proposed techniques, and is not significantly affected by variations in message length and/or message destination distribution.
-
supporting Fully Adaptive Routing in infiniband networks
International Parallel and Distributed Processing Symposium, 2003Co-Authors: J C Martinez, Jose Flich, P Lopez, A Robles, Jose DuatoAbstract:InfiniBand is a new standard for communication between processing nodes and I/O devices as well as for interprocessor communication. The InfiniBand Architecture (IBA) supports distributed Routing. However, Routing in IBA is deterministic because forwarding tables store a single output port per destination ID. This prevents packets from using alternative paths when the requested output port is busy. Despite the fact that alternative paths could be selected at the source node to reach the same destination node, this is not effective enough to improve network performance. However, using Adaptive Routing could help to circumvent the congested areas in the network, leading to an increment in performance. In this paper, we propose a simple strategy to implement forwarding tables for IBA switches that support Adaptive Routing while still maintaining compatibility with the IBA specs. Adaptive Routing can be enabled or disabled individually for each packet at the source node. Also, the proposed strategy enables the use in IBA of Fully Adaptive Routing algorithms without using additional network resources to improve network performance. Evaluation results show that extending IBA switch capabilities with Fully Adaptive Routing noticeably increases network performance. In particular, network throughput increases up to an average factor of 3.9.
Ahmad Khonsari - One of the best experts on this subject based on the ideXlab platform.
-
performance evaluation of Fully Adaptive Routing for the torus interconnect networks
International Conference on Computational Science, 2007Co-Authors: Farshad Safaei, Ahmad Khonsari, Mahmood Fathy, M OuldkhaouaAbstract:Adaptive Routing algorithms have been frequently suggested as a means of improving communication performance in parallel computer networks. These algorithms, unlike deterministic Routing, can utilize network state information to exploit the presence of multiple paths. Before such schemes can be successFully incorporated in networks, it is necessary to have a clear understanding of the factors which affect their performance potential. This paper proposes a new analytical model to obtain message latency in wormhole-switched 2-D torus interconnect networks. The analysis focuses on a Fully Adaptive Routing which has been shown to be one of the most effective in torus networks. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.
-
Analysis of true Fully Adaptive Routing with software-based deadlock recovery
Journal of Systems and Software, 2004Co-Authors: Ahmad Khonsari, Hamid Sarbazi-azadAbstract:Several analytical models of Fully Adaptive Routing (AR) in wormhole-routed networks have recently been reported in the literature. All these models, however, have been discussed for Routing algorithms with deadlock avoidance. Recent studies have revealed that deadlocks are quite rare in the network, especially when enough Routing freedom is provided. Thus the hardware resources, e.g. virtual channels, dedicated for deadlock avoidance are not utilised most of the time. This consideration has motivated researchers to introduce Fully Adaptive Routing algorithms with deadlock recovery. This paper describes a new analytical model of a true Fully AR algorithm with software-based deadlock recovery, proposed in Martinez et al. (Software-based deadlock recovery techniques for true Fully AR in wormhole networks, Proc. Int. Conf. Parallel Processing (ICPP'97), 1997, p. 182) for k-ary n-cubes. The proposed model uses the results from queueing systems with impatient customers to capture the effects of the timeout mechanism used in this Routing algorithm for deadlock detection. Results obtained through simulation experiments confirm that the model predicts message latency with a good degree of accuracy under different working conditions.
-
A Performance Model of True Fully Adaptive Routing in Hypercubes
High Performance Computing Systems and Applications, 2003Co-Authors: Ahmad Khonsari, Hamid Sarbazi-azadAbstract:Recent studies have revealed that deadlocks are generally infrequent in the network. Thus the hardware resources, e.g. virtual channels, dedicated for deadlock avoidance is not utilized most of the time. This consideration has motivated the development of novel Adaptive Routing algorithms with deadlock recovery. This paper describes a new analytical model to predict message latency in hyper-cubes with a true Fully Adaptive Routing algorithm with progressive deadlock recovery. One of the main features of the proposed model is the use of results from queuing systems with impatient customers to capture the effects of the timeout mechanism used in this Routing algorithm for deadlock detection. The validity of the model is demonstrated by comparing analytical Results with those obtained through simulation experiments.
-
disha a performance model of a true Fully Adaptive Routing algorithm in k ary n cubes
Modeling Analysis and Simulation On Computer and Telecommunication Systems, 2002Co-Authors: Ahmad Khonsari, A Farahani, M OuldkhaouaAbstract:A number of analytical models for predicting message latency in k-ary n-cubes have recently been reported in the literature. Most of these models, however, have been discussed for Adaptive Routing algorithms based on deadlock avoidance. Several research studies have empirically demonstrated that Routing algorithms based on deadlock recovery offer maximal adaptivity that can result in considerable improvement in network performance. Disha (see Anjan, K.V. and Pinkston, T.M., Proc. 22nd ACM/IEEE Int. Symp. on Computer Architecture, p.201-10, 1996; Pinkston, T.M., IEEE Trans. Computers, vol.7, no.48, p.649-69, 1999) is an example of a true Fully Adaptive Routing algorithm that uses minimal hardware to implement a simple and efficient progressive method to recover from potential deadlocks. The paper proposes a new analytical model of Disha in wormhole-routed k-ary n-cubes. Simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various networks sizes and under different traffic conditions.
-
performance modelling of a true Fully Adaptive Routing algorithm
International Conference on Parallel Processing, 2001Co-Authors: Ahmad Khonsari, Hamid Sarbaziazad, M OuldkhaouaAbstract:Several recent studies have revealed that deadlocks occur very infrequently in the network, especially when enough Routing freedom is provided. Routing algorithms based on deadlock avoidance reserve some virtual channels or Routing options to specifically deal with deadlocks, and as a result they are not utilized most of the time. Routing algorithms based on deadlock recovery allow messages to use all available virtual channels to cross the network, and efficiently handle infrequently occurred deadlocks. This paper describes a new analytical model of a true Fully Adaptive Routing (TFAR) algorithm with software-based deadlock recovery in k-ary n-cubes. Results obtained through simulation experiments confirm that the model predicts message latency with a good degree of accuracy under different working conditions.
Dong Xiang - One of the best experts on this subject based on the ideXlab platform.
-
achieving balanced buffer utilization with a proper co design of flow control and Routing algorithm
Networks-on-Chips, 2014Co-Authors: Miguel Gorgues, Dong Xiang, Jose Flich, Jose DuatoAbstract:Buffer resource minimization plays an important role to achieve power-efficient NoC designs. At the same time, advanced switching mechanisms like virtual cut-through (VCT) are appealing due to their inherited benefits (less network contention, higher throughput, and simpler broadcast implementations). Moreover, Adaptive Routing algorithms exploit the inherited bandwidth of the network providing higher throughput. In this paper, we propose a novel flow control mechanism, referred to as type-based flow control (TBFC), and a new Adaptive Routing algorithm for NoCs. First, the reduced flow control strategy allows using minimum buffer resources, while still allowing VCT. Then, on top of TBFC we implement the safe/unsafe Routing algorithm (SUR). This algorithm allows higher performance than previous proposals as it achieves a proper balanced utilization of input port buffers. Results show the same performance of Fully Adaptive Routing algorithms but using less resources. When resources are matched, SUR achieves up to 20% throughput improvement.
-
deadlock free Fully Adaptive Routing in irregular networks without virtual channels
Trust Security And Privacy In Computing And Communications, 2013Co-Authors: Dong XiangAbstract:This paper proposes a new flow control scheme in VCT-switched irregular networks. Based on the new scheme, a novel deadlock-free Fully Adaptive Routing algorithm is in-troduced. The algorithm does not need any virtual channel. It requires that each input port of a switch holds at least two 1-packet-sized buffers. The flow control scheme is proposed based on a baseline Routing scheme, where the downstream nodes check the number of safe buffers at the upstream nodes. The proposed Fully Adaptive Routing algorithm is on the basis of different baseline Routing schemes: updown, and multiple spanning tree based Routing schemes. Extensive simulation results validate the effectiveness of the proposed method as compared to well-known existing approaches.
-
deadlock free Fully Adaptive Routing in tori based on a new virtual network partitioning scheme
International Conference on Parallel Processing, 2008Co-Authors: Dong Xiang, Qi Wang, Y PanAbstract:A new, deadlock-free, Fully Adaptive Routing algorithm is proposed for worm hole-switched 3-dimensional tori with only two virtual channels. The deadlock avoidance technique is presented based on a new virtual network partitioning scheme. Unlike the previous virtual network partitioning schemes, the new method allows all virtual networks to share some common virtual channels. A new virtual channel assignment scheme is proposed for the 3-dimensional mesh subnetwork by using a channel overlap scheme. A combination of the virtual network partitioning scheme and the channel overlap scheme provides a deadlock-free Fully Adaptive Routing for 3-dimensional tori. Sufficient theoretical analysis on the proposed virtual network partitioning scheme is presented. Simulation results are presented to demonstrate the effectiveness of the proposed algorithm by comparing with several important previous methods.
-
deadlock free Fully Adaptive Routing in 2 dimensional tori based on new virtual network partitioning scheme
International Conference on Distributed Computing Systems, 2008Co-Authors: Dong Xiang, Y Pan, Qi Wang, Zhen ChenAbstract:A new deadlock-free Fully Adaptive Routing algorithm is proposed for 2-dimensional tori with only two virtual channels. The deadlock avoidance technique is presented based on a new virtual network partitioning scheme. Unlike the previous virtual network partitioning schemes, the new method allows all virtual networks to share some common virtual channels. Two virtual channels should be the lower bound for Fully Adaptive deadlock-free Routing in tori because the dimension order Routing for 2-dimensional tori also needs two virtual channels. The proposed virtual network partitioning scheme can avoid all potential deadlocks and provides Fully Adaptive Routing. Enough theoretical analyses on the proposed virtual network partitioning scheme are presented. Sufficient simulation results are presented to demonstrate the effectiveness of the proposed algorithm by comparing with the dimension-order Routing, two partially Adaptive Routing schemes, Duato's protocol and the load-balanced Routing algorithm GOAL.
-
deadlock free Adaptive Routing in meshes based on cost effective deadlock avoidance schemes
International Conference on Parallel Processing, 2007Co-Authors: Dong Xiang, Yueli Zhang, Y PanAbstract:A new deadlock-free Adaptive Routing algorithm is proposed for n-dimensional meshes with only two virtual channels, where a virtual channel can be shared by two consecutive planes without any cyclic channel dependency. A message is routed along a series of planes. The proposed planar Adaptive Routing algorithm is enhanced to a Fully Adaptive Routing version for 3-dimensional meshes using the idle virtual channels along the last dimension. Another deadlock avoidance technique is proposed for 3- dimensional meshes using a new virtual network partitioning scheme with only two virtual channels. Two virtual networks can share some common virtual channel based on the virtual network partitioning scheme. The deadlock-free Adaptive Routing scheme is then modified to a deadlock-free Adaptive fault-tolerant Routing scheme based on a planarly constructed MCC fault model. Sufficient simulation results are presented to demonstrate the effectiveness of the proposed algorithm.
