Efficient Mapping Algorithm on Mesh-based NoCs in Terms of Cellular Learning Automata

Abstract: Network-on-Chip (NoC) presents the interesting approaches to organize complex communications in many systems. NoC can also be used as one of the effective solutions to cover the existing problems in System-on-Chip (SoC) such as scalability and reusability. The most common topology used in NoC is mesh topology. However, offering the mapping algorithm for mapping applications, based on weighted task graphs, onto the mesh is known as a NP-hard problem. This paper presents an effective algorithm called ‘Boundary Mapping Algorithm’ (BMA), in terms of decreasing the priority of low weighted edges in the task graph to improved performance in the NoCs. A low complexity mapping algorithm cannot present the optimal mapping results for all applications. Then, adding an optimization phase to mapping algorithms can have a positive impact on their performance. So, this study presents an optimization phase based on Cellular Learning Automata to achieve this goal. For the evaluation mapping algorithm and optimization phase, we compared the BMA method with Integer Linear Programming (ILP), Nmap, CastNet and Onyx methods for six real applications. The mapping results indicated that the proposed algorithm can be useful for some applications. Also, optimization phase can be useful for the proposed and other mapping algorithms.

Keywords: Cellular learning automata, mapping algorithm, network on chip, optimization algorithm, power consumption.