---
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 選擇要做哪種運算


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


# 加法器

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

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


符號


## CPAs / Carry Propagate Adders

有三大種類

## Ripple Carry / RCA

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

### 電路圖


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

### 時間

如果有 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}
$$


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

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

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


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

### 電路圖


### 時間

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


也就是說

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 提供，詳情請看總圖


# 比較器：等於

就是取 xnor 再 and 起來


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

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


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

# 總結回顧


記得，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


Right Shifter 要記得依照 Msb

# 老師的有趣內容 - 3

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

## Shifter 電路圖


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

## Multipliers

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


---

# 小數

# 老師的有趣內容 - 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
- 正數


將 (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 |

---

## 特殊情形


## 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 的浮點數的例子


---

# Counter

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


:::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)輸出


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

## Two function Combination


---

# Memory Arrays

老師這裡直接飆車

介紹


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

## Wordine

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


利用 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