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

Ryuta KAWANO; Hiroshi NAKAHARA; Seiichi TADE; Ikki FUJIWARA; Hiroki MATSUTANI; Michihiro KOIBUCHI; Hideharu AMANO

doi:10.1587/transinf.2016EDP7477

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

Ryuta KAWANO, Hiroshi NAKAHARA, Seiichi TADE, Ikki FUJIWARA, Hiroki MATSUTANI, Michihiro KOIBUCHI, Hideharu AMANO

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E100-D No.8 pp.1798-1806

Publication Date: 2017/08/01

Publicized: 2017/05/19

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2016EDP7477

Type of Manuscript: PAPER

Category: Computer System

Authors

Ryuta KAWANO
  Keio University
Hiroshi NAKAHARA
  Keio University
Seiichi TADE
  Keio University
Ikki FUJIWARA
  National Institute of Information and Communications Technology
Hiroki MATSUTANI
  Keio University
Michihiro KOIBUCHI
  National Institute of Informatics
Hideharu AMANO
  Keio University

Keyword

deadlock-free routing, high performance computing, time complexity

Cite this

Copy

Ryuta KAWANO, Hiroshi NAKAHARA, Seiichi TADE, Ikki FUJIWARA, Hiroki MATSUTANI, Michihiro KOIBUCHI, Hideharu AMANO, "A Novel Channel Assignment Method to Ensure Deadlock-Freedom for Deterministic Routing" in IEICE TRANSACTIONS on Information, vol. E100-D, no. 8, pp. 1798-1806, August 2017, doi: 10.1587/transinf.2016EDP7477.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016EDP7477/_p

Copy

@ARTICLE{e100-d_8_1798,
author={Ryuta KAWANO, Hiroshi NAKAHARA, Seiichi TADE, Ikki FUJIWARA, Hiroki MATSUTANI, Michihiro KOIBUCHI, Hideharu AMANO, },
journal={IEICE TRANSACTIONS on Information},
title={A Novel Channel Assignment Method to Ensure Deadlock-Freedom for Deterministic Routing},
year={2017},
volume={E100-D},
number={8},
pages={1798-1806},
abstract={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.},
keywords={},
doi={10.1587/transinf.2016EDP7477},
ISSN={1745-1361},
month={August},}

Copy

TY - JOUR
TI - A Novel Channel Assignment Method to Ensure Deadlock-Freedom for Deterministic Routing
T2 - IEICE TRANSACTIONS on Information
SP - 1798
EP - 1806
AU - Ryuta KAWANO
AU - Hiroshi NAKAHARA
AU - Seiichi TADE
AU - Ikki FUJIWARA
AU - Hiroki MATSUTANI
AU - Michihiro KOIBUCHI
AU - Hideharu AMANO
PY - 2017
DO - 10.1587/transinf.2016EDP7477
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2017
AB - 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.
ER -