基于自适应模拟退火的NoC映射算法

Self-adaptive simulated annealing based mapping algorithm for network on chip

在片上网络(Network on Chip,NoC)系统中,如何完成应用特征图到结构特征图的映射是影响系统实际性能的关键步骤之一。针对NoC系统越发庞大,映射算法耗时也随之增加的问题,提出了自适应模拟退火(Self-Adaptive Simulated Annealing,SASA)的NoC映射算法。采用相对平滑方式实现温度下降过程,针对模拟退火算法易陷于局部最优的缺点,采用自适应方法改变新解生成方式,提高了算法收敛于全局最优的概率。实验结果表明,该算法与常见NoC映射算法(如基于遗传的映射算法)相比,平均性能提升了5.3%,耗时缩短了11.1%。

In the system of Network on Chip（NoC）,how to map an application characterization graph to an architecture characterization graph is a key step which has a great influence on the system performance.Considering that the time consumption of mapping algorithm increases along with the increasing NoC sizes,an Self-Adaptive Simulated Annealing（SASA）based mapping algorithm for NoC is proposed.A smoothly cooling down process is adopted in the SASA.To avoid being trapped in the local optimum,the way to generate new solutions is changed adaptively in order to improve the probability of finding the global optimum.Experimental results show that compared with the traditional mapping algorithms（such as ant colony or genetic based mapping algorithms）,the SASA can improve the average performance 5.3% and save the time consumption 11.1%.