高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

赖李洋, 郑锫骏, 梁海成, 李华伟. 路径规划算法的高层综合设计研究[J]. 电子与信息学报. doi: 10.11999/JEIT240210
引用本文: 赖李洋, 郑锫骏, 梁海成, 李华伟. 路径规划算法的高层综合设计研究[J]. 电子与信息学报. doi: 10.11999/JEIT240210
LAI Liyang, ZHENG Peijun, LIANG Haicheng, LI Huawei. Case Study of High Level Synthesis on Path Planning Algorithm[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240210
Citation: LAI Liyang, ZHENG Peijun, LIANG Haicheng, LI Huawei. Case Study of High Level Synthesis on Path Planning Algorithm[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240210

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

doi: 10.11999/JEIT240210
基金项目: 国家自然科学基金(62090024),广东省自然科学基金(2022A1515011084),广东省扬帆计划紧缺拔尖人才项目(140-14600602),计算机体系结构国家重点实验室开放课题(CARCH201912, 140-15220011)
详细信息
    作者简介:

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

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

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

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

    通讯作者:

    赖李洋 lylai@stu.edu.cn

  • 中图分类号: TN47; TP391.72

Case Study of High Level Synthesis on Path Planning Algorithm

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实现上在开发效率、硬件性能和资源占用率上都有显著提升,验证了高层综合在硬件定制中的可行性和成本优势。
  • 图  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 资源

    资源名称总数
    逻辑单元 LUT87 840
    LUTRAM57 600
    触发器 Flip-flop(FF)175 680
    BRAM128
    I/O 引脚256
    全局时钟缓冲器 BUFG352
    下载: 导出CSV

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

    数据结构LUT个数FF个数BRAM个数运行时长(ns)
    优先队列2 4852 8073.018 598
    队列2 1372 7552.544 325
    堆栈2 1482 7392.538 779
    下载: 导出CSV

    表  3  同为优先队列数据结构下HLS和传统FPGA开发模式比较

    FPGA开发模式运行时间(ns)LUT个数FF个数BRAM个数
    HLS483 4453 2083 30334.5
    RTL523 0467 2537 16159.5
    下载: 导出CSV

    表  4  同为堆栈数据结构下HLS和传统FPGA开始模式比较

    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和传统FPGA开发模式比较

    FPGA开发模式 运行时间(ns) LUT个数 FF个数 BRAM个数
    HLS 3 389 425 1 756 1 555 25
    RTL 5 598 080 7 317 7 053 56
    下载: 导出CSV
  • [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 Gangyi, 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.
  • 加载中
图(13) / 表(6)
计量
  • 文章访问数:  125
  • HTML全文浏览量:  64
  • PDF下载量:  17
  • 被引次数: 0
出版历程
  • 收稿日期:  2024-03-27
  • 修回日期:  2024-06-15
  • 网络出版日期:  2024-06-19

目录

    /

    返回文章
    返回