J. Semicond. > 2020, Volume 41 > Issue 2 > 022405
|

ARTICLES

A routing algorithm for FPGAs with time-multiplexed interconnects

Ruiqi Luo1, 2, 3, Xiaolei Chen4 and Yajun Ha1,

+ Author Affiliations

 Corresponding author: Yajun Ha, Email: hayj@shanghaitech.edu.cn

DOI: 10.1088/1674-4926/41/2/022405

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 arrays, digital integrated circuits, routing algorithm design and analysis, digital integrated circuits



[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 doi: 10.1145/2068716.2068718
[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 doi: 10.1109/TCAD.2018.2887050
[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 doi: 10.1109/TCAD.2017.2768416
[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
Fig. 1.  Island-style architecture, which is the base of TM-ARCH with the time-multiplexed interconnects.

DownLoad: Full-Size Img PowerPoint
Fig. 2.  (a) Signals $ N_1 $ and $ N_2 $ occupy a wire at different time. (b) In time domain, $ N_1 $ and $ N_2 $ do not overlap. (c) TM switches’ different states.

DownLoad: Full-Size Img PowerPoint
Fig. 3.  Routing resource graph of TM-ARCH architecture.

DownLoad: Full-Size Img PowerPoint
Fig. 4.  Pseudo code for computing the occupation bitmaps.

DownLoad: Full-Size Img PowerPoint
Fig. 5.  Pseudo code for computing the congestion cost.

DownLoad: Full-Size Img PowerPoint
Fig. 6.  Pseudo code for computing the congestion cost.

DownLoad: Full-Size Img PowerPoint
Fig. 7.  (Color online) The TM-ARCH and TM-ROUTER evaluation framework.

DownLoad: Full-Size Img PowerPoint

Table 1.   Resource utilization of the system.

Routing schedule Value
$ p_{f_{\rm ac}} $ 0.5 in the first and the second routing iteration; 1.3 times its previous value from the third iteration onwards.
$ h_{f_{\rm ac}} $ 1.0 for all the iterations.
DownLoad: CSV

Table 2.   Main Features of Baseline FPGA Architecture.

Feature parameter Value/specification
LUT size 4
Logic block size 10
Logic block inputs 22
Amount of bias between horizontal and vertical channels No bias
Uniformity of routing channels in the same direction Uniform
Aspect ratio 1 : 1 (Assuming square logic blocks)
Segmentation distribution 100% length 4 wires
Switch types used Uni-directional single driver switches
Switch block topology Wilton
Switch block internal population 100%
Connection block internal population 100%
DownLoad: CSV

Table 3.   Minimum channel width for different $ M_{\rm c} $ values.

Parameter $ M_{\rm c}=1,W_{\rm{min}} $ $ M_{\rm c}=2,W\,{'}_{\rm{min} } $ $ M_{\rm c}=4,W\,{'}_{\rm{min} } $ $ M_{\rm c}=6,W\,{'}_{\rm{min} } $ $ M_{\rm c}=8,W\,{'}_{\rm{min} } $
Alu4 48 48 30 36 26
Apex2 62 62 36 34 22
Apex4 64 64 50 36 28
Bigkey 44 44 32 32 30
Clma 78 76 74 48 34
Des 44 42 34 32 32
Diffeq 38 36 34 32 30
Dsip 38 36 30 30 30
Elliptic 62 58 52 N.A. 34
Ex1010 74 74 60 40 34
Ex5p 68 68 48 34 22
Frisc 74 74 44 40 40
Misex3 54 54 42 26 22
Pdc 90 90 128 60 70
S298 34 34 28 28 20
S38417 48 48 50 26 22
S38584.1 50 50 48 26 22
Seq 60 60 48 26 22
Spla 74 72 N.A. 52 34
Tseng 46 46 40 34 32
Geo.Mean 56 55 44 34 29
Reduction – –1.78% –21.43% –39.28% –48.21%
DownLoad: CSV

Table 4.   Percentages (%) of wire used in each individual microcycle for 20 benchmark circuits with $ M_{\rm c} = 2,4 $.

Parameter $ M_{\rm c}=2 $ $ M_{\rm c}=4 $
1st 2nd 1st 2nd 3rd 4th
Alu4 94.59 4.67 56.04 29.64 4.19 0.45
Apex2 97.09 2.42 67.82 25.32 2.17 0.21
Apex4 87.35 10.56 28.13 56.96 9.45 1.00
Bigkey 93.65 4.77 61.57 28.13 4.77 0.00
Clma 96.50 2.97 68.86 25.69 2.83 0.12
Des 90.08 9.15 63.16 24.61 6.50 1.96
Diffeq 95.97 3.80 74.31 18.47 3.71 0.10
Dsip 94.70 4.28 59.70 31.89 4.04 0.18
Elliptic 95.35 4.46 87.51 7.36 3.65 0.73
Ex1010 90.04 8.67 23.65 64.19 7.98 0.51
Ex5p 82.63 14.85 21.70 56.98 12.71 1.99
Frisc 86.87 12.06 68.23 18.50 10.58 1.41
Misex3 93.09 5.60 52.19 33.60 4.64 0.80
Pdc 95.09 4.36 46.93 42.92 3.88 0.42
S298 85.82 13.48 63.21 21.00 9.76 3.16
S38417 92.87 6.60 65.09 24.77 5.83 0.67
S38584.1 97.41 1.88 73.30 19.91 1.59 0.26
Seq 97.50 2.20 69.24 24.66 1.99 0.17
Spla 95.98 3.60 49.20 41.06 3.31 0.25
Tseng 96.48 3.34 88.49 6.82 2.35 0.73
Geo.Mean 92.85 5.17 55.83 26.19 4.49 0.51
DownLoad: CSV

Table 5.   Minimum channel width for different $ M_{\rm c} $ values.

Parameter $ M_{\rm c}=1 $ $ M_{\rm c}=2 $ $ M_{\rm c}=4 $ $ M_{\rm{c}}=6 $ $ M_{\rm{c}}=8 $
$ W_{\rm{ls}} $ $ T_{\rm{crit}} $ $ W\,{'}_{\rm{ls} } $ $ T\,{'}_{\rm{crit} } $ $ W\,{'}_{\rm{ls} } $ $ T\,{'}_{\rm{crit} } $ $ W\,{'}_{\rm{ls} } $ $ T\,{'}_{\rm{crit} } $ $ W\,{'}_{\rm{ls} } $ $ T\,{'}_{\rm{crit} } $
Alu4 58 3.31 58 3.31 36 3.31 44 3.23 32 3.45
Apex2 74 3.90 74 3.90 46 3.69 44 3.69 26 3.65
Apex4 76 3.80 76 3.80 58 3.13 40 3.20 32 3.20
Bigkey 52 1.80 52 1.87 38 1.80 38 1.80 38 1.80
Clma 94 6.74 94 6.74 88 6.63 58 6.70 44 6.70
Des 52 2.86 48 N.A. 40 2.78 38 2.85 38 2.85
Diffeq 46 4.44 44 4.51 40 4.37 38 4.44 36 4.37
Dsip 46 1.73 44 1.73 36 1.80 36 1.80 36 1.80
Elliptic 74 6.22 70 5.52 62 5.66 N.A. N.A. 40 5.37
Ex1010 88 4.42 88 4.42 72 4.49 48 N.A. 40 4.42
Ex5p 82 3.55 82 3.55 58 3.34 40 3.23 26 3.37
Frisc 88 7.63 88 7.63 52 7.42 48 7.42 48 7.49
Misex3 64 3.13 64 3.13 50 3.06 32 3.20 26 3.27
Pdc 108 5.26 108 5.26 154 4.49 72 4.49 84 4.49
S298 40 N.A. 40 N.A. 34 6.14 34 6.17 24 6.07
S38417 58 4.68 58 4.47 60 4.47 32 4.61 26 4.40
S38584.1 60 3.71 60 3.71 58 N.A. 32 3.64 26 3.65
Seq 72 3.13 72 3.13 58 3.06 32 3.20 26 3.06
Spla 88 4.46 88 4.46 N.A. N.A. 62 4.14 40 4.07
Tseng 56 4.43 52 4.43 48 4.43 40 4.43 38 4.43
Geo.Mean 66 3.90 65 3.95 53 3.83 41 3.75 35 3.85
Reduction N.A. N.A. –1.51% 1.28% –19.69% –1.79% –37.87% –3.84% -46.97% -1.28%
DownLoad: CSV
[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 doi: 10.1145/2068716.2068718
[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 doi: 10.1109/TCAD.2018.2887050
[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 doi: 10.1109/TCAD.2017.2768416
[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

    • Search

    Advanced Search >>

    GET CITATION

    shu

    Export: BibTex EndNote

    Article Metrics

    Article views: 4136 Times PDF downloads: 79 Times Cited by: 0 Times

    History

    Received: 06 December 2019 Revised: 31 December 2019 Online: Accepted Manuscript: 06 January 2020Uncorrected proof: 08 January 2020Published: 11 February 2020

    Catalog

      Email This Article

      User name:
      Email:*请输入正确邮箱
      Code:*验证码错误
      Send
      Article Navigation >  Journal of Semiconductors  > 2020  >  41(2): 022405
      Ruiqi Luo, Xiaolei Chen, Yajun Ha. A routing algorithm for FPGAs with time-multiplexed interconnects[J]. Journal of Semiconductors, 2020, 41(2): 022405. doi: 10.1088/1674-4926/41/2/022405 ****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.
      Citation:
      Ruiqi Luo, Xiaolei Chen, Yajun Ha. A routing algorithm for FPGAs with time-multiplexed interconnects[J]. Journal of Semiconductors, 2020, 41(2): 022405. doi: 10.1088/1674-4926/41/2/022405 ****
      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.
      shu

      A routing algorithm for FPGAs with time-multiplexed interconnects

      DOI: 10.1088/1674-4926/41/2/022405
      • 1.

        School of Information Science and Technology, ShanghaiTech University, Shanghai 201210, China

      • 2.

        Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China

      • 3.

        University of Chinese Academy of Sciences, Beijing 100049, China

      • 4.

        Intel Singapore, Singapore 339510, Singapore

      More Information
      • Corresponding author: Email: hayj@shanghaitech.edu.cn
      • Received Date: 2019-12-06
      • Revised Date: 2019-12-31
      • Published Date: 2020-02-01

      Catalog

        Journal of Semiconductors © 2017 All Rights Reserved   京ICP备05085259号-2

        /

        DownLoad:  Full-Size Img  PowerPoint
        Return
        Return