# 2020q1 Homework2 (fibdrv)
contributed by < `fdgkhdkgh` >

> [作業要求](https://hackmd.io/@sysprog/linux2020-fibdrv)

## 大數運算

在大數運算的使用上，是使用　[tiny-bignum-c](https://github.com/kokke/tiny-bignum-c) ， 簡單來說，就是以一個陣列來儲存大數。並且可以依照自己的需求，看陣列要用多少個元素(並不是動態的)。用動態的應該會更好，可能可以提昇效能(I1)。

## fast doubling

我是照著作業要求的 fast doubing 來寫程式碼，一開始先使用遞迴的方式，來計算出答案。可以嘗試使用 clz 或者不用遞迴來改效能(I2)。

static void big_fib_sequence_v2(long long k)
{
    if(unlikely(k <= 2)) {
        if(k == 0) {
            bignum_from_uint64(&(bigfibo[0]), 0);
            state[k] = 1;
        } else {
            bignum_from_uint64(&bigfibo[k], 1);
            state[k] = 1;
        }
        return;
    } else if(state[k] != 0) {
        return;
    }

    state[k] = 1;

    big_fib_sequence_v2(k / 2 + 1);
    big_fib_sequence_v2(k / 2);

    struct bignum tmp;
    struct bignum tmp2;

    if (k & 1) {
        bignum_mul(&bigfibo[k / 2], &bigfibo[k / 2], &tmp);
        bignum_mul(&bigfibo[k / 2 + 1], &bigfibo[k / 2 + 1], &tmp2);
        bignum_add(&tmp, &tmp2, &bigfibo[k]);
    } else {
        bignum_mul(&bigfibo[k / 2], &bigfibo[k / 2 + 1], &tmp);
        bignum_lshift(&tmp, &tmp, 1);
        bignum_mul(&bigfibo[k / 2], &bigfibo[k / 2], &tmp2);
        bignum_sub(&tmp, &tmp2, &bigfibo[k]);
    }
}

:::danger
上述程式碼的 branch 數量過多，應予以縮減
:notes: jserv
:::

## 實驗成果

實驗的方式是在 kernel driver 裡實做出時間複雜度為 $O(N)$ 的 Fibonacci 數計算，以及 fast doubling。並用 ktime 系列的函式進行時間的計算，計算出運行的時間後，使用 sysfs 回傳給 user space 。原本的 client 沒辦法從 kernel space 拿取太長的輸入，所以改成使用 copy_to_user 將結果以字串的形式回傳到 user space。

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    ktime_t start;
    ktime_t end;

    // set experiment environment
    for (int i = 0; i < 4000; i++) {
        state[i] = 0;
    }

    start = ktime_get();
    big_fib_sequence_v3(*offset);
    end = ktime_get();

    foo = ktime_to_ns(end) - ktime_to_ns(start);
    bignum_to_string(&(bigfibo[*offset]), message, sizeof(message));
    copy_to_user(buf, message, strlen(message));
    return (ssize_t) strlen(message);
}

---

kernel space, 使用 4 個 uint32_t 來表示大數

---

kernel space, 使用 5 個 uint32_t 來表示大數

---

kernel space, 使用 7 個 uint32_t 來表示大數

---

kernel space, 使用 11 個 uint32_t 來表示大數

---

理想上，應該是 fast doubling 的效率會更高。所以我猜是我大數運算的效率太差 (I3) 。並且陣列長度越多，效能越低。所以可以嘗試使用動態陣列，讓所需的陣列長度越短越好 (I1) 。就猜測，大數運算本身運算的方式 (I3) ，以及表示的方式 (I1) 都會影響大數運算的效能。

## 提昇效能

在這裡，我把我所猜測可以增加 fibdrv 效能的因素紀錄下來，並嘗試。每當完成一項，就再進行一次效能測試（ 比較 fast doubing 與普通 $O(N)$ 間的效能差異）。

並且在實驗結果中，也發現幾個離群值，也可以嘗試看看有什麼減少~~雜訊~~離群值的技巧 (I4) 。

:::danger
避免濫用「雜訊」這詞彙，複習統計學用語
:notes: jserv
:::

### Improve 1 (I1) 改成動態陣列表示大數運算

我目前所使用的大數運算的問題是，沒有紀錄目前的數字會使用陣列中的幾個元素，於是在做許多操作的時候都會需要遍尋所有的元素。於是動態陣列（可知道使用了多少個元素），就我的猜測可以加速大數運算的許多操作。[老師的大數運算實作](https://github.com/sysprog21/bignum/blob/master/bn.h)很值得參考。

### Improve 2 (I2) 使用 clz 以及不使用遞迴

我原本是簡單的照著遞迴式子，從數字最大的地方往下遞迴求解 (top down) 。而[老師的例子](https://hackmd.io/@sysprog/linux2020-fibdrv#-%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97)則是從底處開始求值 (bottom up) ， bottom up 的好處是不需要遞迴求解了。可以省下遞迴時的 stack frame 以及執行遞迴的程式時所花費的時間。

首先試著將其改成 bottom up：


:::danger
避免將最初的 Fibonacci 實作稱為 "normal"，不然其他都隱含 "abnormal" 的意思了。可改稱 "naive" (有幼稚、原始和初步等含義，不是 "native")
:notes: jserv
:::

變慢的原因有待查證。

### Improve 3 (I3) 改善大數運算

我原本用的大數運算，在乘法的時候最高複雜度會到 $O(N^3)$，這應該就是效能瓶頸了。簡單的實作可以到 $O(N^2)$，而老師使用的 Karatsuba algorithm 在 k 很大時，會比原本的 $O(N^2)$ 的實作還要快上一些。

$Karatsuba~~algorithm:$

$U=U_1*2^N+U_0$
$V=V_1*2^N+V_0$
且
$Z_2=U_1*V_1$

$Z_1=U_1*V_0+U_0*V_1$
$=\color{red}{(U_1+U_0)*(V_1+V_0)-Z_2-Z_0}$

$Z_0=U_0*V_0$

---

$U*V=(U_1*2^N+U_0)*(V_1*2^N+V_0)$
$=(U_1*2^N)*(V_1*2^N)+U_0*(V_1*2^N)+V_0*(U_1*2^N)+U_0*V_0$ (4 次乘法)
$=U_1*V_1*2^{2N}+(U_0*V_1+U_1*V_0)*2^N+U_0*V_0$
$=Z_2*2^{2N}+Z_1*2^N+Z_0$
$=Z_2*2^{2N}+((U_1+U_0)*(V_1+V_0)-Z_2-Z_0)*2^N+Z_0$
$=Z_2*(2^{2N}-2^N)+((U_1+U_0)*(V_1+V_0))*2^N+Z_0*(1-2^N)$
$=\color{red}{(U_1*V_1)}*\color{green}{(2^{2N}-2^N)}+(\color{red}{(U_1+U_0)*(V_1+V_0))}*\color{green}{2^N}+\color{red}{(U_0*V_0)}*(1-2^N)$ (三次$\color{red}{乘法}$，其餘為$\color{green}{位移}$與$加減)$

---

要注意的是， $(U_1+U_0)*(V_1+V_0)$ 式子裡的加法可能導致位數變多而拖到效能，於是可用另外一種形式：

$Z_1=U_1*V_0+U_0*V_1$
$=\color{red}{(U_1+U_0)*(V_1+V_0)-Z_2-Z_0}$
$=\color{red}{(U_1-U_0)*(V_1-V_0)+Z_2+Z_0}$
證明：
$(U_0-U_1)*(V_1-V_0)+Z_2+Z_0$
$=U_0*V_1\color{red}{-U_0*V_0}\color{green}{-U_1*V_1}+U_1*V_0\color{green}{+U_1*V_1}\color{red}{+U_0*V_0}$
$=U_0*V_1+U_1*V_0$
$=Z_1$

---

$U*V=(U_1*2^N+U_0)*(V_1*2^N+V_0)$
$=(U_1*2^N)*(V_1*2^N)+U_0*(V_1*2^N)+V_0*(U_1*2^N)+U_0*V_0$ (4 次乘法)
$=U_1*V_1*2^{2N}+(U_0*V_1+U_1*V_0)*2^N+U_0*V_0$
$=Z_2*2^{2N}+Z_1*2^N+Z_0$
$=Z_2*2^{2N}+((U_1-U_0)*(V_1-V_0)+Z_2+Z_0)*2^N+Z_0$
$=Z_2*(2^{2N}+2^N)+((U_1-U_0)*(V_1-V_0))*2^N+Z_0*(1+2^N)$
$=\color{red}{(U_1*V_1)}*\color{green}{(2^{2N}+2^N)}+(\color{red}{(U_1-U_0)*(V_1-V_0))}*\color{green}{2^N}+\color{red}{(U_0*V_0)}*(1+2^N)$ (三次$\color{red}{乘法}$，其餘為$\color{green}{位移}$與$加減)$
並且不會在計算 $(U_0-U_1)*(V_1-V_0)$ 時多一位數 => 提升效能
:::danger
用 LaTeX 語法改寫上述
:notes: jserv
:::

但目前還在理解老師的實作，於是我先試著改善原本 [tiny-bignum-c](https://github.com/kokke/tiny-bignum-c) 的實作，更改其乘法的實作方式。

void bignum_mul(struct bn *a, struct bn *b, struct bn *c)
{
    struct bn tmp;
    int i, j;

    bignum_init(c);

    DTYPE upper;
    DTYPE lower;

    for (i = 0; i < BN_ARRAY_SIZE; ++i) {
        for (j = 0; j < BN_ARRAY_SIZE; ++j) {
            if (i + j < BN_ARRAY_SIZE) {
                DTYPE_TMP intermediate =
                    ((DTYPE_TMP) a->array[i] * (DTYPE_TMP) b->array[j]);

                lower = intermediate & MAX_VAL;
                upper = intermediate >> (8 * WORD_SIZE);

                intermediate = (DTYPE_TMP) lower + (DTYPE_TMP) c->array[i+j];

                c->array[i+j] = intermediate & MAX_VAL;
                intermediate  = intermediate >> (8 * WORD_SIZE);

                if (i + j + 1 < BN_ARRAY_SIZE) {
                    intermediate = (DTYPE_TMP) upper + (DTYPE_TMP) c->array[i+j+1] + intermediate;
                    c->array[i+j+1] = intermediate & MAX_VAL;
                    intermediate  = intermediate >> (8 * WORD_SIZE);

                    int k = i + j + 2;
                    while (intermediate > 0 && k < BN_ARRAY_SIZE) {
                        intermediate = (DTYPE_TMP) c->array[k] + intermediate;

                        c->array[k] = intermediate & MAX_VAL;
                        intermediate  = intermediate >> (8 * WORD_SIZE);
                    }
                }
            }
        }
    }
}

---

user space, 使用 11 個 uint32_t 來表示大數

---

效率比之前快上許多， fast doubling 終於快要趕上 normal fibonacci 了！
將這個方法實作在 kernel driver 上：


kernel space, 使用 11 個 uint32_t 來表示大數

---

但比起老師的實作，還是慢上許多 （慢了 20 倍左右），之後希望可以開始進一步研究老師的實作。

### Improve 4 (I4) 減少測試效能時，會遇到的雜訊

依照作業需求提供的提示，將行程固定在某個 CPU 上運行、關閉 ASLR 、設定 scaling_governor 為 performance 、 針對 Intel 處理器，關閉 turbo mode 。並再測試一次效能，可以看到紅線的震盪有變得比較小，但還是會有抖動的情況。

---

kernel space, 使用 11 個 uint32_t 來表示大數

---

### Improve 5 移植老師的 [bignum](https://github.com/sysprog21/bignum) 到 linux kernel driver


teacher's fast doubling : 老師實作的 fast doubling
my original fast doubling : 我最一開始實作的 fast doubling ， 在每一輪會使用 4 次的乘法
my fast doubling : 參考老師實作後，精簡成使用 3 次乘法
naive fibonacci : 使用單純的加法來計算 fibonacci

將數字放大後，可以明顯地看出 fast doubling 的威力，明顯地比 naive fibonacci 快上許多。

### Improve 6 減少雜訊

我使用的作業系統是 ubuntu 18.04
1. 修改 /etc/default/grub

GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=0"

2. sudo update-grup
3. sudo reboot
這時候假如設定有成功的話， ```taskset -cp 1``` 不會顯示 cpu0 為可用
ex : ``` pid 1 目前的近似者清單：1-5 ```
若沒有成功的話，就會顯示所有 cpu 都可用
ex : ``` pid 1 目前的近似者清單：0-5 ```
4. 抑制 address space layout randomization (ASLR)
5. 設定 scaling_governor 為 performance。
6. 針對 Intel 處理器，關閉 turbo mode
7. ```sudo taskset 0x1 executable``` (taskset 的 cpu 從 1 開始)


由圖可看出離群值少了許多。以及每一輪使用 4 次乘法的 ```my original fast doubling``` 比另外兩種 fast doubling (每一輪使用三次乘法)慢上一些。

## TODO

- [x] 撰寫簡單的 linux kernel driver
- [x] 了解 firbdrv 的架構（例如 user space 是怎麼跟 kernel space 進行溝通的）
- [x] 撰寫完整的功能 (fibdrv, python test script)
- [x] 如何對核心模組測試效能（例如核心模式的時間測量）
- [x] 加速 費氏數列的運算 (fast doubling....)
- [x] 精進核心模組的測試方式（減少雜訊）
- [ ] 閱讀 linux device driver ， 弄清楚所有相關名詞與 function
- [ ] 自己實作屬於自己的大數運算
- [ ] 了解[老師的大數運算實作](https://github.com/sysprog21/bignum)，並改進自己的實作方式
- [ ] 使用 clz 加速 fast doubling 的運算

## Reference

[1][Writing a Linux Kernel Module — Part 1: Introduction](http://derekmolloy.ie/writing-a-linux-kernel-module-part-1-introduction/)
寫一個 hello world 的 device driver 。
[2][Writing a Linux Kernel Module — Part 2: A Character Device](http://derekmolloy.ie/writing-a-linux-kernel-module-part-2-a-character-device/)
寫一個 character device ，會從第一個範例延伸至另一個 加了 mutex 的範例。也會教導如何使用 udev rule 來調整存取裝置節點的權限。（雖然範例在我的環境執行時會崩潰）
[3][Introduction to Linux kernel driver programmingdriver programming](https://events19.linuxfoundation.org/wp-content/uploads/2017/12/Introduction-to-Linux-Kernel-Driver-Programming-Michael-Opdenacker-Bootlin-.pdf)
介紹 linux kernel driver ， 以 USB 為例，簡略地走過 linux kernel driver 的程式碼架構
[4][陳鍾誠教授：VFS介紹](http://sp1.wikidot.com/linuxvfs)
[5][Big-Number sysprog21-bignum](https://github.com/sysprog21/bignum)
[6][Big-Number Arbitrary-precision_arithmetic](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic)
[7][Big-Number Small portable multiple-precision unsigned integer arithmetic in C](https://github.com/kokke/tiny-bignum-c)
[8][Sample kobject implementation](https://elixir.bootlin.com/linux/v5.3/source/samples/kobject/kobject-example.c)
[9][快速的乘法](https://pansci.asia/archives/162365)
[10][關閉與開啟 ASLR](https://blog.csdn.net/counsellor/article/details/81543197)

###### tags: `linux2020`