• Journal of Semiconductors
  • Vol. 41, Issue 2, 022405 (2020)
Ruiqi Luo1,2,3, Xiaolei Chen4, and Yajun Ha1
Author Affiliations
  • 1School of Information Science and Technology, ShanghaiTech University, Shanghai 201210, China
  • 2Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China
  • 3University of Chinese Academy of Sciences, Beijing 100049, China
  • 4Intel Singapore, Singapore 339510, Singapore
  • show less
    DOI: 10.1088/1674-4926/41/2/022405 Cite this Article
    Ruiqi Luo, Xiaolei Chen, Yajun Ha. A routing algorithm for FPGAs with time-multiplexed interconnects[J]. Journal of Semiconductors, 2020, 41(2): 022405 Copy Citation Text show less

    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.
    $ t_{\rm{arrival}}(n) = \sum\limits_{m\in source(i)\leadsto n}d_{{m}}+T_{\rm{arrival}}({{source}}(i)), $(1)

    View in Article

    $ t_{\rm{leave}}(n) = t_{\rm{arrival}}(n)+d_{{n}}, $(2)

    View in Article

    $ Bitmap[i] = \left\{ {0,iftarrival>iTucycle+Tgb,0,elseiftleave<(i1)TucycleTgb,1,else,} \right. \!\!$(3)

    View in Article

    $ T_{\rm{ucycle}} = T_{\rm{crit}}/M_{\rm{c}}. $(4)

    View in Article

    $ uOcc[j] = \left\{ {uOcc[j]+1,ifBitmap[j]=1,uOcc[j],else,} \right. $(5)

    View in Article

    $ uOcc[j] = \left\{ {uOcc[j]1,ifBitmap[j]=1,uOcc[j],else,} \right. $(6)

    View in Article

    $ p[j] = 1+{\rm{max}}(0,p_{f_{\rm{ac}}}[uOcc[j]+1-C_{\rm{ap}}]), $(7)

    View in Article

    $ h{[j]^i} = \left\{ {1,i=1,h[j]i1+max(0,hfac[uOcc[j]Cap]),i>1.} \right.$(8)

    View in Article

    $ cCost = p_{{n}}\times h_{{n}}\times b_{{n}}.$(9)

    View in Article

    $ c(n) = Crit(i,j)\times d(n)+[1-Crit(i,j)]\times cCost(n). $(10)

    View in Article

    $ uOcc[i]\leqslant 1, \quad i \in [1,M_{\rm c}]. $(11)

    View in Article