Level-wise Scheduling Algorithm for Fat Tree Interconnection Networks
Zhu Ding, Raymond R. Hoare, Alex K. Jones et al. · Proceedings - Supercomputing · 2006
This paper presents an efficient hardware architecture for scheduling connections on a fat-tree interconnection network for parallel computing systems. Our technique utilizes global routing information to select upward routing paths so that most conflicts can be resolved. Thus, more connections can be successfully scheduled compared with a local scheduler. As a result of applying our technique to two-level, three-level and four-level fat-tree interconnection networks of various sizes in the range of 64 to 4096 nodes, we observe that the improvement of schedulability ratio averages 30% compared with greedy or random local scheduling. Our technique is also scalable and shows increased benefits for large system sizes
Cited by 10 works. doi:10.1109/sc.2006.40
Authors
References
- Fat-trees: Universal networks for hardware-efficient supercomputing
- The network architecture of the Connection Machine CM-5 (extended abstract)
- Experience with active messages on the Meiko CS-2
- Performance evaluation of switch-based wormhole networks
- Benchmarking the CM-5 multicomputer
- Adaptive source routing in multistage interconnection networks
- New adaptive routing algorithm for extended generalized fat trees on-chip