High-performance interconnection networks design

Abstract

Due to the thriving of computation and communication intensive applications and the increase of network scale, high-capacity, low-latency, and low-cost interconnection networks are desperately needed. In this thesis, we focus on interconnection networks design in three major domains: network-on-chip (NoC), packet switch and data center network. NoC aims at providing efficient intra-communication among different elements of the same chip. As the number of cores in a chip multiprocessor (CMP) increases, the classic router-based approach becomes inefficient due to the large die area and high power consumption of routers. In routerless NoC, routers are eliminated by connecting every pair of cores using at least one ring. Under a given physical wiring constraint, the problem of finding a set of arbitrary rings that guarantees the connectivity and minimizes the average distance among all core pairs is NP-hard. To solve it, we formulate the first optimal integer linear programming (ILP1). But ILP1 is too complicated to solve even for very small-size CMPs. By limiting the solution space to rectangle rings only, the second optimal ILP (ILP2) is then designed. In ILP3, the distance calculation in ILP2 is further simplified to make it more scalable. Finally, an efficient heuristic called Onion and its variant Onion+ are designed for large-size CMPs. Packet switch is the most important component of the Internet. To meet the ever-increasing demand for speed, advances in fiber-optics such as DWDM have greatly increased the capacity of a fiber. But due to the speed limit of electronic processing, the growth in switch capacity has lagged behind. In the second part of the thesis, we focus on designing high-speed input-queued packet switch, particularly efficient packet scheduling algorithms for handling mixed unicast and multicast traffic. We first propose a pipelined scheduler. It consists of two component schedulers working in parallel, one for unicast and one for multicast. Although both component schedulers are implemented using the most efficient form of iterative scheduling, or single-bit single-iteration (SBSI), their complexity can be reduced by combining them to form a two-bit single-iteration (2BSI) algorithm. An enhanced variant (2BSI-k) is also designed to guarantee minimum bandwidth for unicast traffic. Finally, a three-bit single-iteration (3BSI) algorithm and its starvation-free variant (3BSI-Q) are proposed for handling variable-size packets. In the third part of the thesis, we study data center networks based on the widely adopted fat-tree interconnection topology. Unlike conventional applications, data center applications are characterized by extensive parallel communications among server clusters known as coflows. Since a coflow is a collection of parallel flows, it is not completed unless all its component flows are finished. Aiming at minimizing the time required by the slowest component flow, or coflow completion time, an efficient online coflow-aware packet scheduling algorithm called critical line first (CLF) is designed. Our extensive simulations under both model-generated traffic patterns and real Facebook traces show that CLF outperforms all existing algorithms.