TY - GEN
T1 - Randomly Optimized Grid Graph for Low-Latency Interconnection Networks
AU - Nakano, Koji
AU - Takafuji, Daisuke
AU - Fujita, Satoshi
AU - Matsutani, Hiroki
AU - Fujiwara, Ikki
AU - Koibuchi, Michihiro
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/9/21
Y1 - 2016/9/21
N2 - In this work we present randomly optimized grid graphs that maximize the performance measure, such as diameter and average shortest path length (ASPL), with subject to limited edge length on a grid surface. We also provide theoretical lower bounds of the diameter and the ASPL, which prove optimality of our randomly optimized grid graphs. We further present a diagonal grid layout that significantly reduces the diameter compared to the conventional one under the edge-length limitation. We finally show their applications to three case studies of off-and on-chip interconnection networks. Our design efficiently improves their performance measures, such as end-to-end communication latency, network power consumption, cost, and execution time of parallel benchmarks.
AB - In this work we present randomly optimized grid graphs that maximize the performance measure, such as diameter and average shortest path length (ASPL), with subject to limited edge length on a grid surface. We also provide theoretical lower bounds of the diameter and the ASPL, which prove optimality of our randomly optimized grid graphs. We further present a diagonal grid layout that significantly reduces the diameter compared to the conventional one under the edge-length limitation. We finally show their applications to three case studies of off-and on-chip interconnection networks. Our design efficiently improves their performance measures, such as end-to-end communication latency, network power consumption, cost, and execution time of parallel benchmarks.
KW - Graph Theory
KW - Network
UR - http://www.scopus.com/inward/record.url?scp=84990943189&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84990943189&partnerID=8YFLogxK
U2 - 10.1109/ICPP.2016.46
DO - 10.1109/ICPP.2016.46
M3 - Conference contribution
AN - SCOPUS:84990943189
T3 - Proceedings of the International Conference on Parallel Processing
SP - 340
EP - 349
BT - Proceedings - 45th International Conference on Parallel Processing, ICPP 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 45th International Conference on Parallel Processing, ICPP 2016
Y2 - 16 August 2016 through 19 August 2016
ER -