片上网络映射问题的改进禁忌搜索算法

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

为求解通信时延受约束的低能耗片上网络(NoC)映射问题,提出一种改进禁忌搜索算法.该算法由局部搜索和精英重组2个步骤经过多次迭代完成,局部搜索采用简化的robust tabu search(RoTS),精英重组步骤选用CO-HX交叉操作.实验结果表明:文中算法与RoTS相比具有优化性能好、搜索空间小的优点,映射结果比分支限界法平均节能16.1%,适于求解大规模NoC映射问题.

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.