# 2023q1 Homework3 (fibdrv)
contributed by < `koty6069` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ uname -r
5.19.0-35-generic
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 10
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
```
## 前期準備
觀察產生的 `fibdrv.ko` 模組
```shell
$ modinfo fibdrv.ko
```
得到以下輸出
```shell
filename: /home/ray/linux2023/fibdrv/fibdrv.ko
version: 0.1
description: Fibonacci engine driver
author: National Cheng Kung University, Taiwan
license: Dual MIT/GPL
srcversion: 9A01E3671A116ADA9F2BB0A
depends:
retpoline: Y
name: fibdrv
vermagic: 5.19.0-35-generic SMP preempt mod_unload modversions
```
觀察 `fibdrv.ko` 核心模組在 Linux 核心掛載後的行為
```shell
$ sudo insmod fibdrv.ko
$ sudo ls -l /dev/fibonacci
crw------- 1 root root 509, 0 3月 13 12:50 /dev/fibonacci
$ sudo cat /sys/class/fibonacci/fibonacci/dev
509:0
$ sudo cat /sys/module/fibdrv/version
0.1
$ sudo lsmod | grep fibdrv
fibdrv 16384 0
$ sudo cat /sys/module/fibdrv/refcnt
0
```
掛載 `fibdrv.ko` 核心模組後，執行 `client` 觀察其輸出
```shell
$ sudo ./client
Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Reading from /dev/fibonacci at offset 2, returned the sequence 1.
...
Reading from /dev/fibonacci at offset 91, returned the sequence 4660046610375530309.
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 7540113804746346429.
```
可看到如同作業說明所描述，在 `fibdrv.c` 中將最大長度限制在 92 ，因此 $F(92)$ 後的輸出皆相同
```c
#define MAX_LENGTH 92
```
## Linux 效能分析設定
> 參考 [作業說明（三）](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c) 和 [`KYG-yaya573142`](https://hackmd.io/@KYWeng/rkGdultSU) 進行設定
### 限定 cpu 給特定程式使用
修改 `/etc/default/grub` ，在 `GRUB_CMDLINE_LINUX_DEFAULT` 加入 `isolcpus=3` 使開機時保留編號 3 的 cpu 核心。
```
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=3"
```
修改完輸入 `sudo update-grub` 以更新設定，重開機後確認設定是否生效。
使用 `taskset` 可發現 PID 1 的處理器親和性不包含編號 3 的核心。
```shell
$ cat /sys/devices/system/cpu/isolated
7
$ taskset -cp 1
pid 1's current affinity list: 0-2,4-7
```
後續可透過 `taskset` 指定編號 3 的核心給特定程式使用。
```shell
$ sudo taskset -c 3 ./client
```
### 排除干擾效能分析的因素
* 抑制 ASLR
```shell
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
* 使用 `performance.sh` 設定 scaliing_gorvernor 為 performance
```shell
$ sudo sh performance.sh
```
* 關閉 turbo mode
```shell
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
* 關閉 SMT
```shell
$ sudo sh -c "echo off > /sys/devices/system/cpu/smt/control"
```
:::warning
執行完上述指令後，編號 4~7 的 cpu 會變成 offline 狀態。
```shell
$ lscpu
...
CPU(s): 8
On-line CPU(s) list: 0-3
Off-line CPU(s) list: 4-7
...
```
:::
### 時間量測
根據 [作業說明](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-c) 使用 `k_time` 相關 API 改寫 `fib_write` 和 `fib_read` 使其能在計算數列時紀錄所花費的時間，幫助後續實驗分析。
接著，在 `client.c` 中使用 `read()` 獲得費氏數列數值，以及使用 `write()` 取得該次計算所花費的時間。
```c
for (int i = 0; i <= offset; i++) {
long long sz;
lseek(fd, i, SEEK_SET);
sz = read(fd, buf, 1);
printf("Reading from " FIB_DEV
" at offset %d, returned the sequence "
"%lld.\n",
i, sz);
sz = write(fd, write_buf, strlen(write_buf));
printf("Time in ns is %lld\n", sz);
fprintf(fp, "%lld\n", sz);
}
```
對應的輸出節錄如下。
```
Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Time in ns is 38
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Time in ns is 24
Reading from /dev/fibonacci at offset 2, returned the sequence 1.
Time in ns is 54
...
```
## 改進費氏數列
### Fast Doubling
參考作業說明[（一）](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-a#L04-fibdrv)[（四）](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-d)和 [Calculating Fibonacci Numbers by Fast Doubling ](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 實作 Fast Doubling ，並結合 bitwise 操作和考慮硬體加速。
使用 clz / ctz 得到 leading 0s 以減少不必要的迭代次數。
```c
int lz = __builtin_clzll(k);
```
參考虛擬碼進行迴圈操作，從最高位的 1 開始往最低位進行判斷：
* 當目前位元為 0 ：計算 $F(2k), F(2k+1)$
* 當目前位元為 1 ：計算 $F(2k), F(2k+1)$ 以外，再計算 $F(2K+2)$
其中，使用 `k & 1UL << i - 1` 來判斷當前位元是否為 1，將 1 向左 shift 到當前位元再使用 `and` 得到當前位元。
```c
for (int i = 64 - lz; i >= 1; i--) {
long long t1 = a * (2 * b - a);
long long t2 = b * b + a * a;
a = t1;
b = t2;
if (k & 1UL << i - 1) {
t1 = a + b;
a = b;
b = t1;
}
}
```
因為每次都要將 `1UL` 向左 shift `i - 1` 位，因此可以將迴圈的起始條件和結束條件都減 1，使得下方 shift 可以改寫成 `1UL << i` 以免除每次都要進行的 `i - 1` 計算。
```c
for (int i = 63 - lz; i >= 0; i--)
```
```c
if (k & 1UL << i)
```
後續在測量時間時，發現使用此方法在 `k = 0` 所花費的時間特別長，導致繪出的比較圖無法看出兩者差異。
```shell
Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Time in ns is 3620888938
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Time in ns is 41
```
因此在最前方加上提前中止的條件以解決此問題。
```c
if (k <= 1)
return k;
```
```shell
Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Time in ns is 38
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Time in ns is 24
```
### 效能比較（尚未排除效能分析干擾因素）
在排除效能分析干擾因素前，先試著比較原始版本和 Fast Doubling 版本的效能差異。
可看出隨著輸入數值增長，原始版本花費的時間也有明顯上升，而 Fast Doubling 版本耗時則幾乎維持在相同程度。
### 效能比較（排除效能分析干擾因素）
在排除干擾後，可看出綠色線的浮動有稍微減緩。
### 計算 $F_{93}$ 之後的 Fibonacci 數
Sign in with Wallet
Connect another wallet