# IC Design & VLSI CAD
## Reference

#### 1. [IC Design](https://www.youtube.com/playlist?list=PLalv9iDiCjWNUJCOSV4WYeDzpbqbAj1Tv)
#### 2. [VLSI CAD I](https://www.coursera.org/learn/vlsi-cad-logic/lecture/CBOe2/welcome-and-introduction)
#### 3. [VLSI CAD II](https://www.coursera.org/learn/vlsi-cad-layout/home/week/1)

## IC Design
### Overview
#### 數位電路
- 輸入是一系列**bitstream**，根據電路的運算處理，輸出是一系列的**bitstream**
- 根據設計來設定怎樣是0、怎樣是1
- 
- 

#### 邏輯閘 (Logic Gates)
- **邏輯閘(logic gates): 基礎六個閘**
- 
- 
- 
- 
- 
- 
- 統整表：
- 
- 

- 簡單數位電路
- 
- 電路 (Circuits)
- 其中的一個閘(gate)一般由2~14個電晶體組成
- 透過**一組互動的閘**來達成特定邏輯功能就是一個電路
- 許多電路放在一個**PCB** (printed circuit board)板上即是一個系統
- 
### 布林代數 (Boolean Algebra)
- 二值 (Two-valued)
- B = {0, 1}
- 封閉性(Closure): 運算結果不是0就是1
- 特性:
- 
- involution: 做兩次not會得到原本的結果
- commutative(交換律) : 位置交換不重要
- associative(結合律) : 先後順序不重要
- distributive(分配律): 見圖
- **demorgan(笛摩根)**: 見圖
- absorption: 見圖
- 表示 (representations):
- 
- 1. Boolean Algebra
- 2. Truth Table
- 3. Circuit Diagram
- 判斷兩個電路相同:
- 可用**布林代數證明**，也可用**真值表證明**
- 
- **笛摩根定理很常用**
- 
- 
- 
- 
- 
### MinTerms and Maxterms
- #### Minterms and Maxterms
- 表示上需要包含所有的變數
- minterm : 全AND項
- n個變數有$2^{n}$項: ex. $xy$, $xy'$, $x'y$, $x'y'$
- maxterm : 全OR項
- n個變數有$2^{n}$項: ex. $(x+y)$, $(x+y')$, $(x'+y)$, $(x'+y')$
- 兩者互補
- 
- #### Canonical Forms
- 嚴謹的表示方式，需要包含所有變數
- 觀察的結果：
- 任何一個電路可以用**全及項的和(sum of minterms)**表示
- 
- **因為OR是以加法(和)表示**
- 任何一個電路可以用**全或項的積(product of maxterms)**表示
- 
- 根據迪摩根定理 : $f1'' = (f1')'$
- $(f1')' = (m0 + m2 + m3 + m5 + m6)' = ((x'y'z') + (x'yz') + (x'yz) + (xy'z) + (xyz'))'$
- $(f1')' = (x'y'z')'(x'yz')'(x'yz)'(xy'z)'(xyz')'$
- $(f1')' = (x + y + z)(x' + y + z')(x + y' + z')(x' + y + z')(x' + y' + z) = M_{0}M_{2}M_{3}M_{5}M_{6}$
- #### 實際上表示的方法
- Canonical forms雖正式，但比較不精簡
- 實際上表示比較**常用 sum of products 或是 product of sums 表示**
- 根據canonical forms精簡範例：
- 
#### Minimization with K-Map : 電路化簡
- #### 目的:
- 減少邏輯閘數量以**減少成本**
- #### **Gate-level minimization**
- 減少邏輯閘
- 方法:
- 1. 布林代數化簡，ex.交換律、分配律、迪摩爾
- 缺點： 跟經驗有關
- 2. **K-map (Karnaugh map)** 最小化
- 只要按照口訣跟步驟就可以完成，較穩定
- 規範： 在**變數少於7個**的情況可以做
- 缺點： **最簡單的表示可能不是唯一**
- #### K-map Method
- 
- 每個正方形代表一個**minterm** (乘積)，而diagram由一些正方形組成
- **相鄰的方形**的不同只能差到**1個bit**
- **相鄰的方形為1可以 透過OR在一起可以簡化**
- **合併法要是1->2->4->8** : 不能合併3個、5個
- **標為1的數字都需要被使用**
- 已經被使用的**盡量不用再使用**，但**若可讓電路更精簡，可以重複使用**
- #### Karnaugh map 化簡：
- **1. 兩個變數的karnaugh map化簡**:

- 
- 
- 
- **2. 三個變數的karnaugh map化簡**:
- 範例： $F(x,y,z) = \Sigma{(2,3,4,5)}$ : minterms $(m_{2} + m_{3} +m_{4} + m_{5})$
- 第一種化簡： 
- 第二種化簡： 
- 範例： $F(x,y,z) = \Sigma{(0,2,4,5,6)}$
- **如果可讓電路更精簡，單格可以用一次以上**： 
- 範例： $F(x,y,z) = \Sigma{(3,4,6,7)}$
- **沒必要不要重複使用：** 
- **3. 四個變數的karnaugh map化簡**:
- 範例： $F(w,x,y,z) = \Sigma{(0,1,2,4,5,6,8,9,12,13,14)}$
- **如果可讓電路更精簡，單格可以用一次以上**： 
- 範例： $F = A'B'C' + B'CD' + A'BCD' + AB'C'$
- 
- 範例： $F(w,x,y,z) = \Sigma{(0,2,3,5,7,8,9,10,11,13,15)}$
- 多種選擇： 

- **4. 四個變數的karnaugh map化簡 with POS**:
- 建議到這個數量以後直接用程式實作
- 過去的例子幾乎都是在簡化後，以sum-of-products(SOP)形式表示，接下來要簡化成product-of-sum(POS) : 透過DeMorgan(迪摩根)
- **F' : sum of products -> F : product of sums**
- 範例： $F(A,B,C,D) = \Sigma{(0,1,2,5,8,9,10)}$ simplify it in **product of sums (POS)** format
- $F' = \Sigma{(3,4,6,7,11,12,13,14,15)}$
- **把F'的組合標示成0，合併為0的地方**
- 
- 根據DeMorgan轉換：
- $(F')' = (AB+CD+BD')' = (A'+B')(C'+D')(B'+D)$
- 範例： $F(A,B,C,D) = \Sigma{(0,2,3,5,7,8,9,10,11,13,15)}$
- 

- #### **規格總結：** 重要！！
- 

### Compliments 補數
...

### [Memory][(https://](https://www.youtube.com/watch?v=O9QUDRblEcA))
- #### latches
- 透過Set/Reset的0/1控制保持或改變值
- #### flipflop
- 透過clk電壓1/0,決定是否把D的輸入記到結果

## VLSI CAD I
### 基礎名詞
#### 1. ASIC (application-specific integrated circuit)
- 為特定用途的電路(ex.紀錄指紋)
#### 2. semi-custom
- 使用過去已設計過的(多個)電路去設計一個複雜電路。
- semi-custom vs full-custom
- **semi-custom:** using pre-existing parts, ex. gates, memories
- **full-custom:** designing right down at the transistor level
#### 3. CAD (Computer-Aided Design)
- 用來指稱電腦輔助設計，但其他領域(如建築)也有CAD的工具，所以在IC Design這邊普遍用EDA(electornic design automation)指稱。

#### 4. SoC (System on Chip)
- 在大型芯片上整合許多功能的區塊
- 

### Computational Boolean Algebra
#### 1. Decomposition strategies
- #### 目的：
- 把複雜function拆成小部分

#### 2. Computational strategies
- #### 目的：
- 讓function跟變數可以被程式運算

#### 介紹主題
- #### (1) **Shannon Expansion**
- 介紹：
- $F(x1, x2, ..., xi, ...,xn)$ : 分別設定$xi = {0,1}改寫$
- $F(x1,x2,...xi,...,xn) = xi * F(xi=1) + xi' * F(xi=0)$
- 即$xi=0$時結果為$F(xi=0)$，當$xi=1$時結果為$F(xi=1)$
- $xi$ 即稱為 **Shannon Cofactor**
- **任何一個 Cofactor 並非一個數字，而是一個函式**
- Multiple Variables 範例:
- 
- 簡約表示方式：
- 
- **Properties of Cofactors**
- 二元布林運算子基本規則：
- 
- #### (2) **Boolean Derivatives (Difference)**
- 計算方式
- xor:
- 
- 可能有誤的解釋：函式f對x微分，就是判斷函式f在x=0和x=1的時候是否不同；不同時xor結果為1，相同xor結果為0。
- 行為：
- 和一般的微分有部分行為相似：
- 
- 1. 微分先後順序不重要
- 2. xor可以拆開
- 3. 常數函式微分結果一直都是0
- **在 AND 和 OR 就和一般微分規則不同**：
- 
- 範例:
- 簡易範例：
- 
- 舉例範例：
- 
- $Cout_{Cin} = ab + (a+b) = a + b$
- $Cout_{\overline{Cin}} = ab$
- $\partial{Cout}/ \partial{Cin}$ = $(a+b) \oplus ab$ = $\overline{(a+b)}(ab) + (a+b)\overline{ab}$ = $a \oplus b$
- 結果：當$a \neq b$ 時，$Cin$會影響$Cout$結果。
- #### (3) **Quatification**
- **Quatification Operators**
- **Universal Quatification : AND**
- 所有cofactors都要滿足
- 

- **Existential Quatification : OR**
- 存在任何一個cofactor滿足
- 
- 總結特性:
- 
- 實際範例(複雜)
- 
- 

- 1. 透過cofactors拆成只有[X,D]變數的function: **針對A1,A0計算cofactors(右上)，即排除他們的影響**
- 2. 計算"是否有[X,D]可以讓所有A1,A0都可以滿足": 計算AND (左下)
- 3. 計算"是否有[X,D]可以讓任一組A1,A0滿足條件" : 計算OR(右下)

- **應用 : Network Repair via Quatification**
- 假設有一個function : $f(a,b) = ab + b'$
- 已知前面半部份的電路設計，要如何設計後半的閘才能得到結果？
- 

- Trick Step 1 : 把懷疑的閘以一個4:1的**多工器(MUX, multiplexor)**取代
- 以**前半部的輸出當select line**，設定巧妙的d**0~d3輸入來模擬所有閘**
- 
- MUX 用途：
- 
- 
- **如何設定d0~d3才能修復此電路？**
- ex. 當僅 d3 = 1 結果正確，是一個AND閘； 當僅 d1~d2=1 結果正確，是一個xor閘。
- 
- Trick Step 2 : 設定一個新的function $Z(a,b,d0,d1,d2,d3) = MUX輸出$，利用xnor檢查是否相等
- 
- **Boolean Statifiability (Boolean SAT) Problem**
- $(\forall{ab}\ Z)[d0,d1,d2,d3]$ : 能否有[d0,d1,d2,d3]能夠讓所有ab都滿足Z=1; Z是最終的輸出(經過xnor閘的)
- 
- **計算過程：**
- function結果: $G(a,b,d0,d1,d2,d3) = d0s1's0' + d1s1's0 + d2s0s1' + d3s0s1$
- 利用ab輸入替換(前半段電路): $G(a,b,d0,d1,d2,d3) = $d0\overline{ab}b + d1\overline{ab}\overline{b} + d2abb + d3ab\overline{b}$
- 計算: $G(a,b,d0,d1,d2,d3) = d0\overline{a}b + d1\overline{b} + d2ab$
- **用xnor驗證G跟F是否相同** : $G\overline{\oplus}F = GF + \overline{G}\overline{F}$
- **帶入G，透過cofactor計算**: 
- $(\forall{ab}\ Z)(...) = d1\overline{d0}d1d2 = d1\overline{d0}d2$
- 判斷結果：d0'd1d2: 可以用OR也可以用XOR閘來修復
- 因為前半部的設計，沒有s0=1和s1=1同時出現的情況(所以沒有d3/d3'出現)

- #### (4) **Tautology**
- #### 定義
- 給定一種表示方式(資料結構)來表示布林函式
- 圖像化：
- 
- 3個變數abc形成的 **Boolean Cube**
- 以圈起來的一群cube(cover of cubes)表示一個函式
- cube表示一個product term，每個cube有$2^k$個vetices
- **如何表示一個cube(即一個product term): PCN(Positional Cube Notation)**
- 
- 每個變數(slot for variable)以**2個bits**表示，以x為例：
- 01 : ...x...
- 10 : ...x'...
- 11 : no x and no x' in product term
- 舉例(abc三個變數)：
- $\overline{a} = [10 11 11]$
- $bc = [11 01 01]$
- 舉例:
- 圈起來的三個部分等同**cube-list** : f(a,b,c) = []+[]+[]
- 

- 建立一種演算法來判斷函式是否針對各種輸入都可以得到1的結果
- 輸入輸出
- Input : cube-list : ex. f(a,b,c) = [10 11 11] + [11 01 01]
- Output: yes/ no, for f==1 always
- **Recursive Computation Strategy**
- 方法：利用Cofactors
- 如果無法判別f()=1，那就拆開看是否每個cofactors結果都是1
- 原理:
- 如果f是tautology(各種輸入都得到1)，他的2個cofactors-$f_{x}$與$f_{x'}$都需要是1
- $F(x) = xF(x=1) + x'F(x=0) = x*1+x'*1 = x+x' = 1$
- #### Recursive Tautology Checking
- #### 如何達成：
- ##### 1. Selection Rules:
- 如何選到正確的變數來計算cofactors
- ##### 2. Termination Rules:
- 如何知道何時可以停止分裂函式、得到f()==1或f()!=1的答案
- ##### 3. Mechanics:
- 帶入x=0, x=1來表示cofactors
- #### 實施：
- 1. 先作mechanics
- - 
- 2. 透過**Unate Function**做到selection/termination
- 一個cube-list如果是unate，更容易確認其是否為tautology
- **unate(統一)**：一個SOP僅具有單一極性，當其中變數在整個函式內 all true, all complemented
- ex1. $ab + ac'd + c'de'$ : unate
- unate : $abc'de'$
- ex2. $xy + x'y + xyz' + z'$ : not unate
- unate: $yz'$
- not unate: $x/x'$
- terminology:
- **positive unate** :
- 當x從0->1，讓f值不變或是f從0->1
- 
- **negative unate**:
- 當x從0->1，讓f值不變或是f從1->0
- **binate**: not unate
- 實際操作：
- **Termination Rules:**
- 

- **Rule 1 :** f==1 : untate 且 all don't care cube[11 11 11 ... 11]
- **Rule 2** :f!=1 : unate 但無 all don't care cube
- **Rule 3** :f==1 : 單一變數且both polarities
- **Selection Rules**
- **讓function變成unate**: 選擇not-unate當作計算cofactors的變數
- **簡化cube-list**: 先選出現在最多的cube內的binate變數
- 條件相同時，選擇 $|true - complement| 最小的（minimum)$ : for tree balance
- 範例：
- ex1. 
- ex2-1. 

- ex2-2. 

- **Unate Recursive Paradigm (URP)：**

                            tautology(cubelist)
                            {
                                if (f is unate)
                                {
                                    //use termination rules to test f==1
                                    if (f==1)
                                        return 1;
                                    else 
                                        return 0;
                                }
                                else if (single var)
                                    return f is unate? 0 : 1;
                                else
                                {
                                    x = most-not-unate variable in f;
                                    //recursive tautology checking
                                    return tautology(fx) && tautology(fx');
                                }
                            }

### [Boolean Representation via BDDs and SAT](https://www.coursera.org/learn/vlsi-cad-logic/home/week/2)
#### Overview
- **通常真實操作下不會用URP，而是使用BDD這個資料結構。**
#### 1. Basic BDD mechanics
- #### 概念 1 : 把布林函式的真值表變成Decision Diagram
- 
- Terminology:
- 
- **variable vertex** : 每個節點（除了leaf node)
- **constant vertex** : 葉節點（terms的結果值）
- **variable ordering**: 變數在decision diagrams的順序（ex.x1x2x3)
- **lo** **pointer** and lo child: 左側表示0的edge與左側的子節點，以**虛線**表示。
- **hi** pointer and hi child: 右側表示1的edge與右側的子節點，以**實線**表示。
- #### 概念 2 : 透過限制 variable ordering 來獲得 Canonical Form的資料結構
- 針對問題：variable ordering不同可以產生多種BDD
- 方法 : 透過限制variable global ordering可以讓資料結構一致（產生一個相同的BDD)
- **每個root到leaf的路徑當中，variable的順序須相同**
- 如果不需要確認這個variable，可以忽略它;每個variable在同個路徑也至多出現一次。
- 
- 但表示方法還是太大，而且可以忽略冗餘讓生成出的diagram仍然無法一致。
- #### 概念 3 : Reduction（縮減）
- 針對問題： 概念2的結果仍然無法產生唯一的BDD
- 方法：判別出**冗餘（redundancies)**，並且**移除**不需要的nodes跟edges
- **實際規範**：
- ##### Rule 1 : 合併相等(equavalent)的葉子
- 合併葉子到剩下0與1
- 
- ##### Rule 2 : 合併isomorphic的節點
- isomorphic ：節點有相同變數與相同子節點(lo/hi須相同）
- 把出發點相同且下個子節點lo/hi值相同的節點合併（來源可能變成2條up)
- ex1 : 
- ex2 : 
- ##### Rule 3 : 清除冗餘的測試
- 變數節點不管值是lo或hi都走到同一個節點，即不需要測試它的值（它的值在這裡沒有影響）
- 
- 
- 最直覺的方法是利用**迭代(iterative)**的方法持續清除冗餘，**但實際上程式不會這樣寫，因為變數太多了（後面介紹）**

- #### 重點總結：
- Reduced Ordered BDD(ROBDD)
- 從BDD開始，訂定出變數順序，化簡圖表
- ROBDD是可以表示所有布林函式的標準資料結構
- 

#### 2. BDD Sharing
- #### Reduced Ordered BDD(ROBDD)
- **從BDD開始，訂定出變數順序，化簡圖表**
- **ROBDD是可以表示所有布林函式的標準資料結構**
- funtion指向BDD的top node，且圖上的邊都是真的指向下一個節點的pointer（但是習慣不畫箭頭）
- 
- 一些例子，使用variable order : x1,x2,x3,x4
- Typical : 
- Odd Parity:
- function是由所有variable之間做xor表示的
- 

- #### BDD Sharing
- #### 重要觀念：
- 所有BDD的節點都表示著一些標準布林函式
- 例子：
- 
- 提示：根據上面的既定節點可以讓原函式變成子函式（ex. $F(x1=0)$等）
- #### Multi-rooted Graph
- 問題：運算當中有很多重複的subfunctions（如下圖灰色區域），我們不想表示同樣的subfunction兩次
- 
- 方法：BDD可以有**多個entry points(或root)**，即有**多個pointers指向**一個node(entry point/root)
- 共用地方分享： 
- 重要小地方： 注意$S_{3}$和$C_{out}$頂端未共用
- 可省下大量的nodes: 

#### 3. BDD Ordering
- #### 實際實施的概念
- Recursive methods
- 利用divide and conquer， 與 URP 相同
- Operators(ops) in BDD:
- AND, OR, NOT, EXOR, CoFactor...etc
- $\forall{Quant}, \exists{Quant}, Satisfy$
- Input/ Output:
- 輸入： shared BDD graphs
- 輸出： 常數0, 1
- ##### 訣竅： **每個我們計算的東西都需要是shared, reduced, ordered的**
- 
- ##### 直觀方法：
- 1. 透過一個gate-level網路，逐步建立
- 新問題：複雜的網路如何處理？
- Ans. BDD Ordering
- 

- #### BDD 應用
- ##### 1. 邏輯比較（函式F與G)
- 
- 分別為函式F與G建立各自的BDD graph
- 相同：
- 如BDD graph相同，F與G的root pointer都會指向同個BDD graph。
- 不同：
- 從F與G的root pointer開始找出從哪裡（哪個變數）不同
- 透過xor找滿足H function的結果（我猜類似network repair那裡的方法）
- ##### 2. Tautology Checking
- 直接確認是否function的pointer直接指向1
- 
- ##### 3. Satifiability
- 所有從root走向leaf=1的路徑（path)都是解
- 

- #### BDD Ordering
- **Variable Ordering會嚴重影響問題(diagram)的複雜度**
- 
- 處理方式：
- 1. **Variable Ordering Heuristics**:
- 好的 BDDs 待你上天堂
- 2. **Characterization**
- **有些問題永遠無法產生好的BDDs**(ex. multipliers)
- 3. **Dynamic Ordering**
- 使用BDD軟體套件來選擇順序
- ##### 實施原則：
- 有關聯的input在順序當中須:
- 靠近(near)彼此
- 鄰近BDD頂端
- 
- ##### 注意事項：Arithmetic Circuits(算術運算電路）
- Arithmetic circuits（運算電路）
- 許多進位鏈算術運算電路有簡單的線性大小ROBDD
- 如加法器，減法器，比較器，Priority encoders?等
- 簡單rule: 交錯變數，如a0b0a1b1a2b2...etc
- 困難的電路：
- 
- ##### 結論：
- 
- ##### 問題：
- 順序有大影響
- BDD太大
- 我們只想知道SAT(是否能滿足這個boolean function)，不需要知道整個函式

#### 4. SAT
- #### Satisfiability (SAT)
- 合適的函式表示： $F(x1,x2,...,xn)$
- 確認assignment:
- 1. 找到**一個 assginment 可以滿足**$F()=1$，**此assignment不需要是唯一的**。
- 2. 如果**沒有任何assignment符合，證明並回傳結果**。
- 

- #### CNF form (Conjunctive Normal Form)
- Standard POS form : product of sums
- 
- **clause**: 一個sum
- positive literal: ex. $c$
- negative literal: ex. $c'$
- 
- **assigment**: 指派部份或全部的變數值
- complete assignment: 所有變數都有給值
- parital assignment: 僅部份變數有給值
- ##### 優點：
- 只有一個clause是0，整個formula即是0(所有clauses的乘積）
- 要使所有clauses=1，才能夠滿足條件
- #### 用 CNF 解決 SAT 實際方法：
- **Recursively!**
- **Decision:**
- 選擇要指派值的變數，簡化CNF formula
- **Deduction:**
- 根據新簡化的clauses，根據clauses的結構與partial assignment，以迭代進行簡化。
- 如何繼續下一步？
- 結束： 如果沒有東西可以簡化或已經能夠判斷SAT
- 重回Secision步驟： 非結束的情況
- 範例：
- 
- **問題： 需要更快的辦法!! Ans : (BCP)**

#### 5. Boolean Constraint Propagation (BCP)
- #### 介紹
- 透過 propagating constraints 來進行 Deduction （用在Deduction階段）

- #### Unit Clause Rule
- BCP常用策略
- unit : 一個clause**只有一個unassigned literal**
- 只有在該unassigned literal為真時，才有可能滿足SAT
- implication : ex. x1=1 make unit clause-> x2=1
- 

- #### BCP Iterative:
- 持續迭代到沒有Implications存在
- Example 1 : conflict, unSAT
- 
- 
- 
- 
- 

- BCP單次可能結果：
- 
- **SAT**: 找到可能的解答
- **UNRESOLVED**: 一個或多個clauses未解，再選下一個unassigned變數，繼續遞迴
- **UNSAT: 發現conflict，須undo並重新assign一個或多個值**
- #### DPLL (Davis-Putnam-Logemann-Loveland Algorithm)
- 介紹：
- 更完整，系統性的搜尋變數assignments
- 有效的CNF形式
- 讓搜尋更早停止，在不增加更多recursion的情況下解決更多assignments
- SAT進展：
- 有效的資料結構表示clauses ： 搜尋更快
- 有效的變數選擇 ： 找到更多implications
- 有效的BCP機制 ： SAT通常花最多時間在這
- 學習機制 ： 找到永遠無法達成SAT的一些pattern，並避免他們
- 好的SAT程式碼可以處理龐大的問題（ex.5萬變數，2.5億literal，5億clauses)
- #### SAT solver
- 現在有很多好的開源solvers
- Examples
- **MiniSAT**
- CHAFF
- GRASP

#### 6. SAT for Logic
- #### BDD vs SAT 功能
- 
-

| 方法 | **BDD** | **SAT**|
| -------- | -------- | -------- |
| work | 不保證在所有case下可以有效 | 不保證在所有case下可以有效 |
| function | **表示**function | **解決function SAT問題** |
| problem | 有可能**OOM ** | 有可能搜尋時間**TLE** |
| assignment(solution) | 會表示**所有**的$\phi$ | **不會找到所有**的$\phi$ |
| support | 大數量的布林操作 | 無法支援大數量的運算子 |
| 得到$\forall{x}F$, $\exists{x}F$ | **都可以達成** | 有解決$\forall{x}F$的版本，也有解決\exists{x}F的版本 |

- #### 典型的 SAT 問題
- 比較logic network是否**相同**
- 
- 每個F與G對應的output，個別進入一個xor比較
- 將每個xor gate出來的結果，進入一個and
- 結果：
- SAT: network不同
- unSAT: network相同
- #### 生成CNF
- ##### 步驟1 : 將Gate轉換成CNF，一次只轉換一個gate
- ##### 步驟2 :Gate Consistency Function (Gate Satisfiability Function)
- 
- 計算d與(ab)'的exnor結果
- $A \overline{\oplus} \overline{ab} = AB + A'B'$
- $\phi_{d} = d \overline{\oplus} \overline{ab} = \overline{a'b'd'+a'bd'+ab'd'} = (a+b+d)(a+b'+d)(a'+b+d) = (a+b+d)(a+d)(b+d)$ [Basic Gates Rules](https://hackmd.io/NtH02fECTTmSavGLYK40cg?view#Basic-Gates-Rules)
- 各種[CNF sub-expression](https://en.wikipedia.org/wiki/Tseytin_transformation)
- 用xnor或xor判斷：
- 
- ##### 步驟3 : assignment數值，得到Gate Consistency Function == '1'，表示這是gate function（consistent）
- 
- ##### 步驟4 : 建立所有Gate Consistency Function，label each wire
- 
- **計算每個gate的gate consistency function，並全部相乘，即AND（每個gate都需要consistent)**

- #### Basic Gates Rules
- 是已經推導出來的精華，可以自己證或背起來！
- 

### [2-Level Logic Synthesis](https://www.coursera.org/learn/vlsi-cad-logic/lecture/ioTvV/2-level-logic-details-for-one-step-expand)

#### 1. 2-Level Logic
- #### 2-Level Minimization
- Example :
- 用SOP(sum of products)表示，僅兩層（很多AND＋1個OR)
- 
- literals : input wires, 即在AND gate有幾個變數
- ex. 14 literals
- 需求： 最少的 AND gate, 最少 input wires

- ##### 作法：
- **不那麼有效與實用的**：boolean algebra(須經驗可能想不到）, Kmaps(可能不知何時停）, Tabular Solution(exponential time)
- **找更好的方法**：
- 不找最佳解，只找**好方法**
- **迭代改進(iterative improvement)**，透過reshape目前的解來獲得可能較好的答案，在沒有改進時停止。
- 最佳 vs 好 by Kmap：
- 
- **good solution:**
- **prime implicants** : 盡量找越大的cubes，無法讓cubes更大
- **irredundant: ** 無法在移除任何一個prime implicants時，同時仍是solution

#### 2. Reduce-Expand-Irredundant Loop : ESPRESSO
- #### 介紹：
- 不一定是最佳解（通常不是）
- 但是是個好解答
- prime
- minimal
- irredundant
- #### 實際作法：
- 
- ##### 步驟 1 : Truth Table with Input Don't Cares
- 比較好表示出一個function
- 真值表的每一列表示Kmap內的一個cube(product term)
- 不一定是prime
- 真值表內的一列可能表示完整真值表(full truth table)當中的好幾列
- ex. abcd (0*0*) 對應 (0000),(0100),(0101),(0001)
- 

- ##### 步驟 2 : Expand Each Cube to be Prime
- **擴展(Expand)**每個cube可以盡可能涵蓋範圍大
- 不一定是比較好的結果
- 

- ##### 步驟 3 : Remove Redundant Cubes
- **redundant** : 移除掉一個cube後，所有的1's仍然完整被覆蓋住
- 移掉所有 redundant 的 cubes
- URP algorithm + covering problem

- ##### 步驟 4 : Reduce the Prime Cover
- **縮減(shrink/reduce)**每個cube，但保持每個1's都要完整覆蓋的狀態
- 可能不一定是prime，但不必要

- ##### 步驟 5 : 重作步驟2與3
- 由於步驟4可能改變目前的cube局面，可能有更好解答

#### 3. Expand in Reduce-Expand-Irredundant Loop
- #### 定義：
- 擴展cube即是從cube移除變數
- 
- #### 效率：
- 
- #### 方法：
- #### 1. 將 Expand 轉換成 Covering Probelm
- **Covering Problem** :
- ex. 選擇最少列，使所有的columns至少有一個1's被包含在內
- 

- #### 2. 用blocking matrix處理的covering problem
- - 
- ##### 2-1 : 建立cube來覆蓋0's (OFF Set)，來確認哪些地方在expand時不該碰到
- 透過 URP **complement** 達到
- ##### 2-2 : 建立 blocking matrix
- **Blocking Matrix** :
- 每一列表示你**想要expand的cube當中的變數們**
- 每一行表示OFF Set (0's的cube)
- 填寫blocking matrix:
- row的變數與column內的極性不同 : 1
- 極性相同/Don't Care ： 0
- 
- **1的意義**：
- **可能在擴展過程中會影響的**
- 擴展(橫軸）$w'$,與（縱軸）$wy'z'$為1，因為擴展$w'$即可能離開$w'$，就有可能處碰到OFF Set即$w'y'z'$。
- 作法：
- 找出**最小可以覆蓋所有column的rows集合**，這些**row變數的乘積(product)就是 legal cube expansion**.
- 

### [Multi-Level Logic Synthesis](https://www.coursera.org/learn/vlsi-cad-logic/lecture/KkQNf/multilevel-logic-and-the-boolean-network-model)

#### Multi-Level vs 2-Level
- #### Multi-level Logic
- **Area** : gates + literals(wires), 即晶片空間有的東西
- 跟literals和gates數量相關，越大需要越多space
- **Delay**: 運算這個function所需要的最高邏輯閘level
- 跟層數有關，越小越少delay

- #### 2-Level vs. Multi-Level Logic
- **沒有2-level限制性這麼多**，且**2-level通常可以得到minimum delay但worst on area。**
- 
- 很少用2-level設計大電路
- 通常用2-level設計小東西
- 
- 甚至很多小東西是用multi-level設計的
- 

#### Boolean Network Model
- #### 概念：
- **connected blocks形成的graph**
- 每個**獨立的component blocks是一個SOP形式的2-lvel Boolean functions**
- 
- terminology:
- primary inputs: a,b
- internal vertices: x= ab+c
- primary outputs: x,y

- #### Total Literal Count
- 先考慮**邏輯複雜度**
- 計算所有nodes中在$=$**右邊的所有變數數量**
- 

- #### 優化Multi-Level Logic
- ~~Multi-Level Logic是一種資料結構，確認需要的operators?(在此是否是處理器？）~~
- 基礎類型：
- 
- **Simplify** network nodes
- 目的： 減少literals
- 每個node都是2-level synthesis
- 使用**ESPRESSO tool**
- **Remove** network nodes
- 小節點看起來不需要特別分開在獨立節點時處理
- 把small factor推進去相關的大節點，減少nodes
- 減少delay，增加space(literals)!
- **Add** new network nodes!!!
- **factoring**，很難！
- 把大節點（big nodes)相關的地方，分割出小節點(small nodes)！
- **trade-off : 減少space（literals），增加delay!**
- 

#### Algebraic Model for Factoring
- #### Algebraic Model
- #### 概念:
- **讓函式可以以polynomial方式處理**
- 在使用上避免"布林變數"獨有的那些，即**只使用那些真實數字可以用的規則**
- #### 真實數字與布林變數規則:
- 
- #### 初步作法:
- 讓變數與補數以不相干的方式處理
- 1. 以**SOP表示布林函式**(像polynomials那樣)
- 2. 每個product term都以一個variables set表示
- 3. SOP表示法即一個包含這些products(cubes)的list
- 
- 缺點:
- **失去了部分變數的表現力**
- #### Algebraic Division
- #### Terminology:
- **divisor** : fundtion D
- **quotient**: 商
- **remainder**: 餘數，若是0，remainder可以稱為factor
- 
- 範例:
- 
- #### 演算法:
- 輸入:
- 以**list of cubes**表示的**函式F**
- **Divisor D**
- 輸出:
- Quotient : Q = F/D
- cubes
- 0 : 空(empty)
- Remainder R
- cubes
- 0 : 如果D是factor
- ##### 策略:
- 走過D當中的每個cubes(cubewise)
- 
- 
- 步驟:
- 把F跟D**拆成一個個cube**
- F有n個cube，D有m個cube，可以做成m*n的表格
- 1. 每格中紀錄第$n_{i}$個cube除以$m_{j}$的cube的結果
- 如果$n_{i,j}$中有$m_{i,j}$的變數存在，表格內紀錄**劃掉**$m_{i,j}$剩下的變數
- 2. 把n個F的cube結果用**OR合併**
- 3. 把m個D的cube做**交集**
- 4. 把D的所有cube與交集後的結果相乘，以F減去結果得到remainder
- 
- ##### 限制事項:
- 1. **Algebraic**:
- 在這樣的計算方法中，務必把**補數先轉換成新的變數**來計算
- **no Boolean, just Algebraic!**
- 
- 2. **Redundant Cubes**:
- 在做F/D的計算時，**F不能有冗餘的cubes**
- cube在SOP的形式中不能有重疊(overlap,cover)
- minimal with repect to single-cube containment
- **可能會違反"Algebraic"的運算規則!**
- 
- ##### 問題: 如何找到合適的Divisor/Factor?

- #### Kernels and Ko-Kernels
- #### Terminology
- Kernels of F
- **用來找到 function F 的 Divisors**
- $K(F)$
- **two-level SOP**
- 函式F的**基礎的結構**
- Co-Kernel
- **用來找到 Kernels**
- #### cube-free
- **乘上single cube的divisor後不能讓F沒有remainder**。即**不能讓F整除single-cube**。
- 
- 
- #### co-kernel
- **single-cube**
- #### Kernel
- ##### F在除以co-kernel後，得到的factor是cube-free
- **kernel本人cube-free**
- 
- ##### Brayton & McMullen Theorem
- multiple-cube divisor
- intersection of kernels
- 
- 
- Real Example:
- 

- #### Finding Kernels
- #### Recursive Method
- 
- #### 問題: k1是F的kernel，那**k1的kernel**呢?
- $F = cube1 * k1 + remainder$, $kenrel of k1 = K(k1)?$
- #### 解法: **遞迴的找**下一個kernel:
- 
- **k2是k1的kernel，k2同時也是F的kernel**
- **co-kernel = cube1 * cube2**
- #### Hierachy of Kernels (階層式)
- 
- #### 定義:
- ##### 1. **以樹的形式表示**
- ##### 2. level-0 kernel :
- 表示**沒有其他kernel在裡面**，即可以得到cube-free的方法只有乘上1
- ##### 3. level-n kernel :
- 包含**至少1個以上的kernel(level-(n-1))在內**，且沒有除自己以外level-n的kernel包含在內。
- #### Find Kernel Recursively
- 使用algebraic division將function除以可能的co-kernels
- **核心概念: co-kernels存在多個cubes，即多個cubes的聯集**
- **技巧: 必須從cube-free function開始做，如尚未cube-free，使用最大的相同(biggest common cube)簡化function來達成。**
- 

- #### Kernel Algorithm
- #### 方法:
- 從單一一個變數開始
- 如果該變數存在於2個以上的cubes，recursively做
- 如果recursive後沒有辦法再拆解，回傳:
- kernel: 多個cubes/common cubes後的聯集
- co-kernel: common cubes
- 
- #### Example:
- 
- 
- #### 問題:
- **可能會重複找同一個kernel好幾次**
- **就算記住哪些變數已經在co-kernels中試過了，abc與cba在目前的算法中視為不同的，仍會重複找**
- 

- #### 總結:
- 
- 也有 Boolean Division 可以在不損失表現力的情況下計算，但計算上比較複雜。

### Multilevel Factor Extract and Don't Cares

- #### Single Cube Case
- #### 方法:
- **找到 prime rectangle**
- 與Kmaps相似
- #### 步驟:
- #### 1. 建立 cube-literal matrix:
- 將一組 **SOP Algebraic Model Boolean** 方程式，轉換成縱軸是各個cubes(product term)，橫軸是各個literal:
- **有出現在product term中的literal**: 紀錄為1。
- 沒有出現的: dot(點.)，表示**Don't Care**。
- 
- #### 2. 找到 rectangle
- **covering probelm** : 找到**一組 rows $R$ 與 columns $C$的交集，其中每row/col都是1**。
- **不需要是連續**的row(cube),column(literal)，只需確保其中都是1。
- 

- #### 結果:
- ##### Primes 即是找到的最大可能的 common single-cube divisors
- prime rectangle 中的 **literals product**，**是相乘(乘積喔)!**
- 

- #### 計算效益 (literal count bookkeeping):
- ##### 減少literals
- 
- Example:
- 
- ab原本出現6次: -6
- 新節點X=ab耗費ab : +2
- ab替換成X: +3
- 節省1個: -6 + 2 + 3 = -1

- #### Multiple Cube Case
- 
- #### 方法:
- 概念與single-cube相似
- 建立matrix
- 找prime rectangle
- 計算literal count bookkeeping
- #### 步驟:
- #### 1. 找到kernel 與 co-kernel
- Brayton-McMullen提出 multiple-cube facotrs是kernels中的product terms的**交集**。
- 

- #### 2. 建立 Co-Kernel--Cube Matrix
- 
- 將一組 **SOP Algebraic Model Boolean** 方程式，轉換成:
- **縱軸座標**: 各個equation的**co-kernel**(**不同equation的要分開獨立row**)
- **橫軸座標**: kernel的所有**unique cube**(**相同的cube共用**一個column)
- ##### 根據縱軸co-kernel對應的kernel是否包含橫軸的cube填寫:
- 
- 有包含: 1
- 沒包含: Don't Case, dot(.)
- #### 3. 找到rectangle
- 與single cube相同，以covering problem找
- 
- #### 結果:
- ##### Prime rectangle 是好的divisors
- **橫軸(columns) 中的 cube 做OR， 注意是相加 (SUM)!**

- #### 計算效益:
- ##### 減少literals
- 
- Example:
- 
- #### 注意事項:
- ##### 1. 可以繼續extract出第2、第3的divisors
- ##### 2. 想實施1，需要在找到前一個divisor後，更新matrix以反映現在的新Boolean Logic Network！

- #### 問題:
- 實際上我們**不會計算所有的**kernels/co-kernels
- **成本太高了**！
- 使用heuristics的方法**找到一個可能是divisor的quick set**
- extract **a subset of** useful kernels

- #### Finding Prime Rectangles
- #### 目標:
- 前面知道怎麼做出matrix，但需要知道實際上怎麼框出來rectangle的方法。
- #### 概念:
- ##### 使用Greedy 在 rectangle Covering 問題
- #### PING PONG 作法 ???
- 
- ##### 1. 選擇 best single row (最佳省下literal的)
- ##### 2. 找尋其他 rows in same place，一次增加一個直到無法增加
- ##### 3. 找尋其他 columns in same place，一次增加一個直到無法增加
- ##### 4. 重複 2,3 直到無法增加
- #### 不同效益比較:
- 

- #### Don't Cares (DCs)
- #### Don't Cares 的應用
- ##### 先前透過 **Algebraic Model 簡化**了模型
- **優點**: **擺脫**了複雜困難的**布林行為**
- **缺點**: 損失了一些特性，**導致結果很難最優(lost some optimality or result quality)**
- ##### 透過 Don't Cares 把特性放回去
- **取出 Don't Cares，並且在各個節點(each node)中利用他們!**
- ##### 在 Multi-level的最大差異：
- **很多，但是是 Implicit的，需要把它們找出來！**

- #### Don't Cares 概念
- #### 一個**永遠不會發生**的 **input pattern**
- #### 2-Level DCs
- 
- #### Multi-Level DCs
- implicit, 需特別尋找

- #### Multi-Level DCs
- ##### 範例與使用方式:
- 在**不知道周遭關係(surrounding environments)**時:
- 
- 在**知道特定變數的來源時(知道部分周遭關係)**:
- **可以知道某些input pattern不可能發生！**
- 
- 
- 
- **轉換後透過Don't Cares(DCs)+Kmaps簡化f**:
- **為什麼可以這麼做？**
- Kmaps基本上是**用SOP表格表示函式**，再透過rectangle簡化。
- **每個product term之間是OR關係**，故**根本不可能出現的輸入**被OR加在函式中，**完全不影響表示**！
- 
- 在**知道更多周遭關係**時
- **可以知道更多的input pattern不可能發生！**
- 
- 
- **在Kmaps中變成Don't Cares(DCs)的變數甚至可以不用表示:**
- 

- **透過Primary Output跟其他節點關係擴展影響**
- **f對Z在什麼情況下不影響(Don't Care)**
- 
- X是0的時候，f不管是0/1，Z=0 :
- $XbY$在$0--$時 insensitive，新版本的Don't Care
- 
- **總結不需要一些nodes:**
- 

- #### 結論:
- Don't Cares (DCs) 是 implicit 且 powerful的
- **需要進一步的方法自動找到 Don't Cares！**
- **Don't Care Cover**:
- 整體來說，Don't Cares(DCs)指在 Boolean function 內**當 input pattern 不可能出現時，當作1**
- **三種類別**：
- **SDCs**
- **CDCs**
- **ODCs**

- #### Satisfiability Don't Cares(SDCs)
- #### 定義：
- 表示每個node那些不可能發生的input/output pattern
- 與Boolean Logic Network內部的wires相關
- 
- #### 方法:
- 找出那些 X 與 expression 不同的情況
- **透過 XOR**！
- 
- #### 總結：
- ##### 重要但無法單獨透SDCs找出簡化的方法！

- #### Controllability Don't Cares(CDCs)
- #### 定義：
- **對於一個 network node，不可能出現的 input patterns**
- #### 方法：
- ##### 1. 取得一個node，所有 wires input 的 SDCs
- ##### 2. 將所有 $SDCs_{f}$ 做 OR
- ##### 3. Universally Quantify 移除那些"未使用"(NOT USED)在此node當中的變數: ex. $\forall{b}$
- 
- #### 過程：
- ##### $SDCs$-> $CDC_{f}$
- ##### 找到f的SDCs
- 
- ##### 可以忽略掉primary inputs(沒有network node)的SDCs
- **primary inputs**: a,b,c,d
- 忽略primary inputs, 只看 X,Y 的 SDCs
- 
- ##### 計算SDCs+做OR+移除f沒有使用到的變數
- 
- 反向驗證合理性:
- 

- #### 特殊Case : External CDCs
- ##### primary inputs 有 Don't Care
- ##### 直接加在OR其他的$SDC_{f}$的地方！
- 
- 反向驗證合理性：
- 
- #### 結論:
- 給出對於$node_{f}$ **不可能出現的input pattern**，以**DCs的方法使用**
- 主要有兩種：
- ##### internal local CDCs:
- 計算 **wires to f 的SDCs**
- ##### external global CDCs:
- DC patterns for network input(**primary inputs**)
- ##### CDCs 並不是所有可能用來簡化nodes的DCs
- ##### CDCs是利用 in front of node F的結構找到DCs
- ##### 還有一種 ODCs 是利用 in back of node F的結構找到DCs

- #### Output Don't Cares(ODCs)
- #### 定義：
- #### patterns可以讓節點的輸出在整個網絡的輸出處被遮蓋
- ##### 即無法在整個網路的輸出處觀察到這個節點的輸出
- ##### 即節點輸出部會影響到任何整體網絡的輸出
- 
- 
- #### 注意的是： 這些patterns並非完全不可能發生(not impossible!)
- #### 概念：
- #### Output F sensitive to input X?
- ##### "導數的補數"是 1 : X 會影響 F
- 
- ##### $Z_{(f=0)}$, $Z_{(f=1)}$ 結果相同
- 
- #### 方法：
- ##### 1. 計算Z對F微分的"導數的補數"，任何使 "導數的補數為1" 的pattern，讓F insensitive for Z。
- ##### 2. Universally Quantify 不是F的輸入的所有變數
- ##### 3. 布林函式用來masking這個node的輸入
- 
- #### 過程：
- ##### 計算 $\overline{\partial{Z}/\partial{F}}$：
- 
- 

- ##### 移除未出現的變數的影響：
- 
- 反向驗證合理性:
- 
- #### General Case (一般的情形) :
- ##### Z 有很多個 inputs
- #### 方法：
- ##### 計算所有的 $\overline{\partial{Z}/\partial{F}}$ 並相乘: 必須同時符合
- 
- #### 總結：
- ##### CDCs+ ODCs = full DCs for simplify
- 
- ##### 新的問題：
- 很大的網路並**不會取得所有的DCs**
- 一些**技巧**去選擇**取出DCs**
- local CDCs
- **不需要取出所有也已經足夠簡化網路**！
- 
- 

## VLSI CAD II : Layout and Timing Verification

### 基本階段/實際順序：
- #### Technology Mapping
- logic gate 透過合成(sythesized) to real gates
- #### Placement
- gates在chip上如何排列
- #### Routing
- 連接在chip上的所有gates
- #### Timing Analysis
- mapped/placed/routed logic的速度

### 基本知識

### Placement
- Placer
- 

- 
- #### Wirelength Models
- Terminology:
- net
- wire in a layout
- netlist
- gates + wires
- 2 points vs 4 points vs hundreds of points
- 2 points net vs 4 points net
- 根據connect在一起的gate的數量
- 
- fanout
- 
- hundreds of points
- 
- many different paths
- path in dense layout may not shortest path
- #### Half perimeter wirelength (HPWL)
- most famous wirelength estimator
- **步驟:**
- 假設gate在每個grid中央
- 畫出包含所有gate的最小bounding box
- HPWL = deltaX + deltaY
- 
- 
- **是wirelength的lower bound**
- #### Simple terative Improvement Placement
- 
- 
- **步驟**:
- 隨機placement開始
- 計算HPWL
- 隨機交換2個閘
- 重新計算各個nets的$\delta{HPWL}$，只要計算有改變的(不要每個都算XD)
- 如果變小，交換閘，並持續改進
- 如果變大，表示這個新的placement不好，不要交換
- 優缺點:
- 缺點:依然太慢了
- 
- 優點: 容易理解也容易實作

- #### Simulated Annealing

- #### The Quadratic Placer

### Technology Mapping

### Routing

### Timing