# 2023q1 Homework3(quiz3)
contributed by <`ctfish7063`>
###  測驗`1`
###  測驗`2`
###  測驗`3`
參見 [bucket_uniform.c](https://gist.github.com/jserv/15c6ef4383d5d010326cdc4382ffdd1d)
#### Ans
`AAAA`: 56
`BBBB`: 48
`CCCC`: 40
`DDDD`: 32
`EEEE`: 24
`FFFF`: 16
`GGGG`: 8
`HHHH`: 0
`IIII`: mask111
`JJJJ`: mask011
#### 延伸問題
1. 解釋 Linear feedback shift register (LFSR) 的運作原理，搭配在 Linux 核心原始程式碼中，用 `git log` 和 `grep` 找出 LFSR 的應用案例

LFSR 是一種將其狀態輸入線性方程式後進行回饋(下一狀態的輸入)的 shift register ，作為線性方程式輸入的狀態們稱為 `taps`，而線性方程式中又以 XOR 最為常見。線性方程式在 [$GF(2)$](https://en.wikipedia.org/wiki/Finite_field) 下可用二進位法表示，以下為 8 bits 的情況：

| Polynomial | Binary |
| ------------- | ---------- |
| $x^6+x^4+x+1$ | {01010011} |

在使用 XOR 的情況下，第 6 、4、1 個 bit 為 taps (常數 $1 = x^0$ 的部份代表 lfsr 的輸入)， 可以將函式寫成：

    //single state change of lfsr
    uint8_t lfsr(uint8_t prev) {
        //the input is xor of the 6, 4, 1 bits
        uint8_t new = (x >> 2) ^ (x >> 4) ^ (x >> 7) & 1u;
        return (prev >> 1) | (new << 7);
    }

在 Linux 的 [tools/perf/bench/numa.c](https://www.cs.rice.edu/~la5/doc/perf-doc/d5/d16/numa_8c_source.html#l00733) 中可以看到 lfsr 的蹤影。從 `numa.c` 的目錄位置便可以猜出這是用來測試效能的程式，在檔案的開頭也註解道：
> numa: Simulate NUMA-sensitive workload and measure their NUMA performance

可見此程式的用途為模擬並測量NUMA架構下的表現。函式如下，可以看出選擇了第 31, 27, 26, 1 bit 作為 taps 來進行線性運算：

    #define BIT(x) (1ul << x)

    static inline uint32_t lfsr_32(uint32_t lfsr)
    {
        const uint32_t taps = BIT(1) | BIT(5) | BIT(6) | BIT(31);
        return (lfsr>>1) ^ ((0x0u - (lfsr & 0x1u)) & taps);
    }

至於用途應和題目示範相同，用來作為 PRNG 使用，可以看到底下的函式 [do_work](https://www.cs.rice.edu/~la5/doc/perf-doc/d5/d16/numa_8c_source.html#l00762)
在設定了 `g->p.data_rand_walk` 的情況下，此函數會隨機的尋找起始點來進行資料存取和清空。

2. 解釋上述程式碼運作的原理
整體程式運作是透過 `lfsr` 產生隨機數 `x` ，再透過 `bucket_number` 將 `x` 轉為編號並在該編號的 bucket 中加 1 ，理想上隨機編號應能均勻在各 buckets 中添加數字，因此 buckets 中的數字應該相差無幾 ，以下為參考輸出：

    lfsr$ ./bucket_uniform
    number of buckets: 120
    number of bits: 7
    0:8656 , 1:8358 , 2:8371 , 3:8399 , 4:8420 , 5:8377 , 6:8387 , 7:8330 , 8:8396 , 9:8500 , 
    10:8469 , 11:8503 , 12:8290 , 13:8469 , 14:8447 , 15:8535 , 16:8451 , 17:8253 , 18:8497 , 19:8687 , 
    20:8440 , 21:8334 , 22:8384 , 23:8517 , 24:8479 , 25:8414 , 26:8475 , 27:8537 , 28:8206 , 29:8462 , 
    30:8374 , 31:8428 , 32:8412 , 33:8502 , 34:8486 , 35:8548 , 36:8700 , 37:8541 , 38:8510 , 39:8454 , 
    40:8409 , 41:8509 , 42:8353 , 43:8447 , 44:8577 , 45:8377 , 46:8399 , 47:8514 , 48:8413 , 49:8581 , 
    50:8299 , 51:8599 , 52:8601 , 53:8360 , 54:8455 , 55:8405 , 56:8408 , 57:8322 , 58:8358 , 59:8435 , 
    60:8441 , 61:8554 , 62:8387 , 63:8605 , 64:8394 , 65:8330 , 66:8403 , 67:8469 , 68:8313 , 69:8414 , 
    70:8448 , 71:8471 , 72:8401 , 73:8754 , 74:8545 , 75:8476 , 76:8416 , 77:8553 , 78:8416 , 79:8519 , 
    80:8510 , 81:8254 , 82:8473 , 83:8421 , 84:8447 , 85:8564 , 86:8451 , 87:8310 , 88:8428 , 89:8570 , 
    90:8383 , 91:8346 , 92:8481 , 93:8438 , 94:8497 , 95:8565 , 96:8484 , 97:8382 , 98:8599 , 99:8459 , 
    100:8594 , 101:8335 , 102:8364 , 103:8352 , 104:8489 , 105:8279 , 106:8471 , 107:8348 , 108:8521 , 109:8338 , 
    110:8484 , 111:8507 , 112:8349 , 113:8482 , 114:8448 , 115:8531 , 116:8360 , 117:8411 , 118:8644 , 119:8373 , 

* `lfsr`
透過上面講述的方法產生隨機數 `x` 。
* `log2_64`
函式利用查表的方式計算最小的大於等於輸入的 2 的冪。首先判斷輸入 `x` 是否在 64~32 bit 中有 set bit，若有則除以 $2^{32}$ ；再檢查前 16 bit, 若有便除以 $2^{16}$；最後檢查前 8 bit, 若有會在除以 $2^8$；以上操作的目的在於將 `x` 限縮到 $2^8 = 256$ 以便進行查表，再將查表結果加上右移過的 bit 數目便能得到答案。使用這個函式便可以得到儲存 buckets 數量( N_BUCKETS )所需要的 bit 數量( N_BITS )。
* `bucket_number`
函式透過 bit mask 取出 `x` 的後 N_BITS 個 bits 作為隨機的 bucket 編號。由於 N_BITS 個 bit 所能存下的數字可能大於 N_BUCKETS， 函式提供了兩種 bit mask 作為，其中 `mask011` 以少取用第一個 bit 作為編號大於 N_BUCKETS 的備用方案， `mask111` 則全取。

4. 在 Linux 核心原始程式碼中找到 $log_2(x)$ 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 $log_2(x)$ 的應用案例並解說。
5. `lab0-c` 提供類似的實作 log2_lshift16.h，解釋其原理並嘗試改進其效能
###  測驗`4`
`KKKK`: r | shift | x >> 1