---
title: 2023q1 Homework3 (fibdrv)
tags: Linux核心實作
---
# 2023q1 Homework3 (fibdrv)
contributed by < [`lorian0738`](https://github.com/lorian0738) >
## 自我檢查清單
- [ ] 研讀上述 ==Linux 效能分析的提示== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
- [ ] 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 [clz / ctz](https://en.wikipedia.org/wiki/Find_first_set) 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
- [ ] 複習 C 語言 [數值系統](https://hackmd.io/@sysprog/c-numerics) 和 [bitwise operation](https://hackmd.io/@sysprog/c-bitwise)，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
- [ ] 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措，紀錄你的認知和疑惑
- [ ] 注意到 `fibdrv.c` 存在著 `DEFINE_MUTEX`, `mutex_trylock`, `mutex_init`, `mutex_unlock`, `mutex_destroy` 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題。嘗試撰寫使用 [POSIX Thread](https://en.wikipedia.org/wiki/POSIX_Threads) 的程式碼來確認。 $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉
## 了解更多核心模組
* [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module#Linux-%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84%E9%81%8B%E4%BD%9C%E5%8E%9F%E7%90%86)
* 《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》
* [Introduction to Linux kernel driver programming](https://events.linuxfoundation.org/wp-content/uploads/2017/12/Introduction-to-Linux-Kernel-Driver-Programming-Michael-Opdenacker-Bootlin-.pdf)
* [Part 1: Introduction](http://derekmolloy.ie/writing-a-linux-kernel-module-part-1-introduction/)
* [Part 2: A Character Device](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/)
## 前期準備
* 檢查 Linux 核心版本
```
$ uname -r
```
輸出：
```
5.15.0-67-generic
```
* 安裝 linux-headers 套件
```
$ sudo apt install linux-headers-`uname -r`
```
輸出：
```
正在讀取套件清單... 完成
正在重建相依關係... 完成
正在讀取狀態資料... 完成
linux-headers-5.15.0-67-generic is already the newest version (5.15.0-67.74).
升級 0 個，新安裝 0 個，移除 0 個，有 239 個未被升級。
```
* 確認 linux-headers 套件已正確安裝於開發環境
$ dpkg -L linux-headers-5.4.0-66-generic | grep "/lib/modules"
```
$ dpkg -L linux-headers-5.15.0-67-generic | grep "/lib/modules"
```
輸出：
```
/lib/modules
/lib/modules/5.15.0-67-generic
/lib/modules/5.15.0-67-generic/build
```
* 檢驗目前的使用者身份
```
$ whoami
```
輸出：
```
cyh
```
預期為「不是 root 的使用者名稱」，例如 jserv (或者你安裝 Ubuntu Linux 指定的登入帳號名稱)。
* 由於測試過程需要用到 sudo，請一併查驗:
```
$ sudo whoami
```
輸出：
```
root
```
預期輸出是 root
:notes: 在下列操作中，請避免用 root 帳號輸入命令，而該善用 sudo
之後的實驗中，若濫用 root 權限，可能會破壞 GNU/Linux 開發環境 (當然，你還是可重新安裝)，現在開始養成好習慣
* 安裝後續會用得到的工具
```
$ sudo apt install util-linux strace gnuplot-nox
```
* 取得原始程式碼
* 先 fork 到自己的 GitHub
* git clone
```
$ git clone git@github.com:lorian0738/fibdrv.git
$ cd fibdrv
```
* 編譯並測試
```
$ make check
```
> 注意：這個指令會先卸載再掛載再卸載，在額外執行時會發現沒有掛載到，故可以僅輸入 $ make 編譯就好
預期：
```
綠色的 Passed [-] 字樣，隨後是
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
實際輸出：
```
Passed [-]
f(93) fail
input: 7540113804746346429
expected: 12200160415121876738
```
=> 符合預期
* 觀察產生的 fibdrv.ko
```
$ modinfo fibdrv.ko
```
預期可得以下輸出:
```
description: Fibonacci engine driver
author: National Cheng Kung University, Taiwan
license: Dual MIT/GPL
name: fibdrv
vermagic: 5.4.0-45-generic SMP mod_unload
```
實際輸出：
```
filename: /home/cyh/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.15.0-67-generic SMP mod_unload modversions
```
好奇 vermagic 是什麼，但維基百科沒有，[網站](http://lishiwen4.github.io/linux-kernel/linux-kernel-module-version-check)中提到：
```
Linux的vermagic用於內核模塊的版本檢查，其值由kernel Makefile中的“VERMAGIC_STRING”來表示，在編譯kernel的過程中生成。
總的來說，在vermagic中，只有內核版本是一定會被包含的，而其它的要看具體的kernel配置。
VERMAGIC_STRING = <UTS_RELEASE> ["SMP"] ["preempt"] ["mod_unload"]["modversions"]
```
因此可能是因為 kernel 配置不同而比預期輸出多了 modversions
* 觀察 fibdrv.ko 核心模組在 Linux 核心掛載後的行為
* 要先透過 insmod 將模組載入核心後才會有下面的裝置檔案 /dev/fibonacci
```
$ sudo insmod fibdrv.ko
```
(註：Makefile 中 load 也有一樣的功能，可直接下 make load 在終端機)
```
$ ls -l /dev/fibonacci
```
輸出：
```
crw------- 1 root root 511, 0 3月 8 16:49 /dev/fibonacci
```
```
$ cat /sys/class/fibonacci/fibonacci/dev
```
輸出：
```
511:0
```
新建立的裝置檔案 /dev/fibonacci，注意到 236 這個數字，在你的電腦也許會有出入。試著對照 fibdrv.c，找尋彼此的關聯。
```
$ cat /sys/module/fibdrv/version
```
輸出：
```
0.1
```
預期輸出是 0.1(相同)，這和 fibdrv.c 透過 MODULE_VERSION 所指定的版本號碼相同。
```
$ lsmod | grep fibdrv
```
輸出：
```
fibdrv 16384 0
```
```
$ cat /sys/module/fibdrv/refcnt
```
輸出：
```
0
```
這兩道命令的輸出都是 0，意味著目前的 reference counting。
## [Linux 效能分析](https://hackmd.io/@sysprog/linux2023-fibdrv-c#-Linux-%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90%E7%9A%84%E6%8F%90%E7%A4%BA)
### 查看行程的 CPU affinity
查看指定行程的處理器親和性 (PID = process ID)
#### 第一種（十六進位）
```
$ taskset -p PID
```
輸入：
```
$ taskset -p 1
```
輸出：
```
pid 1's current affinity mask: ff
```
十六進位的 ff 轉成二進位的格式會是 11111111，這 8 個 1 分別代表該行程可以在第 0 到第 7 個 CPU 核中執行，最低（LSB; 最右邊）的位元代表第 0 個 CPU 核
#### 第二種（直接輸出列表）
輸入：
```
$ taskset -cp 1
```
輸出：
```
pid 1's current affinity list: 0-7
```
### 限定 CPU 給特定的程式使用
使用 isolcpus 這個 Linux 核心起始參數，讓特定的 CPU 核在開機時就被保留下來
設定的方式：
1. 開機時使用 boot loader 所提供的自訂開機參數功能，手動加入 `isolcpus=cpu_id` 參數
2. 直接加在 GRUB 的設定檔中
於是只有那些被 taskset 特別指定的行程可使用這些 CPU 核
選擇直接加在 GRUB 設定檔中，保留第 0 個 CPU 核：
> 參考網站：[1](https://www.ltsplus.com/linux/linux-hide-grub-boot-menu) [2](https://www.twblogs.net/a/5d3f74ccbd9eee5174229c27)
1. 先備份
```
$ sudo cp /etc/default/grub /etc/default/grub.bak
```
2. 開啟 GRUB 檔
```
$ sudo vi /etc/default/grub
```
3. 添加 isolcpus 參數
```
GRUB_CMDLINE_LINUX="isolcpus=1,3"
```
4. 更新
```
sudo update-grub
```
5. 輸出：
```
Sourcing file `/etc/default/grub'
Sourcing file `/etc/default/grub.d/init-select.cfg'
Generating grub configuration file ...
Found linux image: /boot/vmlinuz-5.15.0-67-generic
Found initrd image: /boot/initrd.img-5.15.0-67-generic
Found linux image: /boot/vmlinuz-5.15.0-60-generic
Found initrd image: /boot/initrd.img-5.15.0-60-generic
Memtest86+ needs a 16-bit boot, that is not available on EFI, exiting
Warning: os-prober will not be executed to detect other bootable partitions.
Systems on them will not be added to the GRUB boot configuration.
Check GRUB_DISABLE_OS_PROBER documentation entry.
Adding boot menu entry for UEFI Firmware Settings ...
done
```
6. 重新開機確認
輸入：
```
$ taskset -p 1
```
輸出：
```
pid 1's current affinity mask: fe
```
第 0 個 CPU 核已被保留！
### 以特定的 CPU 執行程式
首先編譯產生執行檔
```
$ make
```
接著利用 taskset 將執行檔綁定在特定 cpu
因為前面保留第 0 個 cpu：
```
$ sudo taskset 0x1 ./client
```
其中 0x1 表示第 0 個 cpu
### 排除干擾效能分析的因素
1. 抑制 [address space layout randomization](https://en.wikipedia.org/wiki/Address_space_layout_randomization) (ASLR)
```
$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
```
2. 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 `performance.sh`
首先以 `sudo vi performance.sh` 建立檔案並填入以下：
```
for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
do
echo performance > ${i}
done
```
再執行
```
$ sudo sh performance.sh
```
3. 針對 Intel 處理器，關閉 turbo mode
```
$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
```
[turbo boost](https://www.intel.com/content/www/us/en/gaming/resources/turbo-boost.html)：
> it lets the CPU run at its base clock speed when handling light workloads, then jump to a higher clock speed for heavy workloads.
因此這會讓 CPU 至少一直以基本時脈速度運行，對效能測試會有影響
## [核心模式的時間測量](https://hackmd.io/@sysprog/linux2023-fibdrv-c#%E6%A0%B8%E5%BF%83%E6%A8%A1%E5%BC%8F%E7%9A%84%E6%99%82%E9%96%93%E6%B8%AC%E9%87%8F)
### ktime_t
參考教材以新的資料結構 `ktime_t` 測量時間，如下：
```c
static long long fib_time_proxy(long long k)
{
kt = ktime_get();
long long result = fib_sequence(k);
kt = ktime_sub(ktime_get(), kt);
return result;
}
/* calculate the fibonacci number at given offset */
static ssize_t fib_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
return (ssize_t) fib_time_proxy(*offset);
}
/* write operation is skipped */
static ssize_t fib_write(struct file *file,
const char *buf,
size_t size,
loff_t *offset)
{
return ktime_to_ns(kt); // output fib time
}
```
改完後下 make check 指令會看到：
```
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
-Writing to /dev/fibonacci, returned the sequence 0
...
```
client.c 中，原本 write 的部份：
```c
for (int i = 0; i <= offset; i++) {
sz = write(fd, write_buf, strlen(write_buf));
printf("Writing to " FIB_DEV ", returned the sequence %lld\n", sz);
}
```
其中在 `unistd.h` 中可見
```c
/* Write N bytes of BUF to FD. Return the number written, or -1.
This function is a cancellation point and therefore not marked with
__THROW. */
extern ssize_t write (int __fd, const void *__buf, size_t __n) __wur
__attr_access ((__read_only__, 2, 3));
```
可知 write 的功能是將存在 BUF 的 N 個 bytes 傳給 FD，回傳寫入的字數
其中 BUF 的意思是 buffer
FD 根據[維基百科](https://en.wikipedia.org/wiki/File_descriptor)，指的是 file descriptor：檔案描述子，為 Unix 或 Unix-like 作業系統常用的詞，是一個檔案或讀寫操作的行程唯一標識符 (process-unique identifier)，例如 pipe 或 network socket，通常為非負整數，負數保留於沒有值或是錯誤。
這個函式也作為一個 cancellation point，問了 chatGPT：
```
Cancellation point 是指在多線程編程中，一個可以取消執行緒運行的特定點。
當執行緒到達這個點時，它可以檢查是否有取消請求，如果有，則可以將自己取消。
Cancellation point 是一個非常重要的概念，因為它可以讓程序更加靈活地處理
取消請求，避免出現死鎖或無法取消的情況。
在 POSIX 環境下，許多系統函數都是 cancellation point，
例如 pthread_join()、read()、write() 等。
```
:::info
看不懂為什麼很多字前面後面都要加上__，有待釐清...
:::
還是不知道要怎麼做，因此參考了[同學的想法](https://hackmd.io/@Hongweii/2023q1-fivdrv#%E6%99%82%E9%96%93%E6%B8%AC%E9%87%8F%E8%88%87%E6%95%88%E8%83%BD%E5%88%86%E6%9E%90)，因為要做完計算 kt 的值才會是對的，因此先用 `read` 做計算，再 call `wite` 的函式才會對
read：
```c
/* Read NBYTES into BUF from FD. Return the
number read, -1 for errors or 0 for EOF.
This function is a cancellation point and therefore not marked with
__THROW. */
extern ssize_t read (int __fd, void *__buf, size_t __nbytes) __wur
__fortified_attr_access (__write_only__, 2, 3);
```
因此改成：
```c
for (int i = 0; i <= offset; i++) {
sz = read(fd, buf, 1);
long long time = write(fd, write_buf, strlen(write_buf));
printf("Writing to " FIB_DEV ", returned the sequence %lld\n", time);
}
```
改完以後輸出：
```
-Writing to /dev/fibonacci, returned the sequence 87
-Writing to /dev/fibonacci, returned the sequence 61
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
-Writing to /dev/fibonacci, returned the sequence 46
...
```
但這樣改的話迴圈中 `sz = read(fd, buf, 1);` 的 sz 沒有用到，會 commit 不了，因為程式會認為它佔用空間卻沒有實質影響。可以直接寫在後面的迴圈就好，而計算時間後應該輸出成檔案再用 gnuplot 繪製。
#### gnuplot
根據教材 [gnuplot 語法解說和示範](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FSkwp-alOg) 可知應該將想繪製的資料做成 txt 或 csv 檔再用附檔名為 gp 的檔案讀取繪圖
* 首先準備 csv 檔：(於 client.c 的檔案中)
```c
// prepare csv for gnuplot
FILE *fp = fopen("time.csv", "w+");
if (fp == NULL) {
fprintf(stderr, "fopen() failed.\n");
exit(EXIT_FAILURE);
}
```
w+ 表示為了讀出和寫入而打開檔案，在檔案已存在的前提下，會把原來的內容覆蓋掉; 如果檔案不存在就創建一個新的。（[參考](http://pl-learning-blog.logdown.com/posts/1102314)）
若開啟失敗則報錯
```c
fprintf(fp, "nth Fibonacci, Fast Doubling\n");
```
將 nth Fibonacci 和 Fast Doubling 寫入檔案的第一列作為標題
```c
for (int i = 0; i <= offset; i++) {
lseek(fd, i, SEEK_SET);
sz = read(fd, buf, 1);
long long time = write(fd, write_buf, strlen(write_buf));
printf("Reading from " FIB_DEV
" at offset %d, returned the sequence "
"%lld.\n",
i, sz);
fprintf(fp, "%d, %lld\n", i, time);
}
```
迴圈中首先計算 Fibonacci，算完後取得花費時間 time，再將該迴圈計算第 i 個費波那契數與取得的 time 逐列寫入檔案中
```c
fclose(fp);
```
最後關閉檔案
* 寫 gp 檔
首先下指令：
```
$ gnuplot
```
會出現：
```
G N U P L O T
Version 5.4 patchlevel 2 last modified 2021-06-01
Copyright (C) 1986-1993, 1998, 2004, 2007-2021
Thomas Williams, Colin Kelley and many others
gnuplot home: http://www.gnuplot.info
faq, bugs, etc: type "help FAQ"
immediate help: type "help" (plot window: hit 'h')
Terminal type is now 'unknown'
gnuplot>
```
不知道 Terminal type 是什麼意思，[搜尋](https://askubuntu.com/questions/710783/gnuplot-terminal-set-unknown)後得知 gnuplot 無法識別有效的終端機，因此要輸入以下進行設定：
```
gnuplot> set terminal
```
會輸出：
```
Available terminal types:
cairolatex LaTeX picture environment using graphicx package and Cairo backend
canvas HTML Canvas object
cgm Computer Graphics Metafile
context ConTeXt with MetaFun (for PDF documents)
domterm DomTerm terminal emulator with embedded SVG
dpu414 Seiko DPU-414 thermal printer [small medium large]
dumb ascii art for anything that prints text
dxf dxf-file for AutoCad (default size 120x80)
emf Enhanced Metafile format
epscairo eps terminal based on cairo
epslatex LaTeX picture environment using graphicx package
epson_180dpi Epson LQ-style 180-dot per inch (24 pin) printers
epson_60dpi Epson-style 60-dot per inch printers
epson_lx800 Epson LX-800, Star NL-10, NX-1000, PROPRINTER ...
fig FIG graphics language V3.2 for XFIG graphics editor
gif GIF images using libgd and TrueType fonts
hp500c HP DeskJet 500c, [75 100 150 300] [rle tiff]
hpdj HP DeskJet 500, [75 100 150 300]
hpgl HP7475 and relatives [number of pens] [eject]
hpljii HP Laserjet series II, [75 100 150 300]
hppj HP PaintJet and HP3630 [FNT5X9 FNT9X17 FNT13X25]
Press return for more:
...
```
因為找不到 wxt, qt, x11, aqua 等可以直接看輸出圖形的形式，因此直接將圖片輸出另存成 png 檔
可以利用 help 取得更多資訊，例如：
```
gnuplot> help terminal png
```
輸出：
```
Syntax:
set terminal png
{{no}enhanced}
{{no}transparent} {{no}interlace}
{{no}truecolor} {rounded|butt}
{linewidth <lw>} {dashlength <dl>}
{tiny | small | medium | large | giant}
{font "<face> {,<pointsize>}"} {fontscale <scale>}
{size <x>,<y>} {{no}crop}
{background <rgb_color>}
PNG, JPEG and GIF images are created using the external library libgd.
PNG plots may be viewed interactively by piping the output to the
'display' program from the ImageMagick package as follows:
set term png
set output '| display png:-'
You can view the output from successive plot commands interactively by typing
<space> in the display window. To save the current plot to a file,
left click in the display window and choose `save`.
`transparent` instructs the driver to make the background color transparent.
Default is `notransparent`.
Press return for more:
`interlace` instructs the driver to generate interlaced PNGs.
Default is `nointerlace`.
The `linewidth` and `dashlength` options are scaling factors that affect all
lines drawn, i.e. they are multiplied by values requested in various drawing
commands.
By default output png images use 256 indexed colors. The `truecolor` option
instead creates TrueColor images with 24 bits of color information per pixel.
Transparent fill styles require the `truecolor` option. See `fillstyle`.
A transparent background is possible in either indexed or TrueColor images.
`butt` instructs the driver to use a line drawing method that does
not overshoot the desired end point of a line. This setting is only
applicable for line widths greater than 1. This setting is most useful when
drawing horizontal or vertical lines. Default is `rounded`.
The details of font selection are complicated.
Two equivalent simple examples are given below:
set term png font arial 11
set term png font "arial,11"
Press return for more:
For more information please see the separate section under `fonts`.
The output plot size <x,y> is given in pixels---it defaults to 640x480.
Please see additional information under `canvas` and `set size`.
Blank space at the edges of the finished plot may be trimmed using the `crop`
option, resulting in a smaller final image size. Default is `nocrop`.
```
進行設定：
```
gnuplot> set terminal png enhanced truecolor
```
輸出：
```
Terminal type is now 'png'
Options are 'truecolor nocrop enhanced size 640,480 font "arial,12.0" '
```
接著直接寫腳本後續利用比較方便，輸入 `vim gnuplot.gp` 或直接用 VS code 創建檔案：
```
set title "fibonacci time"
set xlabel "nth fibonacci"
set ylabel "ns"
set terminal png font " Times_New_Roman,12 "
set output "time.png"
plot "time.csv" using 1:2 with linespoints linewidth 2 title "fast doubling"
```
設定圖片標題、座標軸名稱、字體字形、輸出檔案名稱、以及要用來繪製圖形的行列
最後輸入以下繪圖：
```
$ gnuplot gnuplot.gp
```
終於得到圖片：
> 註：因為是寫完 Fast Doubling 才開始研究計算時間的方法，因此這邊輸出的圖行為 Fast Doubling 的時間，也尚未考慮其他影響時間的因素，因排版關係 Fast Doubling 的實作也在此部份後面([連結](https://hackmd.io/L1VyEBVGTDK5g078qY9itQ?both#%E4%BB%A5-Fast-Doubling-%E6%89%8B%E6%B3%95%E6%94%B9%E5%AF%AB))
#### commit
commit 時沒有先用 `clang-format -i` 確認格式，才注意到註解應該都要在 `//` 後空一格再寫、`#include` 的順序是有照字母排的，這樣確實比較好看
### 考慮 copy_to_user
> 教材提到：進行效能分析時，要考慮到 copy_to_user 函式的時間開銷，特別留意到資料大小成長後造成的量測誤差
## Fibonacci
### 以 Fast Doubling 手法改寫
> #### 考慮到硬體加速 F(n) 的手法
> clz / ctz 一類的指令
在 fibdrv.c 中 `static long long fib_sequence(long long k)` 計算 Fibonacci 的值：
```c
for (int i = 2; i <= k; i++) {
f[i] = f[i - 1] + f[i - 2];
}
```
而[教材](https://hackmd.io/@sysprog/linux2023-fibdrv-a#-%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97)中提到 Fast Doubling 手法：
$$
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
$$
示範案例:
求解 $F(10)$:10~10~ = 1010~2~
| i | start | 4 | 3 | 2 | 1 | result |
|---|-------|----------|----------|----------|---------|--------|
| n | - | ==1==010 | 1==0==10 | 10==1==0 | 101==0== | - |
|F(m) | F(0) | F(0*2+1) | F(1*2) | F(2*2+1) | F(5*2) | F(10) |
| a | 0 | 1 | 1 | 5 | 55 | 55 |
| b | 1 | 1 | 2 | 8 | 89 | - |
可以更快速的計算，參考給的 sudo code 後改寫如下：
```c
static long long fib_sequence(long long k)
{
/* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
long long a = 0, b = 1;
int leading_zero = __builtin_clzll(k);
k = k << leading_zero;
for (int len = 64 - leading_zero; len > 0; len--) {
long long t1 = a * (2 * b - a);
long long t2 = b * b + a * a;
a = t1;
b = t2;
if (((k >> 63) & 1) == 1) {
t1 = a + b;
a = b;
b = t1;
}
k = k << 1;
}
return a;
}
```
首先計算 k 的 leading zero bits 個數，左移 k 使 MSB 移至最高位(前面的 0 都可以略過計算)。
迴圈中先求出 F(2k) 和 F(2k+1) 的值分別紀錄在 t1 和 t2，確認現在是做到 2k 還是 2k+1，若最高位為0，則表示是 2k，回傳 t1；若最高位為 1，則表示是 2k+1，回傳 t2，紀錄 a 為 2k+1的值、b 為 F(2k+2) = F(2k) + F(2k+1)，方便後續計算，最後將 k 左移一位，表示乘以 2。
但要將這段修改 commit 時卻得到訊息：
```
Following files need to be cleaned up:
fibdrv.c
fibdrv.c:39:17: portability: Shifting signed 64-bit value by 63 bits is implementation-defined behaviour [shiftTooManyBitsSigned]
if (((k >> 63) & 1) == 1) {
^
Fail to pass static analysis.
```
才想到因為 k 是有號數，移動有號數造成 SAR (arithmetic right-shift)算術右移；移動無號數是 SHR (logical right-shift) 邏輯位移。
而我原本想做的是邏輯右移，但在有號的情況下，做算數位移最高位元不會變，因此不能右移 63 個位元。
改成將 1 左移到 64位元的最高位元，與 k 做 ＆ 運算，若非 0 則表示現在 k 的最高位為 1
```c
if (k & (unsigned long long) 1 << 63) {
t1 = a + b;
a = b;
b = t1;
}
```
#### gnuplot 繪圖
上述方法使用硬體加速直接計算 leading zero bits，繪圖比較
原本想法是在程式中將已經做好的 csv 讀取後再與新獲得的時間重新做一個新的 csv 檔
經過同學友善提示之後，直接將沒有用 clz 計算的時間輸出成另一個檔名再用 Linux 的 paste 功能合併成一個檔案(合併在右邊)，如下：
```
paste -d ", " time.csv time2.csv > time_fd.csv
```
-d 表示更改兩個檔案資料之間的分隔，原本預設是 tab，這裡改成逗號
再來寫兩個想要合併的檔案，在 > 之後寫合併的檔名
:::info
然而這樣做出來的檔案會僅以逗號分隔，但是 csv 檔應該要用逗號加空白分隔，例如預期：
`1, 1, 1`
但會做出
`1, 1,1`
這會導致 gnuplot 在讀 csv 檔的時候讀不到第三欄
目前為了確認繪製正確先手動加入空白分隔，應該要找到更自動化的方法解決這個問題
:::
目前解法 1：在做成要合併的 csv 前就加好空格
目前解法 2：放棄使用 csv 檔，改用 txt 檔也能畫圖
更改 `gnuplot.gp` ：
```gp
set title "fibonacci time"
set xlabel "nth fibonacci"
set ylabel "ns"
set terminal png font " Times_New_Roman,12 "
set output "time_fd.png"
plot \
"time_fd.csv" using 1:2 with linespoints linewidth 2 title "fast doubling", \
"time_fd.csv" using 1:3 with linespoints linewidth 2 title "fast doubling without clz"
```
輸出圖形：
可看出運用 clz 的加速效果
但這張圖沒有綁定 cpu 再進行測定，透過[上述](https://hackmd.io/L1VyEBVGTDK5g078qY9itQ?both#%E4%BB%A5%E7%89%B9%E5%AE%9A%E7%9A%84-CPU-%E5%9F%B7%E8%A1%8C%E7%A8%8B%E5%BC%8F)綁定後再測：
可看出在某些情況下用 clz 會表現的比較好
:::info
但對於下面這張圖跑的時間整體比上面那張還久有點困惑，照理來說跑在獨立的 cpu 整體表現應該要比較好，與同學們討論後認為可能是因為這都只是跑一次的結果，應該要平均比較準確，且只跑 100 個有點少，速度原本就非常快，且還沒有做大數運算，可能要跑多一點再觀察
:::
也輸出了與一開始作法的比較圖，比更改後的表現還好，應該要能跑更多之後再來測
### 計算 F~93~ (包含) 之後的 Fibonacci 數 (功能受限)
### 減少 copy to user 傳送的資料量
### 逐步縮減 Fibonacci 的執行時間，過程中要充分量化
Sign in with Wallet
Connect another wallet