J. Semicond. > Volume 41?>?Issue 2?> Article Number: 022405

A routing algorithm for FPGAs with time-multiplexed interconnects

Ruiqi Luo 1, 2, 3, , Xiaolei Chen 4, and Yajun Ha 1, ,

+ Author Affiliations + Find other works by these authors

PDF

Turn off MathJax

Abstract: Previous studies show that interconnects occupy a large portion of the timing budget and area in FPGAs. In this work, we propose a time-multiplexing technique on FPGA interconnects. In order to fully exploit this interconnect architecture, we propose a time-multiplexed routing algorithm that can actively identify qualified nets and schedule them to multiplexable wires. We validate the algorithm by using the router to implement 20 benchmark circuits to time-multiplexed FPGAs. We achieve a 38% smaller minimum channel width and 3.8% smaller circuit critical path delay compared with the state-of-the-art architecture router when a wire can be time-multiplexed six times in a cycle.

Key words: field programmable gate arraysdigital integrated circuitsrouting algorithm design and analysisdigital integrated circuits

Abstract: Previous studies show that interconnects occupy a large portion of the timing budget and area in FPGAs. In this work, we propose a time-multiplexing technique on FPGA interconnects. In order to fully exploit this interconnect architecture, we propose a time-multiplexed routing algorithm that can actively identify qualified nets and schedule them to multiplexable wires. We validate the algorithm by using the router to implement 20 benchmark circuits to time-multiplexed FPGAs. We achieve a 38% smaller minimum channel width and 3.8% smaller circuit critical path delay compared with the state-of-the-art architecture router when a wire can be time-multiplexed six times in a cycle.

Key words: field programmable gate arraysdigital integrated circuitsrouting algorithm design and analysisdigital integrated circuits



References:

[1]

Lemieux G, Lewis D. Design of interconnection networks for programmable logic. Dordrecht: Kluwer Academic Publishers, 2004

[2]

Trimberger S, Carberry D, Johnson A, et al. A time-multiplexed FPGA. The 5th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 1997, 22

[3]

Betz V, Rose J. VPR: A new packing, placement and routing tool for FPGA research. International Workshop on Field Programmable Logic and Applications. Springer, Berlin, Heidelberg, 1997, 213

[4]

Luu J, Kuon I, Jamieson P, et al. VPR 5.0: FPGA CAD and architecture exploration tools with single-driver routing, heterogeneity and process scaling. ACM Trans Reconfig Technol Syst, 2011, 4(4), 32

[5]

Trimberger S. Scheduling designs into a time-multiplexed FPGA. Proceedings of the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays, 1998, 153

[6]

Lin C C, Chang D, Wu Y L, et al. Time-multiplexed routing resources for FPGA design. Proceedings of Custom Integrated Circuits Conference, 1996, 152

[7]

Francis R, Moore S, Mullins R. A network of time-division multiplexed wiring for FPGAs. Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip, 2008, 35

[8]

Shen M, Zhang W, Luo G, et al. Serial-equivalent static and dynamic parallel routing for FPGAs. IEEE Trans Comput-Aid Des Integr Circuits Syst, 2018

[9]

Shen M, Luo G, Xiao N. Exploiting box expansion and grid partitioning for parallel FPGA routing. 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2018, 209

[10]

Shen M, Luo G. Accelerate FPGA routing with parallel recursive partitioning. Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2015, 118

[11]

Shen M, Xiao N. Fine-grained parallel routing for FPGAs with selective expansion. 2018 IEEE 36th International Conference on Computer Design (ICCD), 2018, 577

[12]

Shen M, Xiao N. Raparo: resource-level angle-based parallel routing for FPGAs. 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2019, 312

[13]

Shen M, Luo G. Megrez: Parallelizing FPGA routing with strictly-ordered partitioning. 2017 IEEE 25th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2017, 27

[14]

Vercruyce D, Vansteenkiste E, Stroobandt D. CRoute: a fast high-quality timing-driven connection-based FPGA router. 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2019, 53

[15]

Wang D, Duan Z, Tian C, et al. A runtime optimization approach for FPGA routing. IEEE Trans Comput-Aid Des Integ Circuits Syst, 2017, 37(8), 1706

[16]

Patil S B, Liu T, Tessier R. A bandwidth-optimized routing algorithm for hybrid FPGA networks-on-chip. 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2018, 25

[17]

Chaplygin Y, Novozhilov I, Losev V, et al. Algorithm for design and structure optimization of the FPGA routing block with a given number of trace signals. 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 2019, 1589

[18]

Farooq U, Chotin-Avot R, Azeem M, et al. Using timing-driven inter-FPGA routing for multi-FPGA prototyping exploration. 2016 Euromicro Conference on Digital System Design (DSD), 2016, 641

[19]

Omam S R, Tang X, Gaillardon P E, et al. A study on buffer distribution for RRAM-based FPGA routing structures. 2015 IEEE 6th Latin American Symposium on Circuits and Systems (LASCAS), 2015, 1

[20]

Chen S C, Chang Y W. FPGA placement and routing. Proceedings of the 36th International Conference on Computer Aided Design, 2017, 914

[21]

Huriaux C, Sentieys O, Tessier R. Effects of I/O routing through column interfaces in embedded FPGA fabrics. 2016 26th International Conference on Field Programmable Logic and Applications (FPL), 2016, 1

[22]

Kashif A, Khalid M A S. Experimental evaluation and comparison of time-multiplexed multi-FPGA routing architectures. 2016 IEEE 59th International Midwest Symposium on Circuits and Systems (MWSCAS), 2016, 1

[23]

Palczewski M. Plane parallel A* maze router and its application to FPGAs. Proceedings 29th ACM/IEEE Design Automation Conference, 1992, 6911

[24]

McMurchie L, Ebeling C. PathFinder: a negotiation-based performance-driven router for FPGAs. Proceedings of the 1995 ACM Third International Symposium on Field-Programmable Gate Arrays, 1995, 111

[25]

Sapatnekar S. Timing. Springer Science & Business Media, 2004

[26]

Kuon I, Rose J. iFAR–intelligent FPGA architecture repository. 2008

[1]

Lemieux G, Lewis D. Design of interconnection networks for programmable logic. Dordrecht: Kluwer Academic Publishers, 2004

[2]

Trimberger S, Carberry D, Johnson A, et al. A time-multiplexed FPGA. The 5th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 1997, 22

[3]

Betz V, Rose J. VPR: A new packing, placement and routing tool for FPGA research. International Workshop on Field Programmable Logic and Applications. Springer, Berlin, Heidelberg, 1997, 213

[4]

Luu J, Kuon I, Jamieson P, et al. VPR 5.0: FPGA CAD and architecture exploration tools with single-driver routing, heterogeneity and process scaling. ACM Trans Reconfig Technol Syst, 2011, 4(4), 32

[5]

Trimberger S. Scheduling designs into a time-multiplexed FPGA. Proceedings of the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays, 1998, 153

[6]

Lin C C, Chang D, Wu Y L, et al. Time-multiplexed routing resources for FPGA design. Proceedings of Custom Integrated Circuits Conference, 1996, 152

[7]

Francis R, Moore S, Mullins R. A network of time-division multiplexed wiring for FPGAs. Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip, 2008, 35

[8]

Shen M, Zhang W, Luo G, et al. Serial-equivalent static and dynamic parallel routing for FPGAs. IEEE Trans Comput-Aid Des Integr Circuits Syst, 2018

[9]

Shen M, Luo G, Xiao N. Exploiting box expansion and grid partitioning for parallel FPGA routing. 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2018, 209

[10]

Shen M, Luo G. Accelerate FPGA routing with parallel recursive partitioning. Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, 2015, 118

[11]

Shen M, Xiao N. Fine-grained parallel routing for FPGAs with selective expansion. 2018 IEEE 36th International Conference on Computer Design (ICCD), 2018, 577

[12]

Shen M, Xiao N. Raparo: resource-level angle-based parallel routing for FPGAs. 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2019, 312

[13]

Shen M, Luo G. Megrez: Parallelizing FPGA routing with strictly-ordered partitioning. 2017 IEEE 25th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2017, 27

[14]

Vercruyce D, Vansteenkiste E, Stroobandt D. CRoute: a fast high-quality timing-driven connection-based FPGA router. 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2019, 53

[15]

Wang D, Duan Z, Tian C, et al. A runtime optimization approach for FPGA routing. IEEE Trans Comput-Aid Des Integ Circuits Syst, 2017, 37(8), 1706

[16]

Patil S B, Liu T, Tessier R. A bandwidth-optimized routing algorithm for hybrid FPGA networks-on-chip. 2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2018, 25

[17]

Chaplygin Y, Novozhilov I, Losev V, et al. Algorithm for design and structure optimization of the FPGA routing block with a given number of trace signals. 2019 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 2019, 1589

[18]

Farooq U, Chotin-Avot R, Azeem M, et al. Using timing-driven inter-FPGA routing for multi-FPGA prototyping exploration. 2016 Euromicro Conference on Digital System Design (DSD), 2016, 641

[19]

Omam S R, Tang X, Gaillardon P E, et al. A study on buffer distribution for RRAM-based FPGA routing structures. 2015 IEEE 6th Latin American Symposium on Circuits and Systems (LASCAS), 2015, 1

[20]

Chen S C, Chang Y W. FPGA placement and routing. Proceedings of the 36th International Conference on Computer Aided Design, 2017, 914

[21]

Huriaux C, Sentieys O, Tessier R. Effects of I/O routing through column interfaces in embedded FPGA fabrics. 2016 26th International Conference on Field Programmable Logic and Applications (FPL), 2016, 1

[22]

Kashif A, Khalid M A S. Experimental evaluation and comparison of time-multiplexed multi-FPGA routing architectures. 2016 IEEE 59th International Midwest Symposium on Circuits and Systems (MWSCAS), 2016, 1

[23]

Palczewski M. Plane parallel A* maze router and its application to FPGAs. Proceedings 29th ACM/IEEE Design Automation Conference, 1992, 6911

[24]

McMurchie L, Ebeling C. PathFinder: a negotiation-based performance-driven router for FPGAs. Proceedings of the 1995 ACM Third International Symposium on Field-Programmable Gate Arrays, 1995, 111

[25]

Sapatnekar S. Timing. Springer Science & Business Media, 2004

[26]

Kuon I, Rose J. iFAR–intelligent FPGA architecture repository. 2008

[1]

P. A. Gowri Sankar, K. Udhayakumar. MOSFET-like CNFET based logic gate library for low-power application: a comparative study. J. Semicond., 2014, 35(7): 075001. doi: 10.1088/1674-4926/35/7/075001

[2]

Zheng Wang, Libing Zhou, Wenting Xie, Weiguang Chen, Jinyuan Su, Wenxuan Chen, Anhua Du, Shanliao Li, Minglan Liang, Yuejin Lin, Wei Zhao, Yanze Wu, Tianfu Sun, Wenqi Fang, Zhibin Yu. Accelerating hybrid and compact neural networks targeting perception and control domains with coarse-grained dataflow reconfiguration. J. Semicond., 2020, 41(2): 022401. doi: 10.1088/1674-4926/41/2/022401

[3]

Yingbo Zhao, Gang Dong, Yintang Yang. Analysis and optimization of TSV-TSV coupling in three-dimensional integrated circuits. J. Semicond., 2015, 36(4): 045011. doi: 10.1088/1674-4926/36/4/045011

[4]

Liu Dan, Lu Wengao, Chen Zhongjian, Ji Lijiu, Zhao Baoying. Low Power Design Orienting 384×288 Snapshot Infrared Readout Integrated Circuits. J. Semicond., 2008, 29(1): 93.

[5]

Xie Yongle, Li Xifeng. A Method to Locate Parametric Faults in Analog Integrated Circuits. J. Semicond., 2008, 29(3): 598.

[6]

Hongchao Zheng, Yuanfu Zhao, Suge Yue, Long Fan, Shougang Du, Maoxin Chen, Chunqing Yu. The single-event effect evaluation technology for nano integrated circuits. J. Semicond., 2015, 36(11): 115002. doi: 10.1088/1674-4926/36/11/115002

[7]

Hu Huiyong, Zhang Heming, Jia Xinzhang, Dai Xianying, Xuan Rongxi. Study on Si-SiGe Three-Dimensional CMOS Integrated Circuits. J. Semicond., 2007, 28(5): 681.

[8]

Deng Yong, Shi Yibing, Zhang Wei. Diagnosis of soft faults in analog integrated circuits based on fractional correlation. J. Semicond., 2012, 33(8): 085007. doi: 10.1088/1674-4926/33/8/085007

[9]

liang Tao, Jia Xinzhang. A numerical integration-based yield estimation method for integrated circuits. J. Semicond., 2011, 32(4): 045012. doi: 10.1088/1674-4926/32/4/045012

[10]

Ruan Wenbiao, Chen Lan, Ma Tianyu, Fang Jingjing, Zhang He, Ye Tianchun. Optimization of a Cu CMP process modeling parameters of nanometer integrated circuits. J. Semicond., 2012, 33(8): 086001. doi: 10.1088/1674-4926/33/8/086001

[11]

Yuanfu Zhao, Chunqing Yu, Long Fan, Suge Yue, Maoxin Chen, Shougang Du, Hongchao Zheng. A prediction technique for single-event effects on complex integrated circuits. J. Semicond., 2015, 36(11): 115003. doi: 10.1088/1674-4926/36/11/115003

[12]

Xiangfei Chen. Precision photonic integration for future large-scale photonic integrated circuits. J. Semicond., 2019, 40(5): 050301. doi: 10.1088/1674-4926/40/5/050301

[13]

Lintao Liu, Yuhan Gao, Jun Deng. Design and implementation of a reconfigurable mixed-signal SoC based on field programmable analog arrays. J. Semicond., 2017, 38(11): 115001. doi: 10.1088/1674-4926/38/11/115001

[14]

Xiaogang Tong, Jun Liu, Chenyang Xue. High-Q micro-ring resonators and grating couplers for silicon-on-insulator integrated photonic circuits. J. Semicond., 2013, 34(8): 085006. doi: 10.1088/1674-4926/34/8/085006

[15]

Liang Tao, Jia Xinzhang, Chen Junfeng. Accurate metamodels of device parameters and their applications in performance modeling and optimization of analog integrated circuits. J. Semicond., 2009, 30(11): 115008. doi: 10.1088/1674-4926/30/11/115008

[16]

Li Ming, Zhang Haiying, Xu Jingbo, Fu Xiaojun. Monolithic Integrated Switches and Logic Control Circuits with E/D-Mode GaAs PHEMTs. J. Semicond., 2008, 29(9): 1823.

[17]

Hongda Chen, Zan Zhang, Beiju Huang, Luhong Mao, Zanyun Zhang. Progress in complementary metal-oxide-semiconductor silicon photonics and optoelectronic integrated circuits. J. Semicond., 2015, 36(12): 121001. doi: 10.1088/1674-4926/36/12/121001

[18]

Chen Si, Yang Zengwang, Gu Mingliang. A fully integrated direct-conversion digital satellite tuner in 0.18 μm CMOS. J. Semicond., 2011, 32(4): 045004. doi: 10.1088/1674-4926/32/4/045004

[19]

Dai Lan, Zhou Yumei, Hu Xiaoyu, Jiang Jianhua. Implementation of a Digital Calibration Algorithm for Pipelined Analog-to-Digital Converters. J. Semicond., 2008, 29(5): 993.

[20]

Gao Tongqiang, Zhang Chun, Chi Baoyong, Wang Zhihua. Design and analysis of a highly-integrated CMOS power amplifier for RFID readers. J. Semicond., 2009, 30(6): 065008. doi: 10.1088/1674-4926/30/6/065008

Search

Advanced Search >>

GET CITATION

R Q Luo, X L Chen, Y J Ha, A routing algorithm for FPGAs with time-multiplexed interconnects[J]. J. Semicond., 2020, 41(2): 022405. doi: 10.1088/1674-4926/41/2/022405.

Export: BibTex EndNote

Article Metrics

Article views: 176 Times PDF downloads: 23 Times Cited by: 0 Times

History

Manuscript received: 06 December 2019 Manuscript revised: 31 December 2019 Online: Accepted Manuscript: 06 January 2020 Uncorrected proof: 10 January 2020 Published: 11 February 2020

Email This Article

User name:
Email:*请输入正确邮箱
Code:*验证码错误
XML 地图 | Sitemap 地图