ACRO: Assignment of channels in reverse order to make arbitrary routing deadlock-free

Ryuta Kawano; Hiroshi Nakahara; Seiichi Tade; Ikki Fujiwara; Hiroki Matsutani; Michihiro Koibuchi; Hideharu Amano

doi:10.1109/ICIS.2016.7550818

ACRO: Assignment of channels in reverse order to make arbitrary routing deadlock-free

Ryuta Kawano, Hiroshi Nakahara, Seiichi Tade, Ikki Fujiwara, Hiroki Matsutani, Michihiro Koibuchi, Hideharu Amano

Department of Information and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings
Editors	Kuniaki Uehara, Masahide Nakamura
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781509008063
DOIs	https://doi.org/10.1109/ICIS.2016.7550818
Publication status	Published - 2016 Aug 23
Event	15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016 - Okayama, Japan Duration: 2016 Jun 26 → 2016 Jun 29

Publication series

Name	2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings

Other

Other	15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016
Country/Territory	Japan
City	Okayama
Period	16/6/26 → 16/6/29

ASJC Scopus subject areas

Computer Science(all)
Energy Engineering and Power Technology
Control and Optimization

Access to Document

10.1109/ICIS.2016.7550818

Cite this

Kawano, R., Nakahara, H., Tade, S., Fujiwara, I., Matsutani, H., Koibuchi, M., & Amano, H. (2016). ACRO: Assignment of channels in reverse order to make arbitrary routing deadlock-free. In K. Uehara, & M. Nakamura (Eds.), 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings Article 7550818 (2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICIS.2016.7550818

ACRO: Assignment of channels in reverse order to make arbitrary routing deadlock-free. / Kawano, Ryuta; Nakahara, Hiroshi; Tade, Seiichi et al.
2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings. ed. / Kuniaki Uehara; Masahide Nakamura. Institute of Electrical and Electronics Engineers Inc., 2016. 7550818 (2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kawano, R, Nakahara, H, Tade, S, Fujiwara, I, Matsutani, H, Koibuchi, M & Amano, H 2016, ACRO: Assignment of channels in reverse order to make arbitrary routing deadlock-free. in K Uehara & M Nakamura (eds), 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings., 7550818, 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings, Institute of Electrical and Electronics Engineers Inc., 15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016, Okayama, Japan, 16/6/26. https://doi.org/10.1109/ICIS.2016.7550818

Kawano R, Nakahara H, Tade S, Fujiwara I, Matsutani H, Koibuchi M et al. ACRO: Assignment of channels in reverse order to make arbitrary routing deadlock-free. In Uehara K, Nakamura M, editors, 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2016. 7550818. (2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings). doi: 10.1109/ICIS.2016.7550818

Kawano, Ryuta ; Nakahara, Hiroshi ; Tade, Seiichi et al. / ACRO : Assignment of channels in reverse order to make arbitrary routing deadlock-free. 2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings. editor / Kuniaki Uehara ; Masahide Nakamura. Institute of Electrical and Electronics Engineers Inc., 2016. (2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings).

@inproceedings{3c82f054e3a6430bba112972c76d849d,

title = "ACRO: Assignment of channels in reverse order to make arbitrary routing deadlock-free",

abstract = "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.",

author = "Ryuta Kawano and Hiroshi Nakahara and Seiichi Tade and Ikki Fujiwara and Hiroki Matsutani and Michihiro Koibuchi and Hideharu Amano",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 15th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2016 ; Conference date: 26-06-2016 Through 29-06-2016",

year = "2016",

month = aug,

day = "23",

doi = "10.1109/ICIS.2016.7550818",

language = "English",

series = "2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

editor = "Kuniaki Uehara and Masahide Nakamura",

booktitle = "2016 IEEE/ACIS 15th International Conference on Computer and Information Science, ICIS 2016 - Proceedings",

}

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

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 -

ACRO: Assignment of channels in reverse order to make arbitrary routing deadlock-free

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this