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

Premalatha Balasubramaniam

Abstract


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.

Keywords


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

Full Text:

PDF

References


.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. https://doi.org/10.3390/electronics8090950

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. https://doi.org/10.1109/ElConRus51938.2021.9396608

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. https://doi.org/10.1109/FPGA.1995.242049

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. https://doi.org/10.1145/3406959

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

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. https://doi.org/10.1109/TPDS.2020.3035787

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. https://doi.org/10.26599/TST.2021.9010092

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. https://doi.org/10.1109/FPL.2015.7294012

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. https://doi.org/10.3390/electronics8080866

PAN, P. Q., “A new face algorithm using LU factori-zation for linear programming”,Preprint,2020.. https://optimization-online.org/wpcontent/ 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.

https://doi.org/10.1007/s00500-019-04519-w

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.

https://doi.org/10.1109/ICCAD45719.2019.8942125

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.

https://doi.org/10.3390/electronics8121439

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. https://doi.org/10.3390/electronics8121439

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

https://doi.org/10.48550/arXiv.2010.11893

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. https://api.semanticscholar.org/CorpusID:61228243




DOI: https://doi.org/10.33180/InfMIDEM2023.302

Refbacks

  • 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.