| Over the past twenty years, the pin bandwidth available to a chip has increased by approximately an order of magnitude every five years---a rate very similar to Moore's Law. This increasing pin bandwidth can be effectively utilized by creating high-radix routers with large number of skinny ports instead of low-radix routers with fat ports. The use of high-radix routers leads to lower cost and better performance, but high-radix networks present many difficult challenges. This thesis explores challenges in scaling to high-radix routers, including topology, routing, and router microarchitecture.; Topology is a critical aspect of any interconnection network as it sets performance bounds and determines the cost of the network. This thesis presents a cost-efficient high-radix topology referred to as the flattened butterfly topology which exploits the availability of high-radix routers. Compared to a folded-Clos topology, the flattened butterfly provides approximately 2x reduction in cost per performance on balanced traffic while maintaining the same cost per performance on adversarial traffic pattern. Given the topology, routing determines the path between the source and its destination. Proper routing is required to exploit the path diversity available in a high-radix network and we discuss the advantages of using adaptive routing in high-radix networks as well as how non-minimal routing is critical to properly exploiting the flattened butterfly topology.; Conventional microarchitectures do not scale to high radix since the complexity of the allocators in the routers scale quadratically with the radix. This thesis presents a hierarchical router organization that results in a distributed, complexity-effective microarchitecture and maintains high performance. As a case study, the implementation of this microarchitecture in the Cray YARC router with 64 ports will also be presented.; With the recent increase in the number of cores on a single-chip, the on-chip interconnection network that connects the on-chip cores and memory together will become more critical in determining the overall performance and cost of the entire chip. In the last part of this thesis, we expand the use of high-radix routers to on-chip networks and show how high-radix routers and the flattened butterfly topology can be mapped to on-chip networks. |
