# 2020q2 Homework2 (fibdrv)
contributed By < `StevenChen8759` >

> Tags: **`linux2020`**
> [作業說明](https://hackmd.io/@sysprog/linux2020-fibdrv#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)

---

## :one: 執行環境
> 在之前的深度學習課程中，因利用筆電配備的 `AMD Raedon R9 M375` GPU 進行深度學習訓練加速( via `Tensorflow ROCm` )，因此已在電腦上安裝了雙系統 (`Windows 8.1` and `Ubuntu 16.04 LTS` )。以下介紹電腦的硬體配置與雙系統規劃。 [color=LightGreen]

### :computer: 筆電硬體配備

| 配備項目 | 配備規格 |
| -------- | -------- |
| 筆電型號 | Lenovo Z51-70 |
|CPU 型號 | Intel Core i5-5200U @ 2.20GHz|
|CPU 多核配置| 2 Cores, 4 Threads (2M4T)|
|主記憶體 (RAM)| 8192MB |
|硬碟大小| 1.0TB |
|原廠作業系統| Windows 8.1|

### :computer: 雙系統配置
* 磁碟配置
* 安裝系統：Ubuntu 16.04 LTS，採 UEFI 模式開機; 其中雙系統選單採用 Ubuntu 主導。
* Ubuntu 開機選單畫面：

:::danger
注意共筆書寫慣例：中英文之間以一個半形空白區隔！
:notes: jserv
:::

## :two: 費氏數列輸出正確性修正

### :camera_with_flash: `fibdiv.c` 之實作錯誤分析
* 參閱 `fibdrv.c` 檔案，發現 `MAX_LENGTH` 設為 `92` ，在數值讀取時，大於 `92` 的輸入將會一律輸出 `f[92]` 。

if (new_pos > MAX_LENGTH)
    new_pos = MAX_LENGTH;  // max case
if (new_pos < 0)
    new_pos = 0;           // min case

* 將 `MAX_LENGTH` 設為 `100` ，並重新編譯模組執行，可發現 `f[93]` 以後的值因為超出 `long long` 的表示範圍，而顯示負數。

#define MAX_LENGTH 100

$ sudo ./client
...
... offset 92, returned the sequence 7540113804746346429.
... offset 93, returned the sequence -6246583658587674878.
... offset 94, returned the sequence 1293530146158671551.
... offset 95, returned the sequence -4953053512429003327.
... offset 96, returned the sequence -3659523366270331776.
... offset 97, returned the sequence -8612576878699335103.
... offset 98, returned the sequence 6174643828739884737.
... offset 99, returned the sequence -2437933049959450366.
... offset 100, returned the sequence 3736710778780434371.
...

* 觀察上列範圍限制的程式片段，可發現費氏數列的輸出皆為正值，因此我們將儲存費氏數列的變數改以 `unsigned long long` 型別儲存，以擴充正數表示範圍。實作如下：

> `client.c` 的修改[color=yellow]

index f5d3b75..820ffed 100644
--- a/client.c
+++ b/client.c
@@ -9,7 +9,7 @@
 
 int main()
 {
-    long long sz;
+    unsigned long long sz;
 
     char buf[1];
     char write_buf[] = "testing writing";
@@ -23,7 +23,7 @@ int main()
 
     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);
+        printf("Writing to " FIB_DEV ", returned the sequence %llu\n", sz);
     }
 
     for (int i = 0; i <= offset; i++) {
@@ -31,7 +31,7 @@ int main()
         sz = read(fd, buf, 1);
         printf("Reading from " FIB_DEV
                " at offset %d, returned the sequence "
-               "%lld.\n",
+               "%llu.\n",
                i, sz);
     }
 
index f5d3b75..820ffed 100644
--- a/client.c
+++ b/client.c
@@ -9,7 +9,7 @@
 
 int main()
 {
-    long long sz;
+    unsigned long long sz;
 
     char buf[1];
     char write_buf[] = "testing writing";
@@ -23,7 +23,7 @@ int main()
 
     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);
+        printf("Writing to " FIB_DEV ", returned the sequence %llu\n", sz);
     }
 
     for (int i = 0; i <= offset; i++) {
@@ -31,7 +31,7 @@ int main()
         sz = read(fd, buf, 1);
         printf("Reading from " FIB_DEV
                " at offset %d, returned the sequence "
-               "%lld.\n",
+               "%llu.\n",
                i, sz);
     }

:::warning
在 `<stdint.h>` 定義 `PRI64u` 和 `PRI64` 一類的巨集，可讓你在 printf 中精準地輸出指定整數型態，請試著改寫上述程式。
:notes: jserv
:::

> `fibdrv.c` 的修改[color=Yellow]

index d142722..d98d435 100644
--- a/fibdrv.c
+++ b/fibdrv.c
@@ -17,17 +17,17 @@ MODULE_VERSION("0.1");
 /* MAX_LENGTH is set to 92 because
  * ssize_t can't fit the number > 92
  */
-#define MAX_LENGTH 92
+#define MAX_LENGTH 100
 
 static dev_t fib_dev = 0;
 static struct cdev *fib_cdev;
 static struct class *fib_class;
 static DEFINE_MUTEX(fib_mutex);
 
-static long long fib_sequence(long long k)
+static unsigned long long fib_sequence(long long k)
 {
     /* FIXME: use clz/ctz and fast algorithms to speed up */
-    long long f[k + 2];
+    unsigned long long f[k + 2];
 
     f[0] = 0;
     f[1] = 1;

* 執行 `make check` 的結果

$ make check
...
--- out	2020-03-19 21:24:22.285899922 +0800
+++ scripts/expected.txt	2020-03-19 21:24:03.409900260 +0800
@@ -192,22 +192,22 @@
... offset 90, returned the sequence 2880067194370816120.
... offset 91, returned the sequence 4660046610375530309.
... offset 92, returned the sequence 7540113804746346429.
-... offset 93, returned the sequence 12200160415121876738.
-... offset 94, returned the sequence 1293530146158671551.
-... offset 95, returned the sequence 13493690561280548289.
-... offset 96, returned the sequence 14787220707439219840.
-... offset 97, returned the sequence 9834167195010216513.
-... offset 98, returned the sequence 6174643828739884737.
-... offset 99, returned the sequence 16008811023750101250.
-... offset 100, returned the sequence 3736710778780434371.
-... offset 100, returned the sequence 3736710778780434371.
...
+... offset 93, returned the sequence 7540113804746346429.
+... offset 94, returned the sequence 7540113804746346429.
+... offset 95, returned the sequence 7540113804746346429.
+... offset 96, returned the sequence 7540113804746346429.
+... offset 97, returned the sequence 7540113804746346429.
+... offset 98, returned the sequence 7540113804746346429.
+... offset 99, returned the sequence 7540113804746346429.
+... offset 100, returned the sequence 7540113804746346429.
...
Makefile:36: recipe for target 'check' failed
make: *** [check] Error 1

* 經過擴充後，發現 `93` 到 `100` 測試值仍為錯誤，查看 `Makefile` 中對 `check` 的定義，發現其對應檢查的檔案 `scripts/expected.txt` 中， `93` 到 `100` 的輸入檢核值皆是相同值，須修改對應的檢核值，使檢查結果正確。
* 但在修改檔案的檢核值前，我們先分析一下 `unsigned long long` 的表示擴充範圍是否可以滿足費氏數列的增長速度：
* 遞迴形式：$F(n)=F(n-1)+F(n-2),F(1)=1,F(0)=0$
* 封閉形式：$F(n) = \dfrac{\sqrt{5}}{5} \cdot (\dfrac{1+\sqrt{5}}{2})^n - \dfrac{\sqrt{5}}{5} \cdot (\dfrac{1-\sqrt{5}}{2})^n$
* 增長複雜度：$F(n) = O(2^n)$
* 由上列分析可知，程式改以 `unsigned long long` 實現，因表示正數的位元增加一個，故表示範圍較 `long long` 型別增加兩倍，而費氏數列的增長速度約為 $O(2^n)$，僅擴充兩倍仍無法滿足費氏數列的空間需求。
* 觀察上列費氏數列輸出 `F[93]` 與 `F[94]` ，可以發現 `F[94]` 的位數較 `F[93]` 少一位，可合理推論 `F[94]` 之值大於擴充後可表示的範圍，這印證了上列的推論。
* 因此，我們需要自訂大數型別，擴充更大的數值存放空間，使其可以存放費氏數列93項以後的值。

### :camera_with_flash: 大數型別 - 原理與 ADT 定義

* 我們沿用[作業一](https://hackmd.io/@sysprog/linux2020-lab0)中的 `link list` ，將其改寫成儲存數個字元的 `doubled link list` ，結構如下所示：

typedef struct BLT {
    char value;
    struct BLT *prev;
    struct BLT *next;
} bnlist_t;

* 使用 `doubled linked list` 的原因，主要在於結構須同時操作加法進位與數字列印，為了方便函式操作，並減少程式碼複雜性，故採 `doubled linked list` 實現。
* 在實作 `list node` 後，我們定義類似作業一中 `queue_t` 的大數型別：

typedef struct {
    int cnt_d;     // Record count of list nodes(digits)
    bnlist_t *msd; // Point to MSD(Most Significant Digit)
    bnlist_t *lsd; // Point to LSD(Least Significant Digit)
} bignum_t;

* 相關操作函式的定義

/* Create a big number with initialize value zero */
bignum_t *bn_create();

/* Make fibonacci number array, store with big number structure */
bignum_t *bn_make_fibonacci(size_t);

/* Allocate digit nodes to specific input number */
void bn_set_digit(bignum_t*, int);

/* Add two big number with new memory space allocation */
bignum_t *bn_add_with_malloc(bignum_t *,bignum_t *);

/* Print big number in Big-endian(MSD first) */
void bn_print();

/* Free created space after usage */
void bn_free();

### :camera_with_flash: 大數型別 - 函式實作
* 在初步的實現中，採用陣列儲存與相加方法，計算費氏數列的值。基於這樣的實現，我們目前暫時只實作 `bn_add` ，且因陣列操作的特性，我們一律配置新的記憶體空間給大數型別，並將結果儲存於該記憶體位址，`bn_add` 函式則回傳對應位址的指標給呼叫自己的函式。
* 加法操作的原理，如下圖所示：
* 詳細程式碼敬請參閱我的github - [bignum.c](https://github.com/StevenChen8759/fibdrv/blob/master/bignum/bignum.c)，此處便不再贅述。

### :camera_with_flash: 大數型別 - 編譯與操作測試
* 使用以下的編譯指令並執行輸出檔案，結果如下：

$ gcc -g bignum.c -o bn_test
$ ./bn_test
F[0] = 0
F[1] = 1
F[2] = 1
F[3] = 2
F[4] = 3
F[5] = 5
F[6] = 8
F[7] = 13
F[8] = 21
F[9] = 34
F[10] = 55
F[11] = 89
F[12] = 144
F[13] = 233
F[14] = 377
F[15] = 610
F[16] = 987
...

### :camera_with_flash: 由實現的大數型別產生正確的費氏數列驗證檔案
* 修改 `bn_make_fibonacci` 函式，使其文字輸出對應 `expected.txt` ，並輸出正確的費氏數列值。

/* Calculate Fibonacci Number (Start from 2)  */
    for (i = 2; i <= n; i++) {
        bn_fib[i] = bn_add_with_malloc(bn_fib[i - 1], bn_fib[i - 2]);
        printf(
            "Reading from /dev/fibonacci at offset %zu, returned the sequence ",
            i);
        bn_print(bn_fib[i]);
        printf(".\n");
    }

    for (i = n; i != SIZE_MAX; i--) {
        printf(
            "Reading from /dev/fibonacci at offset %zu, returned the sequence ",
            i);
        bn_print(bn_fib[i]);
        printf(".\n");
    }

* `bignum.c` 中 `main` 函式對應的呼叫

bn_make_fibonacci(100);  // Change number if necessary

* 複製原有的 `expected.txt` 檔案，利用編輯器刪除原本的費氏數列讀取值，並執行下列指令。

./bn_test >> expected.txt

* 利用diff比較修改後的檔案

$ diff scripts/expected.txt bignum/expected.txt
195,210c195,210
< Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738.
< Reading from /dev/fibonacci at offset 94, returned the sequence 19740274219868223167.
< Reading from /dev/fibonacci at offset 95, returned the sequence 31940434634990099905.
< Reading from /dev/fibonacci at offset 96, returned the sequence 51680708854858323072.
< Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977.
< Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049.
< Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
< Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.
< Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.
< Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
< Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049.
< Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977.
< Reading from /dev/fibonacci at offset 96, returned the sequence 51680708854858323072.
< Reading from /dev/fibonacci at offset 95, returned the sequence 31940434634990099905.
< Reading from /dev/fibonacci at offset 94, returned the sequence 19740274219868223167.
< Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738.
---
> Reading from /dev/fibonacci at offset 93, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 94, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 95, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 96, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 97, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 98, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 99, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 100, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 100, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 99, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 98, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 97, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 96, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 95, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 94, returned the sequence 7540113804746346429.
> Reading from /dev/fibonacci at offset 93, returned the sequence 7540113804746346429.

### :camera_with_flash: 大數型別 - 套用至 `fibdrv.c`

* 修改 `Makefile`，增加目標 `bignum` ，使其可編譯出 `bignum.o`。

BIGNUM_DIR := bignum

bignum: $(BIGNUM_DIR)/bignum.c
    $(CC) -c -I$(BIGNUM_DIR) -o $(BIGNUM_DIR)/bignum.o $(BIGNUM_DIR)/bignum.c

* 修改目標 `all` ，令編譯 `fibdrv.ko` 時加入 `bignum.o`。

all: $(GIT_HOOKS) bignum client
    $(MAKE) -I$(PWD)/$(BIGNUM_DIR) -C $(KDIR) M=$(PWD) modules

* 增加 `fibdrv.c` 中，以大數型別實現費氏數列計算的函式, 並更換回傳的函式。
* 執行編譯後，我們發現 bignum 中的設計是以

## :three: 高效率的費氏數列計算函式實作

### :camera_with_flash: `Fast Doubling` 方法概述
* 基於線性代數的矩陣計算，我們可以得到下列費氏數列關係式:
* $F(2k) = F(k)\cdot[2\cdot F(k + 1) - F(k) ]$
* $F(2k + 1) = F(k+1)^2 + F(k)^2$
* 透過遞迴關係的計算，我們可以較原始的 `Dynamic Programming` 減少約一半的計算量。
* 在 `Fast Doubing` 實作中會經常使用 `clz` 與 `ctz` 指令，其作用範例如下:
> Input: `0x38` -> `2'b00111000`
> Output for `clz` -> 2 (count of leading zero is 2)
> Output for `ctz` -> 3 (count of tailing zero is 3)
> Ref: https://en.wikipedia.org/wiki/Find_first_set
> [color=Green]
* 引用[你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/@sysprog/c-recursion)中， [Fast doubling](https://hackmd.io/@sysprog/c-recursion#Fast-doubling) 的程式碼，並更改對應的回傳型別。

### :camera_with_flash: 以 `unsigned long long` 型別實現 `Fast Doubling`

static unsigned long long fib_sequence_fd_ull(long long k)
{
    unsigned long long t0 = 1, t1 = 1;  // For F[n], F[n+1]
    unsigned long long t3 = 1, t4 = 0;  // For F[2n], F[2n+1]

    int i = 1;

    if (k <= 0)
        return 0;

    while (i < k) {
        if ((i << 1) <= k) {
            t4 = t1 * t1 + t0 * t0;
            t3 = t0 * (2 * t1 - t0);
            t0 = t3;
            t1 = t4;
            i = i << 1;
        } else {
            t0 = t3;
            t3 = t4;
            t4 = t0 + t4;
            i++;
        }
    }
    return t3;
}

* 簡易的輸出測試

$ make unload
$ make load
$ 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 3, returned the sequence 2.
Reading from /dev/fibonacci at offset 4, returned the sequence 3.
Reading from /dev/fibonacci at offset 5, returned the sequence 5.
Reading from /dev/fibonacci at offset 6, returned the sequence 8.
Reading from /dev/fibonacci at offset 7, returned the sequence 13.
Reading from /dev/fibonacci at offset 8, returned the sequence 21.
Reading from /dev/fibonacci at offset 9, returned the sequence 34.
Reading from /dev/fibonacci at offset 10, returned the sequence 55.
Reading from /dev/fibonacci at offset 11, returned the sequence 89.
Reading from /dev/fibonacci at offset 12, returned the sequence 144.
Reading from /dev/fibonacci at offset 13, returned the sequence 233.
Reading from /dev/fibonacci at offset 14, returned the sequence 377.
Reading from /dev/fibonacci at offset 15, returned the sequence 610.
Reading from /dev/fibonacci at offset 16, returned the sequence 987.
Reading from /dev/fibonacci at offset 17, returned the sequence 1597.
...

### :camera_with_flash: 以 `bignum_t` 型別實現 `Fast Doubling`

:::warning
TODO: 嘗試分析 [bignum](https://github.com/sysprog21/bignum) 裡頭的實作技巧，這是我目前開發出最快的 Fibonacci (任意位數) 實作，當然，仍有進步空間。
:notes: jserv
:::

## :four: 時間效能評測與其機制設計

### :straight_ruler: 評測機制設計
* 因為 `fibdrv.ko` 運作在 `核心空間 (Kernel Space)`，因此我們應以[核心空間的時間測量法](https://hackmd.io/@sysprog/linux2020-fibdrv#%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)測量其運作時間。
* 在 `fibdrv.c` 增加函式 `fib_time_measure_agent` ，並透過兩個型別為 `ktime_t`變數 `kt_dp` 與 `kt_fd` 分別儲存 `Dynamic Progrmming` 與 `Fast doubling` 兩種方法的測量結果。實作程式碼如下：

static ktime_t kt_dp, kt_fd;
static bool ktime_return_fd;

static unsigned long long fib_time_measure_agent(long long k)
{
    unsigned long long result;

    kt_dp = ktime_get();
    // Calculate via Dynamic Programming
    fib_sequence_dp_ull(k);
    kt_dp = ktime_sub(ktime_get(), kt_dp);

    // Calculate via Fast Doubling
    kt_fd = ktime_get();
    result = fib_sequence_fd_ull(k);
    kt_fd = ktime_sub(ktime_get(), kt_fd);

    // Set to return dynamic programming`s time
    ktime_return_fd = false;

    return result;
}

* 在讀取執行時間時，我們透過設定變數 `ktime_return_fd` 讓 `write` 回傳兩種實現的讀取時間。
* 透過變數值的設定操作， `User Space` 的程式第一次呼叫 `write` 系統呼叫時，會回傳 `Dynamic Programming` 方法的執行時間，而第二次呼叫時則回傳 `Fast Doubling` 的執行時間。
* 程式碼實作如下：

static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{

    if (ktime_return_fd) {

        ktime_return_fd = false;
        return ktime_to_ns(kt_fd);
    }
    else {

        ktime_return_fd = true;
        return ktime_to_ns(kt_dp);
    }
}

> 在實作透過 `write()` 系統呼叫讀取執行時間時，原本的計畫是透過傳輸字串 `dp` 與 `fd` 兩種方式回傳 `Dynamic Progrmming` 與 `Fast doubling` 兩種方法的測量結果；但是在字串處理上似乎是沒辦法使用指標直接處理字串讀取，透過 `strace` 看起來是存取位址發生錯誤使程式無法執行，推論造成錯誤的原因是 `Kernel Space` 的程式存取 `User Space` 的記憶體位址。
>
>補充：看過老師在 2020/03/23 的 Code Review 後，有看到其他同學使用 `copy_from_user` 函式將欲傳入的字串複製到 `Kernel Space` ，以解決位址存取權限的問題。
>
> [name=Steven HH Chen][time=Mon, Mar 23, 2020 11:01 PM][color=Yellow]

* 透過測試程式 `fib_tperf` 操作 `fibdrv` 核心模組，以取得執行的數據，並列印為指定格式。程式碼實作如下：

#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <unistd.h>
#include <inttypes.h>
#include <stdint.h>

#include "bignum/bignum.h"

#define FIB_DEV "/dev/fibonacci"

int main()
{
    unsigned long long sz;

    char buf[1];
    char wr_dp[] = "d", wr_fd[] = "f";
    int offset = 93;

    int fd = open(FIB_DEV, O_RDWR);
    if (fd < 0) {
        perror("Failed to open character device");
        exit(1);
    }

    for (int i = 0; i <= offset; i++) {
        unsigned long long sz;

        lseek(fd, i, SEEK_SET);
        sz = read(fd, buf, 1);
        printf("%d, %llu", i, sz);

        sz = write(fd, wr_dp, strlen(wr_dp));
        printf(", %llu", sz);

        sz = write(fd, wr_fd, strlen(wr_fd));
        printf(", %llu\n", sz);
    }

    return 0;
}

* 在 `Makefile` 中新增目標 `timeperf` ，讓 `shell` 自動完成執行時間走勢圖的輸出。實作如下：

all: $(GIT_HOOKS) bignum client fib_tperf modules

clean:
	$(MAKE) -C $(KDIR) M=$(PWD) clean
	$(RM) client out fib_tperf ./bignum/bignum.o

reload: unload load

fib_tperf: fib_timeperf.c
	$(CC) -o $@ $^

timeperf: reload fib_tperf
	sudo ./fib_tperf > fib_timeperf.csv
	gnuplot scripts/fibperf.gp
	eog fib_timeperf.png

* 透過[我的 gnuplot 腳本](https://github.com/StevenChen8759/fibdrv/blob/master/scripts/fibperf.gp) 繪圖，結果測試如下：(註: 此為繪圖指令與 `make` 指令測試，非正確的效能數值)
* 在 `Windows 8.1` 上運作的 `ubuntu` 虛擬機上將程式功能完成後，需透過 `git` 版控系統與其指令，將實作的程式碼功能移植至安裝於實體機器的 `ubuntu` 上，**以測量到準確的運作時間**。

### :straight_ruler: 評測以 `unsigned long long` 型別實現兩種費氏數列計算方法的效能

* 在移植到Ubuntu原生主機上之後，透過 `make timeperf` 指令繪製走勢圖，輸出如下：

* 多跑幾次 `timeperf` 之後，會遇到如下的有趣結果：

* 參考[作業二說明](https://hackmd.io/@sysprog/linux2020-fibdrv)中[排除干擾效能分析的因素](https://hackmd.io/@sysprog/linux2020-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)一節，設定指定的系統參數，並重新測量，結果如下所示：
* 可發現經[排除干擾效能分析的因素](https://hackmd.io/@sysprog/linux2020-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)後，我們得到的測量時間呈現些微的上升，這是因為關閉了系統的加速機制所致。

### :straight_ruler: 評測以 `bignum` 型別實現兩種費氏數列計算方法的效能

*　在修改過 `fib_timeperf.c` 之後，我們同樣透過 `make timeperf` 指令繪製走勢圖，輸出如下：
*　在[排除干擾效能分析的因素](https://hackmd.io/@sysprog/linux2020-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)後重新測量，結果如下所示：

### :straight_ruler: 混合評測費氏數列計算的效能

* 以下評測包含四種方法的走勢，分述如下：
* 使用型別：`ull` ，方法：`Dynamic Programming`
* 使用型別：`ull` ，方法：`Fast Doubling`
* 使用型別：`bignum` ，方法：`Dynamic Programming`
* 使用型別：`bignum` ，方法：`Fast Doubling`
* 使用預設環境的測量：
* [排除干擾效能分析的因素](https://hackmd.io/@sysprog/linux2020-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)後的測量：

## :five: 問題與討論

### :bulb: `PRIu64` 的使用

### :bulb: `sysprog21/bignum` 的實作分析與改善

### :bulb: 組合語言指令 `clz` 與 `ctz` 如何加速費氏數列計算

### :bulb: 減少費氏數列計算中乘法所佔的成本

### :bulb: 指令 `lsmod` 中 `used by` 欄位的實作

### :bulb: `mutex` 在模組 `fibdrv` 中的作用

## :six: 結論與心得
* 在最初的實作中，我在沒有考慮到費氏數列的增長率為 $O(2^n)$ 的情況下，就很蠻幹地將 `long long` 型別改以 `unsigned long long` 實現，造成浪費許多時間思考如何修改程式，卻仍無法解決問題的窘境 (可形容為 `jserv` 老師經常提到的**舉燭**)，因此在任何程式功能實作之前，我們都應多花一點時間規劃，並思考功能的實現是否能滿足需求。
* 在 `Kernel Space` 與 `User Space` 上撰寫程式，其概念上有很大的差異，在撰寫程式上須與作業系統的概念結合，如此才能寫出功能正確、效能較佳的程式。

## :seven: 同場加映：在 `Raspberry Pi 3 Model B` 上測量 `fibdrv` 的效能。

### :computer: 硬體規格與系統配置

### :straight_ruler: 在樹莓派上評測費氏數列計算的效能