基于混沌粒子群的三维片上网络映射算法设计与实现

发布时间：2018-05-26 11:22

本文选题：三维片上网络 + 映射算法　；参考：《西安电子科技大学》2015年硕士论文

【摘要】：随着嵌入式领域的快速发展,片上系统瓶颈问题日益明显,相关的研究人员提出了将计算机网络的理念引入嵌入式系统设计领域,因此片上网络应运而生。片上网络将通信节点和资源节点分离,以分组交换为基本通讯技术,采用全局异步-局部同步的通讯机制,凭借路由策略和交换技术在功耗和延时方面表现出更优越的性能,从而满足嵌入式发展的需求,成为了如今嵌入式系统设计的大方向。片上网络想要发挥功耗和延时方面的优越性需要一个合理高效的映射算法。三维片上网络的映射算法是一个NP完全问题,有许多智能算法被应用于片上网络的映射问题上,但是仍然存在算法效率低,映射不合理以及功耗和延时不能兼顾的问题,因此我们还需要对三维片上网络的映射策略进行进一步研究。本文主要针对三维片上网络的映射算法做了相关研究。首先简要介绍了三维片上网络的拓扑结构、片上网络平台、路由算法、映射相关理论以及功耗和延时模型,进而分别对基于遗传、蚁群和粒子群的映射算法进行了实现和性能分析,鉴于遗传算法、蚁群算法和粒子群算法的不足之处,本文设计和实现了一种基于混沌粒子群的映射算法,算法主要分为两个个阶段,前一阶段依据DAG图所提供的信息得到各个任务的优先权值,关键路径上任务的优先权值最大,优先映射前驱任务已经完成的关键路径任务来缩短任务执行总时间;第二阶段利用第一阶段生成的任务到内核的映射结果,借助混沌粒子群算法和功耗延时模型来生成近似最优的内核映射方案。通过TGFF(随机任务生成器)生成随机任务集合,设置相关的算法参数,运用Java开发软件Eclipse分别借助遗传算法、蚁群算法和混沌粒子群算法来编写映射算法。按照编写的映射算法将任务数据先向内核映射,再将内核向网络节点映射来完成仿真;仿真结果表明:相比于遗传算法和蚁群算法,基于混沌粒子群的映射算法在功耗、延时整体性能以及收敛效果方面都比较好。论文完成了三维片上网络映射算法设计及仿真验证。论文工作对三维片上网络映射算法的研究有一定的参考意义。
[Abstract]:With the rapid development of embedded field, the bottleneck problem of on-chip system becomes more and more obvious. Related researchers put forward the idea of introducing the concept of computer network into the field of embedded system design, so the on-chip network came into being. The on-chip network separates the communication node from the resource node, takes packet switching as the basic communication technology, adopts the global asynchronous local synchronous communication mechanism, and shows better performance in power consumption and delay by means of routing strategy and switching technology. Therefore, to meet the needs of embedded development has become the main direction of embedded system design. In order to exert the advantages of power consumption and delay, the on-chip network needs a reasonable and efficient mapping algorithm. The mapping algorithm of 3D on-chip network is a NP-complete problem. Many intelligent algorithms have been applied to the mapping problem of the on-chip network. However, there are still some problems such as low efficiency, unreasonable mapping, and the imbalance of power consumption and delay. Therefore, we need to further study the mapping strategy of three-dimensional on-chip network. This paper mainly focuses on the mapping algorithm of three-dimensional on-chip network. Firstly, the topology of 3D on-chip network, on-chip network platform, routing algorithm, mapping theory, power consumption and delay model are briefly introduced. The mapping algorithm of ant colony and particle swarm is implemented and its performance is analyzed. In view of the deficiency of genetic algorithm, ant colony algorithm and particle swarm optimization algorithm, a mapping algorithm based on chaotic particle swarm optimization is designed and implemented in this paper. The algorithm is mainly divided into two stages. In the previous stage, the priority value of each task is obtained according to the information provided by the DAG diagram, and the priority value of the task on the critical path is the largest. First mapping the critical path tasks completed by the precursor task to shorten the total task execution time; the second stage uses the mapping results from the first phase to the kernel. Chaotic particle swarm optimization algorithm and power delay model are used to generate an approximate optimal kernel mapping scheme. The random task set is generated by TGFF (random task generator), and the related algorithm parameters are set up. The mapping algorithm is compiled by Java development software Eclipse with the help of genetic algorithm, ant colony algorithm and chaotic particle swarm optimization algorithm, respectively. According to the mapping algorithm, the task data is mapped to the kernel first and then the kernel to the network node to complete the simulation. The simulation results show that compared with genetic algorithm and ant colony algorithm, the mapping algorithm based on chaotic particle swarm in power consumption. The overall performance of delay and convergence effect are better. The algorithm design and simulation verification of three-dimensional on-chip network mapping are completed in this paper. The work of this paper has some reference significance for the research of three-dimensional on-chip network mapping algorithm.
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN47;TP18

【参考文献】