Title :
Adaptive Routing in High-Radix Clos Network
Author :
Kim, John ; Dally, William ; Dally, J. ; Abts, Dennis
Author_Institution :
Stanford Univ., CA
Abstract :
Recent increase in the pin bandwidth of integrated-circuits has motivated an increase in the degree or radix of interconnection network routers. The folded-Clos network can take advantage of these high-radix routers and this paper investigates adaptive routing in such networks. We show that adaptive routing, if done properly, outperforms oblivious routing by providing lower latency, lower latency variance, and higher throughput with limited buffering. Adaptive routing is particularly useful in load balancing around nonuniformities caused by deterministically routed traffic or the presence of faults in the network. We evaluate alternative allocation algorithms used in adaptive routing and compare their performance. The use of randomization in the allocation algorithms can simplify the implementation while sacrificing minimal performance. The cost of adaptive routing, in terms of router latency and area, is increased in high-radix routers. We show that the use of imprecise queue information reduces the implementation complexity and precomputation of the allocations minimizes the impact of adaptive routing on router latency
Keywords :
multistage interconnection networks; resource allocation; adaptive routing; allocation algorithm; high-radix folded-Clos interconnection network; load balancing; Bandwidth; Costs; Delay; Multiprocessor interconnection networks; Network topology; Permission; Routing; Telecommunication traffic; Throughput; Traffic control;
Conference_Titel :
SC 2006 Conference, Proceedings of the ACM/IEEE
Conference_Location :
Tampa, FL
Print_ISBN :
0-7695-2700-0
Electronic_ISBN :
0-7695-2700-0