路径规划算法的高层综合设计研究

赖李洋; 郑锫骏; 梁海成; 李华伟

doi:10.11999/JEIT240210

路径规划算法的高层综合设计研究

doi: 10.11999/JEIT240210

1.
汕头大学电子系汕头 515063
2.
中国科学院计算技术研究所计算机体系结构国家重点实验室北京 100190

基金项目: 国家自然科学基金(62090024)，广东省自然科学基金(2022A1515011084)，广东省扬帆计划紧缺拔尖人才项目(140-14600602)，计算机体系结构国家重点实验室开放课题(CARCH201912, 140-15220011)

详细信息

作者简介:
赖李洋：男，副教授，硕士生导师，博士，研究方向为集成电路可测试性设计、电子设计自动化、容错计算、芯片设计

郑锫骏：男，硕士生，研究方向为FPGA设计、集成电路可测试性设计

梁海成：男，硕士，研究方向为FPGA设计、电子设计自动化

李华伟：女，研究员，博士生导师，博士，研究方向为数字电路设计自动化、测试验证、智能计算、近似计算

通讯作者:
赖李洋　lylai@stu.edu.cn

中图分类号: TN47; TP391.72
计量
- 文章访问数: 181
- HTML全文浏览量: 80
- PDF下载量: 23
- 被引次数: 0
出版历程
- 收稿日期: 2024-03-27
- 修回日期: 2024-06-15
- 网络出版日期: 2024-06-19
- 刊出日期: 2024-11-01

Case Study of High Level Synthesis on Path Planning Algorithm

1.
Department of Electronics and Information Engineering, Shantou University, Shantou 515063, China
2.
State key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

Funds: The National Natural Science Foundation of China(62090024), The Natural Science Foundation of Guangdong Province(2022A1515011084), Guangdong Province Yangfan Program for Shortage and Top-notch Talents (140-14600602), Open Project of State Key Laboratory of Computer Architecture (CARCH201912, 140-15220011)

摘要

摘要: 随着机器人自动导航技术的快速发展，基于软件实现的路径规划算法在实时性上已无法满足许多应用场景的需求，这就要求对算法进行快速高效的硬件定制，从而获得低延时的性能加速。该文以机器人路径规划中的经典A*算法为对象，通过构建面向硬件设计的C/C++数据结构和函数流程优化，采用高层综合(HLS)实现快速的硬件架构探索和选取较优的设计方案，并完成硬件FPGA综合。实验数据表明，相较于传统寄存器传输级(RTL)开发模式，基于HLS开发模式的路径规划算法在FPGA实现上在开发效率、硬件性能和资源占用率上都有显著提升，验证了高层综合在硬件定制中的可行性和成本优势。
- 机器人自动导航 /
- 路径规划算法 /
- 高层综合 /
- 算法硬件加速
Abstract: With the advancement of robot automatic navigation technology, software-based path planning algorithms can no longer satisfy the needs in scenarios of many real-time applications. Fast and efficient hardware customization of the algorithm is required to achieve low-latency performance acceleration. In this work, High Level Synthesis (HLS) of classic A* algorithm is studied. Hardware-oriented data structure and function optimization, varying design constraints are explored to pick the right architecture, which is then followed by FPGA synthesis. Experimental results show that, compared to the conventional Register Transfer Level (RTL) method, the HLS-based FPGA implementation of the A* algorithm can achieve better productivity, improved hardware performance and resource utilization efficiency, which demonstrates the advantages of high level synthesis in hardware customization in algorithm-centric applications.
- Robot automatic navigation /
- Path panning algorithm /
- High Level Synthesis(HLS) /
- Hardware acceleration

HTML全文

图 1 实现高层综合的基本流程

下载: 全尺寸图片幻灯片

图 2 切片函数的读操作示意图

下载: 全尺寸图片幻灯片

图 3 格点信息的数据结构

下载: 全尺寸图片幻灯片

图 4 开启列表数组

下载: 全尺寸图片幻灯片

图 5 原始算法中的开启列表操作

下载: 全尺寸图片幻灯片

图 6 开启列表操作优化

下载: 全尺寸图片幻灯片

图 7 优先级队列实现的地图路径

下载: 全尺寸图片幻灯片

图 8 堆栈实现的地图路径

下载: 全尺寸图片幻灯片

图 9 队列实现的地图路径

下载: 全尺寸图片幻灯片

图 10 地图样式1

下载: 全尺寸图片幻灯片

图 11 地图样式2

下载: 全尺寸图片幻灯片

图 12 地图样式3

下载: 全尺寸图片幻灯片

图 13 地图样式4

下载: 全尺寸图片幻灯片

1 A*算法的基本流程

(1)初始化开启列表和关闭列表为空
(2)将七点插入开启列表中
(3)while(开启列表不为空)
(4) 从开启列表中取出最小F值的格点作为当前格点，并将之加　　入关闭列表
(5) 　foreach(当前格点的相邻格点)
(6) 　　if(该格点在关闭列表中或是故障格点) then(跳过该格点)
(7) 　　elsif(该格点在开启列表中) then(比较通过当前格点计算　　　　得出的F值是否更小，若更小则更新该格点的F值，设其　　　　父节点为当前节点，并将之插入开启列表)
(8) 　　elsif(该格点不在开启列表中) then(通过当前节点计算该　　　　节点的F值，设其父亲节点为当前节点，并将之插入开启　　　　列表)
(9) 　　elsif(该格点为终点) then(设其父节点为当前节点，并通　　　　过追踪父节点链条至起点，输出起点到终点的路径，算　　　　法结束)
(10) end_foreach
(11)end_while
(12)if(开启列表为空) then(路径搜索失败)

下载: 导出CSV

表 1 SOC FPGA 芯片 PL 资源

资源名称	总数
逻辑单元 LUT	87 840
LUTRAM	57 600
触发器 Flip-flop(FF)	175 680
BRAM	128
I/O 引脚	256
全局时钟缓冲器 BUFG	352

下载: 导出CSV

表 2 15×15地图下不同开启列表优化比较

数据结构	LUT个数	FF个数	BRAM个数	运行时长(ns)
优先队列	2 485	2 807	3.0	18 598
队列	2 137	2 755	2.5	44 325
堆栈	2 148	2 739	2.5	38 779

下载: 导出CSV

表 3 使用优先队列数据结构的HLS和RTL开发模式比较

FPGA开发模式	运行时间(ns)	LUT个数	FF个数	BRAM个数
HLS	483 445	3 208	3 303	34.5
RTL	523 046	7 253	7 161	59.5

下载: 导出CSV

表 4 使用堆栈数据结构的HLS和RTL开发模式比较

FPGA开发模式	运行时间(ns)	LUT个数	FF个数	BRAM个数
HLS	3 305 830	1 669	1 523	25
RTL	5 987 348	7 313	7 065	56

下载: 导出CSV

表 5 使用队列数据结构的HLS和RTL开发模式比较

FPGA开发模式	运行时间(ns)	LUT个数	FF个数	BRAM个数
HLS	3 389 425	1 756	1 555	25
RTL	5 598 080	7 317	7 053	56

下载: 导出CSV

参考文献(17)

[1]	郑岩. 改进势场蚁群算法的机器人自主导航应用研究[D]. [硕士论文], 重庆三峡学院, 2020. doi: 10.27883/d.cnki.gcqsx.2020.000061. ZHENG Yan. Application of improved potential field ant colony algorithm for autonomous robot navigation[D]. [Master dissertation], Chongqing Three Gorges University, 2020. doi: 10.27883/d.cnki.gcqsx.2020.000061.
[2]	郭炜, 魏继增, 郭筝, 等. SoC设计方法与实现[M]. 3版. 北京: 电子工业出版社, 2017: 23–24. GUO Wei, WEI Jizeng, GUO Zheng, et al. SoC Design Methodology and Implementation[M]. 3rd ed. Beijing: Publishing House of Electronics Industry, 2017: 23–24.
[3]	陈志盛, 朱予涵, 刘耿耿, 等. 考虑流端口数量约束下的连续微流控生物芯片流路径规划算法[J]. 电子与信息学报, 2023, 45(9): 3321–3330. doi: 10.11999/JEIT221168. CHEN Zhisheng, ZHU Yuhan, LIU Genggeng, et al. Flow-path planning algorithm for continuous-flow microfluidic biochips with strictly constrained flow ports[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3321–3330. doi: 10.11999/JEIT221168.
[4]	CORMEN T H, LEISERSON C E, RIVEST R L, 等, 殷建平, 徐云, 王刚, 等. 译. 算法导论[M]. 3版. 北京: 机械工业出版社, 2013: 374–376. CORMEN T H, LEISERSON C E, RIVEST R L, et al, YIN Jianping, XU Yun, WANG Gang, et al. translation. Introduction to Algorithms[M]. 3rd ed. Beijing: China Machine Press, 2013: 374–376.
[5]	ABDOKASEB. A C Program to implement A* Search Algorithm[EB/OL]. https://github.com/abdokaseb/AStar-C/, 2022.
[6]	Mentor, A Siemens Business. HLS Bluebook[M]. Software Version v10. 5b, 2020.
[7]	ALTOYAN W and ALONSO J J. Investigating performance losses in high-level synthesis for stencil computations[C]. 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines, Fayetteville, USA, 2020: 195–203. doi: 10.1109/FCCM48280.2020.00034.
[8]	潘妍, 程岳, 高雅濛. 面向FPGA的高层次综合技术综述[J]. 信息技术与信息化, 2022(3): 96–99. DOI: 10.3969/j.issn.1672-9528.2022.03.024. PAN Yan, CHENG Yue, and GAO Yameng. An overview of high-level synthesis techniques for FPGAs[J]. Information Technology and Informatization, 2022(3): 96–99. DOI: 10.3969/j.issn.1672-9528.2022.03.024.
[9]	石添介, 刘飞阳, 田径, 等. 基于高层次综合的FPGA循环神经网络加速器设计[J]. 信息技术与信息化, 2022(1): 151–153. DOI: 10.3969/j.issn.1672-9528.2022.01.042. SHI Tianjie, LIU Feiyang, TIAN Jing, et al. Design of FPGA recurrent neural network accelerator based on high-level synthesis[J]. Information Technology and Informatization, 2022(1): 151–153. DOI: 10.3969/j.issn.1672-9528.2022.01.042.
[10]	叶海雄, 陶宁蓉, 匡兴红, 等. 基于Catapult C高层次综合工具平台优化运动检测算法的研究[J]. 电子设计工程, 2017, 25(14): 1–4. doi: 10.14022/j.cnki.dzsjgc.2017.14.001. YE Haixiong, TAO Ningrong, KUANG Xinghong, et al. Optimization motion detection algorithm based on Catapult C high-level synthesis tool platform[J]. Electronic Design Engineering, 2017, 25(14): 1–4. doi: 10.14022/j.cnki.dzsjgc.2017.14.001.
[11]	徐瑞帆, 肖有为, 罗进, 等. 高层次综合综述[J]. 微纳电子与智能制造, 2021, 3(2): 74–79. doi: 10.19816/j.cnki.10-1594/tn.2021.02.074. XU Ruifan, XIAO Youwei, LUO Jin, et al. The overview of high-level synthesis[J]. Micro/Nano Electronics and Intelligent Manufacturing, 2021, 3(2): 74–79. doi: 10.19816/j.cnki.10-1594/tn.2021.02.074.
[12]	PANDA P R, SHARMA N, KURRA S, et al. Exploration of loop unroll factors in high level synthesis[C]. 2018 31st International Conference on VLSI Design and 2018 17th International Conference on Embedded Systems. Pune, India, 2018: 465–466. doi: 10.1109/VLSID.2018.115.
[13]	谢晓燕, 张玉婷, 刘镇弢. 高层次综合特征检测算法的FPGA实现[J]. 实验室研究与探索, 2018, 37(1): 93–97,117. doi: 10.3969/j.issn.1006-7167.2018.01.023. XIE Xiaoyan, ZHANG Yuting, and LIU Zhentao. FPGA implementation of feature detection algorithm based on high level synthesis[J]. Research and Exploration in Laboratory, 2018, 37(1): 93–97,117. doi: 10.3969/j.issn.1006-7167.2018.01.023.
[14]	申懿鑫, 韩跃平, 唐道光. 高层次综合的SM4算法硬件实现与优化[J]. 单片机与嵌入式系统应用, 2023, 23(8): 11–14. SHEN Yixin, HAN Yueping, and TANG Daoguang. hardware implementation and optimization of SM4 algorithm based on high-level synthesis[J]. Microcontrollers & Embedded Systems, 2023, 23(8): 11–14.
[15]	周成瑞, 杨玲玲. 基于A星算法的全向移动机器人仿真研究[J]. 电脑与信息技术, 2023, 31(3): 29–31. doi: 10.3969/j.issn.1005-1228.2023.03.008. ZHOU Chengrui and YANG Lingling. Simulation research on omnidirectional mobile robot based on A* algorithm[J]. Computer and Information Technology, 2023, 31(3): 29–31. doi: 10.3969/j.issn.1005-1228.2023.03.008.
[16]	王小丽. 基于Vivado HLS雾天图像预处理IP核设计[J]. 电脑编程技巧与维护, 2023(4): 158–161. doi: 10.16184/j.cnki.comprg.2023.04.020. WANG Xiaoli. Vivado HLS foggy sky image preprocessing IP core based design[J]. Computer Programming Skills & Maintenance, 2023(4): 158–161. doi: 10.16184/j.cnki.comprg.2023.04.020.
[17]	韦苏伦, 陶青川. 基于HLS的MobileNet加速器实现[J]. 现代计算机, 2023, 29(8): 91–97. doi: 10.3969/j.issn.1007-1423.2023.08.015. WEI Sulun and TAO Qingchuan. Realization of MobileNet accelerator based on HLS[J]. Modern Computer, 2023, 29(8): 91–97. doi: 10.3969/j.issn.1007-1423.2023.08.015.