The Experts below are selected from a list of 18960 Experts worldwide ranked by ideXlab platform
José Duato - One of the best experts on this subject based on the ideXlab platform.
-
Adaptive Routing for N-Dimensional Twin Torus
IEEE Transactions on Computers, 2016Co-Authors: Francisco J. Andujar, Juan A. Villar, José L. Sánchez, Francisco J. Alfaro, José DuatoAbstract:Torus topology is one of the most common topologies used in the current largest supercomputers due to its properties related to cost, implementation or scalability. N-dimensional twin torus (nDT) topology has been proposed to increase the number of dimensions of the torus networks when port-limited low cost expansion cards are available. These topologies have been characterized and evaluated considering only deterministic Routing. Adaptive Routing algorithms improve communication performance exploiting the path diversity of the torus networks. Due to the particular properties of the nDT torus, designing an Adaptive Routing algorithm presents a challenge. The peculiarities of the internal link, which interconnects the two communication cards of an nDT torus node, complicate the design of the Adaptive Routing. In this paper, we study these peculiarities and propose an Adaptive Routing for nDT tori. Moreover, we show that, by using cards with the same number of ports, we can improve the network performance by building an Adaptive nDT torus instead of an Adaptive nD torus.
-
deterministic versus Adaptive Routing in fat trees
International Parallel and Distributed Processing Symposium, 2007Co-Authors: Crispin Gomez, Pedro López, F Gilabert, M E Gomez, José DuatoAbstract:Clusters of PCs have become very popular to build high performance computers. These machines use commodity PCs linked by a high speed interconnect. Routing is one of the most important design issues of interconnection networks. Adaptive Routing usually better balances network traffic, thus allowing the network to obtain a higher throughput. However, Adaptive Routing introduces out-of-order packet delivery, which is unacceptable for some applications. Concerning topology, most of the commercially available interconnects are based on fat-tree. Fat-trees offer a rich connectivity among nodes, making possible to obtain paths between all source-destination pairs that do not share any link. We exploit this idea to propose a deterministic Routing algorithm for fat-trees, comparing it with Adaptive Routing in several workloads. The results show that deterministic Routing can achieve a similar, and in some scenarios higher, level of performance than Adaptive Routing, while providing in-order packet delivery.
-
IPDPS - Deterministic versus Adaptive Routing in Fat-Trees
2007 IEEE International Parallel and Distributed Processing Symposium, 2007Co-Authors: Crispin Gomez, Pedro López, F Gilabert, M E Gomez, José DuatoAbstract:Clusters of PCs have become very popular to build high performance computers. These machines use commodity PCs linked by a high speed interconnect. Routing is one of the most important design issues of interconnection networks. Adaptive Routing usually better balances network traffic, thus allowing the network to obtain a higher throughput. However, Adaptive Routing introduces out-of-order packet delivery, which is unacceptable for some applications. Concerning topology, most of the commercially available interconnects are based on fat-tree. Fat-trees offer a rich connectivity among nodes, making possible to obtain paths between all source-destination pairs that do not share any link. We exploit this idea to propose a deterministic Routing algorithm for fat-trees, comparing it with Adaptive Routing in several workloads. The results show that deterministic Routing can achieve a similar, and in some scenarios higher, level of performance than Adaptive Routing, while providing in-order packet delivery.
-
Supporting Adaptive Routing in IBA switches
2003Co-Authors: J. C. Martínez, Jose Flich, Antonio Viedma Robles, Pedro López, José DuatoAbstract:InfiniBand is a new standard for communication between processing nodes and I/O devices as well as for inter-processor communication. The InfiniBand Architecture (IBA) supports distributed deterministic Routing 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 supports Adaptive Routing while still maintaining compatibility with the IBA specs. Adaptive Routing can be individually enabled or disabled for each packet at the source node. The proposed strategy enables the use in IBA of any Adaptive Routing algorithm with an acyclic channel dependence graph. In this paper, we have taken advantage of the partial adaptivity provided by the well-known up*/down* Routing algorithm. Evaluation results show that extending IBA switch capabilities with Adaptive Routing may noticeably increase network performance. In particular, network throughput improvement can be, on average, as high as 66%.
-
PDP - Supporting Adaptive Routing in InfiniBand networks
Eleventh Euromicro Conference on Parallel Distributed and Network-Based Processing 2003. Proceedings., 2003Co-Authors: J. C. Martínez, Jose Flich, Antonio Viedma Robles, Pedro López, José 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 deterministic Routing 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 supports Adaptive Routing while still maintaining compatibility with the IBA specifications. Adaptive Routing can be individually enabled or disabled for each packet at the source node. The proposed strategy enables the use in IBA of any Adaptive Routing algorithm with an acyclic channel dependence graph. In this paper, we have taken advantage of the partial adaptivity provided by the well-known up*/down* Routing algorithm. Evaluation results show that extending IBA switch capabilities with Adaptive Routing may noticeably increase network performance. In particular network throughput improvement can be, on average, as high as 46%.
J H Kim - One of the best experts on this subject based on the ideXlab platform.
-
planar Adaptive Routing low cost Adaptive networks for multiprocessors
Journal of the ACM, 1995Co-Authors: Andrew A Chien, J H KimAbstract:Network throughput can be increased by allowing multipath, Adaptive Routing. Adaptive Routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of Adaptive Routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k -ary n -cubes require an exponential number of virtual channels. We describe a family of deadlock-free Routing algorithms, called planar-Adaptive Routing algorithms, that require only a constant number of virtual channels, independent of networks size and dimension. Planar-Adaptive Routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each Routing step. In the fault-free case, planar-Adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-Adaptive router can be extended with misRouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar-Adaptive networks can simultaneously support both in-order and Adaptive, out-of-order packet delivery. Planar-Adaptive Routing is of practical significance. It provides the simplest known support for deadlock-free Adaptive Routing in k -ary n -cubes of more than two dimensions (with k >2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-Adaptive routers is amenable to efficient implementation. Simulation studies show that planar-Adaptive routers can increase the robustness of network throughput for nonuniform communication patterns. Planar-Adaptive routers outperform deterministic routers with equal hardware resources. Further, adding virtual lanes to planar-Adaptive routers increases this advantage. Comparisons with fully Adaptive routers show that planar-Adaptive routers, limited Adaptive routers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual lanes. Planar-Adaptive routers are a special case of limited adaptivity routers. We define a class of Adaptive routers with f degrees of Routing freedom. This class, termed f-flat Adaptive routers , allows a direct cost-performance tradeoff between implementation cost (speed and silicon area) and Routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with the Routing freedom. However, the rate of growth is a much larger constant for high-dimensional networks. All of the properties proven for planar-Adaptive routers, such as deadlock and livelock freedom, also apply to f -flat Adaptive routers.
-
planar Adaptive Routing low cost Adaptive networks for multiprocessors
International Symposium on Computer Architecture, 1992Co-Authors: Andrew A Chien, J H KimAbstract:Network throughput can be increased by allowing multipath, Adaptive Routing. Adaptive Routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of Adaptive Routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels, independent of network size and dimension. Planar Adaptive Routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each Routing step. In the fault-free case, planar-Adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-Adaptive router can be extended with misRouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar Adaptive networks can simultaneously support both in-order and Adaptive, out-of-order packet delivery. Planar-Adaptive Routing is of practical significance. It provides the simplest known support for deadlock-free Adaptive Routing in k-ary n-cubes of more than two dimensions (with k > 2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-Adaptive routers is amenable to efficient implementation.
-
ISCA - Planar-Adaptive Routing: low-cost Adaptive networks for multiprocessors
Proceedings of the 19th annual international symposium on Computer architecture - ISCA '92, 1992Co-Authors: Andrew A Chien, J H KimAbstract:Network throughput can be increased by allowing multipath, Adaptive Routing. Adaptive Routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of Adaptive Routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels, independent of network size and dimension. Planar Adaptive Routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each Routing step. In the fault-free case, planar-Adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-Adaptive router can be extended with misRouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar Adaptive networks can simultaneously support both in-order and Adaptive, out-of-order packet delivery. Planar-Adaptive Routing is of practical significance. It provides the simplest known support for deadlock-free Adaptive Routing in k-ary n-cubes of more than two dimensions (with k > 2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-Adaptive routers is amenable to efficient implementation.
-
SPDP - An evaluation of planar-Adaptive Routing (PAR)
[1992] Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Processing, 1Co-Authors: J H Kim, Andrew A ChienAbstract:Network performance can be improved by allowing Adaptive Routing, but doing so introduces new possibilities of deadlock which can overwhelm the flexibility advantages. Planar-Adaptive Routing resolves this tension by limiting Adaptive Routing to a series of two-dimensional planes, reducing hardware requirements for deadlock prevention. The authors explore the performance of planar-Adaptive routers for two, three, and four-dimensional networks. Under nonuniform traffic loads, the planar-Adaptive router significantly outperforms the dimension-order router, while giving comparable performance under uniform loads. With equal resources, the planar-Adaptive router provides performance superior to fully Adaptive routers because it requires less resources for deadlock prevention, freeing resources to increase the number of virtual lanes. >
Andrew A Chien - One of the best experts on this subject based on the ideXlab platform.
-
planar Adaptive Routing low cost Adaptive networks for multiprocessors
Journal of the ACM, 1995Co-Authors: Andrew A Chien, J H KimAbstract:Network throughput can be increased by allowing multipath, Adaptive Routing. Adaptive Routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of Adaptive Routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k -ary n -cubes require an exponential number of virtual channels. We describe a family of deadlock-free Routing algorithms, called planar-Adaptive Routing algorithms, that require only a constant number of virtual channels, independent of networks size and dimension. Planar-Adaptive Routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each Routing step. In the fault-free case, planar-Adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-Adaptive router can be extended with misRouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar-Adaptive networks can simultaneously support both in-order and Adaptive, out-of-order packet delivery. Planar-Adaptive Routing is of practical significance. It provides the simplest known support for deadlock-free Adaptive Routing in k -ary n -cubes of more than two dimensions (with k >2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-Adaptive routers is amenable to efficient implementation. Simulation studies show that planar-Adaptive routers can increase the robustness of network throughput for nonuniform communication patterns. Planar-Adaptive routers outperform deterministic routers with equal hardware resources. Further, adding virtual lanes to planar-Adaptive routers increases this advantage. Comparisons with fully Adaptive routers show that planar-Adaptive routers, limited Adaptive routers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual lanes. Planar-Adaptive routers are a special case of limited adaptivity routers. We define a class of Adaptive routers with f degrees of Routing freedom. This class, termed f-flat Adaptive routers , allows a direct cost-performance tradeoff between implementation cost (speed and silicon area) and Routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with the Routing freedom. However, the rate of growth is a much larger constant for high-dimensional networks. All of the properties proven for planar-Adaptive routers, such as deadlock and livelock freedom, also apply to f -flat Adaptive routers.
-
planar Adaptive Routing low cost Adaptive networks for multiprocessors
International Symposium on Computer Architecture, 1992Co-Authors: Andrew A Chien, J H KimAbstract:Network throughput can be increased by allowing multipath, Adaptive Routing. Adaptive Routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of Adaptive Routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels, independent of network size and dimension. Planar Adaptive Routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each Routing step. In the fault-free case, planar-Adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-Adaptive router can be extended with misRouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar Adaptive networks can simultaneously support both in-order and Adaptive, out-of-order packet delivery. Planar-Adaptive Routing is of practical significance. It provides the simplest known support for deadlock-free Adaptive Routing in k-ary n-cubes of more than two dimensions (with k > 2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-Adaptive routers is amenable to efficient implementation.
-
ISCA - Planar-Adaptive Routing: low-cost Adaptive networks for multiprocessors
Proceedings of the 19th annual international symposium on Computer architecture - ISCA '92, 1992Co-Authors: Andrew A Chien, J H KimAbstract:Network throughput can be increased by allowing multipath, Adaptive Routing. Adaptive Routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of Adaptive Routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in k-ary n-cubes require an exponential number of virtual channels, independent of network size and dimension. Planar Adaptive Routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each Routing step. In the fault-free case, planar-Adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-Adaptive router can be extended with misRouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar Adaptive networks can simultaneously support both in-order and Adaptive, out-of-order packet delivery. Planar-Adaptive Routing is of practical significance. It provides the simplest known support for deadlock-free Adaptive Routing in k-ary n-cubes of more than two dimensions (with k > 2). Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-Adaptive routers is amenable to efficient implementation.
-
SPDP - An evaluation of planar-Adaptive Routing (PAR)
[1992] Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Processing, 1Co-Authors: J H Kim, Andrew A ChienAbstract:Network performance can be improved by allowing Adaptive Routing, but doing so introduces new possibilities of deadlock which can overwhelm the flexibility advantages. Planar-Adaptive Routing resolves this tension by limiting Adaptive Routing to a series of two-dimensional planes, reducing hardware requirements for deadlock prevention. The authors explore the performance of planar-Adaptive routers for two, three, and four-dimensional networks. Under nonuniform traffic loads, the planar-Adaptive router significantly outperforms the dimension-order router, while giving comparable performance under uniform loads. With equal resources, the planar-Adaptive router provides performance superior to fully Adaptive routers because it requires less resources for deadlock prevention, freeing resources to increase the number of virtual lanes. >
S. Z. Shaikh - One of the best experts on this subject based on the ideXlab platform.
-
A simple Adaptive Routing scheme for congestion control in ShuffleNet multihop lightwave networks
IEEE Journal on Selected Areas in Communications, 1991Co-Authors: Mark J. Karol, S. Z. ShaikhAbstract:The authors describe a simple Adaptive Routing scheme for datagram (connectionless) and virtual circuit (connection-oriented) transmission that relieves congestion resulting from nonuniform traffic patterns and network failures. The authors describe a fixed-Routing algorithm for dedicated channel ShuffleNets. Based on the fixed Routing algorithm, an Adaptive Routing scheme for datagram transmission is presented followed by performance results for uniform and nonuniform traffic patterns and fault tolerance. The Adaptive Routing of datagrams uses only the local queue size information available at the network interface units (NIUs) and redistributes the load as congestion develops. Since datagrams are individually routed through the network, they may not arrive at their destination in the order they were generated and may need to be resequenced. The authors compute an upper estimate on the resequencing buffer size for stream traffic. A virtual circuit version of the Adaptive Routing algorithm eliminates the need for resequencing buffers. >
Mark J. Karol - One of the best experts on this subject based on the ideXlab platform.
-
A simple Adaptive Routing scheme for congestion control in ShuffleNet multihop lightwave networks
IEEE Journal on Selected Areas in Communications, 1991Co-Authors: Mark J. Karol, S. Z. ShaikhAbstract:The authors describe a simple Adaptive Routing scheme for datagram (connectionless) and virtual circuit (connection-oriented) transmission that relieves congestion resulting from nonuniform traffic patterns and network failures. The authors describe a fixed-Routing algorithm for dedicated channel ShuffleNets. Based on the fixed Routing algorithm, an Adaptive Routing scheme for datagram transmission is presented followed by performance results for uniform and nonuniform traffic patterns and fault tolerance. The Adaptive Routing of datagrams uses only the local queue size information available at the network interface units (NIUs) and redistributes the load as congestion develops. Since datagrams are individually routed through the network, they may not arrive at their destination in the order they were generated and may need to be resequenced. The authors compute an upper estimate on the resequencing buffer size for stream traffic. A virtual circuit version of the Adaptive Routing algorithm eliminates the need for resequencing buffers. >
-
A simple Adaptive Routing scheme for ShuffleNet multihop lightwave networks
IEEE Global Telecommunications Conference and Exhibition. Communications for the Information Age, 1Co-Authors: Mark J. Karol, S. ShaikhAbstract:The authors describe a simple, Adaptive Routing scheme for datagram (connectionless) and virtual circuit (connection-oriented) transmission that relieves congestion resulting from nonuniform traffic patterns and network failures. It is a distributed algorithm that uses only local state information available at the user locations. When the network is congestion free, the Routing scheme delivers packets in the minimum number of hops. However, as a channel becomes overloaded, some of the traffic is distributed over less busy channels by automatically bumping packets in nonoptimal directions. The ShuffleNet connectivity makes it possible to disperse packets away from congested portions of the network quickly. Simulations of the Adaptive Routing scheme for datagram transmission demonstrates that it supports nonuniform traffic patterns, reduces the mean queue sizes and variances, and requires small resequencing buffers. >
