New heuristic algorithms for energy aware application mapping and routing on mesh-based NoCs

Ever shrinking technologies in VLSI era made it possible to place several IP (Intellectual Property) blocks onto a single die. This technology improvement also brought the challenge of inventing new communication methods since traditional bus-based systems suffer from signal propagation delays, signal integrity, and scalability on these large platforms. Network-on-Chip (NoC) is the biggest step towards the solution of this communication bottleneck of System-on-Chip (SoC) architectures. Topology selection is the very first step of designing NoC systems and mesh topology is the commonly accepted topology type for NoCs. However, mapping applications represented by the weighted task graphs onto the mesh architectures is an NP-hard problem. In this paper, we present a new low complexity heuristic algorithm, CastNet, for the application mapping and bandwidth constrained routing algorithm for mesh-based NoC architectures aiming to minimize the energy consumption. We compared the presented approach with the one that generates the optimal solutions and two existing heuristic methods. Our experiments on multimedia benchmarks show that the proposed mapping algorithm obtains optimal or, in worst case, within 6% to the optimal solutions in very short times. (C) 2010 Elsevier B.V. All rights reserved.