Advanced Search
Volume 45 Issue 9
Sep.  2023
Turn off MathJax
Article Contents
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

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

doi: 10.11999/JEIT221158
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
  • 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.
  • loading
  • [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.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(5)  / Tables(6)

    Article Metrics

    Article views (666) PDF downloads(101) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return