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

摘要

随着嵌入式领域的快速发展，片上系统瓶颈问题日益明显，相关的研究人员提出了将计算机网络的理念引入嵌入式系统设计领域，因此片上网络应运而生。片上网络将通信节点和资源节点分离，以分组交换为基本通讯技术，采用全局异步-局部同步的通讯机制，凭借路由策略和交换技术在功耗和延时方面表现出更优越的性能，从而满足嵌入式发展的需求，成为了如今嵌入式系统设计的大方向。片上网络想要发挥功耗和延时方面的优越性需要一个合理高效的映射算法。三维片上网络的映射算法是一个NP完全问题，有许多智能算法被应用于片上网络的映射问题上，但是仍然存在算法效率低，映射不合理以及功耗和延时不能兼顾的问题，因此我们还需要对三维片上网络的映射策略进行进一步研究。
　　本文主要针对三维片上网络的映射算法做了相关研究。首先简要介绍了三维片上网络的拓扑结构、片上网络平台、路由算法、映射相关理论以及功耗和延时模型，进而分别对基于遗传、蚁群和粒子群的映射算法进行了实现和性能分析，鉴于遗传算法、蚁群算法和粒子群算法的不足之处，本文设计和实现了一种基于混沌粒子群的映射算法，算法主要分为两个个阶段，前一阶段依据DAG图所提供的信息得到各个任务的优先权值，关键路径上任务的优先权值最大，优先映射前驱任务已经完成的关键路径任务来缩短任务执行总时间；第二阶段利用第一阶段生成的任务到内核的映射结果，借助混沌粒子群算法和功耗延时模型来生成近似最优的内核映射方案。
　　通过TGFF（随机任务生成器）生成随机任务集合，设置相关的算法参数，运用Java开发软件Eclipse分别借助遗传算法、蚁群算法和混沌粒子群算法来编写映射算法。按照编写的映射算法将任务数据先向内核映射，再将内核向网络节点映射来完成仿真；仿真结果表明：相比于遗传算法和蚁群算法，基于混沌粒子群的映射算法在功耗、延时整体性能以及收敛效果方面都比较好。
　　论文完成了三维片上网络映射算法设计及仿真验证。论文工作对三维片上网络映射算法的研究有一定的参考意义。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

缩略语对照表

目录

第一章 绪论

1.1研究背景

1.2 国内外研究现状

1.3 论文的主要内容及结构安排

第二章 三维片上网络关键技术研究

2.1 片上网络的拓扑结构

2.2 交换技术

2.3 路由策略

2.4 片上网络映射方法

2.5 本章小结

第三章 基于三维片上网络的映射算法分析

3.1 片上网络性能模型

3.2 基于遗传的映射算法分析与实现

3.3 基于蚁群的映射算法分析与实现

3.4 粒子群算法

3.5 本章小结

第四章 基于混沌粒子群的三维片上网络映射算法

4.1 粒子群算法的基本操作

4.2 目标函数设计

4.3 混沌扰动

4.4 映射算法流程

4.5 本章小结

第五章 算法仿真与测试

5.1 算法的仿真环境

5.2 任务及内核信息生成

5.3 仿真设置

5.4 算法仿真结果与分析

5.5 本章小结

第六章 总结和展望

参考文献

致谢

作者简介