# NCKU DSP Arch Homework 01
contributed by <[`yanjiun`](https://github.com/yanjiunhaha)>
###### tags: `school`, `108 年上學期`
課程：[VLSI design for digital communication systems -N2109 of NCKU](http://vlsilab.ee.ncku.edu.tw/vlsi.html)
學生：顏君翰 MS student
指導老師：[謝明德](http://vlsilab.ee.ncku.edu.tw/prof.html) PhD

## ==Pracitce find iteration bound in DFG==
### ==Problem 1 : Page.58 in [1]==

digraph P1{
    rankdir=LR
	"1(2)" -> D1
    D1     -> D2
    D2     -> "2(3)"
    "2(3)" -> D3
    "4(1)" -> "1(2)" [label=L2]
    "2(3)" -> "3(3)"
    "3(3)" -> "1(2)" [label=L1]
    D3     -> "4(1)"
    
    D1 [shape=box]
    D2 [shape=box]
    D3 [shape=box]
}

---

#### ==解法一：目測法==
* L1 : 3 -> 1 -> 2 -> 3
Lower bound of Loop 1 :
$\frac{2+2+3}{2}=3.5\ u.t.$

* L2 : 1 -> 2 -> 4 -> 1
Lower bound of Loop 2 :
$\frac{2+3+1}{3}=2\ u.t.$

* Find maxium of all loop in P1
$max{3.5, 2} = 3.5\ u.t.$

==Ans: 3.5 u.tu==

----

#### ==解法二：LPM Algorithm==
1. Format the DFG by longest path delay.

digraph P1_g{
    rankdir=LR
    D1 -> D2 [label=0]
    D3 -> D1 [label=3]
    D2 -> D3 [label=3]
    D2 -> D1 [label=7]
}

* Caculate $L^{(d)}$, d is the number of delays.
2. Initial martx of $L^{(1)}$ by the graph in step 1.
$L^{(1)}=
\begin{bmatrix}
-1 & 0 & -1 \\
7 & -1 & 3 \\
3 & -1 & -1
\end{bmatrix}$

3. Calculate the $L^{(2)}$ by $L^{(1)}$
$L^{(2)}=
\begin{bmatrix}
7 & -1 & 3 \\
6 & 7 & -1 \\
-1 & 3 & -1
\end{bmatrix}$

4. Calculate the $L^{(3)}$ by $L^{(2)}$ and $L^{(1)}$
$L^{(3)}=
\begin{bmatrix}
6 & 7 & -1 \\
14 & 6 & 10 \\
10 & -1 & 6
\end{bmatrix}$

* Find maxium of all loop in P1
5. $max\{\frac{7}{2}, \frac{7}{2}, \frac{6}{3}, \frac{6}{3}, \frac{6}{3}\}=3.5\ u.t.$

==Ans: 3.5 u.tu==

----

#### ==解法三：MCM Algorithm==

digraph P1_g{
    rankdir=LR
    D1 -> D2 [label=0]
    D3 -> D1 [label=3]
    D2 -> D3 [label=3]
    D2 -> D1 [label=7]
}

* Caculate $f^{(d)}$, d is the number of delays.

1. Initial $f^{(0)}$ by D1 of graph
$f^{(0)}=
\begin{bmatrix}
0 \\
\infty \\
\infty \\
\end{bmatrix}$

2. Calculate $f^{(1)}$ by $f^{(0)}$
$f^{(1)}=
\begin{bmatrix}
\infty \\
0 \\
\infty \\
\end{bmatrix}$

4. Calculate $f^{(2)}$ by $f^{(1)}$
$f^{(2)}=
\begin{bmatrix}
-7 \\
\infty \\
-3 \\
\end{bmatrix}$

5. Calculate $f^{(3)}$ by $f^{(2)}$
$f^{(3)}=
\begin{bmatrix}
-6 \\
-7 \\
\infty \\
\end{bmatrix}$

* Find maxium of all loop in Problem1
$T_{\infty}=-min_{i\in\{1, 2, \dots, d-1\}}(max_{m\in\{1, 2, \dots, d-1\}}(\frac{f^{(d)}_{(i)}-f^{(m)}_{(i)}}{d-m}))$

6. step 1 : find $\frac{f^{(d)}_{(i)}-f^{(m)}_{(i)}}{d-m}$
$\frac{1}{3}\begin{bmatrix}-6\\-\infty\\-\infty\end{bmatrix}$ $\frac{1}{2}\begin{bmatrix}-\infty\\-7\\0\end{bmatrix}$ $\frac{1}{1}\begin{bmatrix}1\\-\infty\\-\infty\end{bmatrix}$

7. step 2 : find $max_{m\in\{1, 2, \dots, d-1\}}$
$\begin{bmatrix}1\\-3.5\\\infty\end{bmatrix}$

8. step 3 : find $min_{i\in\{1, 2, \dots, d-1\}}$
$-3.5$

==Ans: 3.5 u.t.==

### ==Problem 3 : Page.59 in [1]==

digraph P2{
    rankdir=LR
    "+(1)" -> "+(7)"
    "+(1)" -> "*(3)" [label=D]
    "+(1)" -> "*(4)" [label="2D"]
    "+(1)" -> "*(5)" [label=D]
    "+(1)" -> "*(6)" [label="2D"]
    "*(3)" -> "+(2)"
    "*(4)" -> "+(2)"
    "+(2)" -> "+(1)"
    "*(5)" -> "+(8)"
    "*(6)" -> "+(8)"
    "+(8)" -> "+(7)"
}

1. Change the circut to DFG.

digraph P2_dfg{
    rankdir=LR
    "1(1)" -> "2(7)"
    "1(1)" -> D1 -> "4(3)"
    "1(1)" -> D4 -> D3 -> "7(4)" 
    "1(1)" -> D2 -> "5(5)" 
    "1(1)" -> D5 -> D6 ->"8(6)" 
    "4(3)" -> "3(2)"
    "7(4)" -> "3(2)"
    "3(2)" -> "1(1)"
    "5(5)" -> "6(8)"
    "8(6)" -> "6(8)"
    "6(8)" -> "2(7)"
    D1 [shape=box]
    D2 [shape=box]
    D3 [shape=box]
    D4 [shape=box]
    D5 [shape=box]
    D6 [shape=box]
}

----

#### ==解法一：目測法==
2. 觀察圖( step.1 )，由於點 2 為終點無法形成 cycle，因此不考慮點 2。生成圖( step. 1 )之子圖如下：

digraph P2_dfg{
    rankdir=LR
    "1(1)" -> D1 
    D1     -> "4(3)" [label=Loop1]
    "1(1)" -> D4 
    D4     -> D3     [label=Loop2]
    D3     -> "7(4)" 
    "4(3)" -> "3(2)" 
    "7(4)" -> "3(2)"
    "3(2)" -> "1(1)" 
    
    D1 [shape=box]
    D4 [shape=box]
    D3 [shape=box]
}

3. 藉由觀察子圖找出兩個 Loop：
Loop1 : D1 -> 4 -> 3 -> 1 -> D1
Lower bound of Loop1
$\frac{4+2+1}{1}=6\ u.t.$

Loop2 : D4 -> D3 -> 7 -> 3 -> 1 -> D4
Lower bound of Loop2
$\frac{4+2+1}{2}=3.5\ u.t.$

4. 計算最大 lower bound 延遲
$max\{6, 3.5\}=6\ u.t.$

==Ans: 6 u.t.==

----

#### 解法二：LPM （不實際）

digraph P2{
    rankdir=LR
    D1 -> D1 [label=6]
    D1 -> D2 [label=6]
    D1 -> D4 [label=6]
    D1 -> D5 [label=6]
    D3 -> D1 [label=7]
    D3 -> D2 [label=7]
    D3 -> D4 [label=7]
    D3 -> D5 [label=7]
    D4 -> D3 [label=0]
    D5 -> D6 [label=0]
}

2. 分析計算複雜度 $O(d^4+de)$
d 為暫存器個數 = V(G) = 6 （圖 G 為上圖）
$O(d^4+de)=6^4+6*10$
==用此方法計算不實際==

2. 還是可以意思意思求出 $L^{(1)}$
$L^{(1)}=
\begin{bmatrix}
6 & 6 & -1 & 6 & 6 & -1 \\
-1 & -1 & -1 & -1 & -1 & -1 \\
7 & 7 & -1 & 7 & 7 & -1 \\
-1 & -1 & 0 & -1 & -1 & -1 \\
-1 & -1 & -1 & -1 & -1 & 0 \\
-1 & -1 & -1 & -1 & -1 & -1 \\
\end{bmatrix}$

----

#### 解法三：MCM
2. Format fig in Step.1 by longest path delays

digraph P2{
    rankdir=LR
    D1 -> D1 [label=6]
    D1 -> D2 [label=6]
    D1 -> D4 [label=6]
    D1 -> D5 [label=6]
    D3 -> D1 [label=7]
    D3 -> D2 [label=7]
    D3 -> D4 [label=7]
    D3 -> D5 [label=7]
    D4 -> D3 [label=0]
    D5 -> D6 [label=0]
}

* Caculate $f^{(d)}$, d is the number of delays.

3. Initial $f^{(0)}$ by D1 of graph
$f^{(0)}=
\begin{bmatrix}
0 \\
\infty \\
\infty \\
\infty \\
\infty \\
\infty \\
\end{bmatrix}$

3. Calculate $f^{(1)}$ by $f^{(0)}$
$f^{(1)}=
\begin{bmatrix}
-6 \\
-6 \\
\infty \\
-6 \\
-6 \\
\infty \\
\end{bmatrix}$
3. Calculate $f^{(2)}$ by $f^{(1)}$
$f^{(2)}=
\begin{bmatrix}
-12\\
-12\\
-6 \\
-12\\
-12\\
-6 \\
\end{bmatrix}$
3. Calculate $f^{(3)}$ by $f^{(2)}$
$f^{(3)}=
\begin{bmatrix}
-18\\
-18\\
-12\\
-18\\
-18\\
-12\\
\end{bmatrix}$
3. Calculate $f^{(4)}$ by $f^{(3)}$
$f^{(4)}=
\begin{bmatrix}
-24\\
-24\\
-18\\
-24\\
-24\\
-18\\
\end{bmatrix}$
3. Calculate $f^{(5)}$ by $f^{(4)}$
$f^{(5)}=
\begin{bmatrix}
-30\\
-30\\
-24\\
-30\\
-30\\
-24\\
\end{bmatrix}$

3. Calculate $f^{(6)}$ by $f^{(5)}$
$f^{(6)}=
\begin{bmatrix}
-36\\
-36\\
-30\\
-36\\
-36\\
-30\\
\end{bmatrix}$

* Find maxium of all loop in Problem2
$T_{\infty}=-min_{i\in\{1, 2, \dots, d-1\}}(max_{m\in\{1, 2, \dots, d-1\}}(\frac{f^{(d)}_{(i)}-f^{(m)}_{(i)}}{d-m}))$

10. step 1 : find $\frac{f^{(d)}_{(i)}-f^{(m)}_{(i)}}{d-m}$
$\frac{1}{6}\begin{bmatrix}-36\\-\infty\\-\infty\\-\infty\\-\infty\\-\infty\end{bmatrix}$ $\frac{1}{5}\begin{bmatrix}-30\\-30\\-\infty\\-30\\-30\\-\infty\end{bmatrix}$ $\frac{1}{4}\begin{bmatrix}-24\\-24\\-24\\-24\\-24\\-24\end{bmatrix}$ $\frac{1}{3}\begin{bmatrix}-18\\-18\\-18\\-18\\-18\\-18\end{bmatrix}$ $\frac{1}{2}\begin{bmatrix}-12\\-12\\-12\\-12\\-12\\-12\end{bmatrix}$ $\frac{1}{1}\begin{bmatrix}-6\\-6\\-6\\-6\\-6\\-6\end{bmatrix}$

7. step 2 : find $max_{m\in\{1, 2, \dots, d-1\}}$
$\begin{bmatrix}-6\\-6\\-6\\-6\\-6\\-6\\\end{bmatrix}$

8. step 3 : find $min_{i\in\{1, 2, \dots, d-1\}}$
$-6$

==Ans: 6 u.t.==

## References
1. [K.K. Parhi, "VLSI Digital Signal Processing System Design And Implementation"](https://www.amazon.com/VLSI-Digital-Signal-Processing-Systems/dp/0471241865)
2. [K.K. Parhi, "Parhi's SLIDES for VLSI SDP design"](http://people.ece.umn.edu/users/parhi/SLIDES/)
3. [Wayne Wolf, "Modern VLSI Design: IP-Based Design, Fourth Edition"](http://www.csit-sun.pub.ro/courses/vlsi/Modern_VLSI_Design.pdf)

### 手稿