Throughput optimization for two-dimensional mesh and torus networks
Daeho Seo · Purdue e-Pubs (Purdue University System) · 2008
Two dimensional networks constitute an important class of interconnection networks in both commercial and research machines. Minimizing latency and maximizing throughput are important design goals. In this thesis, I propose three techniques to improve the throughput achieved in two-dimensional mesh and torus networks. First, the routing algorithm may create an imbalance in the load on network links. Ideally, I would like a routing algorithm to (a) route packets using the minimal number of hops, (b) deliver good worst-case and average-case throughput, and (c) enable low-complexity router implementation. Existing routing algorithms fail to satisfy one or more of design goals mentioned above. We propose a new routing algorithm - O1TURN - satisfying all the stated design goals. Second, crossbar arbitration may underutilize free output ports and thus unnecessarily degrade throughput. The performance of crossbar arbitration depends on two metrics:(a) matching power, (b) arbitration throughput. Unfortunately, these two metrics are conflicting goals to achieve. I propose new crossbar arbitration mechanism - TabArb - that delivers superior matching and high arbitration throughput. It improves the saturation throughput by 14.8%. Third, I address network switching for streaming communication. Unfortunately, traditional packet-switched networks are not suitable for streaming communication. In packet-switching, each packet contends for resources as it traverses the network which can result in significant throughput degradation for streaming applications. I demonstrate a disjoint-path routing that ensures that streaming data has dedicated bandwidth. It improves the throughput of streaming applications by 55% on a 4x4 mesh network.