# NYCU ICLAB POV-2
## 前言
本周的課程正式進入到循序電路（Sequntial Circuit）的環節。當時大一的時候教授用了"在電路中加入時間觀念"這樣的方式帶過 Sequential Circuit，不過我認為這種說法有點太過抽象，所以我想用我自己的講法給出我對 Sequnential Circuit 的理解。
另外在更新文章之餘，我也會和同學慢慢整理lab的完整檔案還有各家好手的程式碼，如果有時間也可能針對design進行講解，還請期待～
## Lecture 02 --- Finite State Machine
### 電路中的儲存元件
基礎邏輯設計都有介紹到電路當中的儲存結構，如 Latch、Flip-Flop等，基本上都是透過穩定的**回授電路**實現"儲存"這樣的行為，或者加上一些其他的控制機關做出"Set"、"Reset"等動作，當然這些都是維持通電才能保持狀態的元件，和真正生活上會用來"儲存"資料 USB / SSD 的物理原理有很大的不同。
但我認為最重要的概念是：為什麼我們需要這種暫時儲存資料的單位？
思考一下，其實任何電路功能都可以用組合邏輯的方式就可以實現，比方說做 10 個數字的加減，大可以製作 9 個加法器並提供 10 個接口給那些數字的來源，但這樣會消耗很可觀的元件數目對吧？一個比較合理的電路，應該只會有**有限的輸入輸出 pin 腳**，這樣就不可能只使用組合邏輯來實現功能了，因為組合邏輯總會在輸入改變時做出改變，一旦輸入電位不穩定，輸出電位也不會穩定。這是什麼意思？以上述例子來說，組合邏輯**永遠只能輸出 10 個數字的總和**，但循序電路卻可以在**某段時間輸出 1+2、某段時間輸出 1+2+3** ......甚至循序電路也不需要一次接收 10 個數字那麼多輸入，**可以一段時間給它 1、再下一段時間給它 2**......
### 有限狀態機與資料通路（Finite State Machine & Datapath）
循序電路其實就是在原本的組合邏輯中加入可以"**儲存**"及"**維持一段時間**"的元件，作為其內部組合邏輯"**隱藏**"**的額外輸入**。我們可以把所有的儲存元件抓出來，它們的數量必定是有限的（$n$），所以產生的 0 / 1 組合必定是有限的（$2^n$），我們可以把每一個 0 / 1 組合稱為一個**狀態（State）**，由於狀態機的下一個狀態是將現在的狀態經過組合邏輯產生，所以**同樣的狀態必定會產生相同的下個狀態**（組合邏輯特性），這就是狀態機之所以有限的原因。資料通路（Datapath）就是指那些組合邏輯的部分。
講了很多抽象的東西，總結起來就是
**1. 所有儲存單位的值代表著一個 State
2. 由 State 和輸入經過組合邏輯後會產生新的 State 和輸出
3. 儲存單位在某些時刻會把新的 State 更新到自身內部（回到1）**
第 3 點中的**"某些時刻"**，其實就是驅動 Latch 和 Flip-Flop 的 clk 訊號
### 呼叫時序元件
上一篇筆記當中也有大概提到怎麼呼叫時序元件了，以下直接給出範例程式碼
```verilog=
//calling edge triggered Flip-Flop
reg d,e;
always@(posedge clk)begin
d <= e;
end
//calling edge triggered asynchronus reset Flip-Flop
reg d,rst;
always@(posedge clk,negedge rst)begin
if(!rst)
d<=0;
else
d<=e;
end
```
這兩種寫法是在合成階段唯二能被 tool 辨識的 Flip-Flop 寫法，其他如同時被 poedge clk 和 negedge clk 觸發的 Flip-Flop、使用initial block 做初始化的 register 等通通都是旁門左道不可合成。
那為什麼我們需要外接訊號來做 asychronus reset 呢？不是因為開機後Flip-Flop 的初始值是 X（Unknown），而是因為實際上電路在運作的**任何狀態都有可能被 reset**，所以我們不能依賴 reset 訊號來之前的 Flip-Flop 狀態來重啟電路，才把它們設為 X（任何值都要能夠被 reset）。
### Set up & Hold
在剛學習到 Flip-Flop 的特性時，我曾經有這樣子的疑問，為什麼使用 clk 控制所有 Flip-Flop 時，**某顆 Flip-Flop 在 edge 上切換數值時不會因此剛好擾亂下一顆連接的 Flip-Flop呢**（意即資料穿透好幾層Flip-Flop）？
答案是：有可能發生，有可能不會發生，而 tool 會想辦法幫助你讓這種情況不會發生。
電路的訊號傳播需要一定時間的延遲，從輸入穩定到輸出穩定需要時間，反過來說從輸入不穩定到輸出不穩定也需要時間，對於 Flip-Flop 來說，需要輸入在時鐘觸發緣前後一定時間內保持穩定，所以只要滿足兩個原則就可以保證時序電路正常運作。
::: info
clk edge 來臨前，任何 FF 的輸入已經穩定下來 **（Setup time check）**
clk edge 來臨後，任何上一級 FF 改變造成的不穩定輸出不會太快影響到本級 FF 保持穩定 **（Hold time check）**
:::
抓住這樣的概念跟靜態時序分析當中一些名詞的解釋，就能輕鬆搞清楚~~邏設/計組/VLSI/數電/ICLAB各學過一次的~~ **Setup time** 和 **Hold time** 是什麼意思囉！
~~同樣學了很多次的東西們：~~
1. ~~捲積＠訊號與系統/DSP/機率/微方/數電/機器學習/深度學習/ICLAB/影像處理~~
2. ~~Laplace & Fourier Transform＠訊號與系統/DSP/微方/控制~~
**與 Flip-Flop 間的組合邏輯有關**
$T_{pd}$：表示一個邏輯區塊輸入穩定後，達到輸出穩定所需的時間（propagation delay）
$T_{cd}$：表示一個邏輯區塊輸入不穩後，達到輸出不穩定的時間。（contamination delay）
**與 Flip-Flop 有關**
$T_{setup}$：clk edge 來臨前，FF 要求輸入達到穩態的時間
$T_{hold}$：clk edge 來臨後，FF 要求輸入維持穩定的時間
$T_{pcq}$：clk edge 來臨後，FF 輸出達到穩定的時間（clk to q propagation delay）
$T_{ccq}$：clk edge 來臨後，FF 輸出開始不穩的時間（clk to q contamination delay）
**與時鐘有關**
$\Delta t_{skew}$：不同的 FF 接收的時鐘訊號**不一定完全同步**，這個差異（可正可負）就是用這一項表示。
$T_{C}$：Cycle time，表示兩個正緣之間的時間長度。
有了範例電路和說明圖片，我們就可以來仔細看看常見的 Setup 和 Hold 的公式代表什麼意思了。
$$
T_C \ge T_{pcq}+T_{pd}+T_{setup}+\Delta t_{skew}
$$
**從 clk edge 出發、FF1 輸出穩定（$T_{pcq}$）（COMB1輸入穩定）、到 COMB1 輸出穩定前（$T_{pd}$），必須要在下個 clk edge 前的 Setup time 達到穩定**
$$
T_{ccq}+T_{cd} - \Delta t_{skew} \ge T_{hold}
$$
**從 clk edge 出發、FF1 輸出不穩（$T_{ccq}$）（COMB1輸入不穩）、到 COMB1 輸出不穩前（$T_{cd}$），必須撐過 FF2 的 Hold time，避免干擾到 FF2。**
現在我們可以詳細地回答開頭的提問了
::: info
Q：某顆 Flip-Flop 在 edge 上切換數值時不會因此剛好擾亂下一顆連接的 Flip-Flop呢？
A：edge 切換後，保持在穩態的 Flip-Flop 輸入需要經過一汙染延遲（Contamination Delay）時間才會變得不穩，只要該 Flip-Flop 能在 Hold time 內不受干擾，就不用擔心此問題。
:::
在這邊也補充一下到了實體布局和繞線階段 tool 會怎麼修 setup 和 hold violation。Setup 可以透過減少共用邏輯、選用高驅動力的元件、複製多個相同邏輯提高驅動力、或甚至做 retiming 來調整 pipeline 架構。Hold 則可以透過加入 buffer 增加延遲，或刻意讓 clk 產生足夠的 skew 保證不會有問題。
**ref：** https://www.edn.com/ways-to-solve-the-setup-and-hold-time-violation-in-digital-logic/
### for & generate
有撰寫過 C++ 程式碼的讀者想必已經用```for```用到快要爛掉了，~~因為確實好用~~。```for```的行為在模擬階段和在 C++ 裡面時很像，但合成階段會有很大的不同：**```for```會被 Desgin Compiler 依序一行一行展開**，例如。
```verilog=
integer i;
always @(posedge clk)begin
for(i = 0;i<4;i=i+1)begin
image_reg[i]<=image_in[i];
end
end
/*
The following code are the format analyzed by design copiler
always @(posedge clk)begin
image_reg[0]<=image_in[0];
image_reg[1]<=image_in[1];
image_reg[2]<=image_in[2];
image_reg[3]<=image_in[3];
image_reg[4]<=image_in[4];
end
*/
```
拜這項性質所賜，```for``` 多了非常多神奇的限制，我自己有遇過的就有
1. 不要在不同```always```內的```for```共用 integer index，有可能產生 race condition。
2. 不能使用 integer index 存取一個多 bits 變量的部分 bits
```verilog=
reg [2:0]a;
reg [2:0]b_reg[0:7],b_in[0:7];
integer i;
always @(posedge clk)begin
for(i=0;i<8;i=i+1)begin
b_reg[i] <= b_in[i][i:0];//[i:0] is illegal
end
end
```
3. 只能使用可確定的數字當作中止條件，不然合成會失敗
```generate```則是另一項特殊的關鍵字，可以用來一次描述多個相同結構的電路。例如現在有一系列的```input[i]```和```output[i]```需要用多個相同的```example_module```連接，這時就可以讓```generate```登場了。
```verilog=
wire [63:0]in[0:31],out[0:31];
genvar i; //only genvar can iterate through generate
generate
for(i = 0;i<=31;i = i+1)begin
//genvar must be step-incremental with constant upperbound
example_module em(.in(in[i]),.out(out[i]));
end
endgenerate
```
在 generate block 會使用```assign/always/module``` 等關鍵字，複製多個相同的電路；另外 generate block 內迭代的變數必須是 ```genvar``` 型別，只能遞增且須有常數上界；generate block 也可以有```generate if```和```generate case```等變形，這些就不多做說明了。
### Sample Code
以下我提供實際存在我作業內的一些代碼，說明一下我做 Flip-Flop 給值時會用的 Coding Style。
1. **always @(posedge clk) 只做給值**->用在複雜的 FSM 或資料暫存器上
```verilog=
//decribing the DFF of FSM, only do assignment
always @(posedge clk,negedge rst_n) begin
if(!rst_n)
cur_state<=0;
else
cur_state<=next_state;
end
//decribing the Combinational part of FSM
parameter IDLE='d0, INPUT = 'd1, OPERATION = 'd2,OUTPUT = 'd3;
always @(*) begin
case (cur_state)
IDLE: if(in_valid) next_state = INPUT;
else next_state = IDLE;
INPUT: if(in_valid) next_state = INPUT;
else next_state = OUTPUT;
OUTPUT:case (Mode)
'd0: begin
next_state = (output_is_over)?IDLE:OUTPUT;
end
'd1: next_state = IDLE;
'd2: next_state = IDLE;
default: next_state = 0;
endcase
default: next_state = IDLE;
endcase
end
```
2. **always @(posedge clk) 加入一些COMB語句**->通常用在描述規則簡單的 shift register 上
```verilog=
reg [31:0] Img_reg [13:0];
integer i;
always @(posedge clk) begin
//the assignment involves some combinational elemets
Img_reg[0]<={32{in_valid}}&Img;
for(i=1;i<=13;i = i+1)
Img_reg[i]<=Img_reg[i-1];
end
```
## Lab02 Cordinates Calculation
### Description
本周的 Lab 要撰寫一個座標處理器，依序給定一些座標點和選擇訊號 mode 後要計算圍成四邊形包含的整數座標點、面積、或其中兩點圍成的直線能不能與另外兩點決定的圓相切／交／割。Pin腳如下
:::success
**Input**
xi, yi (8bit 2補數)
mode (2'b0->梯形渲染 2'b1圓與直線 2'b2算梯形面積)
in_valid, rst_n, clk (基礎控制訊號，未來會不斷出現，rst_n出現在最開頭提供asynchronus active low reset，input 和 invalid 則會在 clk negedge 給值)
**Output**
out_valid (通知 pattern/下級電路本級完成的訊號)
xo, yo (8bits 不同 mode 有不同含意)
:::
in_valid 拉起後，Cycle 1會給 mode 訊號，Cycle 1~4 會依序給 4 組 8bit signed number 的座標點。依據 mode 的不同，需要對座標做不同處理。
### Strategy
本次計算 Performance 的方式是 $Latency\times Area$，因為 Cycle time 被鎖定在 12ns，所以只要注意 in_valid 落下到 out_valid 升起的Cycle 數目就好。未來會有一些 lab 可以調整 Cycle time。
我自己通常會把 **Latency 的最佳化順序設定在最前面**，拿這次 Lab 當例子，從 1 cycle 開始，多一個 cycle performance 直接被翻倍計算。之後 開始設定 Cycle time時，雖然會有「多一個 Cycle 但換取 Cycle time 減少划不划算？」的問題，但不管怎樣，**拿面積換時間通常是個划算的交易**。
---
#### Mode 0
Mode0 保證 4 個座標點會形成一個矩形，我們則要想辦法判定矩形"**圍**"住哪些網格，並將這些網格的座標由左下角往右上輸出。
###### 例圖中的橘色網格的左下角座標就是應該要輸出的座標點
邊界條件（例如壓線要不要輸出、最上面一排要不要輸出......）在這個 Mode 其實不是最重要的一環，重要的是怎麼計算每一列列首和列尾的座標點，接著讓輸出從列首累進到列尾，再切換到下個列首列尾就好了。
注意到 y 座標每 +1，x 就會位移一個斜率。斜率可由兩個 8 bits 數字相除得到，我們假設商是$Q$、餘是$R$、只考慮正斜率，從左下的網格迭代每一個行首的公式是。（負斜率也只需要稍作控制就可以用正數除法的結果迭代）
$X_0 = X_{grid}$
$R_0 = 0$
$X_i = X_{i-1}+Q+Indicator((R{i-1}+R )>\Delta y)$
$R_i \equiv R_{i-1}+R \ (mod\ \ \Delta y)$
值得注意的是，因為測資保證四個座標點都不同（不會退化成三角形），所以我可以在輸出列中間網格時->迭代行首；輸出走到行尾時->迭代行尾來，進一步共用除法器
::: warning
Tips: 除法元件通常會是電路中最關鍵的部分，面積大、$T_{pd}大$，非使用不可時請盡量嘗試共用或將它 pipeline
:::
最後，我在看合成訊息時發現到 compiler 幫我除法取餘各用了一個除法器，所以我就自己刻了一顆除法器，下方有範例程式碼。
#### Mode1
$a(x_0 \ y_0)$：決定直線的一個點
$b(x_1 \ y_1)$：決定直線的第二個點
$c(x_2 \ y_2)$：圓心
$d(x_3 \ y_3)$：圓周上某點
測資會稍微限制大小保證輸入在 6bits 有號數可表示的範圍內。若圓與直線相切則 yo 輸出 2，相割則輸出 1，不相交則輸出 0。
我自己有稍微先重新改寫公式，總之要知道直線是否與圓相切，等效於判斷以下兩個運算式的大小關係
$${
\left|
\begin{array}{cccc}
\vec{ac} \\
\vec{ab} \\
\end{array}
\right|}^2 ?\ \left| \vec{ab} \right|^2 \left| \vec{cd} \right|^2
$$
c 到 ab 直線的距離可由平行四邊形面積除以ab線段長求得，把這個數值和圓半徑比較就能得到結果
這張圖代表我們可以在不同的時間內利用相同的運算單元，橘色代表 4 個 6bits 數字先兩兩互乘再相加的單元，綠色則代表兩個 13bits 數字的乘法，至於為什麼是這樣設計，就留給讀者自行解讀
#### Mode2
Mode2 保證四個座標點是一個四邊形座標點逆時鐘或順時鐘排序後的結果，所以我們可以利用 Surveyor 公式求面積：
$$
Area =|{1\over 2}( \left|
\begin{array}{cccc}
x_0 & x_1 \\
y_0 & y_1 \\
\end{array}
\right| +
\left|
\begin{array}{cccc}
x_1 & x_2 \\
y_1 & y_2 \\
\end{array}
\right| +
\left|
\begin{array}{cccc}
x_2 & x_3 \\
y_2 & y_3 \\
\end{array}
\right| +
\left|
\begin{array}{cccc}
x_3 & x_0 \\
y_3 & y_0 \\
\end{array}
\right|
)|
$$
同樣地，我們可以利用累加器和一個行列式單元來實現 mode2。
最後，將輸入同時送到 3 個 mode 的輸入端，最後再用一個控制訊號接出來到 out 就可以完成了
### Performance
$Area$：79.5k $um^2$
$Latency$：1 $cycle/pattern$
$Ranking$：4/134
Sign in with Wallet
Connect another wallet