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

doi:10.12263/DZXB.20210637

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

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

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

^1.北京大学信息科学技术学院微纳电子学系，北京 100871
^2.北京微电子技术研究所，北京 100076

收稿日期:2021-05-18 修回日期:2021-08-24 出版日期:2022-05-25 发布日期:2022-06-18
通讯作者: 陈雷
作者简介:田春生男，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-sheng¹^,², CHEN Lei², WANG Yuan¹, WANG Shuo², ZHOU Jing², ZHANG Yao-wei², PANG Yong-jing², ZHOU Chong², MA Xiao-jing², DU Zhong², XUE Yu²

^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
Contact: CHEN Lei

摘要/Abstract

摘要：

随着大规模集成电路器件复杂度与容量的不断提升，现场可编程门阵列（Field Programmable Gate Array, FPGA）以高度的并行、可定制和可重构的特性得到了广泛的关注与应用. 在制约FPGA发展的众多因素中，最为关键的便是电子设计自动化（Electronic Design Automation, EDA）技术，作为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.

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

中图分类号:

TN47

田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243-1254.

TIAN Chun-sheng, CHEN Lei, WANG Yuan, WANG Shuo, ZHOU Jing, ZHANG Yao-wei, PANG Yong-jing, ZHOU Chong, MA Xiao-jing, DU Zhong, XUE Yu. Review on Technology of Placement and Routing for the FPGA[J]. Acta Electronica Sinica, 2022, 50(5): 1243-1254.

图/表 5

参考文献 85

1	TRIMBERGER S M. Three ages of FPGAs: A retrospective on the first thirty years of FPGA technology[J]. Proceedings of the IEEE, 2015, 103(3): 318‑331.
2	TRIMBERGER S M. Three ages of FPGAs: a retrospective on the first thirty years of FPGA technology: this paper reflects on how Moore's law has driven the design of FPGAs through three epochs: the age of invention, the age of expansion, and the age of accumulation[J]. IEEE Solid-State Circuits Magazine, 2018, 10(2): 16‑29.
3	IMANI M, ZOU Z W, BOSCH S, et al. Revisiting hyperdimensional learning for FPGA and low-power architectures[C]//2021 IEEE International Symposium on High-Performance Computer Architecture(HPCA). South Korea: IEEE, 2021: 221‑234.
4	ZHANG J X, YANG T, LI Q Z, et al. An FPGA-based neural network overlay for ADAS supporting multi-model and multi-mode[C]//2021 IEEE International Symposium on Circuits and Systems(ISCAS). South Korea: IEEE, 2021: 1‑5.
5	KAN H W, LI R G, SU D D, et al. Trusted edge cloud computing mechanism based on FPGA cluster[C]//2020 IEEE 8th International Conference on Computer Science and Network Technology(ICCSNT). China: IEEE, 2020. 146‑149.
6	刘公绪, 史凌峰, 辛东金. 基于FPGA的零误差大数阶乘算法的设计与实现[J]. 电子学报, 2019, 47(5): 1180‑1184.
	LIU G X, SHI L F, XIN D J. FPGA-based zero-error factorial algorithm for large integer[J]. Acta Electronica Sinica, 2019: 47(5): 1180‑1184. (in Chinese)
7	蹇强, 张培勇, 王雪洁. 一种可配置的CNN协加速器的FPGA实现方法[J]. 电子学报, 2019, 47(7): 1525‑1531.
	JIAN Q, ZHANG P Y, WANG X J. An FPGA implementation method for configurable CNN co-accelerator[J]. Acta Electronica Sinica, 2019, 47(7): 1525‑1531. (in Chinese)
8	LIN Y B, JIANG Z X, GU J Q, et al. DREAMPlace: Deep learning toolkit-enabled GPU acceleration for modern VLSI placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 40(4): 748‑761.
9	LUU J, GOEDERS J, WAINBERG M, et al. VTR 7.0: next generation architecture and CAD system for FPGAs[J]. ACM Transactions on Reconfigurable Technology and Systems, 2014, 7(2): 1‑30.
10	DHAR S, SINGHAL L, IYER M, et al. FPGA accelerated FPGA placement[C]//2019 29th International Conference on Field Programmable Logic and Applications(FPL). Barcelona: IEEE, 2019: 404‑410.
11	ZAPLETINA M A, ZHELEZNIKOV D A, GAVRILOV S V. Improving pathfinder algorithm performance for FPGA routing[C]//2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering(ElConRus). Russia: IEEE, 2021: 2054‑2057.
12	王德奎. 一种利用资源协商的FPGA布局方法[J]. 西安电子科技大学学报, 2019, 46(6): 17‑22
	WANG D K. Approach to FPGA placement using resource negotiation[J]. Journal of Xidian University, 2019, 46(6): 17‑22. (in Chinese)
13	KHATKHATE A, LI C, AGNIHOTRI A R, et al. Recursive bisection based mixed block placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(5): 748‑761.
14	KIM, M C, LEE D J, MARKOV I L. SimPL: an effective placement algorithm[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, 31(1): 50‑60.
15	MAIDEE P, ABABEI C, BAZARGAN. Timing-driven partitioning-based placement for island style FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(3): 395‑406.
16	FIDUCCIA C M, MATTHEYSES R M. A linear-time heuristic for improving network partitions[C]//19th Design Automation Conference. USA: IEEE, 1982: 175‑181.
17	KARYPIS G, KUMAR V. Parallel multilevel k-way partitioning scheme for irregular graphs[C]//Supercomputing Proceedings of the 1996 ACM/IEEE Conference on Supercomputing. USA: IEEE, 1996. 1‑1.
18	KARYPIS G, KUMAR V. Multilevel k-way hypergraph partitioning[C]//Proceedings 1999 Design Automation Conference (Cat. No.99CH36361). USA: IEEE, 1999: 343‑348.
19	KERNIGHAN B W. LIN S. An efficient heuristic procedure for partitioning graphs[J]. The Bell System Technical Journal, 1970, 49(2): 291‑307.
20	VEREDAS F J, CARMONA E J. FPGA placement improvement using a genetic algorithm and the routing algorithm as a cost function[C]//2018 21st Euromicro Conference on Digital System Design(DSD). Czech Republic: IEEE, 2018: 70‑76.
21	SADEGHI A, LIGHVAN M Z, PRINETTO P. Automatic and simultaneous floorplanning and placement in field-programmable gate arrays with dynamic partial reconfiguration based on genetic algorithm[J]. Canadian Journal of Electrical and Computer Engineering, 2020, 43(4): 224‑234.
22	HERATH K, PRAKASH A, JIANG G Y, et al. Ant Colony Optimization based module footprint selection and placement for lowering power in large FPGA designs[C]// 2018 International Conference on ReConFigurable Computing and FPGAs(ReConFig). Mexico: IEEE, 2018: 1‑8.
23	DANASSIS P, SIOZIOS K, SOUDRIS D. ANT3D: simultaneous partitioning and placement for 3-D FPGAs based on Ant Colony Optimization[J]. IEEE Embedded Systems Letters, 2016, 8(2): 41‑44.
24	JING C. Ant-Colony Optimization based algorithm for energy-efficient scheduling on dynamically reconfigurable systems[C]//2015 Ninth International Conference on Frontier of Computer Science and Technology. China: IEEE, 2015: 127‑134.
25	SARI A, PSARAKIS M. Scrubbing-aware placement for reliable FPGA systems[J]. IEEE Transactions on Emerging Topics in Computing, 2020, 8(3): 564‑576.
26	STEINBRUNN M, MOERKOTTE G, KEMPER A. Heuristic and randomized optimization for the join ordering problem[J]. The VLDB Journal, 1997, 6: 191‑208.
27	CARL S. VLSI Placement and Global Routing Using Simulated Annealing[M]. Boston, MA, USA: Springer Science & Business Media, 2012.
28	MURRAY K E, PETELIN O, ZHONG S, et al. VTR 8: high performance CAD and customizable FPGA architecture modelling[J]. ACM Transactions on Reconfigurable Technology and Systems, 2020, 13(2): 1‑55.
29	KAGAWA H, ITO Y, NAKANO K, et al. Fully-pipelined architecture for simulated annealing-based QUBO solver on the FPGA[C]//2020 Eighth International Symposium on Computing and Networking(CANDAR). Japan: IEEE, 2020: 39‑48.
30	BRIK S, STEFFAN J G, ANDERSON J H. Parallelizing FPGA placement using transactional memory[C]//2010 International Conference on Field-Programmable Technology. China: IEEE, 2010: 61‑69.
31	LUDWIN A, BETZ V. Efficient and deterministic parallel placement for FPGAs[J]. ACM Transactions on Design Automation of Electronic Systems, 2011, 16(3): 1‑23.
32	AN W, STEFFAN J G, BETZ V. Speeding up FPGA placement: parallel algorithms and methods[C]//2014 IEEE 22nd Annual International Symposium on Field-Programmable Custom Computing Machines. USA: IEEE, 2014: 178‑185.
33	HU C Y, LU P, YANG M, et al. A SA-based parallel method for FPGA placement[J]. IEICE Electronics Express, 2018, 15(24): 1‑8.
34	VORWERK K, KENNINGS A, GREENE J W. Improving simulated annealing-based FPGA placement with directed moves[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2009, 28(2): 179‑192.
35	BETZ V, ROSE J, MARQUARDT A. Architecture and CAD for Deep-submicron FPGAs[M]. Boston, MA, USA:Springer Science & Business Media, 2012.
36	HENTSCHKE R F, REIS R. Improving simulated annealing placement by applying random and greedy mixed perturbations[C]//Proceedings of the 16th Symposium on Integrated Circuits and Systems Design. Brazil: IEEE, 2003: 267‑272.
37	CHEN G, CONG J. Simultaneous timing-driven placement and duplication[C]//Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field-Programmable Gate Arrays. Monterey, USA: ACM, 2005: 51‑59.
38	YUAN J Q, ZHOU X G, XIA Y S, et al. RBSA: range-based simulated annealing for FPGA placement[C]//2017 International Conference on Field Programmable Technology(ICFPT). Australia: IEEE, 2017: 1‑8.
39	YUAN J Q, CHEN J L, WANG L L, et al. ARBSA: adaptive range-based simulated annealing for FPGA placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 38(12): 2330‑2342.
40	AI-HYARI A, SHAMLI A, MARTIN T, et al. An adaptive analytic FPGA placement framework based on deep-learning[C]//2020 ACM/IEEE 2nd Workshop on Machine Learning for CAD(MLCAD). Iceland: IEEE, 2020: 3‑8.
41	MURRAY K E, BETZ V. Adaptive FPGA placement optimization via reinforcement learning[C]//2019 ACM/IEEE 1st Workshop on Machine Learning for CAD(MLCAD). Canada: IEEE, 2019: 1‑6.
42	ELGAMMAL M A, MURRAY K E, BETZ V. Learn to place: FPGA placement using reinforcement learning and directed moves[C]//2020 IEEE International Conference on Field-Programmable Technology. USA: IEEE, 2020: 1‑6.
43	XU Y H, KHALID M. QPF: efficient quadratic placement for FPGAs[C]//International Conference on Field Programmable Logic and Applications. Finland: IEEE, 2005: 555‑558.
44	GOPALAKRISHNAN P, LI X, PILEGGI L. Architecture-aware FPGA placement using metric embedding[C]// 2006 43rd ACM/IEEE Design Automation Conference. USA: IEEE, 2006: 460‑465.
45	GORT M, ANDERSON J H. Analytical placement for heterogeneous FPGAs[C]//22nd International Conference on Field Programmable Logic and Applications(FPL). Norway: IEEE, 2012: 143‑150.
46	GESSLER F, BRISK P, STOJILOVIC M. A shared-memory parallel implementation of the RePlAce global cell placer[C]//2020 33rd International Conference on VLSI Design and 2020 19th International Conference on Embedded Systems(VLSID). India: IEEE, 2020: 78‑83.
47	LIN T H, BANERJEE P, CHANG Y W. An efficient and effective analytical placer for FPGAs[C]//2013 50th ACM/EDAC/IEEE Design Automation Conference (DAC). USA: IEEE, 2014: 1‑6.
48	CHEN Y C, CHEN S Y, CHANG Y W. Efficient and effective packing and analytical placement for large-scale heterogeneous FPGAs[C]//2014 IEEE/ACM International Conference on Computer-Aided Design(ICCAD). USA: IEEE, 2014: 647‑654.
49	ABUOWAIMER Z, MAAROUF D, MARTIN T, et al. GPlace3.0: routability-driven analytic placer for UltraScale FPGA architectures[J]. ACM Transactions on Design Automation of Electronic Systems, 2018, 23(5): 1‑33.
50	LI W X, DHAR S, PAN D Z. UTPlaceF: A routability-driven FPGA placer with physical and congestion aware packing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(4): 869‑882.
51	LI W X, PAN D Z. A new paradigm for FPGA placement without explicit packing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 38(11): 2113‑2126.
52	LI W X, LIN Y B, PAN D Z. elfPlace: Electrostatics-based placement for large-scale heterogeneous FPGAs[C]//2019 IEEE/ACM International Conference on Computer-Aided Design(ICCAD). USA: IEEE, 2019: 1‑8.
53	VERCRUYCE D, VANSTEENKISTE E, STROOBANDT D. Liquid: High quality scalable placement for large heterogeneous FPGAs[C]//2017 International Conference on Field Programmable Technology(ICFPT). USA: IEEE, 2017: 17‑24.
54	CHEN G J, PUI C W, CHOW W K, et al. RippleFPGA: Routability-driven simultaneous packing and placement for modern FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(10): 2022‑2035.
55	王德奎. FPGA高效布线方法研究[D]. 西安: 西安电子科技大学, 2019.
	WANG D K. Research on Efficient FPGA Routing Algorithm[D]. Xi'an, China: Xidian University, 2019. (in Chinese)
56	MCMURCHIE L, EBELING C. PathFinder: A negotiation-based performance-driven router for FPGAs[C]//Third International ACM Symposium on Field-Programmable Gate Arrays. USA: IEEE, 1995: 111‑117.
57	WANG D K, DUAN Z H, TIAN C, et al. A runtime optimization approach for FPGA routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(8): 1706‑1710.
58	LAVIN C M. Using Hard Macros to Accelerate FPGA Compilation for Xilinx FPGAs[D]. Provo: Brigham Young University, 2012.
59	LAVIN C, PADILLA M, LAMPRECHT J, et al. HMFlow: Accelerating FPGA compilation with hard macros for rapid prototyping[C]//2011 IEEE 19th Annual International Symposium on Field-Programmable Custom Computing Machines. USA: IEEE, 2011: 117‑124.
60	COOLE J, STITT G. BPR: fast FPGA placement and routing using macroblocks[C]//Proceedings of the Eighth IEEE/ACM/IFIP International Conference on Hardware/Software Codesign And System Synthesis. USA: IEEE, 2012: 275‑284.
61	GORT M, ANDERSION J H. Combined architecture/algorithm approach to fast FPGA routing[J]. IEEE Transactions on Very Large Scale Integration(VLSI) Systems, 2013, 21(6): 1067‑1079.
62	FERREIRA R, ROCHA L, SANTOS A G, et al. A runtime FPGA placement and routing using low-complexity graph traversal[J]. ACM Transactions on Reconfigurable Technology and Systems, 2015, 8(2): 1‑16.
63	NGUYEN A H N, AONO M, HARA-AZUMI Y. FPGA-based hardware/software co-design of a bio-inspired SAT solver[J]. IEEE Access, 2020, 8: 49053‑49065.
64	MA S H, AMPADU P. Optimal SAT-based minimum adder synthesis of linear transformations[C]//2019 IEEE 62nd International Midwest Symposium on Circuits and Systems(MWSCAS). USA: IEEE, 2019: 335‑338.
65	HE A P, YU L Y, ZHANG H T, et al. A FPGA based SAT solver with high random and concurrent strategies[C]//2018 IEEE International Conference on Software Quality, Reliability and Security Companion(QRS‑C). Portugal: IEEE, 2018: 221‑228.
66	VANSTEENKISTE E. New FPGA Design Tools and Architectures[D]. Ghent: Ghent University, 2016.
67	VERCRUYCE D, VANSTEENKISTE E, STROOBAN‑ DT D. CRoute: A fast high-quality timing-driven connection-based FPGA router[C]//2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines(FCCM). USA: IEEE, 2019: 53‑60.
68	MURRAY K E, ZHONG S, BETZ V. AIR: A fast but lazy timing-driven FPGA router[C]//2020 25th Asia and South Pacific Design Automation Conference(ASP-DAC). China: IEEE, 2020: 338‑344.
69	STOJILOVIC M. Parallel FPGA routing: Survey and challenges[C]//2017 27th International Conference on Field Programmable Logic and Applications(FPL). Belgium: IEEE, 2017: 1‑8.
70	HOO C H, HA Y H, KUMAR A. ParaFRo: A hybrid parallel FPGA router using fine grained synchronization and partitioning[C]//2016 26th International Conference on Field Programmable Logic and Applications(FPL). Switzerland: IEEE, 2016: 1‑11.
71	SHEN M H, LUO G J, XIAO N. Exploiting box expansion and grid partitioning for parallel FPGA routing[C]// 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines(FCCM). USA: IEEE, 2018: 209‑209.
72	KORILIJA D, STOJILOVIC M. FPGA-assisted deterministic routing for FPGAs[C]//2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). Brazil: IEEE, 2019: 155‑162.
73	CHAN P K, SCHLAG M D F. Acceleration of an FPGA router[C]//The 5th Annual IEEE Symposium on Field‑Progra‑ mmable Custom Computing Machines Cat. USA: IEEE, 1997： 175‑181.
74	CHAN P K, SCHLAG M D F, EBELING C, et al. Distributed-memory parallel routing for field-programmable gate arrays[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000, 19(8): 850‑862.
75	GORT M, ANDERSON J H. Accelerating FPGA routing through parallelization and engineering enhancements special section on PAR-CAD 2010[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, 31(1): 61‑74.
76	SHEN M H, LUO G J. Accelerate FPGA routing with parallel recursive partitioning[C]//2015 IEEE/ACM International Conference on Computer-Aided Design(ICCAD). USA: IEEE, 2015: 118‑125.
77	SHEN M H, LUO G J, XIAO N. Coarse-grained parallel routing with recursive partitioning for FPGAs[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 32(4): 884‑899.
78	WANG D K, DUAN Z H, TIAN C, et al. ParRA: A shared memory parallel FPGA router using hybrid partitioning approach[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(4): 830‑842.
79	GORT M, ANDERSON J H. Deterministic multi-core parallel routing for FPGAs[C]//2010 International Conference on Field-Programmable Technology. China: IEEE, 2010: 78‑86.
80	SHEN M H, XIAO N. Fine-grained parallel routing for FPGAs with selective expansion[C]//2018 IEEE 36th International Conference on Computer Design(ICCD). USA: IEEE, 2018: 577‑586.
81	LIU L, KAPRE N. Timing-aware routing in the RapidWright framework[C]//2019 29th International Conference on Field Programmable Logic and Applications (FPL). Spain: IEEE, 2019: 24‑30.
82	SHEN M H, LUO G J, XIAO N. Exploring GPU-accelerated routing for FPGAs[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 30(6): 1331‑1345.
83	MOCTAR Y O M, BRISK P. Parallel FPGA routing based on the operator formulation[C]//2014 51st ACM/EDAC/IEEE Design Automation Conference(DAC)[C]. USA: IEEE, 2014. 1‑6.
84	MOCTAR Y, STOJILOVIC M, BRISK P. Deterministic parallel routing for FPGAs based on Galois parallel execution model[C]//2018 28th International Conference on Field Programmable Logic and Applications(FPL). Ireland: IEEE, 2018: 21‑25.
85	ZHU C, WANG J, LAI J M. A novel net-partition-based multithread FPGA routing method[C]//2013 23rd International Conference on Field programmable Logic and Applications. Portugal: IEEE, 2013: 1‑4.

布局技术	优势	不足
基于划分的布局技术	将复杂的电路设计分割为较简单的电路设计，能够快速对局部电路进行处理，收敛速度快	布局质量上存在劣势，容易陷入局部最优解
基于启发式的布局技术	相对于最优算法而提出，在时间允许的情况下，能够获得布局的最优解	运行时间长，布局收敛速度慢
基于解析式的布局技术	完全依赖于数学方法，最终的布局质量能够通过数学分析来证明，具有较高的布局质量，收敛较快	较高的数学功底以抽象FPGA布局问题，不同的FPGA抽象形式不同，不能通用

布局技术	优势	不足
基于划分的布局技术	将复杂的电路设计分割为较简单的电路设计，能够快速对局部电路进行处理，收敛速度快	布局质量上存在劣势，容易陷入局部最优解
基于启发式的布局技术	相对于最优算法而提出，在时间允许的情况下，能够获得布局的最优解	运行时间长，布局收敛速度慢
基于解析式的布局技术	完全依赖于数学方法，最终的布局质量能够通过数学分析来证明，具有较高的布局质量，收敛较快	较高的数学功底以抽象FPGA布局问题，不同的FPGA抽象形式不同，不能通用

分类		Benchmarks	串行对比基准	并行模型	同步方法	确定性	可扩展性	文献
粗粒度	字典序法	alu4， s1A	PathFinder	分布式内存	消息传递	不具备	扩展性低	［73］
	负载均衡法	MCNC， VPR 5.0	VPR 5.0	分布式内存	消息传递	具备	扩展性低	［75］
	迭代划分法	VPR 7.0	VPR 7.0	共享式内存	同步锁	具备	扩展性高	［70］
		VPR 7.0	VPR 7.0	分布式内存	消息传递	具备	扩展性低	［76］
		VPR 7.0	VPR 7.0	分布式内存	消息传递	具备	扩展性高	［77］
		VPR 7.0， Titan	VPR 7.0	共享式内存	同步锁	具备	扩展性高	［78］
细粒度	Posix线程	VPR 8.0	VPR 8.0	共享式内存	消息传递	具备	扩展性高	［71］
		MCNC， VPR5.0	VPR5.0	分布式内存	同步路障	具备	扩展性低	［79］
		VPR 7.0	VPR 7.0	共享式内存	同步锁	具备	扩展性高	［80］
		VPR 7.0	VPR 7.0	共享式内存	同步锁	具备	扩展性高	［82］
	Galois模型	IWLS	VPR 5.0	共享式内存	同步锁	不具备	扩展性高	［83］
	Galois模型	IWLS	VPR 5.0	共享式内存	同步锁	具备	扩展性高	［84］
混合粒度	/	Titan	VPR 7.0	共享式内存	同步锁	不具备	扩展性高	［72］
混合粒度	/	MCNC	VPR 5.0	共享式内存	同步路障	具备	扩展性低	［85］

分类		Benchmarks	串行对比基准	并行模型	同步方法	确定性	可扩展性	文献
粗粒度	字典序法	alu4， s1A	PathFinder	分布式内存	消息传递	不具备	扩展性低	［73］
	负载均衡法	MCNC， VPR 5.0	VPR 5.0	分布式内存	消息传递	具备	扩展性低	［75］
	迭代划分法	VPR 7.0	VPR 7.0	共享式内存	同步锁	具备	扩展性高	［70］
		VPR 7.0	VPR 7.0	分布式内存	消息传递	具备	扩展性低	［76］
		VPR 7.0	VPR 7.0	分布式内存	消息传递	具备	扩展性高	［77］
		VPR 7.0， Titan	VPR 7.0	共享式内存	同步锁	具备	扩展性高	［78］
细粒度	Posix线程	VPR 8.0	VPR 8.0	共享式内存	消息传递	具备	扩展性高	［71］
		MCNC， VPR5.0	VPR5.0	分布式内存	同步路障	具备	扩展性低	［79］
		VPR 7.0	VPR 7.0	共享式内存	同步锁	具备	扩展性高	［80］
		VPR 7.0	VPR 7.0	共享式内存	同步锁	具备	扩展性高	［82］
	Galois模型	IWLS	VPR 5.0	共享式内存	同步锁	不具备	扩展性高	［83］
	Galois模型	IWLS	VPR 5.0	共享式内存	同步锁	具备	扩展性高	［84］
混合粒度	/	Titan	VPR 7.0	共享式内存	同步锁	不具备	扩展性高	［72］
混合粒度	/	MCNC	VPR 5.0	共享式内存	同步路障	具备	扩展性低	［85］

[1]	张建民, 黎铁军, 马柯帆, 肖立权. 一种加速FPGA布线的不可满足子式求解算法[J]. 电子学报, 2021, 49(6): 1210-1216.
[2]	罗阳锦, 张升伟, 陆浩. 高光谱微波辐射计宽带高速数字系统设计[J]. 电子学报, 2021, 49(2): 380-386.
[3]	王卫杰, 胡少亮, 郑宇腾, 赵振国, 周海京. 并行预处理有限元方法及其在系统级封装结构电磁模拟中的应用[J]. 电子学报, 2021, 49(1): 58-63.
[4]	孙志卓, 黄洪, 张全新, 谭毓安, 李元章, 张小松. 一种能耗优化的RAID小写预读方法[J]. 电子学报, 2019, 47(9): 1987-1993.
[5]	曹保锋, 郑毅, 李鹏, 张雪芹, 李欣, 李小强, 胡淼. 微弱电磁脉冲信号低失真度实时检测的FPGA实现[J]. 电子学报, 2019, 47(8): 1797-1802.
[6]	刘公绪, 史凌峰, 辛东金. 基于FPGA的零误差大数阶乘算法的设计与实现[J]. 电子学报, 2019, 47(5): 1180-1184.
[7]	王卫杰, 陈晓洁, 周海京. 基于区域分解的大规模并行有限元快速算法[J]. 电子学报, 2019, 47(3): 741-747.
[8]	曲志坚, 陈宇航, 李盘靖, 刘晓红, 李彩虹. 基于多算子协同进化的自适应并行量子遗传算法[J]. 电子学报, 2019, 47(2): 266-273.
[9]	杨林峰, 胡桂莉, 张晨, 张振荣. 基于CPU-GPU协同并行内点算法求解结构化非线性规划[J]. 电子学报, 2019, 47(2): 382-389.
[10]	佟星元, 王超峰, 贺璐璐, 董嗣万. 基于Q^N旋转布局的10位500MS/s分段电流舵DAC[J]. 电子学报, 2019, 47(11): 2304-2310.
[11]	闵富红, 金秋森. 双忆阻Shinriki振荡器的超级多稳态和反单调性分析[J]. 电子学报, 2019, 47(11): 2263-2270.
[12]	闫青丽, 陈建峰. 分布式声源定位系统节点最优布局方法及性能研究[J]. 电子学报, 2018, 46(5): 1186-1193.
[13]	王今雨, 伍卫国, 秦朝楠, 赵东方, 聂世强. UPRFloor:一种动态可重构FPGA建模方法与布局策略[J]. 电子学报, 2018, 46(12): 2862-2869.
[14]	李冰, 周岑军, 陈帅, 吉建华. 用于SRAM PUFs的伪随机数发生器的FPGA实现[J]. 电子学报, 2017, 45(9): 2106-2112.
[15]	吴珊, 周学功, 王伶俐. 基于SRAM型FPGA单粒子效应的故障传播模型[J]. 电子学报, 2017, 45(8): 1976-1984.

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

Review on Technology of Placement and Routing for the FPGA

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 85

相关文章 15

编辑推荐

Metrics