論文

査読有り
2017年8月

A Novel Channel Assignment Method to Ensure Deadlock-Freedom for Deterministic Routing

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
  • Ryuta Kawano
  • ,
  • Hiroshi Nakahara
  • ,
  • Seiichi Tade
  • ,
  • Ikki Fujiwara
  • ,
  • Hiroki Matsutani
  • ,
  • Michihiro Koibuchi
  • ,
  • Hideharu Amano

E100D
8
開始ページ
1798
終了ページ
1806
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1587/transinf.2016EDP7477
出版者・発行元
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

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(|vertical bar N vertical bar . log vertical bar N vertical bar), when compared with another conventional algorithm that requires almost the same number of VCs.

Web of Science ® 被引用回数 : 1

リンク情報
DOI
https://doi.org/10.1587/transinf.2016EDP7477
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000406868400028&DestApp=WOS_CPL