Joint Multicast Routing and Network Design Optimization for Networks-on-Chip

This paper considers the problem of synthesizing custom Networks-on-Chip (NoC) architectures that are optimized for a given application. Both unicast and multicast traffic flows are considered in the input specification. This paper formulate the joint multicast routing and network design problem using a rip-up and reroute procedure, where each multicast routing step is formulated as a minimum directed spanning tree problem, and the authors proposes a very efficient algorithm called Ripup-Reroute-and-Router-Merging (RRRM). The new formulation adopts a rip-up and reroute concept that provides them with a heuristic iterative mechanism to identify increasingly improving solutions. The minimum directed spanning tree formulation efficiently captures the best routing solutions for multicast flows during the topology synthesis procedure.