UC San Diego

With the increasing number of processing cores in many- core chip-multiprocessors (CMPs) and with the ever-growing number of IPs being integrated in multiprocessor systems- on-chips (MPSoCs), the need for a scalable high-bandwidth communication fabric becomes more evident. Networks-on- Chip (NoCs) have successfully catered to these needs and are fast emerging as the de-facto communication fabric in both the CMP and MPSoC domains. Both throughput and latency are important performance metrics in the design of NoCs. This thesis focuses on a throughput- driven NoC design paradigm where maximizing NoC throughput is the primary design objective. NoCs that can sustain high throughput are necessary to handle high on-chip traffic volumes expected in current and future many-core processors with a large number of processing cores and potentially running a larger number of concurrent threads. For bandwidth-hungry applications, an increase in the sustainable throughput often translates into significant reductions in communication latency during temporary traffic bursts when the network is driven close to saturation. The problem of maximizing throughput in NoCs is tackled using two different approaches. First, novel oblivious and adaptive routing algorithms are proposed for mesh and torus topologies that maximize throughput by load -balancing traffic over all network links. The proposed oblivious routing algorithms guarantee optimal worst-case throughput, which is the throughput sustained under the most adversarial traffic. Providing such guarantees is important for general-purpose CMPs where target applications and resulting traffic patterns are not known at design time. Compared to existing solutions that achieve optimal worst-case throughput, the proposed algorithms achieve significantly lower latency and higher average-case throughput. The adaptive routing algorithm proposed for mesh networks improves the accuracy of congestion estimation over prior solutions by maintaining fine-grained destination- based congestion estimates that provide greater visibility into the global congestion state of the network. This results in better routing decisions and more efficient load- balancing. Next, a new router architecture is proposed that extends NoC throughput by more efficiently multiplexing packets onto network links. It deviates from the input- buffered router architecture traditionally used in NoCs. Instead, it practically emulates an output-buffered router that is known to achieve higher throughput