An Advanced Cost-Aware Mapping Algorithm Based on Frog Leaping and Tabu Search for Two-Dimensional Network-On-Chip

Abstract

One of the main challenges in two-dimensional Network on Chip (NoC) architectures is mapping application graphs onto tile-based architectures. Without appropriate mapping algorithms, the system's performance can be significantly degraded. Various mapping algorithms have been proposed for NoC. However, most of these methods have not been able to address the main challenges in mapping algorithms, particularly the communication cost. To this end, a mapping algorithm named FTMA (Frog leaping and Tabu Search Mapping Algorithm) for two-dimensional mesh topology-on-chip base is proposed which utilizes the combination of frog leaping mapping algorithm and Tabu search for mapping operation. Using these two algorithms in the proposed method provides several advantages for the mapping algorithm. These advantages include finding the best mapping in the shortest time, utilizing smart memory to reduce extra costs, and being suitable for most application graphs. The algorithm is also appropriate for graphs with a large number of nodes and provides a final solution. Simulation results show that the proposed mapping algorithm reduces communication costs. The reduction percentages are 7.45, 15.34, 11.60, 15.18, 17.68, and 15.64 compared to the ISFLA, IAM, ELIXIR, PSMAP, ACO, NMAP, LMAP, and BMA methods, respectively.