# 台大 109 硬體
###### tags: `NTU` `109` `硬體`

1.
(a)

float conv(float *f, float *g, int n, int M)
{
    float res = 0.0;

    for (int m = -M; m <= M; m++) {
        res += f[n-m] * g[m];
    }
    return res;
}

(b)

    // f is in x0
    // g is in x1
    // n is in x2
    // M is in x3
.L2
    mov x5, #0              // 1. float res = 0.0
    sub x4, xzr, x3         // 2. int m = -M
.L0
    bgt x4, x3, .L1         // 3. compare m with M
    sub x8, x2, x4          // 4. n-m 
    ldr x6, [x0, x8, lsl 2] // 5. load f[n-m]
    ldr x7, [x1, x4, lsl 2] // 6. load g[m]
    fmul x7, x7, x6         // 7.
    fadd x5, x5, x7         // 8. res += f[n-m]*g[m]
    addi, x4, x4, #1        // 9. m++
    b .L0                   // 10.
.L1
    mov x0, x5              // 11.
    ret                     // 12.

\(c\)
- 2, 3 有 RAW
- 3 有 Control hazard
- 4, 5 有 RAW
- 5,6 和 7 有 RAW
- 7 和 8 有 RAW
- 10 有 Control hazard

(d)
可用一個暫存器，紀錄 branch 的歷史。比方說可用 1-bit 或是 2-bit 的 branch preditor。搭配 speculative execution，如果預測夠準，Control hazard 的負面效應會下降很多。

(e)
類似這樣

    // f is in x0
    // g is in x1
    // n is in x2
    // M is in x3
.L0
    bgt x4, x3, .L1           // compare m with M
    sub x8, x2, x4            // n-m 
    subi x9, x8, #1           // n-(m+1)
    addi x12, x4, #1          // m+1
    ldr x6, [x0, x8, lsl 2]   // load f[n-m]
    ldr x10, [x0, x9, lsl 2]  // load f[n-(m+1)]
    ldr x7, [x1, x4, lsl 2]   // load g[m]
    ldr x11, [x1, x12, lsl 2] // load g[m+1]
    fmul x7, x7, x6           
    fmul x11, x11, x10
    fadd x5, x5, x7           // res += f[n-m]*g[m]
    fadd x5, x5, x11          // res += f[n-(m+1)]*g[m+1]
    addi, x4, x4, #2          // m += 2
    b .L0

只要搭配適當的指令排序和暫存器分配，就可以減少相依指令的 stall。

(f)

先來看 M = 1 的情況
第一次存取 f 的時候會 miss，再來存取 g 的時候也會 miss，然後把 f 給踢出去，所以 f 下次要存取時還是會 miss。因此 M=1 時，miss rate 是 100%

再來看 M = 4 的情況
假設 CPU 抓取資料時，是抓取 16 bytes 對齊的 data block。
再來假設 g 是從第 0 個 block 開始放，f 是從第 3 個 block 開始放。
- 第 1 次存取 f 時會 miss，然後放在第 3 個 block。
- 第 1 次存取 g 時會 miss，然後於在第 0 個 block。
- 第 5 次存取 f 時會 miss，然後放在第 2 個 block。
- 第 5 次存取 g 時會 miss，然後於在第 1 個 block。
- 第 9 次存取 f 時會 miss，然後放在第 1 個 block。
- 第 9 次存取 g 時會 miss，然後於在第 2 個 block。
- 第 13 次存取 f 時會 miss，然後放在第 0 個 block。
- 第 13 次存取 g 時會 miss，然後於在第 3 個 block。
miss rate 為 $\frac{1}{4}$

M = 8 的情況也一樣，$\frac{1}{4}$

(g) 呃...blocking (?口?)
(h) 可以。利用 pthread 等 multithreading library 即可。
(i) 也可以。做法同上
:::info
它到底想考什麼...？
只是做 convolution 的話，根本不需要寫入記憶體，不會有 cache coherence 的問題。根據這前提，i 跟 h 基本上是一樣的問題吧
:::

(j)
- 總共有 8 個指令，共 32 bytes。當中有 2 個 FLOP (fmul, fadd)，所以 arithmetic intensity 為 $\frac{1}{16}$
- attainable performance 為 1.0 GFLOPs/sec
- 加入快取記憶體後，記憶體頻寬將不會是限制，「理論上」可達到最高的性能，也就是 16 GFLOPs/sec。
- 加入 vector unit 後，性能提升了 4 倍，所以 roofline 的水平線會往上走到 64GFLOPs/sec。但這對於我們的 kernel 沒什麼影響，因為我們的 intensity 才 $\frac{1}{16}$，效能瓶頸是在記憶體。要能充分利用 vector unit，必須改寫程式碼。

2.
(a) NO，不是所有程式碼都適合平行化。如果很多個 thread 都會同時存取同一個全域變數，那平行化並不會帶來多大的效益

(b) YES，記憶體越多，理論上 page fault rate 就會越低

\(c\) YES，如果每個 process 所需的執行時間都一樣長的話

(d) YES，如果記憶體夠大，不會發生 thrashing 的話

(e) YES

(f) ?

(g) YES

(h) NO，現在的 C library 都會做 buffering，看似寫入，但其實只是先暫存在程序自己的定址空間，其它程序並不會看到。

(i) YES

(j) ?

3. ?
4. ?
5. ?