An Effective Methodology to Improve the Performance of the Up*/Down* Routing Algorithm Export

@article{citeulike:3345342, abstract = {Networks of workstations (NOWs) are being considered as a cost-effective alternative to parallel computers. Most NOWs are arranged as a switch-based network and provide mechanisms for discovering the network topology. Hence, they provide support for both regular and irregular topologies, which makes routing and deadlock avoidance quite complicated. Current proposals use the Up*/down* routing algorithm to remove cyclic dependencies between channels and avoid deadlock. However, routing is considerably restricted and most messages must follow nonminimal paths, increasing latency and wasting resources. In this work, we propose and evaluate a simple and effective methodology to compute Up*/down* routing tables. The new methodology is based on computing a depth-first search (DFS) spanning tree on the network graph that decreases the number of routing restrictions with respect to the breadth-first search (BFS) spanning tree used by the traditional methodology. Additionally, we propose different heuristic rules for computing the spanning trees to improve the efficiency of Up*/down* routing. Evaluation results for several different topologies show that computing the Up*/down* routing tables by using the new methodology increases throughput by a factor of up to 2.48 in large networks with respect to the traditional methodology, and also reduces latency significantly.}, address = {Piscataway, NJ, USA}, author = {Sancho, Jose C.}, citeulike-article-id = {3345342}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1009230.1009300}, citeulike-linkout-1 = {http://dx.doi.org/10.1109/TPDS.2004.28}, doi = {10.1109/TPDS.2004.28}, issn = {1045-9219}, journal = {IEEE Trans. Parallel Distrib. Syst.}, keywords = {routing}, number = {8}, pages = {740--754}, posted-at = {2008-09-27 18:02:46}, priority = {2}, publisher = {IEEE Press}, title = {An Effective Methodology to Improve the Performance of the Up*/Down* Routing Algorithm}, url = {http://dx.doi.org/10.1109/TPDS.2004.28}, volume = {15}, year = {2004} }

TY - JOUR ID - citeulike:3345342 L3 - citeulike-article-id:3345342 N2 - Networks of workstations (NOWs) are being considered as a cost-effective alternative to parallel computers. Most NOWs are arranged as a switch-based network and provide mechanisms for discovering the network topology. Hence, they provide support for both regular and irregular topologies, which makes routing and deadlock avoidance quite complicated. Current proposals use the Up*/down* routing algorithm to remove cyclic dependencies between channels and avoid deadlock. However, routing is considerably restricted and most messages must follow nonminimal paths, increasing latency and wasting resources. In this work, we propose and evaluate a simple and effective methodology to compute Up*/down* routing tables. The new methodology is based on computing a depth-first search (DFS) spanning tree on the network graph that decreases the number of routing restrictions with respect to the breadth-first search (BFS) spanning tree used by the traditional methodology. Additionally, we propose different heuristic rules for computing the spanning trees to improve the efficiency of Up*/down* routing. Evaluation results for several different topologies show that computing the Up*/down* routing tables by using the new methodology increases throughput by a factor of up to 2.48 in large networks with respect to the traditional methodology, and also reduces latency significantly. IS - 8 JF - IEEE Trans. Parallel Distrib. Syst. SN - 1045-9219 AD - Piscataway, NJ, USA EP - 754 TI - An Effective Methodology to Improve the Performance of the Up*/Down* Routing Algorithm PB - IEEE Press VL - 15 SP - 740 KW - routing AU - Sancho, Jose PY - 2004/// UR - http://dx.doi.org/10.1109/TPDS.2004.28 ER -