# 2022q1 Homework3 (fibdrv)
contributed by < `rickywu0421` >
> [作業說明](https://hackmd.io/@sysprog/linux2022-fibdrv#-作業要求)
> [GitHub](https://github.com/rickywu0421/fibdrv)
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 43 bits physical, 48 bits virtual
CPU(s): 6
On-line CPU(s) list: 0-5
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 23
Model: 113
Model name: AMD Ryzen 5 3500X 6-Core Processor
Stepping: 0
Frequency boost: enabled
CPU MHz: 2200.000
CPU max MHz: 4120.3120
CPU min MHz: 2200.0000
BogoMIPS: 7200.03
Virtualization: AMD-V
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 3 MiB
L3 cache: 32 MiB
NUMA node0 CPU(s): 0-5
```
## Fast Doubling
用 Fast doubling 的手段可以使計算 Fibonacci number 的時間複雜度降為 $O(logn)$。
詳細的推導過程請參考 [Fibdrv Fast Doubling](https://hackmd.io/@sysprog/linux2022-fibdrv)。
套用以下公式：
$$
\begin{split}
\left\{
\begin{array}{l}
F_{2n+1} &= F_{n+1}^2 + F_n^2 \\
F_{2n}
&= F_n\ (2 F_{n+1} - F_{n})
\end{array}
\right.
\end{split}
$$
對應的虛擬碼如下：
```
Fast_Fib(n)
a = 0; b = 1; // m = 0
for i = (number of binary digit in n) to 1
t1 = a*(2*b - a);
t2 = b^2 + a^2;
a = t1; b = t2; // m *= 2
if (current binary digit == 1)
t1 = a + b; // m++
a = b; b = t1;
return a;
```
以上的 "number of binary digit in n" 意思是 n 的 most significant set bit, 也就是 $log_2n$ 的值。
## Find most significant set bit by $log_2n$
上述演算法中, 為了得到 most significant set bit, 我們需要計算 $log_2n$, 而此函式的執行效率將顯著的影響程式執行效能, 尤其在 n 的值較小時。
以下實驗之 data model 為 LP64, 故 `unsigned long` 之資料位元數為 64。且實驗假設不會出現 `n == 0` 的情況。
### Brute Force
由 MSB 迭代至 LSB, 找到第一個 set bit 時停止。
```c
int log2(unsigned long n)
{
int i;
for (i = 63; i >= 0; i--)
if (n & (1 << i))
break;
return i;
}
```
### Count Leading Zeros
其實計算 $log_2n$ 等於先算出最高位有幾個 0 (leading zeros), 再用 63 扣掉就好。
故原本的 $log_2n$ 可以改寫為：
```c
#define log2(n) \
(8 * sizeof(unsigned long) - clz(n) - 1)
```
#### clz 版本 1: iteration
## 修正 Fibonacci 數的計算
### 定義大數結構體 - ubign
原始程式碼以 `long long` 型態的變數儲存 fibonacci number, 其計算到 f(93) 時會發生 integer overflow。
為了計算更高的 fibonacci number, 我定義了以下結構體：
```c
typedef uint32_t ubn_b_t;
typedef struct _ubn {
ubn_b_t arr[UBN_ARRAY_SIZE];
} ubn_t;
```
該結構體內部的成員為 `uint32_t` 的陣列, 陣列的大小 (`UBN_ARRAY_SIZE`) 可以根據要計算的 fibonacci number 大小進行調整。若要計算到 f(1000), 則 `UBN_ARRAY_SIZE` 必須至少為 24, 也就是用 96 bytes 的空間儲存 fibonacci number。
選擇 `uint32_t` 作為陣列元素型態而不使用 `uint64_t` 的原因為：在進行大數運算時 (add, sub, mul...), 可以使用 `uint64_t` integer 作為儲存運算結果的變數。
若使用 `uint64_t` 作為陣列元素型態, 則需要用 128 bit integer 儲存運算結果, 但其並非為編譯器預設提供的型態。(gcc 有提供 built-in type `__int128`)
該結構體儲存大數的位元組順序為 little endian。以下為一 96 bit integer 儲存到 `ubn_t` 的示意圖：
$\underbrace{0111...11}_{32bit}\underbrace{1101...01}_{32bit}\underbrace{0010...10}_{32bit} => \underbrace{0010...10}_{arr[0]}, \underbrace{1101...01}_{arr[1]}, \underbrace{0111...11}_{arr[2]}$
範例中的 `arr[3]` 到 `arr[UBN_ARRAY_SIZE - 1]` 則會被 zero padding。
### 基本運算操作
以下操作的函式中, 傳入的 `ubn_t` 均為指標型態, 避免 copy 變數造成的空間及時間浪費。
#### ubn_from_extend
將 `ubn_b_extend_t` 變數儲存到 `ubn_t` 中。
```c
typedef uint64_t ubn_b_extend_t;
#define UBN_BLOCK_SIZE sizeof(ubn_b_t)
static inline void ubn_from_extend(ubn_t *ubn, ubn_b_extend_t tmp)
{
ubn_init(ubn);
ubn->arr[0] = tmp;
ubn->arr[1] = tmp >> (8 * UBN_BLOCK_SIZE);
}
```
#### ubn_add
如何判斷是否 carry：相加後的數 < 被加數
```c
static void ubn_add(ubn_t *a, ubn_t *b, ubn_t *c)
{
int carry = 0;
for (int i = 0; i < UBN_ARRAY_SIZE; i++) {
ubn_b_t tmp_a = a->arr[i];
c->arr[i] = a->arr[i] + b->arr[i] + carry;
carry = (c->arr[i] < tmp_a);
}
}
```
#### ubn_sub
如何判斷是否 borrow：相減後的數 > 被減數
```c
static void ubn_sub(ubn_t *a, ubn_t *b, ubn_t *c)
{
int borrow = 0;
for (int i = 0; i < UBN_ARRAY_SIZE; i++) {
ubn_b_t tmp_a = a->arr[i];
c->arr[i] = a->arr[i] - b->arr[i] - borrow;
borrow = (c->arr[i] > tmp_a);
}
}
```
#### ubn_lshift_b
用於乘法操作, 將 `ubn_t` left shift 若干個 block, 並在低位元組的地方補 0。
```c
void ubn_lshift_b(ubn_t *ubn, int block)
{
for (int i = UBN_ARRAY_SIZE - 1; i >= block; i--)
ubn->arr[i] = ubn->arr[i - block];
/* Zero padding */
memset(ubn->arr, 0, UBN_BLOCK_SIZE * block);
}
```
#### ubn_mul
計算 `i` 個偏移量的 `a` 乘上 `j` 個偏移量的 `b`, 將結果放到 `ubn_t`, 並 left shift (`i + j`) 個偏移量, 再加到 `c`。
```c
void ubn_mul(ubn_t *a, ubn_t *b, ubn_t *c)
{
ubn_init(c);
for (int i = 0; i < UBN_ARRAY_SIZE; i++) {
for (int j = 0; j < UBN_ARRAY_SIZE; j++) {
if ((i + j) < UBN_ARRAY_SIZE) {
ubn_t ubn;
ubn_b_extend_t tmp = (ubn_b_extend_t) a->arr[i] * b->arr[j];
ubn_from_extend(&ubn, tmp);
ubn_lshift_b(&ubn, i + j);
ubn_add(&ubn, c, c);
}
}
}
}
```
#### ubn_to_str
參考 [blueskyson](https://hackmd.io/OfRzBJjGRjGiHM_j-LGoRg?both) 的作法：
從 `ubn_t` 的最高為 1 的位元起,
1. 往 LSB 的方向逐個位元檢查是否為 1, 若是, 則 buf 中的數 + 1。
2. 將 buf 中的每個值加上自己, 並處理進位問題, 即可達成概念上的乘 2。
3. 重複步驟 1, 直到所有位元都已被檢查過
```c
void ubn_to_str(ubn_t *ubn, char *buf)
{
buf_init(buf);
/* Skip zero block */
int index;
for (index = UBN_ARRAY_SIZE - 1; !ubn->arr[index]; index--)
;
for (; index >= 0; index--) {
for (ubn_b_t mask = 1U << ((BITS_PER_BYTE * UBN_BLOCK_SIZE) - 1);
mask; mask >>= 1U) {
int carry = ((ubn->arr[index] & mask) != 0);
for (int i = UBN_STR_SIZE - 2; i >= 0; i--) {
buf[i] += buf[i] + carry - '0';
carry = (buf[i] > '9');
if (carry)
buf[i] -= 10;
}
}
}
buf[UBN_STR_SIZE - 1] = '\0';
/* Eliminate leading zeros in buf */
int offset;
for (offset = 0;
(offset < UBN_STR_SIZE - 2) && (buf[offset] == '0');
offset++)
;
int i;
for (i = 0; i < (UBN_STR_SIZE - 1 - offset); i++)
buf[i] = buf[i + offset];
buf[i] = '\0';
}
```
#### fib_sequence
透過 [fast dobuling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 的方式計算 fibonacci number。
我使用 `__builtin_clzll(n)` 先找到最高被 set 的位元, 接著 skip 這個位元, 從下一個位元開始計算, 如此便能將起始條件從 f(0) 改為 f(1), 省去一次 loop 的運算。
```c
#define flsll(n) (64 - __builtin_clzll(n))
static ubn_t fib_sequence(long long n)
{
ubn_t a, b, c, d;
if (!n) {
ubn_from_extend(&a, (ubn_b_extend_t) 0);
return a;
}
if (n == 1) {
ubn_from_extend(&a, (ubn_b_extend_t) 1);
return a;
}
/* Starting from f(1), skip the most significant 1-bit */
int i = (flsll(n) - 1) - 1;
ubn_from_extend(&a, (ubn_b_extend_t) 1); /* f(1) = 1 */
ubn_from_extend(&b, (ubn_b_extend_t) 1); /* f(2) = 1 */
for (int mask = 1 << i; mask; mask >>= 1) {
ubn_t tmp1, tmp2, tmp3;
ubn_from_extend(&tmp1, (ubn_b_extend_t) 2); /* tmp1 = 2 */
ubn_mul(&tmp1, &b, &tmp2); /* tmp2 = 2 * b */
ubn_sub(&tmp2, &a, &tmp3); /* tmp3 = 2 * b - a */
ubn_mul(&a, &tmp3, &c); /* c = a * (2 * b - a) */
ubn_mul(&a, &a, &tmp1); /* tmp1 = a * a */
ubn_mul(&b, &b, &tmp2); /* tmp2 = b * b */
ubn_add(&tmp1, &tmp2, &d); /* d = a * a + b * b */
if (n & mask) {
a = d;
ubn_add(&c, &d, &b); /* f(2k+2) = f(2k) + f(2k+1) = c + d */
} else {
a = c;
b = d;
}
}
return a;
}
```
### copy_to_user
原始程式碼使用 read 的回傳值當做 fibonacci number, 其回傳的形態為 `ssize_t`, 翻閱 [include/linux/types.h](https://elixir.bootlin.com/linux/latest/source/include/linux/types.h)：
```c
typedef __kernel_ssize_t ssize_t;
```
再翻閱 [/include/uapi/asm-generic/posix_types.h](https://elixir.bootlin.com/linux/latest/source/include/uapi/asm-generic/posix_types.h#L69)
```c
typedef long __kernel_long_t;
#if __BITS_PER_LONG != 64
typedef int __kernel_ssize_t;
#else
typedef __kernel_long_t __kernel_ssize_t;
#endif
```
得知, 在 64 bit 的機器下, `ssize_t` 等同於 64 bit signed integer, 其能容納的 fibonacci number 最高為 92。
於是改用 `copy_to_user()` 將 `ubn_t` 轉換成字串, 再從 kernel space 複製到 user space。
```c
/**
* @buf: user space buffer
* @str: fibonacci number
* @len: length of @str
*/
copy_to_user((void *) buf, str, len);
```
## 效能分析
### 在 kernel space 計算 fibdrv 執行時間
透過 [include/linux/ktime.h](https://elixir.bootlin.com/linux/latest/source/include/linux/ktime.h) 及 [include/linux/timekeeping.h](https://elixir.bootlin.com/linux/latest/source/include/linux/timekeeping.h) 中定義的 `ktime_get()` , `ktime_sub()` 及`ktime_to_ns()` 達成計時的效果。
#### 記錄計算 fibonacci number 之花費時間
```c
#include <linux/ktime.h>
...
kt_fib = ktime_get();
ubn_t fib = fib_sequence(*offset);
ubn_to_str(&fib, str);
kt_fib = ktime_sub(ktime_get(), kt_fib);
kt_fib_long = ktime_to_ns(kt_fib);
```
#### 記錄 copy_to_user 之花費時間
```c
kt_copy = ktime_get();
ret = copy_to_user((void *) buf, str, len);
kt_copy = ktime_sub(ktime_get(), kt_copy);
kt_copy_long = ktime_to_ns(kt_copy);
```
### 在 user space 計算 fibdrv 執行時間
透過 `clock_gettime()` 得到起始及結束時間 (以`struct timespec` 表示)
```c
#include <time.h>
...
clock_gettime(CLOCK_MONOTONIC, &start);
ret = read(fd, buf, UBN_STR_SIZE);
clock_gettime(CLOCK_MONOTONIC, &end);
```
`struct timespec` 之定義如下：
```c
struct timespec {
time_t tv_sec; /* seconds */
long tv_nsec; /* nanoseconds */
};
```
透過以下操作可得到起始到結束的經過時間：
```c
struct timespec diff;
diff.tv_sec = end.tv_sec - start.tv_sec;
diff.tv_nsec = end.tv_nsec - start.tv_nsec;
long long elapsed_time = diff.tv_nsec + diff.tv_sec * 1000000;
```
### 以統計手法去除極端值
假設數據分佈接近常態分佈的情況下，一個標準差到三個標準差之內的資料量約佔 68%, 95%, 99.7%：
> 圖片來源：[wikipedia](https://en.wikipedia.org/wiki/Standard_deviation)
#### python script 實作
使用 python script: [driver.py](https://github.com/rickywu0421/fibdrv/blob/master/scripts/driver.py) 執行若干次使用者程式蒐集數據, 並去除距離平均兩個標準差以上的數據。
> 參考自 [4ce43c4](https://github.com/colinyoyo26/fibdrv/commit/4ce43c4e7ee0b80c4ce9e6dcd995bbfdf239206c)
`data` 為跑若干次程式中計算的某個 fibonacci number 的時間, 此函式回傳 `data` 中距離平均小於 2 個標準差的數據：
```python
def outlier_filter(data, threshold=2):
data = np.array(data)
z = np.abs((data - data.mean()) / data.std())
return data[z < threshold]
```
處理計算每項計算的時間 (kernel, user, `copy_to_user`), 將資料去除 outlier 後回傳過濾過的資料：
```python
def data_processing(data, n):
catgories = data[0].shape[0]
samples = data[0].shape[1]
final = np.zeros((catgories, samples))
for c in range(catgories):
for s in range(samples):
final[c][s] = \
outlier_filter([data[i][c][s] for i in range(n)]).mean()
return final
```
### 計算 fibnocci number 作圖 (version 1)
以下是計算 0 到 1000 的 fibonacci number 之結果：
- 數據取樣 50 次, 並去除 outlier
我們根據上圖可以觀察出, n ~= 50 時有微幅的波動。
### 設定 process 的 cpu affinity
透過 taskset 指令, 搭配 coremask (0x1), 將 process 固定在 cpu0 上執行：
```bash
taskset 0x1 ./client
```
### 限定 CPU 給此程式使用
taskset 可指定 process 給特定的 CPU 使用, 但不代表其他 process 不會佔用指定的 CPU。設定的方式有兩種，一個是在開機時使用 boot loader 所提供的自訂開機參數功能，手動加入 `isolcpus=cpu_id` 參數，或是直接加在 GRUB 的設定檔中，這樣 Linux 的排程器在預設的狀況下就不會將任何一般行程放在這個被保留的 CPU 核心中執行，只有那些被 taskset 特別指定的行程可使用這些 CPU 核心。
修改 GRUB 設定檔 /etc/default/grub：
```bash
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=0"
```
並重開機以生效。
### 排除干擾效能分析的因素
- 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR)
```bash
sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
- 設定 cpu0 的 scaling_governor 為 performance
```bash
sudo sh -c "echo performance > /sys/devices/system/cpu/cpu0/cpufreq/scaling_governor"
```
### 計算 fibnocci number 作圖 (version 2)
一樣是計算 0 到 1000 的 fibonacci number 之結果：
- 數據取樣 50 次, 並去除 outlier
相較 version 1, 此次執行的結果擺脫了 n ~= 50 時的波動。
Sign in with Wallet
Connect another wallet