Case Study of High Level Synthesis on Path Planning Algorithm

LAI Liyang; ZHENG Peijun; LIANG Haicheng; LI Huawei

doi:10.11999/JEIT240210

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2022 >

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

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

PDF( 2600 KB)

Case Study of High Level Synthesis on Path Planning Algorithm

doi: 10.11999/JEIT240210

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)

Received Date: 2024-03-27
Rev Recd Date: 2024-06-27

Available Online: 2024-06-19

Abstract

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.
- Automatic navigation,
- Path panning algorithm,
- High Level Synthesis(HLS),
- Hardware acceleration

FullText(HTML)

References(17)

References

[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]. Proceedings of 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]. Proceedings of 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.