An Improved Tabu Search Algorithm for Network-on-Chip Mapping

An improved tabu search algorithm is proposed to solve the low energy network-on-chip (NoC) mapping problem subject to communication latency constraints. An efficient local search and subsequent reconstruction of elite solutions is applied in an iterated way. The local search procedure uses simplified robust tabu search (RoTS). In the reconstruction procedure, COHX crossover operator is adopted to produce new feasible solution. Experimental results demonstrate that the improved tabu search algorithm can give better quality solutions and smaller searching space than RoTS, and 16.1% energy savings are achieved, on average, compared to branch and bound algorithm. It is more effective to solve large-scale NoC mapping problems.