基于可重构架的动态网络路径规划算法研究与实现

发布时间：2017-04-27 02:08

  本文关键词：基于可重构架的动态网络路径规划算法研究与实现，由笔耕文化传播整理发布。

【摘要】：最短路径规划问题是一个经典的数学问题,广泛应用于多种与路径规划技术相关的领域。例如：科技领域中的无人驾驶汽车、无人机、智能机器人、巡航导弹打击目标与导弹防御系统；日常生活领域中的智能汽车导航、地理信息系统；决策调控领域中的物流规划领域边际问题和资源合理分配问题；通信技术领域中的路由规划问题等。随着人类社会的发展和科技的不断进步,社会近百年的科技成就大大超过了人类社会以往几千年的成就总和。现代城市规模之巨大,路网之复杂,处理的数据量也随之增加；例如：纽约市路网地图就包含了26万个节点,73万条边.面对大规模的路网数据量,传统的最短路径规划算法在求解时耗时较长,不能满足应用中的实时性要求。可重构处理器与GPP (General Purpose Processor,通用处理器)相比,可重构计算架构的数据并行性度高,数据处理能力强,它不依赖于指令流的数据处理方式,而是基于数据流的并行处理,在算法的合适映射下,可以充分挖掘路径规划算法并行度高的特点,发挥其并行处理的优势。它与ASIC (Application Specific Integrated Circuit,专用集成电路)相比,可重构处理器具有灵活多变的硬件架构,来适应软件层次上改变相关的运算,从而适应不同的算法。本文利用可重构技术的硬件架构,从经典的路径网络规划算法特点出发,得到可重构体系基本机构为阵列形式,再通过对经典算法的任务划分映射,得到相对应的数据流图和调度表。这样就实现了在可重构硬件阵列处理单元上对算法的映射实现,最后把优化后的算法在可重构硬件平台的执行,并对其性能进行验证。这样设计方式可实现对不同算法的硬件重复利用,而且其设计流程同样适用于其它的网图领域。本文主要特色性研究成果是：(1)提出基于可重构技术的路径规划算法加速处理方法；利用可重构硬件平台的动态可配置性与并行性,分别结合经典Dijkstra算法和TSP算法,得到了一种针对路径规划算法的新型加速处理方法。(2)在可重构硬件架构平台上完成了Dijkstra算法和TSP算法的实现和验证,与通用计算平台相比,分别获得了2.1倍与3.2倍的加速比。通过对经典Dijkstra和TSP算法的并行优化,分析其内部数据结构的依赖关系,划分成适合于可重构阵列上面执行的任务,可大大的降低了原算法的时间复杂度与空间复杂度,从而获得了一定的加速比。
【关键词】：路径规划算法 可重构 并行算法 Dijkstra算法 TSP算法
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-11
• 1 引言11-19
• 1.1 论文研究背景及其意义11-12
• 1.2 可重构计算系统简介12-16
• 1.2.1 重构计算系统概述13-14
• 1.2.2 可重构计算体系的国内外研究现状14-15
• 1.2.3 可重构计算系统的优势15-16
• 1.3 本文研究内容和创新工作16-17
• 1.4 论文组织结构17-19
• 2 可重构硬件架构技术研究19-27
• 2.1 可重构硬件结构综述19-20
• 2.2 可重构处理硬件架构20-22
• 2.2.1 可重构阵列执行流程21-22
• 2.2.2 可重构架构存储22
• 2.3 可重构处理阵列PEA22-25
• 2.3.1 执行流程23
• 2.3.2 阵列单元Router23-24
• 2.3.3 可重构阵列PE执行流程24-25
• 2.4 ALU概述25-26
• 2.5 本章小结26-27
• 3 基于可重构硬件架构的动态路径规划算法的加速研究27-39
• 3.1 路径规划算法的可重构并行技术实现27-30
• 3.1.1 并行算法基础概述28-29
• 3.1.2 可重构计算框架基本原理29
• 3.1.3 可重构任务并行过程29-30
• 3.2 可重构的动态路径技术实现框架30-31
• 3.3 可重构的动态路径规划算法与其他优化算法的比较31
• 3.4 DIJKSTRA算法的可重构架构设计31-35
• 3.4.1 DIJKSTRA算法原理31-34
• 3.4.2 基于可重构架构的DIJKSTRA算法并行化分析34-35
• 3.5 TSP算法的可重构架构设计35-37
• 3.5.1 TSP算法原理35-37
• 3.5.2 基于可重构架构的TSP算法并行化分析37
• 3.6 本章小结37-39
• 4 基于可重构架构的动态路径规划算法优化与实现39-49
• 4.1 算法映射概念39-40
• 4.2 验证工具链及平台40-42
• 4.3 基于可重构硬件架构的DIJKSTRA算法优化与实现42-45
• 4.3.1 可重构硬件架构的DIJKSTRA算法优化42-43
• 4.3.2 可重构硬件架构的DIJKSTRA算法的映射实现43-45
• 4.4 基于可重构硬件架构的TSP算法优化与实现45-48
• 4.4.1 可重构硬件架构的TSP算法的优化45-46
• 4.4.2 可重构硬件架构的TSP算法的实现46-48
• 4.5 本章小结48-49
• 5 可重构硬件架构的路径规划算法性能分析与比较49-64
• 5.1 实验验证平台49-51
• 5.2 实验研究方法51-53
• 5.3 基于可重构硬件架构下的DIJKSTRA算法性能验证53-59
• 5.3.1 实验验证步骤53-56
• 5.3.2 实验结果分析与比较56-59
• 5.4 基于可重构硬件架构的TSP算法性能验证59-63
• 5.4.1 实验验证步骤59-61
• 5.4.2 实验结果分析与比较61-63
• 5.5 本章小结63-64
• 6 结束语64-66
• 6.1 论文工作总结64-65
• 6.2 问题与展望65-66
• 参考文献66-69
• 作者简历69-71
• 学位论文数据集71

【相似文献】

中国期刊全文数据库 前10条

1 禹建丽,VALERIKroumov,成久洋之;机器人路径规划算法及其应用(英文)[J];数学季刊;2002年03期

2 王力虎,张海洪;一种室内自主清扫机器人的路径规划算法[J];机床与液压;2005年07期

3 刘海;郭小勤;余得贵;;清洁机器人全覆盖路径规划算法综述[J];机电产品开发与创新;2008年06期

4 杨志晓;郭胜国;;基于改进蚁群算法的机器人路径规划算法[J];微计算机信息;2008年20期

5 孙立光;史其信;;基于离散势能场的行人路径规划算法研究[J];交通标准化;2009年23期

6 马文辉;崔莹;;云模型在机器人路径规划算法中的研究[J];知识经济;2010年14期

7 马占春;宁小美;;云进化机器人路径规划算法[J];科技通报;2012年10期

8 陈书光;;机器人路径规划算法探讨[J];商;2012年15期

9 王伟，储林波，马玉林;一种改进的机器人路径规划算法[J];哈尔滨工业大学学报;1998年02期

10 宁志刚;;一种高效的机器人路径规划算法[J];科技致富向导;2011年18期

中国重要会议论文全文数据库 前6条

1 汪永红;刘小春;张有为;侯一凡;;嵌入式GIS中大区域路径规划算法研究[A];《测绘通报》测绘科学前沿技术论坛摘要集[C];2008年

2 原晓伟;任雪梅;;参数自调整的机器人路径规划算法[A];第二十三届中国控制会议论文集（下册）[C];2004年

3 涂自然;王维;梁以业;禹建丽;;基于强化学习的自适应变步长机器人路径规划算法[A];2003年中国智能自动化会议论文集（上册）[C];2003年

4 雷东升;诸彤宇;;一种基于实时路况信息的动态路径规划算法[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

5 史久根;徐胜生;;基于文化-粒子群算法的机器人路径规划算法[A];2011中国仪器仪表与测控技术大会论文集[C];2011年

6 王仲宾;魏闯先;田卫东;周红娟;;一种改进的基于切线的机器人路径规划算法[A];计算机技术与应用进展——全国第17届计算机科学与技术应用（CACIS）学术会议论文集（上册）[C];2006年

中国博士学位论文全文数据库 前1条

1 彭飞;约束条件下的船舶装配拆卸随机采样路径规划研究[D];华中科技大学;2013年

中国硕士学位论文全文数据库 前10条

1 王亚春;移动机器人路径规划算法研究[D];天津理工大学;2015年

2 杜沅泽;人群动画中融入情绪模型的实时路径规划算法研究[D];郑州大学;2015年

3 李骏豪;针对复杂环境的室内路径规划算法的设计与实现[D];电子科技大学;2014年

4 谢娟;路径规划算法的研究及应用[D];电子科技大学;2015年

5 刘军强;一种飞行器导航算法研究及其系统设计[D];西安电子科技大学;2014年

6 张琪;分队战术CGF路径规划算法研究[D];国防科学技术大学;2013年

7 孙首兵;基于RFID技术的仓库数字货架的研究与开发[D];合肥工业大学;2014年

8 王腾飞;3D打印技术中分层与路径规划算法的研究及实现[D];河北工业大学;2015年

9 柏强;基于可重构架的动态网络路径规划算法研究与实现[D];北京交通大学;2016年

10 陈峰;环境搜索与路径规划算法的研究[D];吉林大学;2012年

  本文关键词：基于可重构架的动态网络路径规划算法研究与实现，，由笔耕文化传播整理发布。

本文编号：329691