A Novel Channel Assignment Method to Ensure Deadlock-Freedom for Deterministic Routing
A Novel Channel Assignment Method to Ensure Deadlock-Freedom for Deterministic Routing
复制标题
DOI：
10.1587/transinf.2016edp7477
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Ryuta Kawano;Hiroshige Nakahara;S. Tade;I. Fujiwara;Hiroki Matsutani;M. Koibuchi;H. Amano
中科院分区：
文献类型：
--
作者：
Ryuta Kawano;Hiroshige Nakahara;S. Tade;I. Fujiwara;Hiroki Matsutani;M. Koibuchi;H. Amano
HPC系统和数据中心的交换间网络可以通过应用减少跳数的随机快捷拓扑来改进。在这种网络中路由最少的；然而，死锁的自由是不能保证的。多虚拟通道（VCs）有效地避免了这个问题。然而，以前的工作并没有提供所需vc的数量与算法的时间和内存复杂性之间的良好权衡。在这项工作中，提出了一种新的快速算法ACRO，该算法具有死锁自由，并且消耗少量vc。通过哈希表实现了一种减少风险的启发式方法，与我们以前的工作相比，它提高了算法的可扩展性。此外，实验结果表明，在相同时间复杂度的情况下，与传统算法相比，ACRO算法可以将vc的平均数量减少63%。此外，与另一种需要几乎相同数量的vc的传统算法相比，ACRO将时间复杂度降低了O（|N |·log |N |）。关键词：无死锁路由，高性能计算，时间复杂度
Inter-switch networks for HPC systems and data-centers can be improved by applying random shortcut topologies with a reduced number of hops. With minimal routing in such networks; however, deadlock-freedom is not guaranteed. Multiple Virtual Channels (VCs) are efficiently used to avoid this problem. However, previous works do not provide good trade-offs between the number of required VCs and the time and memory complexities of an algorithm. In this work, a novel and fast algorithm, named ACRO, is proposed to endorse the arbitrary routing functions with deadlock-freedom, as well as consuming a small number of VCs. A heuristic approach to reduce VCs is achieved with a hash table, which improves the scalability of the algorithm compared with our previous work. Moreover, experimental results show that ACRO can reduce the average number of VCs by up to 63% when compared with a conventional algorithm that has the same time complexity. Furthermore, ACRO reduces the time complexity by a factor of O(|N | · log |N |), when compared with another conventional algorithm that requires almost the same number of VCs. key words: deadlock-free routing, high performance computing, time complexity