NCKU DSP Arch NOTE

contributed by <yanjiun>

tags: mynote

課程：VLSI design for digital communication systems -N2109 of NCKU
學生：顏君翰 MS student
指導老師：謝明德 PhD

Retiming (請假)

• 目標：
  • Clock period miniretiming
  • Registers minimization （Linear Problem)
• 特性：
  • Retiming dose not alter the iteration bound in a DFG
  • Retiming 使用 Shortest Path Algorithm 解 constrains graph 得出
    $r(V)$
  • Constrains 有三種
    1. feasible constrains : 不能讓邊上變負的。（必須）
    2. period constrains : 增加最大延遲條件。（通常會加上，需使用合理時間）
    3. registers constrains : 增加某點的fanout條件。（使問題變成線性規劃問題，解題複雜度大幅提升，斟酌使用）
       • 如要使用需要最先使用 registers constrains，再算後續條件。

Demo

• 對以下電路實作完整 Retiming
  

1. feasible constrains
2. Registers constrains
3. Period constrains

Fesaible constrains (origin DFG)

轉換為 DFG 表示法。

Registers minimization (add dummy node and breath

$\beta$ )

增加虛擬點在要限制暫存器之 fanout

$w(\hat{e})=w_{max}-w(e),where{w}_{max}=max\{W_{out}(Node)\}$

$\beta =count.(E_{out}(Node))$

1. 限制點
   $Nod{e}_1$
2. $w_{max}=2D$
   
   $\beta =2$
3. $w_{35}=2D-w_{13}=D$
   
   $w_{45}=2D-w_{14}=0$

Clock period constrains (computing

$W(U,V)$ and

$D(U,V)$)

$w^{\prime }=Mw(e)-t(U),whereM=t_{max}N$

$S_{UV}^{\prime }:\mathrm{對}\mathrm{上}\mathrm{圖}\mathrm{做}ShorestPathAlgorithm$

$W(U,V)=\lceil \frac{S_{UV}^{\prime }}{M}\rceil ,whenU\ne V$

$D(U,V)=MW(U,V)-S_{UV}^{\prime }+t(V)$

• 限制最長延遲
  $c=2$
  
  $r(U)-r(V)\le W(U,V)-1,whenD(U,V)>c$
  
• 加上原圖
  
  
  使用 Shortest path algorithm 求解
• 並且最小化 COST
  ILP Algorithm
  

Definations

• $G$: Original DFG,
  $G_r$: Retimed DFG
• $r(V)$: Delay transferred from outgoing edges of node V to the incident deges of node V.

• $w(e)$: weigth(delay) of the edge
  $e$

• $w_r(e)$: weight(delay) of the dege
  $e$ after retiming.

• $U\stackrel{w_r(e)}{\to }V$ after retiming has a weight of
  $w_r(e)=w(e)+r(V)-r(U)$
  • 因為當前的個數
    $w(e)$ 加上前面拿入的
    $r(V)$ 減去拿出到後面的
    $r(U)$

• weighty of path
  

  $w(p)=\sum _{i=0}^{k-1}w(e_i)$

• path computaion time
  

  $t(p)=\sum _{i_0}^{k}t(V_i)$

Minimium clock period

• $\mathrm{\Phi }(G)=max\{t(p):w(p)=0\}$

• $W(U,V)=min\{w(p):U\stackrel{p}{\to }V\}$
  • Minimum number of registers on any path from node U to node V

• $D(U,V)=max\{t(p):U\stackrel{p}{\to }Vandw(p)=W(U,V)\}$
  • Maximum computation time among all paths from U to V with weight
    $W(U,V)$

• $M=t_{max}n$
  • $t_{m}ax$:max node computation time
  • $n$: number of nodes

• $w^{\prime }(e)=Mw(e)-t(U)$
  • for all edges to create new graph
    $G^{\prime }$

• $S_{UV}^{\prime }$: Solve shortest path problem on
  $G^{\prime }$
  • $IfU\ne Vthen$
    
    $W(U,V)=\lceil \frac{S_U^{\prime }V}{M}\rceil$
    
    $D(U,V)=MW(U,V)-S_{UV}^{\prime }+t(V)$
  • $IfU=Vthen$
    
    $W(U,V)=0$
    
    $D(U,V)=t(U)$

Minimium registers

• $R_v=\underset{V\stackrel{e}{\to }?}{max}\{w_r(e)\}$
  • non-linear function, need reformulate.

Reformulate graph

1. add a dummy node
   $\hat{U}$ to
   $V$
   • $t(\hat{U})=0$ : with no computing time.
   • $w(\widehat{e_i})=w_{max}-w(e_i)$, where
     $w_{max}$ 是
     $V(e)$ 邊中最大的延遲
   • $\beta =1/k$ : 原本
     $V$點有
     $k$條邊，
     $\hat{U}$每條邊則為
     $1/k$條
     

• Registers constrains
  • Minimium the
    $\sum _{V}r(V)(\sum _{?->V}\beta (e)-\sum _{V->?}\beta (e))$
    

介紹

forward cutsets retiming(pipeline) < cutsets retiming < retiming

• Retiming
  

• Cutset retiming rules
  

• forward cutsets retiming(pipeline)
  

• $uN-slow$ DFG
  Replace each delay in a DFG with N delays.
  

• Retiming 2-slow Graph
  
  

Shortest Path Algorithm

Floyd-Warshall algorithm

如果沒有負圈，就會找到最短路徑

1. Initial frist matrix by DFG
   
   $R^{(1)}=\left[\begin{array}{cccc}\mathrm{\infty }& -3& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 1& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2\\ 1& \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }\end{array}\right]$

• if
  $k^{(k+1)}(U,V)>r^k(U,k)+r^k(k,V)$

2. $R^{(2)}=\left[\begin{array}{cccc}\mathrm{\infty }& -3& \mathrm{\infty }& \mathrm{\infty }\\ \mathrm{\infty }& \mathrm{\infty }& 1& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2\\ 1& -2& \mathrm{\infty }& \mathrm{\infty }& \end{array}\right]$

• if
  $k^{(k+1)}(U,V)>r^k(U,k)+r^k(k,V)$

3. $R^{(3)}=\left[\begin{array}{cccc}\mathrm{\infty }& -3& -2& -1\\ \mathrm{\infty }& \mathrm{\infty }& 1& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2\\ 1& -2& -1& 0& \end{array}\right]$

• if
  $k^{(k+1)}(U,V)>r^k(U,k)+r^k(k,V)$

4. $R^{(4)}=\left[\begin{array}{cccc}\mathrm{\infty }& -3& -2& -1\\ \mathrm{\infty }& \mathrm{\infty }& 1& 2\\ \mathrm{\infty }& \mathrm{\infty }& \mathrm{\infty }& 2\\ 1& -2& -1& 0& \end{array}\right]$

• if
  $k^{(k+1)}(U,V)>r^k(U,k)+r^k(k,V)$

5. $R^{(5)}=\left[\begin{array}{cccc}0& -3& -2& -1\\ 3& 0& 1& 2\\ 3& 0& 1& 2\\ 1& -2& -1& 0& \end{array}\right]$