A novel heuristic algorithm for IP block mapping onto mesh-based networks-on-chip

With advancement in the nanometer era, more and more intellectual property (IP) blocks can be integrated on a single die. Network-on-chip (NoC) has emerged as a viable alternative to unplug the communication bottleneck in system-on-chip. In the NoC synthesis flow, IP block mapping problem is one of the holistic research problems, which aims to minimize the overall communication cost or power consumption of the network. Since mesh is a well-accepted topology, we focus on IP mapping problem onto mesh-based NoCs in this paper. The IP mapping problem is proven to be NP-hard. No exact algorithm is expected to solve it in the polynomial time, and considerable computation time is required for even small-scale instances. In this paper, we analyze the symmetry character in mesh and propose an adaptive memetic algorithm (AMA) to solve the application mapping problem. The novel AMA method integrates both global and local optimization techniques, which contributes to the effectiveness and efficiency of the algorithm. Experiments have been carried out under both real application and synthetic benchmarks. Experimental results indicate that the proposed AMA outperforms the existing heuristics (CastNet and genetic algorithm) in the aspects of solution quality and power consumption. Within acceptable time limit, AMA could obtain optimal or suboptimal solutions when compared with the exact algorithm.