Multi-Stage Co-Optimization FPGA Routing for Time-Division Multiplexing Technique

LIU Genggeng; XU Wenlin; ZHOU Ruping; XU Ning

doi:10.11999/JEIT221158

Volume 45 Issue 9

Sep. 2023

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2023 > 45(9): 3430-3438

LIU Genggeng, XU Wenlin, ZHOU Ruping, XU Ning. Multi-Stage Co-Optimization FPGA Routing for Time-Division Multiplexing Technique[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3430-3438. doi: 10.11999/JEIT221158

Citation:

LIU Genggeng, XU Wenlin, ZHOU Ruping, XU Ning. Multi-Stage Co-Optimization FPGA Routing for Time-Division Multiplexing Technique[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3430-3438. doi: 10.11999/JEIT221158

Citation:

PDF( 1262 KB)

Multi-Stage Co-Optimization FPGA Routing for Time-Division Multiplexing Technique

doi: 10.11999/JEIT221158

LIU Genggeng^{1, 2
,
,},
XU Wenlin¹,
ZHOU Ruping¹,
XU Ning³

1.
College of Computer and Data Science, Fuzhou University, Fuzhou 350116, China
2.
Fujian Key Laboratory of Network Computing and Intelligent Information Processing (Fuzhou University), Fuzhou 350116, China
3.
School of Information Engineering, Wuhan University of Technology, Wuhan 430070, China

Funds: The National Natural Science Foundation of China (61877010)

Received Date: 2022-09-06
Rev Recd Date: 2023-03-31

Available Online: 2023-04-04

Publish Date: 2023-09-27

Abstract

Abstract

Time-Division Multiplexing (TDM) technology is widely applied to solving the IO limitation problem to improve the routability of FPGA system. However, the increase of the TDM ratio leads to a significant increase in system delay. Therefore, a Multi-Stage Co-Optimization FPGA routing (MSCOFRouting) for Time-Division Multiplexing is proposed in this paper to optimize the system delay and the routability of FPGA system. First, an adaptive routing algorithm is proposed to reduce routing congestion, improve the routability, solve the routing optimization problem between FPGAs, and provide high-quality routing results for subsequent TDM ratio assignment. Second, to avoid the delay degradation caused by excessive TDM ratio of large-scale net groups, a TDM ratio assignment algorithm based on Lagrangian relaxation is utilized to assign the initial TDM ratio with a smaller delay to the edge distribution system of the routing graph. In addition, a multi-level TDM ratio optimization algorithm is used to reduce the TDM ratios of the net group with maximum TDM ratios. The TDM ratio reduction is employed for the net group and the FPGA connection pair. Meanwhile, a multi-thread parallelization method is integrated into the three algorithms above to improve further the efficiency of MSCOFRouter. Experiments show that MSCOFRouting can obtain the results satisfying the TDM ratio constraint, and achieve the best routing optimization results and TDM ratio assignment results.
- FPGA systems,
- Logic verification,
- Time-division multiplexing,
- Routing,
- Lagrangian relaxation

FullText(HTML)

References(18)

References

[1]	TURKI M, MARRAKCHI Z, MEHREZ H, et al. Signal multiplexing approach to improve inter-FPGA bandwidth of prototyping platform[J]. Design Automation for Embedded Systems, 2015, 19(3): 223–242. doi: 10.1007/s10617-014-9155-4
[2]	LING A and ANDERSON J. The role of FPGAs in deep learning[C]. Proceedings of the 2017 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Monterey, USA, 2017: 3.
[3]	CHIU G R, LING A C, CAPALIJA D, et al. Flexibility: FPGAs and cad in deep learning acceleration[C]. Proceedings of the 2018 International Symposium on Physical Design, Monterey, USA, 2018: 34–41.
[4]	HUNG W N N and SUN R. Challenges in large FPGA-based logic emulation systems[C]. Proceedings of the 2018 International Symposium on Physical Design, Monterey, USA, 2018: 26–33.
[5]	HAUCK S. The roles of FPGAs in reprogrammable systems[J]. Proceedings of the IEEE, 1998, 86(4): 615–638. doi: 10.1109/5.663540
[6]	CHEN S C, SUN R, and CHANG Yaowen. Simultaneous partitioning and signals grouping for time-division multiplexing in 2.5D FPGA-based systems[C]. 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Diego, USA, 2018: 1–7.
[7]	TURKI M, MARRAKCHI Z, MEHREZ H, et al. Iterative routing algorithm of inter-FPGA signals for multi-FPGA prototyping platform[C]. The 9th International Symposium on Reconfigurable Computing: Architectures, Tools and Applications, Los Angeles, USA, 2013: 210–217.
[8]	FAROOQ U, CHOTIN-AVOT R, AZEEM M, et al. Inter-FPGA routing environment for performance exploration of multi-FPGA systems[C]. 2016 International Symposium on Rapid System Prototyping (RSP), Pittsburgh, USA, 2016: 1–7.
[9]	PUI C W and YOUNG E F Y. Lagrangian relaxation-based time-division multiplexing optimization for multi-FPGA systems[J]. ACM Transactions on Design Automation of Electronic Systems, 2020, 25(2): 21. doi: 10.1145/3377551
[10]	INAGI M, TAKASHIMA Y, and NAKAMURA Y. Globally optimal time-multiplexing in inter-FPGA connections for accelerating multi-FPGA systems[C]. 2009 International Conference on Field Programmable Logic and Applications, Prague, Czech Republic, 2009: 212–217.
[11]	ZHUANG Zhen, HUANG Xing, LIU Genggeng, et al. ALIFRouter: A practical architecture-level inter-FPGA router for logic verification[C]. 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE), Grenoble, France, 2021: 1570–1573.
[12]	SU Y H, SUN R, and HO P H. 2019 CAD contest: System-level FPGA routing with timing division multiplexing technique[C]. 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Westminster, USA, 2019: 1–2.
[13]	FRESCHI V and LATTANZI E. A prim–Dijkstra algorithm for Multihop calibration of networked embedded systems[J]. IEEE Internet of Things Journal, 2021, 8(14): 11320–11328. doi: 10.1109/JIOT.2021.3051270
[14]	CHEN Xiaohua, ZHOU Ruping, LIU Genggeng, et al. Timing-driven X-architecture Steiner minimum tree construction based on social learning multi-objective particle swarm optimization[C]. Companion Proceedings of the Web Conference, Ljubljana, Slovenia, 2021: 77–84.
[15]	KULIK A, SHACHNAI H, and TAMIR G. On Lagrangian relaxation for constrained maximization and reoptimization problems[J]. Discrete Applied Mathematics, 2021, 296: 164–178. doi: 10.1016/j.dam.2020.10.001
[16]	SHARMA A, CHINNERY D, DHAMDHERE S, et al. Rapid gate sizing with fewer iterations of Lagrangian relaxation[C]. 2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Irvine, USA, 2017: 337–343.
[17]	MANGIRAS D, STEFANIDIS A, SEITANIDIS I, et al. Timing-driven placement optimization facilitated by timing-compatibility flip-flop clustering[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(10): 2835–2848. doi: 10.1109/TCAD.2019.2942001
[18]	ZHUANG Zhen, LIU Genggeng, HUANG Xing, et al. MSFRoute: Multi-stage FPGA routing for timing division multiplexing technique[C/OL]. Proceedings of the 2020 on Great Lakes Symposium on VLSI, 2020: 107–112.