An Effective Design of Deadlock-Free Routing Algorithms Based on 2D Turn Model for Irregular Networks
An Effective Design of Deadlock-Free Routing Algorithms Based on 2D Turn Model for Irregular Networks
复制标题
DOI：
10.1109/tpds.2007.36
复制
发表时间：
2007-03
影响因子：
5.3
通讯作者：
A. Jouraku;M. Koibuchi;H. Amano
中科院分区：
文献类型：
--
作者：
A. Jouraku;M. Koibuchi;H. Amano
系统区域网络 (SAN) 通常接受任意拓扑，已用于连接 PC 集群中的主机。尽管无死锁路由通常用于使用虫洞或虚拟直通交换的低延迟通信，但互连自适应性给建立无死锁路径带来了困难。上*/下*路由算法已被广泛用于避免不规则网络中的死锁，但由于它采用一维有向图，因此往往会产生不平衡的路径。当前的研究引入了一种二维有向图，在该图上提出了称为左上首转（L转）路由和右下最后一转（R转）路由的自适应路由，以使路径尽可能均匀分布。该方案保证了无死锁，因为它使用转弯模型方法，并且二维图中的额外自由度有助于确保禁止的转弯均匀分布。仿真结果表明，均匀分布禁止转弯可带来更好的吞吐量和延迟，通过这种方式，流量将更多地分布到叶节点。满足此条件的 L 转弯路由与两个基于上*/下*的路由相比，吞吐量提高了 100%，并且还减少了延迟
System area networks (SANs), which usually accept arbitrary topologies, have been used to connect hosts in PC clusters. Although deadlock-free routing is often employed for low-latency communications using wormhole or virtual cut-through switching, the interconnection adaptivity introduces difficulties in establishing deadlock-free paths. An up*/down* routing algorithm, which has been widely used to avoid deadlocks in irregular networks, tends to make unbalanced paths as it employs a one-dimensional directed graph. The current study introduces a two-dimensional directed graph on which adaptive routings called left-up first turn (L-turn) routings and right-down last turn (R-turn) routings are proposed to make the paths as uniformly distributed as possible. This scheme guarantees deadlock-freedom because it uses the turn model approach, and the extra degree of freedom in the two-dimensional graph helps to ensure that the prohibited turns are well-distributed. Simulation results show that better throughput and latency results from uniformly distributing the prohibited turns by which the traffic would be more distributed toward the leaf nodes. The L-turn routings, which meet this condition, improve throughput by up to 100 percent compared with two up*/down*-based routings, and also reduce latency