Journal Home > Volume 27 , Issue 6
Tsinghua Science and Technology 2022, 27(6): 902-911 https://doi.org/10.26599/TST.2021.9010092
Open Access | Issue | Published: 21 June 2022

A Two-Stage Method for Routing in Field-Programmable Gate Arrays with Time-Division Multiplexing

Show Author's Information Peihuang Huang,  Longkun Guo( ),  Long Sun,  Xiaoyan Zhang
College of Mathematics and Data Science, Minjiang University, Fuzhou 350116, China
School of Mathematics Science, Nanjing Normal University, Nanjing 210024, China
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China
School of Mathematics Science and Institute of Mathematics, Nanjing Normal University, Nanjing 210024, China
Keywords:
approximation algorithm, Field-programmable gate array (FPGA) routing, time-division multiplexing, minimum Steiner tree, exact algorithm
Cite this article:
Huang P, Guo L, Sun L, et al. A Two-Stage Method for Routing in Field-Programmable Gate Arrays with Time-Division Multiplexing. Tsinghua Science and Technology, 2022, 27(6): 902-911. https://doi.org/10.26599/TST.2021.9010092
Download citation
EndNote(RIS)
BibTeX

653

Views

118

Downloads

Citations

0

Crossref

1

WoS

1

Scopus

0

CSCD

Abstract Full text About this article

Emerging applications widely use field-programmable gate array (FPGA) prototypes as a tool to verify modern very-large-scale integration (VLSI) circuits, imposing many problems, including routing failure caused by the limited number of connections among blocks of FPGAs therein. Such a shortage of connections can be alleviated through time-division multiplexing (TDM), by which multiple signals sharing an identical routing channel can be transmitted. In this context, the routing quality dominantly decides the performance of such systems, proposing the requirement of minimizing the signal delay between FPGA pairs. This paper proposes algorithms for the routing problem in a multi-FPGA system with TDM support, aiming to minimize the maximum TDM ratio. The algorithm consists of two major stages: (1) A method is proposed to set the weight of an edge according to how many times it is shared by the routing requirements and consequently to compute a set of approximate minimum Steiner trees. (2) A ratio assignment method based on the edge-demand framework is devised for assigning ratios to the edges respecting the TDM ratio constraints. Experiments were conducted against the public benchmarks to evaluate our proposed approach as compared with all published works, and the results manifest that our method achieves a better TDM ratio in comparison.


menu
Abstract
Full text
Outline
About this article

A Two-Stage Method for Routing in Field-Programmable Gate Arrays with Time-Division Multiplexing

Show Author's information Peihuang Huang, Longkun Guo( ), Long Sun, Xiaoyan Zhang
College of Mathematics and Data Science, Minjiang University, Fuzhou 350116, China
School of Mathematics Science, Nanjing Normal University, Nanjing 210024, China
College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China
School of Mathematics Science and Institute of Mathematics, Nanjing Normal University, Nanjing 210024, China

Abstract

Emerging applications widely use field-programmable gate array (FPGA) prototypes as a tool to verify modern very-large-scale integration (VLSI) circuits, imposing many problems, including routing failure caused by the limited number of connections among blocks of FPGAs therein. Such a shortage of connections can be alleviated through time-division multiplexing (TDM), by which multiple signals sharing an identical routing channel can be transmitted. In this context, the routing quality dominantly decides the performance of such systems, proposing the requirement of minimizing the signal delay between FPGA pairs. This paper proposes algorithms for the routing problem in a multi-FPGA system with TDM support, aiming to minimize the maximum TDM ratio. The algorithm consists of two major stages: (1) A method is proposed to set the weight of an edge according to how many times it is shared by the routing requirements and consequently to compute a set of approximate minimum Steiner trees. (2) A ratio assignment method based on the edge-demand framework is devised for assigning ratios to the edges respecting the TDM ratio constraints. Experiments were conducted against the public benchmarks to evaluate our proposed approach as compared with all published works, and the results manifest that our method achieves a better TDM ratio in comparison.

Keywords: approximation algorithm, Field-programmable gate array (FPGA) routing, time-division multiplexing, minimum Steiner tree, exact algorithm

References(21)

[1]
L. Sun, L. Guo, and P. Huang, System-level FPGA routing for logic verification with time-division multiplexing, in Proc. 21st Int. Conf. on Parallel and Distributed Computing, Applications and Technologies, Shenzhen, China, 2020, pp. 210–218.
DOI Google Scholar
[2]
C. Constantinescu, Trends and challenges in VLSI circuit reliability, IEEE Micro, vol. 23, no. 4, pp. 14–19, 2003.
DOI Google Scholar
[3]
W. N. N. Hung and R. Sun, Challenges in large FPGA-based logic emulation systems, in Proc. 2018 Int. Symp. on Physical Design, Monterey, CA, USA, 2018, pp. 26–33.
DOI Google Scholar
[4]
S. Asaad, R. Bellofatto, B. Brezzo, C. Haymes, M. Kapur, B. Parker, T. Roewer, P. Saha, T. Takken, and J. Tierno, A cycle-accurate, cycle-reproducible multi-FPGA system for accelerating multi-core processor simulation, in Proc. ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays, Monterey, CA, USA, 2012, pp. 153–162.
DOI Google Scholar
[5]
W. T. Wang, Z. X. Shen, and V. Dinavahi, Physics-based device-level power electronic circuit hardware emulation on FPGA, IEEE Trans. Ind. Inform., vol. 10, no. 4, pp. 2166–2179, 2014.
DOI Google Scholar
[6]
P. S. Graham, Logical hardware debuggers for FPGA-based systems, PhD dissertation, Brigham Young University, Provo, UT, USA, 2001.
[7]
G. Schelle, J. Collins, E. Schuchman, P. Wang, X. Zou, G. Chinya, R. Plate, T. Mattner, F. Olbrich, P. Hammarlund, et al., Intel nehalem processor core made FPGA synthesizable, in Proc. 18th Annual ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays, Monterey, CA, USA, 2010, pp. 3–12.
DOI Google Scholar
[8]
J. H. Han, Z. L. Li, W. M. Zheng, and Y. H. Zhang, Hardware implementation of spiking neural networks on FPGA, Tsinghua Science and Technology, vol. 25, no. 4, pp. 479–486, 2020.
DOI Google Scholar
[9]
J. Q. Huang, W. T. Han, X. Y. Wang, and W. G. Chen, Heterogeneous parallel algorithm design and performance optimization for WENO on the Sunway Taihulight supercomputer, Tsinghua Science and Technology, vol. 25, no. 1, pp. 56–67, 2020.
DOI Google Scholar
[10]
M. Inagi, Y. Takashima, and Y. Nakamura, Globally optimal time-multiplexing in inter-FPGA connections for accelerating multi-FPGA systems. in Proc. 2009 Int. Conf. on Field Programmable Logic and Applications, Prague, Czech Republic, 2009, pp. 212–217.
DOI Google Scholar
[11]
J. Babb, R. Tessier, and A. Agarwal, Virtual wires: Overcoming pin limitations in FPGA-based logic emulators, in Proc. 1993 IEEE Workshop on FPGAs for Custom Computing Machines, Napa, CA, USA, 1993, pp.142–151.
Google Scholar
[12]
M. Inagi, Y. Takashima, Y. Nakamura, and A. Takahashi, Optimal time-multiplexing in inter-FPGA connections for accelerating multi-FPGA prototyping systems, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E91.A, no. 12, pp. 3539–3547, 2008.
DOI Google Scholar
[13]
C. W. Pui, G. Wu, F. Y. C. Mang, and E. F. Y. Young, An analytical approach for time-division multiplexing optimization in multi-FPGA based systems, in Proc. 2019 ACM/IEEE Int. Workshop on System Level Interconnect Prediction, Las Vegas, NV, USA, 2019, pp. 1–8.
DOI Google Scholar
[14]
T. W. Lin, W. C. Tai, Y. C. Lin, and I. H. R. Jiang, Routing topology and time-division multiplexing co-optimization for multi-FPGA systems. in Proc. 2020 57th ACM/IEEE Design Automation, San Francisco, CA, USA, 2020, pp. 1–6.
DOI Google Scholar
[15]
M. Inagi, Y. Takashima, and Y. Nakamura, Globally optimal time-multiplexing of inter-FPGA connections for multi-FPGA prototyping systems, IPSJ Trans. Syst. LSI Des. Methodol., vol. 3, pp. 81–90, 2010.
DOI Google Scholar
[16]
B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, 5th ed. Berlin, Germany: Springer, 2012.
DOI
[17]
S. Fortune, J. Hopcroft, and J. Wyllie, The directed subgraph homeomorphism problem, Theor. Comput. Sci., vol. 10, no. 2, pp. 111–121, 1980.
DOI Google Scholar
[18]
R. K. Ahuja, K. Mehlhorn, J. Orlin, and R. E. Tarjan, Faster algorithms for the shortest path problem, J. ACM, vol. 37, no. 2, pp. 213–223, 1990.
DOI Google Scholar
[19]
J. W. Suurballe and R. E. Tarjan, A quick method for finding shortest pairs of disjoint paths, Networks, vol. 14, no. 2, pp. 325–336, 1984.
DOI Google Scholar
[20]
P. Zou, Z. F. Lin, X. Shi, Y. J. Wu, J. L. Chen, J. Yu, and Y. W. Chang, Time-division multiplexing based system-level FPGA routing for logic verification, in Proc. 2020 57th ACM/IEEE Design Automation, San Francisco, CA, USA, 2020, pp. 1–6.
DOI Google Scholar
[21]
M. Inagi, Y. Takashima, Y. Nakamura, and A. Takahashi, ILP-based optimization of time-multiplexed I/O assignment for multi-FPGA systems, in Proc. 2008 IEEE Int. Symp. on Circuits and Systems, Seattle, WA, USA, 2008, pp. 1800–1803.
Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 10 July 2021
Revised: 27 September 2021
Accepted: 31 October 2021
Published: 21 June 2022
Issue date: December 2022

Copyright

© The author(s) 2022.

Acknowledgements

This work was supported by the Natural Science Foundation of Fujian Province (No. 2020J01845), the National Natural Science Foundation of China (Nos. 61772005 and 11871280), the Outstanding Youth Innovation Team Project for Universities of Shandong Province (No. 2020KJN008), and Qinglan Project.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return