TY - GEN
T1 - ACRO
T2 - 15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016
AU - Kawano, Ryuta
AU - Nakahara, Hiroshi
AU - Tade, Seiichi
AU - Fujiwara, Ikki
AU - Matsutani, Hiroki
AU - Koibuchi, Michihiro
AU - Amano, Hideharu
N1 - Publisher Copyright:
© 2016 IEEE.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2016/8/23
Y1 - 2016/8/23
N2 - Distributed routing methods with small routing tables are scalable design on irregular networks for large-scale High Performance Computing (HPC) systems. Recently proposed compact routing methods, however, do not guarantee deadlock-freedom. Cyclic channel dependencies on arbitrary routing are typically removed with multiple Virtual Channels (VCs). However, challenges still remain to provide good trade-offs between a number of required VCs and a time complexity of an algorithm for assignment of VCs to paths. In this work, a novel algorithm ACRO is proposed for enriching arbitrary routing functions with deadlock-freedom with a reasonable number of VCs and a time complexity. Experimental results show that ACRO can reduce the average number of required VCs by up to 63% compared with the conventional algorithm that has the same time complexity. Furthermore, ACRO reduces a time complexity by a factor of O(|N| · log|N|) compared with that of the other conventional algorithm that needs almost the same number of VCs.
AB - Distributed routing methods with small routing tables are scalable design on irregular networks for large-scale High Performance Computing (HPC) systems. Recently proposed compact routing methods, however, do not guarantee deadlock-freedom. Cyclic channel dependencies on arbitrary routing are typically removed with multiple Virtual Channels (VCs). However, challenges still remain to provide good trade-offs between a number of required VCs and a time complexity of an algorithm for assignment of VCs to paths. In this work, a novel algorithm ACRO is proposed for enriching arbitrary routing functions with deadlock-freedom with a reasonable number of VCs and a time complexity. Experimental results show that ACRO can reduce the average number of required VCs by up to 63% compared with the conventional algorithm that has the same time complexity. Furthermore, ACRO reduces a time complexity by a factor of O(|N| · log|N|) compared with that of the other conventional algorithm that needs almost the same number of VCs.
UR - http://www.scopus.com/inward/record.url?scp=84987968758&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84987968758&partnerID=8YFLogxK
U2 - 10.1109/ICIS.2016.7550818
DO - 10.1109/ICIS.2016.7550818
M3 - Conference contribution
AN - SCOPUS:84987968758
T3 - 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings
BT - 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings
A2 - Uehara, Kuniaki
A2 - Nakamura, Masahide
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 26 June 2016 through 29 June 2016
ER -