• 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\{ {\begin{array}{*{20}{l}} {0,} & {{\rm{if}}} & {{t_{{\rm{arrival}}}} \gt i{T_{{\rm{ucycle}}}} + {T_{{\rm{gb}}}}},\\ {0,} & {{\rm{else}}\;{\rm{if}}} & {{t_{{\rm{leave}}}} \lt (i - 1){T_{{\rm{ucycle}}}} - {T_{{\rm{gb}}}}},\\ {1,} & {{\rm{else}}}, \end{array}} \right. \!\!$(3)

    View in Article

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

    View in Article

    $ uOcc[j] = \left\{ {\begin{array}{*{20}{l}} {uOcc[j] + 1,} & {{\rm{if}}} & {Bitmap[j] = 1},\\ {uOcc[j],} & {{\rm{else}}}, & {} \end{array}} \right. $(5)

    View in Article

    $ uOcc[j] = \left\{ {\begin{array}{*{20}{l}} {uOcc[j] - 1,} & {{\rm{if}}} & {Bitmap[j] = 1},\\ {uOcc[j],} & {{\rm{else}}}, & {} \end{array}} \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\{ {\begin{array}{*{20}{l}} {1,} & {i = 1},\\ {h{{[j]}^{i - 1}} + {\rm{max}} (0,{h_{{f_{{\rm{ac}}}}}}[uOcc[j] - {C_{{\rm{ap}}}}]),} & {i \gt 1}. \end{array}} \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

    Ruiqi Luo, Xiaolei Chen, Yajun Ha. A routing algorithm for FPGAs with time-multiplexed interconnects[J]. Journal of Semiconductors, 2020, 41(2): 022405
    Download Citation