LEF: An Effective Routing Algorithm for Two-Dimensional Meshes
LEF: An Effective Routing Algorithm for Two-Dimensional Meshes
复制标题
DOI：
10.1587/transinf.2019edp7019
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Thiem Van Chu;Kenji Kise
中科院分区：
文献类型：
--
作者：
Thiem Van Chu;Kenji Kise
总结 我们为基于二维网格的片上网络 (NoC) 设计了一种新的不经意路由算法，称为 LEF（长边优先），它提供高吞吐量和低设计复杂性。 LEF 的基本思想来自于为具有非对称网状或环面互连的超级计算机选择适当的维度顺序路由 (DOR) 算法的传统智慧：首先路由最长维度可提供比其他策略更好的性能。在 LEF 中，我们结合了 XY DOR 和 YX DOR。当路由数据包时，选择哪种DOR算法取决于源节点和目的节点之间的相对位置。选择适当的 DOR 算法的决策并不固定于网络形状，而是基于每个数据包做出。我们还提出了一种有效的 LEF 死锁避免方法，其中虚拟通道的使用比传统方法更灵活。我们针对 O1TURN 评估 LEF，O1TURN 是另一种有效的不经意路由算法，也是基于奇偶轮模型的最小自适应路由算法。评估结果表明，当通信在非对称网格内时，LEF 特别有效。在 16 × 8 NoC 中，LEF 在某些情况下甚至优于自适应路由算法，吞吐量比 O1TURN 高出约 4% 至约 64.5%。我们的结果还表明，所提出的死锁避免方法有助于显着提高 LEF 的性能，并且可用于提高 O1TURN 的性能。我们还研究了具有数千个节点的大规模 NoC 中的 LEF。我们的结果表明，随着 NoC 规模的增加，路由算法的性能受到网络资源分配策略的影响变得更加强烈，并且每种算法的效果不同。这在具有大约 100 个节点的中等规模 NoC 的结果中很明显
SUMMARY We design a new oblivious routing algorithm for two-dimensional mesh-based Networks-on-Chip (NoCs) called LEF (Long Edge First) which o ff ers high throughput with low design complexity. LEF’s basic idea comes from conventional wisdom in choosing the appropriate dimension-order routing (DOR) algorithm for supercomputers with asymmetric mesh or torus interconnects: routing longest dimensions first provides better performance than other strategies. In LEF, we combine the XY DOR and the YX DOR. When routing a packet, which DOR algorithm is chosen depends on the relative position between the source node and the destination node. Decisions of selecting the appropriate DOR algorithm are not fixed to the network shape but instead made on a per-packet basis. We also propose an e ffi cient deadlock avoidance method for LEF in which the use of virtual channels is more flexible than in the conventional method. We evaluate LEF against O1TURN, another e ff ective oblivious routing algorithm, and a minimal adaptive routing algorithm based on the odd-even turn model. The evaluation results show that LEF is particularly e ff ective when the communication is within an asymmetric mesh. In a 16 × 8 NoC, LEF even outperforms the adaptive routing algorithm in some cases and delivers from around 4% up to around 64.5% higher throughput than O1TURN. Our results also show that the proposed deadlock avoidance method helps to improve LEF’s performance significantly and can be used to improve O1TURN’s performance. We also examine LEF in large-scale NoCs with thousands of nodes. Our results show that, as the NoC size increases, the performance of the routing algorithms becomes more strongly influenced by the resource allocation policy in the network and the e ff ect is di ff erent for each algorithm. This is evident in that results of middle-scale NoCs with around 100 nodes