低功耗片上网络映射的遗传及蚂蚁融合算法

针对带宽和时延约束下的低功耗片上网络映射问题,提出了基于遗传和蚂蚁算法融合的映射算法.该算法利用遗传算法的快速搜索能力,获得若干优化解,并按照这些优化解的最优顺序给蚂蚁路径赋初值,以初始化蚂蚁算法的信息素分布.然后,借助具有交叉和变异操作的蚂蚁算法,充分利用蚂蚁算法的正反馈特性,搜索低功耗映射问题的更优解.该算法具有收敛速度快、优化效果好的特点,可用于求解大规模片上网络映射问题.实验结果表明:当系统规模扩大时,该算法在搜索时间方面明显优于遗传类算法和蚂蚁类算法,如系统规模为64处理单元时,搜索速度提高率最高可达220.3％,在较快收敛的同时,还保持了较好的优化效果,与蚂蚁类算法的差别可保持在9.1％以内.

Fusion Strategy with Genetic and Ant Algorithms for Low-Power NoC Mapping

To solve low-power mapping with bandwidth and latency constraints of network-on-chip(NoC),a fusion mapping with genetic and ant algorithms is proposed.Several optimal solutions are obtained by quick searching of genetic algorithm,then the initial values of ant paths are assigned according to the order of these optimal solutions to initialize the pheromone distribution of ant algorithm.Resorting the ant algorithm with crossover and mutation operation,and taking full advantage of the positive feedback features of the ant algorithm,the exact solution of the low-power mapping is searched out.This fusion strategy can be used to solve the large-scale NoC mappings with good optimization precision and convergence.The experimental results indicate that this strategy obviously outperforms genetic and ant algorithms for larger scale systems,the improvement of search rate can be heightened up to 220.3% for system of 64 processing elements,and the optimization difference gets less than 9.1% compared with ant algorithm.