Parallel Routing for FPGA Using Improved Lagrange Heuristics with Sub-Gradient Method and Steiner Tree

Premalatha Balasubramaniam


One of the most time-consuming processes in the Field Programmable Gate Array (FPGA) design cycle is the routing of the nets. For this reason, versatile Place and Route (VPR), a widely used algorithm, routes efficiently but takes a long time to complete. Using parallelization is one approach to quicken this design flow. A method based on Linear Programming (LP) might be employed to enhance the speed of this routing process further. This strategy, however, has two drawbacks: a local minimum and the solution's violation of boundaries. So, to overcome these issues, this paper proposed Parallel Routing for FPGA Using Improved Lagrange Heuristics with a Sub-Gradient method and Steiner tree (PR-ILH). The Lagrange relaxation process is enhanced by a series of innovative Lagrange heuristics presented in this work. Lagrange heuristics and sub-gradient optimization are both made use of by PR-ILH, which combines their advantages to provide more effective routing while reducing the complexity of parameter tuning. The use of the Steiner tree further improves the usage of resources and overall performance. It has also provided an improved method for updating the step size that this iterative process takes. Tests have been conducted on standard metrics, demonstrating that the proposed approach surpasses the ParaLaR and other existing improved techniques. Compared to ParaLaR, the proposed PR-ILH approach can enhance the minimum channel width and the violation of the restrictions by up to 25.1%. Compared to ParaLaR, PR-ILH realizes savings of roughly 15.4% in the total wire length. PR-ILH algorithm effectively reduces route latency, improving circuit speed and responsiveness in the FPGA routing process.


: Parallel Routing, FPGA, VPR, Sub-gradient, Improved Lagrange Heuristics, Steiner tree.

Full Text:



.Jiang, Y., Chen, H., Yang, X., Sun, Z., & Quan, W,.” Design and Implementation of CPU & FPGA Co-Design Tester for SDN Switches. Electronics”,Vol.8,no.9,pp. 950.2019.

Zapletina, M. A., Zheleznikov, D. A., & Gavrilov, S. V. , “ Improving pathfinder algorithm perfomance for FPGA routing”, In 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engi-neering(ElConRus),pp.2054-2057,January 2019. IEEE.

McMurchie, L., & Ebeling, “PathFinder: A negotia-tion-based performance-driven router for FPGAs”, In Proceedings of the 1995 ACM third international sym-posium on Field-programmable gate arrays,pp.111-117, February1995.

Zhou, Y., Vercruyce, D., & Stroobandt, D, “ Acceler-ating FPGA routing through algorithmic enhancements and connection-aware parallelization”,ACM Transactions on Reconfigurable Technology and Sys-tems(TRETS),Vol.13,no.4,pp.1-26,2020.

Martin, T., Barnes, C., Grewal, G., & Areibi, S.,” In-tegrating Machine-Learning Probes in FPGA CAD: Why and How?”, IEEE Design & Test,2023.

Shen, M., Luo, G., & Xiao, N., “ Coarse-grained paral-lel routing with recursive partitioning for FPGAs. IEEE Transactions on Parallel and Distributed Systems, Vol.32,no.4,pp.884-899,2020.

Huang, P., Guo, L., Sun, L., & Zhang, X., “A Two-Stage Method for Routing in Field-Programmable Gate Arrays with Time-Division Multiplexing”,Tsinghua Science and Technology, Vol.27,no.6,pp.902-911,2022.

Hoo, C. H., Kumar, A., & Ha, Y, “ ParaLaR: A parallel FPGA router based on Lagrangian relaxation”, In 2015 25th International Conference on Field Programmable Logic and Applications (FPL)pp. 1-6.September 2015. IEEE.

Lee, H., & Kim, K, “ Real-Time Monte Carlo Optimi-zation on FPGA for the Efficient and Reliable Message Chain Structure. Electronics, Vol.8,no.8, pp:866,2019.

PAN, P. Q., “A new face algorithm using LU factori-zation for linear programming”,Preprint,2020.. uploads/ 2020/11/ 8085.pdf

Ghanbari, R., Ghorbani-Moghadam, K., Mahdavi-Amiri, N., & De Baets, B.,”Fuzzy linear programming problems: models and solutions”,Soft Comput-ting,Vol.24,no.13,pp.10043-10073,2020.

Pui, C. W., & Young, E. F,” Lagrangian relaxation-based time-division multiplexing optimization for mul-ti-FPGA systems”,ACM Transactions on Design Auto-mation of Electronic Systems (TODAES), Vol.25,no.2, pp.1-23,2019.

Agrawal, R., Hoo, C. H., Ahuja, K., & Kumar, A. (2018). Parallel FPGA router using sub-gradient method and Steiner tree. arXiv preprint arXiv:1803.03885.

Agrawal, R., Ahuja, K., Hau Hoo, C., Duy Anh Ngu-yen, T., & Kumar, A. (2019). ParaLarPD: Parallel FPGA router using primal-dual sub-gradient method. Elec-tronics,8(12),1439.

Agrawal, R., Ahuja, K., Maheshwari, D., & Kumar, A.,”ParaLarH: parallel FPGA router based upon La-grange heuristics”, arXiv preprint arXiv:2010.11893, 2020.

Yang, S., “Logic synthesis and optimization benchmarks user guide: version 3.0”, Research Triangle Park, NC, USA: Microelectronics Center of North Caro-lina(MCNC),pp.502-508,1991.



  • There are currently no refbacks.

Copyright (c) 2023 Premalatha Balasubramaniam

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.