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.
|Title of host publication
|Proceedings - 45th International Conference on Parallel Processing, ICPP 2016
|Institute of Electrical and Electronics Engineers Inc.
|Number of pages
|Published - 2016 Sept 21
|45th International Conference on Parallel Processing, ICPP 2016 - Philadelphia, United States
Duration: 2016 Aug 16 → 2016 Aug 19
|Proceedings of the International Conference on Parallel Processing
|45th International Conference on Parallel Processing, ICPP 2016
|16/8/16 → 16/8/19
- Graph Theory
ASJC Scopus subject areas
- General Mathematics
- Hardware and Architecture