基于云自适应遗传算法的NoC路径分配研究

摘要

Path allocation is one of the two key steps in Network-on-Chip (NoC) design flow. The result of the path allocation impacts the performance of NoC system, especially towards commu nication delay. Under the multi -constraint condition, the NoC path allocation is NP -complete problem and to find out the optimal solution is hard. The common method is to use the heuristic algorithm to obtain the second-best solution. This paper proposes one NoC path allocation solu tion based on adaptive genetic algorithm based on cloud theory (CAGA). The algorithm can improve crossover probabilityPc, and mutation probabilityPm automatically by using the cloud model, combining the fitness with three parameters of the cloud model, such asE, , E, , H, , so as to optimized genetic algorithm. The algorithm is applied to 2D- Mesh topological structure of the NoC, which to optimize the distribution of static communication results. The experiment results show that the algorithm to minimize bandwidth demand and balance in all links load has required better result.%路径分配是NoC设计流程中的两个关键步骤之一；路径分配的结果对NoC系统的性能尤其是通讯延时有着很重要的影响；多约束条件下的NoC路径分配问题是NP完全问题,要求出其最优解比较困难,目前常用的方法是利用启发式算法求得其较优解；文中提出一种基于云自适应遗传算法的NoC路径分配解决方案,该算法利用云模型对传统遗传算法加以改进,采取新的方法自动调整遗传算法过程中的交叉概率pc和变异概率pm,将适应度与云模型的3个参数Ex、En、He相互结合,从而达到优化遗传算法的目的；将此算法应用于2D-Mesh拓扑结构的NoC中,以平衡链路负载和联合优化为实验目标,以优化静态通讯分配结果；实验证明,文章所采取的算法在平衡链路负载和联合优化方面均取得了良好的效果.