Try   HackMD

2023q1 Homework3 (fibdrv)

contributed by < lorian0738 >

自我檢查清單

  • 研讀上述 Linux 效能分析的提示 描述,在自己的實體電腦運作 GNU/Linux,做好必要的設定和準備工作
    從中也該理解為何不希望在虛擬機器中進行實驗;
  • 研讀上述費氏數列相關材料 (包含論文),摘錄關鍵手法,並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
  • 複習 C 語言 數值系統bitwise operation,思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
  • 學習指出針對大數運算的加速運算和縮減記憶體操作成本的舉措,紀錄你的認知和疑惑
  • 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣,什麼場景中會需要呢?撰寫多執行緒的 userspace 程式來測試,觀察 Linux 核心模組若沒用到 mutex,到底會發生什麼問題。嘗試撰寫使用 POSIX Thread 的程式碼來確認。
    搭配閱讀〈並行和多執行緒程式設計

了解更多核心模組

前期準備

  • 檢查 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

    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
    在下列操作中,請避免用 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 是什麼,但維基百科沒有,網站中提到:

    ​​​​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 效能分析

查看行程的 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 2

  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 (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

    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 至少一直以基本時脈速度運行,對效能測試會有影響

核心模式的時間測量

ktime_t

參考教材以新的資料結構 ktime_t 測量時間,如下:

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 的部份:

    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 中可見

/* 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 根據維基百科,指的是 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() 等。

看不懂為什麼很多字前面後面都要加上__,有待釐清

還是不知道要怎麼做,因此參考了同學的想法,因為要做完計算 kt 的值才會是對的,因此先用 read 做計算,再 call wite 的函式才會對

read:

/* 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);

因此改成:

    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 語法解說和示範 可知應該將想繪製的資料做成 txt 或 csv 檔再用附檔名為 gp 的檔案讀取繪圖

  • 首先準備 csv 檔:(於 client.c 的檔案中)

    ​​​​    // prepare csv for gnuplot
    ​​​​    FILE *fp = fopen("time.csv", "w+");
    ​​​​    if (fp == NULL) {
    ​​​​        fprintf(stderr, "fopen() failed.\n");
    ​​​​        exit(EXIT_FAILURE);
    ​​​​    }
    

    w+ 表示為了讀出和寫入而打開檔案,在檔案已存在的前提下,會把原來的內容覆蓋掉; 如果檔案不存在就創建一個新的。(參考
    若開啟失敗則報錯

    ​​​​fprintf(fp, "nth Fibonacci, Fast Doubling\n");
    

    將 nth Fibonacci 和 Fast Doubling 寫入檔案的第一列作為標題

    ​​​​    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 逐列寫入檔案中

    ​​​​    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 是什麼意思,搜尋後得知 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 的實作也在此部份後面(連結)

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 的值:

    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

教材中提到 Fast Doubling 手法:

F(2k)=F(k)[2F(k+1)F(k)]F(2k+1)=F(k+1)2+F(k)2
示範案例:
求解
F(10)
:1010 = 10102

i start 4 3 2 1 result
n - 1010 1010 1010 1010 -
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 後改寫如下:

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

        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,這裡改成逗號
再來寫兩個想要合併的檔案,在 > 之後寫合併的檔名

然而這樣做出來的檔案會僅以逗號分隔,但是 csv 檔應該要用逗號加空白分隔,例如預期:
1, 1, 1
但會做出
1, 1,1
這會導致 gnuplot 在讀 csv 檔的時候讀不到第三欄
目前為了確認繪製正確先手動加入空白分隔,應該要找到更自動化的方法解決這個問題

目前解法 1:在做成要合併的 csv 前就加好空格
目前解法 2:放棄使用 csv 檔,改用 txt 檔也能畫圖

更改 gnuplot.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 再進行測定,透過上述綁定後再測:


可看出在某些情況下用 clz 會表現的比較好

但對於下面這張圖跑的時間整體比上面那張還久有點困惑,照理來說跑在獨立的 cpu 整體表現應該要比較好,與同學們討論後認為可能是因為這都只是跑一次的結果,應該要平均比較準確,且只跑 100 個有點少,速度原本就非常快,且還沒有做大數運算,可能要跑多一點再觀察

也輸出了與一開始作法的比較圖,比更改後的表現還好,應該要能跑更多之後再來測

計算 F93 (包含) 之後的 Fibonacci 數 (功能受限)

減少 copy to user 傳送的資料量

逐步縮減 Fibonacci 的執行時間,過程中要充分量化