Topology Agnostic Virtual Channel Assignment and Protocol Level Deadlock Avoidance in a Network-on-Chip

A Virtual Channel (VC) is a Time Division Multiplexed (TDM) slice of a physical channel/link. A crucial step of interconnect synthesis is to assign VCs to traffic that avoids deadlocks while meeting Power, Performance and Area (PPA) objectives. For a Network on Chip (NoC), VC assignment is tightly coupled with topology generation and routing. Inefficient VC assignment can lead to NoCs which may be an order of magnitude inferior in terms of PPA. However, both VC assignment and topology generation are combinatorially hard problems. Thus, combining VC assignment with topology generation makes it difficult to efficiently solve either.In this paper, we present a topology agnostic VC assignment approach for statically routed NoCs. This segregation enables us to solve the VC assignment problem first and then subsequently generate topology. By solving VC assignment first, we reduce the problem space of topology generation leading to NoCs with tighter PPA. We model the VC assignment problem as a Traffic Conflict Graph (TCG), capturing a global view of Quality of Service (QoS), Head-of-Line (HoL) conflicts, burstiness and external protocol level dependencies (e.g. PCIe root-complex). We apply combinatorial optimization techniques on TCG to arrive at an efficient VC assignment, that ensures deadlock free designs. The algorithm has been implemented in production NoC Synthesis tool. Results obtained on more than a dozen multi-million gate System-on-Chip (SoC) demonstrate an average improvement of 30% across metrics such as routers, resizers, power/clock domain converters, latencies etc. while meeting the performance vis-à-vis hand-tuned NoCs. The hand-tuned designs have been manually optimized over several man-months by expert designers, while the tool achieves better results in a few minutes.