2022q1 Homework3 (fibdrv)

--- tags: linux2022 --- # 2022q1 Homework3 (fibdrv) contributed by < `hsuedw` > * [作業繳交](https://hackmd.io/@sysprog/linux2022-homework3) * [作業需求](https://hackmd.io/@sysprog/linux2022-fibdrv) * Due Date: Mar 21, 2022 --- # 預備知識 * [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module) # 工作環境 * 作業系統 * Ubuntu 20.04.4 LTS (Focal Fossa) * Linux kernel: 5.13.0-30-generic :::spoiler details ``` $ uname -a Linux edward-ubuntu 5.13.0-30-generic #33~20.04.1-Ubuntu SMP Mon Feb 7 14:25:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux ``` ::: * 硬體資源 * CPU: Intel(R) Core(TM) i5-7400 CPU @ 3.00GHz, 4 cores :::spoiler CPU details ``` $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 39 bits physical, 48 bits virtual CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 158 Model name: Intel(R) Core(TM) i5-7400 CPU @ 3.00GHz Stepping: 9 CPU MHz: 3000.000 CPU max MHz: 3500.0000 CPU min MHz: 800.0000 BogoMIPS: 6000.00 Virtualization: VT-x L1d cache: 128 KiB L1i cache: 128 KiB L2 cache: 1 MiB L3 cache: 6 MiB NUMA node0 CPU(s): 0-3 ``` ::: * RAM: 8 GB * 編譯器 ``` $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 ``` --- # Fix VLA not allowed in kernel issue 編譯 `fibdrv` 時，發現下列警告訊息。雖然 `fibdrv` 仍可安裝並計算 Fibonacci number。不過，既然 Linux kernel 不允許使用 variable length array (VLA)，那就把先把這個警告訊息處理掉。目前採用的解法是用動態規劃 (Dynamic Programming) 裡的狀態壓縮技巧處理。原本的 `fib_sequence()` 裡有個 `f` 陣列，用來計算 `f[k]`。這樣做的時間與空間複雜度都是 O(k)。不過，仔細想想，以 buttom-up DP 實作的演算法只需要 `f[k - 1]` 與 `f[k - 2]` 就可以計算出 `f[k]`。所以不需要一個長度為 `k` 的陣列。所以改用下列實作，既可避開禁止使用 VLA 的警告訊息，又可降低空間複雜度到 O(1)。 :::spoiler Fix VLA not allowed in kernel issue (commit: dd77cd1) ```c static long long fib_sequence(long long k) { if (k < 2) return k; long long fk = -1, fk_2 = 0, fk_1 = 1; for (int i = 2; i <= k; i++) { fk = fk_2 + fk_1; fk_2 = fk_1; fk_1 = fk; } return fk; } ``` ::: # 使用 sysfs 介面 `fibdrv` 遇到的第一個要解決的問題就是因為 C 語言內建的 `long long` 資料型態所能表示的最大值為 2^63^ - 1 = ‭9,223,372,036,854,775,807‬。導致在計算 F~93~ 出現溢位 (overflow)。 > F~93~ = 15080227609492692858 就算是改用 `unsigned long long` 最大值也只能是 2^64^ - 1 = ‭18,446,744,073,709,551,615‬。勉強可以用來計算 F~93~。但是作業的要求是至少要計算到 F~100~，甚至是更後面的 Fibonacci number。所以必須要使用自訂資料型態實作 big number。不過，若是以目前 `fibdrv` 所採用的 VFS，實作 `open`、`close`、`read`、`write` 等 system call 的方式將 `fibdrv` 計算出來的 Fibonacci number (用自訂資料型態實作 big number 表示) 困擾。在用 VFS 的實作前提下，可能的解決方案有兩種。 1. 使用 `ioctl` 這個 system call。這樣可以一次把自訂 big number 型態的 object 讀到 user space 中。不過，這樣做的話， `fibdrv` 必須向 `client` 揭露 big number 資料型態定義與其他相關實作細節。 2. 按照目前 `client` 所提示的實作方式，用 `lseek` 與 `read` 兩個 system call 搭配操作。先用 `lseek` 設定準備要讀取的資料的位置，再用 `read` 把指定的資料讀出來。一次讀一個 `long long` 的資料，直到把自訂 big number 資料結構中記錄 Fibonacci number 的所有 `long long` 讀完為止。這兩種做法對 `client` 而言，都不是很友善。因為 `client` 必須重組資料才能得到完整的 Fibonacci number。而且必須揭露許多 `fibdrv` 的實作細節給 `client`。會加深 `fibdrv` 與 `client` 間 coupling 的程度。 > [Coupling (computer programming)](https://en.wikipedia.org/wiki/Coupling_(computer_programming)) 比較好的做法應該是 `client` 能夠直接讀到計算完成的 Fibonacci number。並且不要揭露任何關於 `fibdrv` 內部的實作細節給 `client`。所以我打算使用 sysfs 介面。目前打算在 sysfs 下產生三個檔案。藉以向 `client` 揭露 `fibdrv` 的計算結果。 1. `/sys/kernel/fibonacci/input`: `client` 在此檔案中寫入想要計算的 Fibonacci number 的項數。例如，寫入 10 表示想要計算 F~10~。 3. `/sys/kernel/fibonacci/output`: `fibdrv` 計算的 Fibonacci number。例如，F~10~ = 55。 4. `/sys/kernel/fibonacci/time`: `fibdrv` 計算 Fibonacci number 所花費的時間。 :::spoiler 測試目前實作的 sysfs interface (commit: 6d04220) ``` $ make clean all make -C /lib/modules/5.13.0-30-generic/build M=/home/edward/workspace/linux_2022/homework3/fibdrv clean make[1]: Entering directory '/usr/src/linux-headers-5.13.0-30-generic' CLEAN /home/edward/workspace/linux_2022/homework3/fibdrv/Module.symvers make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-30-generic' rm -f client out cc -o client client.c make -C /lib/modules/5.13.0-30-generic/build M=/home/edward/workspace/linux_2022/homework3/fibdrv modules make[1]: Entering directory '/usr/src/linux-headers-5.13.0-30-generic' CC [M] /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.o MODPOST /home/edward/workspace/linux_2022/homework3/fibdrv/Module.symvers CC [M] /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.mod.o LD [M] /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.ko BTF [M] /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.ko Skipping BTF generation for /home/edward/workspace/linux_2022/homework3/fibdrv/fibdrv.ko due to unavailability of vmlinux make[1]: Leaving directory '/usr/src/linux-headers-5.13.0-30-generic' $ $ sudo insmod fibdrv.ko $ $ lsmod | grep fibdrv fibdrv 16384 0 $ $ sudo su [sudo] password for edward: # # whoami root # # cat /sys/kernel/fibonacci/input 0 # # cat /sys/kernel/fibonacci/output 0 # # echo 10 > /sys/kernel/fibonacci/input # # cat /sys/kernel/fibonacci/input 10 # # cat /sys/kernel/fibonacci/output 55 # # echo 92 > /sys/kernel/fibonacci/input # cat /sys/kernel/fibonacci/input 92 # # cat /sys/kernel/fibonacci/output 7540113804746346429 ``` ::: * 參考資料: [Brief sysfs Tutorial](https://www.cs.swarthmore.edu/~newhall/sysfstutorial.pdf) [Documentation/filesystems/sysfs.rst](https://github.com/torvalds/linux/blob/master/Documentation/filesystems/sysfs.rst) [Sample kobject implementation](https://elixir.bootlin.com/linux/latest/source/samples/kobject/kobject-example.c) (注意: 切換到對應的 Linux 核心版本) --- # 實作 big number * 本階段目標 - [x] 實作 big number 資料結構。 - [x] 實作 big number 加法運算。使 `fibdrv` 可用原本的迭代演算計算 Fibonacci number (F~92~ 以上)。 - [x] 實作 big number 轉字串。在字串中以十六進位表示 Fibonacci number。 - [x] 為 Fast Doubling 計算 Fibonacci number 做準備。 - [x] 實作 big number bitwise left shift - [x] 實作 big number 減法運算。 - [x] 實作 big number 乘法運算。 * big number 資料結構 ```c /* * bignum data structure * number[0] contains least significant bits * number[size - 1] contains most significant bits * sign = 1 for negative number */ typedef struct _bignum { NUM_TYPE *num; size_t sz; int sign; } bignum; ``` * 目前只有用到 `num` 與 `sz` 兩個欄位。 * `num` 是指向一個 `kmalloc()` 動態宣告的記憶體空間。其大小為 `BIGNUM_SZ * sizeof(NUM_TYPE)`。目前 `BIGNUM_SZ` 設定為 `500`。`NUM_TYPE` 定義為 `uint32_t`。以目前這樣的實作可以算到 F~23000~。 * big number 加法運算 ```c= // s = a + b void bignum_add(bignum *s, const bignum *a, const bignum *b) { memset(s->num, 0, s->sz * sizeof(NUM_TYPE)); int carry = 0; for (int i = 0; i < s->sz; ++i) { TMP_TYPE tmp = (TMP_TYPE) a->num[i] + b->num[i] + carry; carry = tmp > MAX_VAL; s->num[i] = tmp & MAX_VAL; } return; } ``` * `TMP_TYPE` 被定義為 `uint64_t`。`NUM_TYPE` 被定義為 `uint32_t`。而 `a->num[i]` 的型態為 `NUM_TYPE` 也就是 `uint32_t`。 * 所以，在第 8 行執行加法運算時，被加數 (`a->num[i]`) 與加數 (`b->num[i]`) 均被轉型為 `uint64_t`。然後在第 9 行判斷變數 `tmp` 是否大於 `uint32_t` 所能表示的最大值決定是否有發生進位。 * big number 轉字串。在字串中以十六進位表示 Fibonacci number ```c ssize_t bignum_to_string(bignum *bn, char *buf) { ssize_t s_len = BIGNUM_SZ * sizeof(NUM_TYPE) * 2 + 1; ssize_t j = 0, blk_sz = sizeof(NUM_TYPE) * 2 + 1; char *s = (char *) kmalloc(s_len, GFP_KERNEL); for (int i = bn->sz - 1; i >= 0; --i) j += snprintf(s + j, blk_sz, "%08X", bn->num[i]); j = snprintf(buf, s_len + 1, "%s\n", s); kfree(s); return j; } ``` * 目前這個將 big number 轉為字串的實作是以十六進位顯示。因為 big number 是以二進位的想法在實作運算。這樣可以省去轉換為十進位的運算成本。 * 這個 big number 轉為字串的實作沒有去掉 leading zeros。應該稍後會回來實作這部分。 * big number bitwise left shift ```c // bn = bn << shift void bignum_lshift(bignum *bn, size_t shift) { shift %= 32; // only handle shift within 32 bits atm if (!shift) return; for (int i = bn->sz - 1; i > 0; i--) bn->num[i] = bn->num[i] << shift | bn->num[i - 1] >> (32 - shift); bn->num[0] <<= shift; } ``` * big number 的 bitwise left shift 運算是為了 fast doubling 演算法做準備。因為在計算 F(2k) 時，需要對 F(k+1) 乘 2。 * 對數字左移一個 bit，相當於對此數字執行乘 2 運算。 * big number 減法運算 ```c // d = a - b void bignum_sub(bignum *d, const bignum *a, const bignum *b) { memset(d->num, 0, d->sz * sizeof(NUM_TYPE)); bignum *tmp = bignum_create(BIGNUM_SZ); bignum_cpy(tmp, b); // Calculate the two's complement for b. tmp->num[0] = ~tmp->num[0]; int carry = ((TMP_TYPE) tmp->num[0] + 1) > MAX_VAL; tmp->num[0] += 1; for (int i = 1; i < tmp->sz; ++i) { tmp->num[i] = ~tmp->num[i]; carry = ((TMP_TYPE) tmp->num[i] + carry) > MAX_VAL; tmp->num[i] += carry; } // d = a - b = a + b(two's complement) bignum_add(d, a, tmp); } ``` * big number 的減法運算基本上就是先對減數取其二補數 (two's complement)。然後再利用 big number 加法運算將被減數與被減數二補數相加。 * big number 乘法運算 ```c static void bn_mult_add(bignum *p, int offset, TMP_TYPE x) { TMP_TYPE carry = 0; for (int i = offset; i < p->sz; ++i) { carry += p->num[i] + (x & MAX_VAL); p->num[i] = carry; carry >>= 32; x >>= 32; if (!x && !carry) return; } } // p = a * b void bignum_mult(bignum *p, const bignum *a, const bignum *b) { memset(p->num, 0, p->sz * sizeof(NUM_TYPE)); for (int i = 0; i < a->sz; ++i) for (int j = 0; j < b->sz; ++j) { TMP_TYPE carry = (TMP_TYPE) a->num[i] * b->num[j]; bn_mult_add(p, i + j, carry); } } ``` * Debug tools: * [fibonacci number generator](https://www.omnicalculator.com/math/fibonacci) * [Decimal to Hexadecimal converter](https://www.rapidtables.com/convert/number/decimal-to-hex.html) * [Online Big Number Calculator](https://defuse.ca/big-number-calculator.htm) * [Hexadecimal to Decimal converter](https://www.rapidtables.com/convert/number/hex-to-decimal.html) * 參考實作: * [KYG-yaya573142](https://github.com/KYG-yaya573142/fibdrv/blob/master/bn_kernel.c) * [sysprog21](https://github.com/sysprog21/bignum/blob/master/bignum.c) * [bignum.c](https://www3.cs.stonybrook.edu/~skiena/algorist/book/programs/bignum.c) * [kokke](https://github.com/kokke/tiny-bignum-c/blob/master/bn.c) --- # 實作時間量測在 `fibdrv.c` 中使用 `ktime` 量測每次計算 Fibonacci number 所花費的時間。單位是 nano second。我把實作 fast doubling (`fib_fast_doubling()`) 與 iteration (`fib_sequence()`) 的函式原型設計得一樣，然後利用函式指標 (function pointer) 依據不同的需求將不同的演算法送入 `fib_time_cost()` 中。 ```c static void fib_time_cost(void (*fib_algo)(NUM_TYPE), NUM_TYPE k) { kt = ktime_get(); fib_algo(k); kt = ktime_sub(ktime_get(), kt); } ``` 在 `client.c` 中使用 `clock_gettime()` 量測讀取 Fibonacci number 所需花費的時間。單位是 nano second。 ```c : struct timespec t1, t2; size_t rd_len, out_len = 0; // Read a Fibonacci number from linux kernel. // The output of the Fibonacci driver is a hexdecimal number. char fib_output[FIB_OUTPUT_LEN]; int fd_out = open(FIB_OUTPUT, O_RDONLY); clock_gettime(CLOCK_MONOTONIC, &t1); while (rd_len = read(fd_out, fib_output + out_len, FIB_OUTPUT_LEN - out_len)) { out_len += rd_len; } clock_gettime(CLOCK_MONOTONIC, &t2); fib_output[FIB_OUTPUT_LEN - 1] = '\0'; close(fd_out); : // Record the time for reading a Fibonacci number. uint64_t rd_time = (uint64_t)((t2.tv_sec * 1e9 + t2.tv_nsec) - (t1.tv_sec * 1e9 + t1.tv_nsec)); snprintf(tmp_buf, TMP_BUF_LEN, "%d %lu\n", k, rd_time); int fd_rd_time = open(rd_time_file, O_CREAT | O_APPEND | O_WRONLY, S_IRUSR | S_IRGRP | S_IROTH); write(fd_rd_time, tmp_buf, strlen(tmp_buf)); close(fd_rd_time); ``` --- # 簡化實驗流程這個階段的目標是要透過下列方法簡化實驗流程。 * 在 `sysfs` 中新增 `/sys/kernel/fibonacci/algo`。利用它來動態調整計算 Fibonacci number 的演算法。 * 在 `fibdrv.c` 中，實作 iteration 與 fast doubling 的函式原型如下所示: ```c static void fib_fast_doubling(NUM_TYPE k); static void fib_sequence(NUM_TYPE k); ``` * 定義函式指標 `fib_algo` 動態指向上述兩個函式中的一個。`fib_algo` 預設指向 `fib_fast_doubling`。 ```c static void (*fib_algo)(NUM_TYPE); ``` * 對 `/sys/kernel/fibonacci/algo` 分別寫入 `"iteration"` 與 `"fast-doubling"` 就可以控制計算 Fibonacci number 的演算法。 ```c static ssize_t fib_algo_store(struct kobject *kobj, struct kobj_attribute *attr, const char *buf, size_t count) { if (strncmp(buf, "iteration", 9) == 0) { /* Set the algorithm to be iteration. */ pr_info("%s: Set the algorithm to be iteration.\n", KBUILD_MODNAME); fib_algo = fib_sequence; } else if (strncmp(buf, "fast-doubling", 13) == 0) { /* Set the algorithm to be fast-doubling. */ pr_info("%s: Set the algorithm to be fast-doubling.\n", KBUILD_MODNAME); fib_algo = fib_fast_doubling; } else { pr_info("%s: %s is not support.\n", KBUILD_MODNAME, buf); pr_info("%s: Set the algorithm to be fast-doubling.\n", KBUILD_MODNAME); fib_algo = fib_fast_doubling; } return strlen(buf); } --- # 為效能分析設定實驗環境 ## 將行程固定在特定的 CPU 中執行執行 `taskset` 並使用 `-cp` 參數再加上 process ID 查看指定行程的處理器親和性(CPU affinity)。已執行結果看來，我可以使用 CPU 0~3。 ``` $ taskset -cp 1 pid 1's current affinity list: 0-3 ``` 接下來使用 boot loader 所提供的自訂開機參數功能，手動加入 `isolcpus=cpu_id` 參數。讓特定的 CPU 核心在開機時就被保留下來，不讓其他的行程干擾我要執行的程式。我先保留 CPU 0。首先切換目錄到 `/etc/default`，然後備份 `grub`。 ```shell $ cd /etc/default $ sudo cp grub grub-org ``` 然後修改 `/etc/default/grub` 中的 `GRUB_CMDLINE_LINUX_DEFAULT` 參數。在此參數後加上 `isolcpus=0` 也就是保留 CPU 0 給特定程式使用。 ``` GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=0" ``` 執行下列指令更新 boot loader 的開機參數。 ```shell $ sudo update-grub Sourcing file `/etc/default/grub' Sourcing file `/etc/default/grub.d/init-select.cfg' Generating grub configuration file ... Found linux image: /boot/vmlinuz-5.13.0-35-generic Found initrd image: /boot/initrd.img-5.13.0-35-generic Found linux image: /boot/vmlinuz-5.13.0-30-generic Found initrd image: /boot/initrd.img-5.13.0-30-generic Found memtest86+ image: /boot/memtest86+.elf Found memtest86+ image: /boot/memtest86+.bin done ``` 先檢查 `/sys/devices/system/cpu/isolated` 的內容，應該要是空的。 ```shell $ cat /sys/devices/system/cpu/isolated ``` 然後，重新開機。 ```shell $ sudo reboot ``` 待重新開機完成後，在檢查 `/sys/devices/system/cpu/isolated` 的內容。應該要是 0。也就是我剛剛在 `/etc/default/grub` 中用 `isolcpus=0` 保留下來的 CPU。 ```shell $ cat /sys/devices/system/cpu/isolated 0 ``` 接著就可以用 `taskset` 指定 CPU 來執行程式。在這個作業中，執行 `client` 並透過 `sysfs` 介面操作 `fibdrv` 計算 Fibonacci numbers。 ```shell # taskset -c 0 ./client $PWD fd_fib.time fd_rd.time ``` 將這個動作整合到 `Makefile` 中。以簡化後續的實作流程。以下是在 `Makefile` 中新增的兩個 rule。 ```Makefile it_time: client # This rule must be run as root echo "iteration" > /sys/kernel/fibonacci/algo # Bind the executable to CPU 0. taskset -c 0 ./client $(PWD) it_fib.time it_rd.time fd_time: client # This rule must be run as root echo "fast-doubling" > /sys/kernel/fibonacci/algo # Bind the executable to CPU 0. taskset -c 0 ./client $(PWD) fd_fib.time fd_rd.time ``` ## 排除干擾效能分析的因素 * 暫時抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR) ```shell $ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space" ``` * 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 `performance.sh`: ```shell for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor do echo performance > ${i} done ``` 然後再用下列執行 `performance.sh`。 ```shell $ sudo sh performance.sh ``` * 針對 Intel 處理器，關閉 turbo mode ```shell $ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo" ``` * 將上述這些排除干擾效能分析的因素的動作全部整合進 `Makefile` 以簡化後續實驗流程。 ```Makefile set_env: # This rule must be run as root # Suppress address space layout randomization (ASLR) sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space" sudo sh performance.sh # For Intel CPU, disable turbo mode sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo" ``` * 參考資料: [排除干擾效能分析的因素](https://hackmd.io/@sysprog/linux2022-fibdrv#%E6%8E%92%E9%99%A4%E5%B9%B2%E6%93%BE%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E5%9B%A0%E7%B4%A0) --- # 效能分析(內建資料型別) ## 初步觀察以下列這個 commit 的程式碼搭配本文一開始所描述的環境做實驗。 > commit: ab44371 > branch: perf.built-in-type :::spoiler fast doubling ```c static long long fib_fast_doubling_org(long long n) { if (n <= 1) { // base case: // F(0) = 0 // F(1) = 1 // Performanc measure strat. kt = ktime_get(); int ret = n; // Performanc measure stop. kt = ktime_sub(ktime_get(), kt); return ret; } // Performanc measure strat. kt = ktime_get(); long long a = 0, b = 1; unsigned int mask_len = sizeof(unsigned int) * 8 - 1; for (unsigned int k = 1U << mask_len; k; k >>= 1) { long long k1 = a * (2 * b - a); // F(2k) = F(k)[2F(k+1) - F(k)] long long k2 = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2 if (n & k) { a = k2; // F(2k+1) b = k1 + k2; // F(2k+2) } else { a = k1; // F(2k) b = k2; // F(2k+1) } } // Performanc measure stop. kt = ktime_sub(ktime_get(), kt); return a; } ``` ::: 執行下列指令畫出 `iteration` 與 `fast doubling` 的效能比較。 ```shell $ make clean plot_clean all $ make unload load $ sudo su $ make plot ``` 結果會畫在 `fibdrv_perf.png` 中。 ![fibdrv_perf_built_in_type.png](https://i.imgur.com/tTvAOk6.png) Iteration 演算法的時間複雜度為 O(n)，fast doubling 演算法的時間複雜度為 O(logn)。由上圖的實驗結果可看出這個趨勢。 ## 設法改善 fast doubling 的效能由作業說明 ([H03: fibdrv, 費氏數列](https://hackmd.io/@sysprog/linux2020-fibdrv#-%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97)) 中的虛擬碼與示範案例，以及[Calculating Fibonacci Numbers by Fast Doubling](https://chunminchang.github.io/blog/post/calculating-fibonacci-numbers-by-fast-doubling) 的說明可窺見，以 fast doubling 計算 Fibonacci number 可對所欲求取的項數的二進位表示法決定計算步驟。所以可以利用 `gcc` 提供的 `__builtin_clz()` 減少尋找 MSB (most significant bit) 的時間。 > commit: ab44371 > branch: perf.built-in-type :::spoiler fast doubling with clz ```c static long long fib_fast_doubling_clz(long long n) { if (n <= 1) { // base case: // F(0) = 0 // F(1) = 1 // Performanc measure strat. kt = ktime_get(); int ret = n; // Performanc measure stop. kt = ktime_sub(ktime_get(), kt); return ret; } // Performanc measure strat. kt = ktime_get(); long long a = 0, b = 1; unsigned int mask_len = sizeof(unsigned int) * 8 - 1 - __builtin_clz(n); for (unsigned int k = 1U << mask_len; k; k >>= 1) { long long k1 = a * (2 * b - a); // F(2k) = F(k)[2F(k+1) - F(k)] long long k2 = a * a + b * b; // F(2k+1) = F(k)^2 + F(k+1)^2 if (n & k) { a = k2; // F(2k+1) b = k1 + k2; // F(2k+2) } else { a = k1; // F(2k) b = k2; // F(2k+1) } } // Performanc measure stop. kt = ktime_sub(ktime_get(), kt); return a; } ``` ::: ![fibdrv_perf2_built_in_type.png](https://i.imgur.com/4R1dkZK.png) # 效能分析 (自行實作的 big number) ## 初步觀察以下列這個 commit 的程式碼搭配本文一開始所描述的環境做實驗。 > commit: 2b8c55a > branch: master :::spoiler fast doubling (big number) ```c static void fib_fast_doubling_org(NUM_TYPE k) { if (k <= 1) { answer = bignum_create(BIGNUM_SZ); // Performanc measure strat. kt = ktime_get(); answer->num[0] = k; // Performanc measure stop. kt = ktime_sub(ktime_get(), kt); return; } bignum *a = bignum_create(BIGNUM_SZ); answer = a; bignum *b = bignum_create(BIGNUM_SZ); bignum *c = bignum_create(BIGNUM_SZ); bignum *d = bignum_create(BIGNUM_SZ); bignum *tmp1 = bignum_create(BIGNUM_SZ); bignum *tmp2 = bignum_create(BIGNUM_SZ); // Performanc measure strat. kt = ktime_get(); unsigned int mask_len = sizeof(unsigned int) * 8 - 1; a->num[0] = 0; // base case, F(0) = 0 b->num[0] = 1; // base case, F(1) = 1 for (unsigned int i = 1U << mask_len; i; i >>= 1) { bignum_cpy(tmp1, b); bignum_lshift(tmp1, 1); // tmp1 = 2 * F(k+1) bignum_sub(tmp2, tmp1, a); // tmp2 = 2 * F(k+1) - F(k) bignum_mult(c, a, tmp2); // F(2k) = F(k) * [2 * F(k+1) - F(k)] bignum_mult(tmp1, a, a); // tmp1 = a * a bignum_mult(tmp2, b, b); // tmp2 = b * b bignum_add(d, tmp1, tmp2); // F(2k+1) = F(k) * F(k) + F(k+1) * F(k+1) if (k & i) { bignum_cpy(a, d); bignum_add(b, c, d); } else { bignum_cpy(a, c); bignum_cpy(b, d); } } // Performanc measure stop. kt = ktime_sub(ktime_get(), kt); bignum_destroy(b); bignum_destroy(c); bignum_destroy(d); bignum_destroy(tmp1); bignum_destroy(tmp2); } ``` ::: 執行下列指令畫出 `iteration` 與 `fast doubling` 的效能比較。 ```shell $ make clean plot_clean all $ make unload load $ sudo su $ make plot ``` 結果會畫在 `fibdrv_perf.png` 中。 ![fibdrv_perf_big_number.png](https://i.imgur.com/cATslVE.png) ## 以 clz 改善以 big number 實作的 fast doubling 效能 > commit: 2b8c55a > branch: master :::spoiler fast doubling (big number) with clz ```c static void fib_fast_doubling_clz(NUM_TYPE k) { if (k <= 1) { answer = bignum_create(BIGNUM_SZ); // Performanc measure strat. kt = ktime_get(); answer->num[0] = k; // Performanc measure stop. kt = ktime_sub(ktime_get(), kt); return; } bignum *a = bignum_create(BIGNUM_SZ); answer = a; bignum *b = bignum_create(BIGNUM_SZ); bignum *c = bignum_create(BIGNUM_SZ); bignum *d = bignum_create(BIGNUM_SZ); bignum *tmp1 = bignum_create(BIGNUM_SZ); bignum *tmp2 = bignum_create(BIGNUM_SZ); // Performanc measure strat. kt = ktime_get(); unsigned int mask_len = sizeof(unsigned int) * 8 - 1 - __builtin_clz(k); a->num[0] = 0; // base case, F(0) = 0 b->num[0] = 1; // base case, F(1) = 1 for (unsigned int i = 1U << mask_len; i; i >>= 1) { bignum_cpy(tmp1, b); bignum_lshift(tmp1, 1); // tmp1 = 2 * F(k+1) bignum_sub(tmp2, tmp1, a); // tmp2 = 2 * F(k+1) - F(k) bignum_mult(c, a, tmp2); // F(2k) = F(k) * [2 * F(k+1) - F(k)] bignum_mult(tmp1, a, a); // tmp1 = a * a bignum_mult(tmp2, b, b); // tmp2 = b * b bignum_add(d, tmp1, tmp2); // F(2k+1) = F(k) * F(k) + F(k+1) * F(k+1) if (k & i) { bignum_cpy(a, d); bignum_add(b, c, d); } else { bignum_cpy(a, c); bignum_cpy(b, d); } } // Performanc measure stop. kt = ktime_sub(ktime_get(), kt); bignum_destroy(b); bignum_destroy(c); bignum_destroy(d); bignum_destroy(tmp1); bignum_destroy(tmp2); } ``` ::: ![fibdrv_perf2_clz_big_number.png](https://i.imgur.com/1YhlJk4.png) 由實驗數據看來，原本的 iteration 演算法隨著項數的增長，所花費的時間以線性關係成長。而 fast doubling 演算法的曲線則是呈現類似對數 (logarithm) 的關係。雖然兩個演算法的時間複雜度與理論吻合，可是fast doubling 所花費的時間卻比 iteration 來的高。以這個趨勢來看，當項數足夠大的時候，iteration 所花費的時間會超越 fast doubling。不過，已經算到 F~23000~ 了 fast doubling 所花費的時間仍然比 iteration 高。看來我實作的 big numger 還有很大的改善空間。 --- # 自我檢查清單 - [ ] 研讀上述 Linux 效能分析的提示描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 → 從中也該理解為何不希望在虛擬機器中進行實驗; - [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說 - [ ] 複習 C 語言數值系統和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本; - [ ] 研讀 KYG-yaya573142 的報告，指出針對大數運算，有哪些加速運算和縮減記憶體操作成本的舉措？ - [ ] lsmod 的輸出結果有一欄名為 Used by，這是 “each module’s use count and a list of referring modules”，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？ >搭配閱讀 The Linux driver implementer’s API guide » Driver Basics - [ ] 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。