Skip to main content

Adaptive channel queue routing on k-ary n-cubes

Publication ,  Conference
Singh, A; Dally, WJ; Gupta, AK; Towles, B
Published in: Annual ACM Symposium on Parallel Algorithms and Architectures
January 1, 2004

This paper introduces a new adaptive method, Channel Queue Routing (CQR), for load-balanced routing on k-ary n-cube interconnection networks. CQR estimates global congestion in the network from its channel queues while relying on the implicit network backpressure to transfer congestion information to these queues. It uses this estimate to decide the directions to route in each dimension. It further load balances the network by routing in the selected directions adaptively. The only other algorithm that uses global congestion in its routing decision is the Globally Adaptive Load-Balance (GAL) algorithm introduced in [13]. GAL performs better than any other known routing algorithm on a wide variety of throughput and latency metrics. However, there are four serious issues with GAL. First, it has very high latency once it starts routing traffic non-minimally. Second, it is slow to adapt to changes in traffic. Third, it requires a complex method to achieve stability. Finally, it is complex to implement. These issues are all related to GAL's use of injection queue length to infer global congestion. CQR uses channel queues rather than injection queues to estimate global congestion. In doing so, it overcomes the limitations of GAL described above while matching its high performance on all the performance metrics described in [13]. CQR gives much lower latency than GAL at loads where non-minimal routing is required. It adapts rapidly to changes in traffic, is unconditionally stable, and is simple to implement.

Duke Scholars

Published In

Annual ACM Symposium on Parallel Algorithms and Architectures

DOI

Publication Date

January 1, 2004

Volume

16

Start / End Page

11 / 19
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Singh, A., Dally, W. J., Gupta, A. K., & Towles, B. (2004). Adaptive channel queue routing on k-ary n-cubes. In Annual ACM Symposium on Parallel Algorithms and Architectures (Vol. 16, pp. 11–19). https://doi.org/10.1145/1007912.1007915
Singh, A., W. J. Dally, A. K. Gupta, and B. Towles. “Adaptive channel queue routing on k-ary n-cubes.” In Annual ACM Symposium on Parallel Algorithms and Architectures, 16:11–19, 2004. https://doi.org/10.1145/1007912.1007915.
Singh A, Dally WJ, Gupta AK, Towles B. Adaptive channel queue routing on k-ary n-cubes. In: Annual ACM Symposium on Parallel Algorithms and Architectures. 2004. p. 11–9.
Singh, A., et al. “Adaptive channel queue routing on k-ary n-cubes.” Annual ACM Symposium on Parallel Algorithms and Architectures, vol. 16, 2004, pp. 11–19. Scopus, doi:10.1145/1007912.1007915.
Singh A, Dally WJ, Gupta AK, Towles B. Adaptive channel queue routing on k-ary n-cubes. Annual ACM Symposium on Parallel Algorithms and Architectures. 2004. p. 11–19.

Published In

Annual ACM Symposium on Parallel Algorithms and Architectures

DOI

Publication Date

January 1, 2004

Volume

16

Start / End Page

11 / 19