From simple heuristics to evolutionary approach for routing messages in a NoC

The concept of network-on-chip (NoC) [1] is an emerging field in VLSI in which networking principles play an important role. As the number of modules on a chip multiplies, on-chip communication solutions are evolving. Traditional solutions based on shared-buses have hit their scalability limit, hence chip architectures rather employ interconnection network with short links connected by routers. Many challenges have yet to be tackled. An important issue is to define routing schemes on NoC topologies in order to allow packets to be routed to diverse destinations. Such topologies are often laid onto planar graphs or grids. NoC architectures are based on packet-switched networks and routers can implement various protocols from simple switching to intelligent routing. In this presentation, we address unicast routing, where the packets have a single destination and where routing always follows a deterministic path on the network. The goal is the construction of shortest origin destination paths with no conflicts between packets allowing a given bandwidth between NoC components. It is assumed that traffic requirements are known in advance, as it is often the case for special purpose applications, and the NoC's topological layout is already given. First, we state the optimisation problem. Then, we propose a heuristic and a metaheuristic approach to address this problem