---
# System prepended metadata

title: 第十週
tags: [計概]

---

---
title: 第十週
tags: 計概
---
# 老師的有趣內容 - 1
:::info
- 為什麼要刷leetcode
    - 因為公司要徵求一個 Programmer ，但是人太多所以只能問 Leetcode 最快
- 可是如果只會刷 leetcode，那你就是一個碼農
- 你其他的額外技巧才是重要的，才是你的價值
:::
:::success
- 公司真的會去看你的code
    - 可能是真人或機器人，去判斷你的code skill
    - ：那怎樣才算好的code skill 🤔 忘記問了
    - 或是看你的paper


- 老師說明年暑假可以開始實習
    - 第一份工作不用太在意薪水，累積經驗用

- ML 跟 DL 期末沒有要考，只考 ALU 跟 DB 和其他
    - 聽到要上好多新內容，wakuwaku
:::


## CPU  種類

- CISC：Intel, AMD
- RISC：ARM

# Hamming Distance

如何快速地在大量的東西中，找到我想要的特定東西
老師說常用到的方法就是算 「Hamming Distance」，也就是bit的差異數
像 1001 跟 0011 ，最右邊是第 0 位，在第 3 跟第 1 位的值不一樣
所以 Hamming Distance 就是 2
xor可以得到相異的位數

像是從 2T 的資料中找到特定的資料，用 Hammy distance 去找
那要算的話就是要用 bit 運算這樣才快

>老師說當然也需要一些硬體加速

對於 CISC 的 CPU 來說，那些運算已經有 instruction set 幫你寫好這些加速的指令，不用自己刻，但是要加入這麼多指令會有很多缺點

反而RISC有精簡的指令集，因此比較適合做平行，成本耗能低等等

詳情 RISC 跟 CISC 的差異

# ALU

>其實一個簡化的 CPU 就是 ALU，因為以前 CPU 就是用來算術的

就是提供特定數學運算的電路，有一個叫 F 的 selector 選擇要做哪種運算

![](https://drive.google.com/uc?id=1NOUdjLw91ZB3mcIQfxSi8XgX7LuJdFUX&export=download)

但是實際上，F 不是選「要哪個功能」，而是選「要哪個結果」，因為當 ALU 一收到輸入，全部他有負責的的結果就都算好了

![](https://drive.google.com/uc?id=19ply-6SMV2AHDn5-n3BwylwBPcUyruHO&export=download)

# 加法器

:::success
還好之前有看過硬件茶談，有先備知識
:::

- 半加法器：沒有前一位的進位 C~in~
- 全加法器：有前一位的進位 C~in~

![](https://drive.google.com/uc?id=17tF4diPfRxgmXaxymRPnzKVGBIxva5hQ&export=download)

符號

![](https://drive.google.com/uc?id=1KdTwNbr99s4W07w0s4ysETgQx708YxbT&export=download)

## CPAs / Carry Propagate Adders

有三大種類

## Ripple Carry / RCA

中文叫==行波進位全加法器==，或==串行進位全加法器==

### 電路圖

![](https://drive.google.com/uc?id=1Ew39loHa6pkdYbEdvkIrsPb4Gg_rHgxP&export=download)

但是每次都要等前一位計算完才可以計算下一位，所以延遲很高，比較慢

### 時間

如果有 N 個 全加法器(FA)

$$
t_{ripple} = Nt_{FA}
$$

## Carry lookahead / CLA

中文叫==超前進位全加法器==或==並行進位全加法器==

:::info
但其實下面是 RCA 跟 CLA 的混合，到底下再說為甚麼
:::

把 Ripple 拆成 k 個 block，再對每個 block 動手腳：

- 每個 block 就是一個 CLA
- 老師說這是常用的加速技巧
- 這好像 DAC 的思路


---

- 每個 block 去分別計算兩個「結果」：
    - Generate：
        - 由兩個輸入去判斷會不會「產生」進位
        - $G_{i}=A_{i}B_{i}$
    - Propagate
        - 由兩個輸入去判斷會不會「傳遞」進位
        - $P_{i}=A_{i}+B_{i}$
        - 用來跟前一個進位做 AND 運算

有了上面兩個結果，就可以算到底會不會進位
$$
C_{i+1} = A_{i}B_{i} + (A_{i}+B_{i})C_{i} = G_{i} + P_{i}C_{i}
$$

![](https://drive.google.com/uc?id=1qagjtBQDhzsAyuj7WneA5mf9pAtbuF4k&export=download)

接下來，就可以計算每個 Block 會不會有進位

圖中的 G~3:0~ 代表這個 Block 會不會「產生」進位，P~3:0~ 就是會不會「傳遞」進位

實際推導，就是把 C~4~ 依照上面的公式一個一個代入，然後跟 C~in~ AND 的部分就是整塊的 P~3:0~

![](https://drive.google.com/uc?id=10Z7fI6I5G7dnOmmKOsULII3c3Sy9MAiQ&export=download)

:::warning
搭配硬件[茶談的影片](https://www.youtube.com/watch?v=0KIyBXOIuPA&list=PL7mmImi_1wpMVhVpBWr3Bob7kdchdDEoX&index=49)解說服用效果更佳
:::

### 電路圖

![](https://drive.google.com/uc?id=14X4ZmT__imm3gTZEJEr1TXNifreGHH6k&export=download)


### 時間

如果有 N 個 全加法器(FA)，並且 Block 大小為 k

![](https://drive.google.com/uc?id=1R8uNIdOWGsqxcUh-s5TofKgOE38HuHpD&export=download)

也就是說

1. ↓先算出全部人的 $P_{i}$ 跟 $G_{i}$ ：$t_{pg}$
2. ↓再算出每一組的 $P_{j:j-3}$ 跟 $G_{j:j-3}$ ：$t_{pg\_block}$
3. ↓再算出每一組的傳給下一組的進位 $C_{4k-1}$ ：$(\frac{N}{k}-1)t_{AND\_OR}$
4. 最後本位的結果，只需要前一位的進位以及兩個輸出即可決定；而由於每個 block 都有傳輸出給下一個 block，所以 block 間就可以平行運算串行進位的部分，也就是：$kt_{FA}$

:::success
- 整體來看，就是把整體分成各自獨立的 Block ；由於每個 Block 都會提供「進位 C 」給下一個 Block，這樣每個 Block 間就可以平行運算了
    - 『提供「進位 C 」』這個步驟，就類似 Block 間的 RCA
    - 每個 Block 內的運算就是各自獨立的 CLA
:::

## Prefix

這個老師說以前有講但這次不講，因為花太多時間

# 減法器

就是用二補數法，將要減的數弄成 2 補數

而 2 補數需要的「加 1」，可以巧妙的藉由 F 提供，詳情請看總圖

![](https://drive.google.com/uc?id=1MzYYCuDIiE_plf9e8biLF0kZzoa0AVJR&export=download)

# 比較器：等於

就是取 xnor 再 and 起來

![](https://drive.google.com/uc?id=16uFnM0rRRRbLGhRx8iALH9ot0N7QfL6b&export=download)

# 比較器：小於 (SLT:Set Less Than)

只要看兩數相減是不是負數，就知道大小了；所以就利用減法器的結果，取 MSB 出來當輸出

![](https://drive.google.com/uc?id=13FIAfMXO2lhl_I_XNBI5fhxNJU0wqo_R&export=download)


可以注意到，他只取 MSB ，也就是[N-1]的部分
不過在總圖那邊，會看到 Zero Extender，原因是為了回傳相同 bit 大小出去

# 總結回顧

![](https://drive.google.com/uc?id=19ply-6SMV2AHDn5-n3BwylwBPcUyruHO&export=download)

記得，F 是選擇結果而不是選擇要做什麼

F 的第 2 位算是一個「決定」的位數，將功能分成兩大類，主要就是差在將 B 取反
而減法需要取反加 1，所以會多拉一條到加法那裡當作最初的 C~in~，這就是前面說的巧妙的方式

而那個 F 就是之前講過的==機器碼 Machine code==


---

# 老師的有趣內容 - 2

:::warning
- RISC-V
    - 老師說很看好這個

- 老師說可能會遇到一些事情
	- 像是要做 FB 的 AR 眼鏡，當你把那個眼鏡拆開來
	- 會發現有四顆 ARM 的 DSP 晶片，用來做很大的乘法
	- 還有一些 GPU 用來做矩陣的乘法
	- 還有一些 NPU 給神經網絡
- 當你用工具可以做 profiling ，也就是去看程式碼中每個區塊看誰比較慢
	- 比較慢的地方
    - 可以改用機器碼寫
	- 或是去調用 CPU、GPU、NPU 的 Instruction Set
- 而這還只是優化而已，你還要會設計更好的演算法
:::
:::info
- 總之，不能只會軟體，上面凸顯了硬體的重要性在這

- 但是老師說，不可能全部都會，挑有興趣的就可以了
:::


# Shifter & Rotator

有下面三類

- Logical shifter >>
- Arithmetic shifter>>>
- Rotator

![](https://drive.google.com/uc?id=1wF1XZraIC3TwvJRr1gxScRtRlhFHOIfa&export=download)

Right Shifter 要記得依照 Msb

# 老師的有趣內容 - 3

:::success
- 老師說 rotator 跟 shifter 很常用
- 老師說為什麼有一些演算法或結構通常會有 8，因為這個數字，可以巧妙的利用上面那兩個
    - 但是老師沒說仔細的範例，不過他有舉例子 oct tree
- 在電腦視覺應用，這也是你的 code 比別人精簡、比別人快的基礎
:::

## Shifter 電路圖

![](https://drive.google.com/uc?id=1CyCZrq49bs-hZl5znAGsu6uio5R70E1c&export=download)

Shift 的設計蠻直觀的，老師說可以想想Decoder

## Multipliers

老師這裡快速帶過，不過詳請可以看[硬件茶談](https://www.youtube.com/watch?v=8T6O0MHrHVQ&list=PL7mmImi_1wpMVhVpBWr3Bob7kdchdDEoX&index=58)

![](https://drive.google.com/uc?id=1gja1e1rQuBuY__1lFHTBL6fsP9tFNPSl&export=download)

---

# 小數

# 老師的有趣內容 - 4

:::warning
- 老師說浮點數耗電耗記憶體又慢，實際運用上要盡量避免
- 會有精度問題，有 truncate error 要小心
    - 可能會讓你的電腦當掉(?
    - 尤其在像流體力學，大氣那些的數值運算，通常還要用到double或特別的資料型態
    - 或者用整數去逼近，這就是技術所在
:::



## Fixed point

就是以前學的小數表示方式，此時二補數都還可以用來加減
不過 +1 的這個部分變成對 LSB + 1
例如 -7.5 轉成 4bit int 跟 4bit fraction
- 7.5~10~=0111.1000~2~
- 取反得 1000.0111~2~
- 對 LSB +1 得 1000.1000

## Floating point 32 bits

就是用成科學表示法，但是就不能直接做加減了，因為存的內容不一樣
現在用的標準是IEEE 754

:::info
1 bit sign, 8 bits Exponent, 23 bits Mantissa 
:::


$$
±M×2^{E}
$$

:::success
老師說如果你的產品有用到一些國際的專利，那專利費是很可觀的
或者，如果換成是你創一個專利出來，就換你躺著賺
:::

### Sign

表示正負數

### Mantissa

數值的部分

由於第一位一定是 1，所以在儲存時就不留了，可以多一 bit 空間
當然計算時會加回去

### Exponent 

指數的部分

負數指數的話不用 2 補數，而是用一個「biased」，8 bit 的話是 127
實際儲存時是讓你的指數加上 biased，例如 1 次方的話實際會存 128
所以最多只能到2的127次方跟-126次方...想不到吧，128跟-127被用作特殊情形
圖片在下方，[請參考](https://zh.wikipedia.org/zh-tw/IEEE_754)

---
### 儲存

最後「從頭到尾」用16進制表示

## 範例 228

將 228~10~ 用浮點數表示

- 228 = 11100100 = 1.11001 × 2^7^
    - Exponent：127(01111111) + 7(00000111) = 134(10000110)
        - Biased + Exponent
    - Mantissa：1.11001
        - 1 不用記，所以是 11001
    - Sign：0
        - 正數

![](https://drive.google.com/uc?id=1Nwzwi31USkR3U5-PdaengKUdrrPbtsdA&export=download)

將 (4)0100 (3)0011 (6)0110 (4)0100 (0)0000 (0)0000 (0)0000 (0)0000 用 16 進制儲存
也就是 0x43640000

這也是為什麼要宣告型態；因為都是用16進制去存，但是不同型態會有不同的結果

## 範例負數 -1109.25

- 1109.25 = 1109+0.25 = 10001010101+0.1 = 1.000101010101×2^10^
    - Exponent：127 + 10 = 137(10001001)
        - Biased + Exponent
    - Mantissa：1.000101010101
        - 1 不用記，所以是 00010101010100000000000
    - Sign：1
            - 負數

| Sign | Exponent |        Fraction         |
|:----:|:--------:|:-----------------------:|
|  1   | 10001001 | 00010101010100000000000 |

- 換成 16 進制：0xC48AA800

|  C   |  4   |  8   |  A   |  A   |  8   |  0   |  0   |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| 1100 | 0100 | 1000 | 1010 | 1010 | 1000 | 0000 | 0000 |

## 範例 Double 正數 133169151.34375

- 133169151 + 0.34375 = 111111011111111111111111111 + 0.01011
- = 1.1111101111111111111111111101011×2^26^
    - Exponent：1023(01111111111) + 26(00000011010) = 1049(10000011001)
        - Biased + Exponent
    - Mantissa：1.1111101111111111111111111101011
        - 1 不用記，所以是 1111101111111111111111111101011000000000000000000000
    - Sign：0

| Sign |  Exponent   |                       Fraction                       |
|:----:|:-----------:|:----------------------------------------------------:|
|  0   | 10000011001 | 1111101111111111111111111101011000000000000000000000 |

- 換成 16 進制

|  4   |  1   |  9   |  F   |  B   |  F   |  F   |  F   |  F   |  D   |  6   |  0   |  0   |  0   |  0   |  0   |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| 0100 | 0001 | 1001 | 1111 | 1011 | 1111 | 1111 | 1111 | 1111 | 1101 | 0110 | 0000 | 0000 | 0000 | 0000 | 0000 |



---

## 特殊情形

![](https://drive.google.com/uc?id=1_mtAR2nlz_xnZwT0341BhvCw54hG-HG5&export=download)

## Double 64 bits

:::info
1 bit sign, 11 bits Exponent, 52 bits Mantissa 
:::

Double 就是很在意精度，所以mantissa才這麼多

:::warning
老師說雖然硬體有加速，但是還是要盡量避免
:::

## Rounding

當下列情形發生時，就會有 Rounding

- Overflow：數字太大
- Underflow：數字太小

有四個 mode 可以決定

- Down
- Up
- Toward zero
- To nearest

下面是一個只能表示 3 bits 的浮點數的例子

![](https://drive.google.com/uc?id=1SEdWoBpW-Gh-xh6-faArTa9naZqIpZJJ&export=download)

---

# Counter

每過一個 CLK 就 + 1，然後到了最大值就 Overflow 回到 0

![](https://drive.google.com/uc?id=13_HtNAvo9_UDQ5TTa8RNOfjzoSZNCEGD&export=download)

:::info
老師快速帶過
:::

# Shift Register

三種

- 輸入
    - Shift a new bit in on each clock edge 
- 輸出
    - Shift a bit out on each clock edge 
- Serial-to-parallel converter
    - 將序列的(Serial)輸入並列地(parallel)輸出

![](https://drive.google.com/uc?id=1aM8l1EaLGEKCUdaUEW5uFyWmKnpJUzH9&export=download)

老師說網路上資料是一個一個吃進來，但是最後要直接輸出原本的樣子，所以就是每次吃一個進來就shift 一次，也就是上面的第三個

## Two function Combination

![](https://drive.google.com/uc?id=1Fkrr_EDnEQqyuIlTSmC5PC-jqfiQfTHX&export=download)


---

# Memory Arrays

老師這裡直接飆車

介紹

![](https://drive.google.com/uc?id=1tJCGVoVtyoPhs2xSLCCvDkcOUf54S2Ep&export=download)

向上圖下方就是一個 2^2^ × 3-bit 的 Memory Array

## Wordine

實際上的線路長得像下面的圖

![](https://drive.google.com/uc?id=1EarUrDgcjEW38ndKvylyKPsdwz-qEd-7&export=download)

利用 Decoder 定址，以讀取或寫入特定位置的值
如果只要修改特定的 bit 會有另一個 bitline 可以控制

## Random access memory / RAM

- 同時也是可揮發性的 volatile，也就是斷電後資料就會不見

有兩種，DRAM跟SRAM，一個是用 capacitor，另一個是用  cross-coupled inverters

SRAM和DRAM的差異在於，DRAM得隨時充電，而SRAM儲存記憶不必作自動充電的動作，會出現充電動作的唯一時刻是有寫入動作時。如果沒有寫入的指令，在SRAM裏不會有任何東西被更動，這也是它為什麼被稱為靜態的原因。SRAM的優點是它比DRAM快得多。缺點則是它比DRAM貴許多，通常被採用來作為快取記憶體（Cache Memory）

## Read only memory / ROM

- 同時也是不可揮發性的 nonvolatile，也就是斷電後資料還在

讀取很快，但是寫入很慢，或幾乎不可能

像是相機中的 Flash memory
