电子学报 ›› 2022, Vol. 50 ›› Issue (5): 1243-1254.DOI: 10.12263/DZXB.20210637

所属专题: 长摘要论文

• 综述评论 • 上一篇    下一篇

面向FPGA的布局与布线技术研究综述

田春生1,2, 陈雷2, 王源1, 王硕2, 周婧2, 张瑶伟2, 庞永江2, 周冲2, 马筱婧2, 杜忠2, 薛钰2   

  1. 1.北京大学信息科学技术学院微纳电子学系,北京 100871
    2.北京微电子技术研究所,北京 100076
  • 收稿日期:2021-05-18 修回日期:2021-08-24 出版日期:2022-05-25
    • 通讯作者:
    • 陈雷
    • 作者简介:
    • 田春生 男,1993年生于吉林梅河口.现为北京大学信息科学技术学院与北京微电子技术研究所联合博士后.主要研究方向为集成电路自动化设计.E-mail: tiancs@pku.edu.cn
      陈 雷 男,1978年生于安徽淮南.现为北京微电子技术研究所研究员,硕士生导师.主要研究方向为超大规模集成电路设计.E-mail: chenleinpu@vip.126.com
      王 源 男,1979年生于陕西扶风.现为北京大学教授,博士生导师.主要研究方向为大规模集成电路设计.E-mail: wangyuan@pku.edu.cn
      王 硕 男,1985年生于河南南阳.现为北京微电子技术研究所高级工程师.主要研究方向为FPGA布局布线算法和FPGA软错误缓解技术.E-mail: 66188893@qq.com
      周 婧 女,1986年生于山东烟台,现为北京微电子技术研究所高级工程师,主要研究方向为FPGACAD工具研发.E-mail: zhoujenny0915@126.com
      张瑶伟 男,1997年生于山西运城.现为中国运载火箭技术研究院电子科学与技术硕士研究生.主要研究方向为FPGA的三模冗余、高层次综合技术.E-mail: zyw18810532787@163.com
    • 基金资助:
    • 国家自然科学基金 (U20A20204); 国家科技重大专项 (2009ZYHJ0005)

Review on Technology of Placement and Routing for the FPGA

TIAN Chun-sheng1,2, CHEN Lei2, WANG Yuan1, WANG Shuo2, ZHOU Jing2, ZHANG Yao-wei2, PANG Yong-jing2, ZHOU Chong2, MA Xiao-jing2, DU Zhong2, XUE Yu2   

  1. 1.Department of Micro/nanoelectronics, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
    2.Beijing Microelectronics Technology Institute, Beijing 100076, China
  • Received:2021-05-18 Revised:2021-08-24 Online:2022-05-25 Published:2022-06-18
    • Corresponding author:
    • CHEN Lei
    • Supported by:
    • National Natural Science Foundation of China (U20A20204); National Science and Technology Major Project of the Ministry of Science and Technology (2009ZYHJ0005)

摘要:

随着大规模集成电路器件复杂度与容量的不断提升,现场可编程门阵列(Field Programmable Gate Array, FPGA)以高度的并行、可定制和可重构的特性得到了广泛的关注与应用. 在制约FPGA发展的众多因素中,最为关键的便是电子设计自动化(Electronic Design Automation, EDA)技术,作为FPGA EDA流程中的关键环节,布局和布线技术的研究对于FPGA的重要性不言而喻. 本文综述了面向FPGA的布局和布线技术,包括基于划分的布局、基于启发式的布局、基于解析式的布局、FPGA串行布线和FPGA并行布线等技术,分析对比了不同技术方法的优缺点,在此基础上,本文还展望了未来FPGA布局和布线技术的发展趋势,将为FPGA未来健康可持续的发展提供有力支撑.

长摘要
现场可编程门阵列(FPGA)又被称为集成电路领域的“变形金刚”,作为一种半定制电路,一经面世便被广泛应用于现代数字系统的设计中。随着各种新兴技术的不断涌现,FPGA的应用范围也在逐步从普通的消费电子向物联网、高性能运算、人工智能以及航空航天等领域不断拓展。在制约FPGA发展的众多因素中,最为关键的便是电子设计自动化(EDA)技术,如图画家之笔、渡河之舟,没有EDA,FPGA的发展将寸步难行。布局与布线作为FPGA EDA工具设计流程中两个至关重要的环节,同时也是设计流程中最耗时的步骤,其最终结果直接决定了所设计的电路在FPGA芯片上实现后的性能。因此,布局和布线技术的研究对于FPGA的健康可持续发展具有重大的意义。本文从方法论的角度探讨了FPGA的布局与布线方法,结合基于划分的布局、基于启发式的布局、基于解析式的布局、FPGA串行布线和FPGA并行布线等关键技术对近年来国内外研究人员做出的努力进行了回顾,分析对比了不同技术方法的优缺点,并在此基础上,从人工智能技术对FPGA布局和布线流程的优化、探索多驱动的布局和布线策略以及研究更加简单可行的并行加速方法三个方面对未来的发展趋势进行展望,以期为本领域及相关领域的专家和学者提供参考。

关键词: 现场可编程门阵列, 电子设计自动化, 布局, 布线, 并行计算

Abstract:

With the continuous increase in the complexity and capacity of large-scale integrated circuit devices, field programmable gate array(FPGA) has received extensive attention and applications for its high degree of concurrency, customizable and reconfigurable features. Among the many factors that restrict the development of FPGA, the most critical is electronic design automation(EDA) technology. As a key link in the FPGA EDA process, the importance of placement and routing technology for FPGA is self-evident. This article reviews the technology of placement and routing for the FPGA, including partition-based placement, heuristic-based placement, analytical-based placement, FPGA serial routing and FPGA parallel routing. The advantages and disadvantages of different technologies are analyzed and compared. On this basis, the development trend of FPGA placement and routing technology in the future is also prospected, which will provide strong support for the healthy and sustainable development of FPGAs.

Extended Abstract
Field Programmable Gate Array (FPGA) is also known as the “Transformer” in the field of integrated circuits. As a semi-custom circuit, it has been widely used in the design of modern digital systems as soon as it comes out. After more than 30 years of development, FPGA has embedded a variety of IP cores, integrated millions of logic cells, and contains billions of transistors. The advantages of FPGA are high degree of concurrency, short development cycle, and the ability to reconfigure and implement different functions at any time, eliminating the long waiting cycle of user-customized Application Specific Integrated Circuit (ASIC) and the huge cost risk that needs to be borne. FPGAs are widely used in modern digital systems, such as mobile phones, aerospace, communication equipment, automotive electronics, home applications, satellites and other fields, and the scope of FPGA applications continues to expand. With the development of various emerging technologies, the application scope of FPGA has expanded from ordinary consumer electronics to smart grids, high-performance computing, Internet of Things (IoTs), Artificial Intelligence (AI) and other fields. Among the many factors that restrict the development of FPGA, the most critical is Electronic Design Automation (EDA) technology, such as the pen of a graphic artist and the boat of crossing the river. Without EDA, the development of FPGA will be impossible. When using FPGA to design a system, the user first uses a Hardware Description Language (HDL) to describe the circuit or system function to be implemented in next. Then, the FPGA EDA software tool is used to compile the circuit step by step, and finally convert the circuit into the form of binary code stream. Finally, the binary code stream is used to configure the state of devices such as switches and Look-Up Tables (LUT) inside the FPGA, so as to realize the target circuit or system function on the FPGA chip. Due to the improvement of FPGA integration and increase in the scale of modern FPGA circuits, it takes longer and longer for FPGA EDA software to compile the circuit into binary code stream. FPGA EDA software has fallen behind the rapid development of FPGA hardware. The design process of FPGA EDA tools mainly includes design input, behavior synthesis, logic mapping, packing, placement, routing and binary code stream generation. Among them, placement and routing are the most import steps in the design process, and they are also the most time-consuming steps. The final result of placement and routing directly determines the performance of the design circuit after it is implemented on the FPGA. Therefore, the research of placement and routing technology is of great significance to the healthy and sustainable development of FPGA. In this article, we categorize all methods of placement and routing for the FPGA by different grouping criteria and evaluate their performance from the methodological point of view. For the technology of placement for the FPGA, the first category of methods is the partition-based placement method, which refers to the partition of placement instances through continuous recursive iterations on the basis of the most original placement instances based on the known placement constraints, until all the placement instances are less than the preset threshold. The second uses some natural phenomena in the existing scientific fields as design principles to model the placement process of FPGA heterogeneous logic cells. The last category of methods is the analytical-based placement approach, which formulate the placement as a more sophisticated continuous optimization problem and solve it using various principled gradient descent methods. For the technology of routing for the FPGA, there are two categories, serial and parallel routing methods. The advantages and disadvantages of different technologies are analyzed and compared. On this basis, the future development trend is prospected from three aspects: optimization of FPGA placement and routing process by artificial intelligence technology, exploration of multi-driver placement and routing strategies, and research on more simple and feasible parallel acceleration methods, with a view to providing reference for experts and scholars in this field and related fields.

Key words: field programmable gate arrays, electronic design automation, placement, routing, parallel computing

中图分类号: