An effective methodology to improve the performance of the up*/down* routing algorithm
An effective methodology to improve the performance of the up*/down* routing algorithm
复制标题
提高上行*/下行*路由算法性能的有效方法
DOI：
--
复制
发表时间：
2004
影响因子：
5.3
通讯作者：
J. Duato
中科院分区：
文献类型：
--
作者：
J. Sancho;A. Robles;J. Duato
工作站网络(NOW)正被认为是并行计算机的一种经济高效的替代方案。大多数NOW被安排为基于交换机的网络，并提供用于发现网络拓扑的机制。因此，它们同时支持规则和不规则拓扑，这使得路由和死锁避免变得非常复杂。当前的建议使用向上*/向下*路由算法来消除通道之间的循环依赖并避免死锁。然而，路由受到相当大的限制，大多数消息必须遵循非最短路径，从而增加了延迟和资源浪费。我们提出并评估了一种简单而有效的方法来计算向上*/向下*路由表。新方法基于在网络图上计算深度优先搜索(DPS)生成树，从而减少了相对于传统方法使用的广度优先搜索(BFS)生成树的路由限制数量。此外，我们还提出了不同的启发式规则来计算生成树，以提高向上*/向下*路由的效率。对几种不同拓扑的评估结果表明，与传统方法相比，使用新方法计算UP*/DOWN*路由表在大型网络中的吞吐量提高了2.48倍，并显著降低了延迟。
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. 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 (DPS) 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.