2020q1 Homework2 (fibdrv)

contributed by < haogroot >

tags: linux2020

Kernel version: 5.3.0-40-generic
OS: Ubuntu 19.10
CPU model: Intel® Core™ i7-8565U CPU @ 1.80GHz

自我檢查清單

• 研讀上述 Linux 效能分析的提示 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
  $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
• 研讀上述費氏數列相關材料 (包含論文)，摘錄關鍵手法，並思考 clz / ctz 一類的指令對 Fibonacci 數運算的幫助。請列出關鍵程式碼並解說
• 複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本;
• lsmod 的輸出結果有一欄名為 Used by，這是 "each module's use count and a list of referring modules"，但如何實作出來呢？模組間的相依性和實際使用次數 (reference counting) 在 Linux 核心如何追蹤呢？
• 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題

初步效能量測

在 kernel module 中透過 ktime_get() 來量測計算所需時間，在 user space 透過 clock_gettime()來測量。

由於 read 預設是回傳 ssize_t，只有 8 bytes，我們無法回傳 fib_sequence() 執行時間與大數計算的結果，改為將結果寫入 fib_read() 的參數 char *buf，在 kernel space 宣告一個陣列 kbuffer 來儲存，將 ktime 所計算的時間寫到前八個 bytes，大數計算的結果寫到接下來的位置，最後透過 copy_to_user()將 kernel space 的資料傳到 user space。

char kbuffer[168];
static ssize_t fib_read(char *buf)
{
    // Write Fibonacci result to kbuffer...
    ssize_t retval = fib_sequence(*offset, kbuffer);
    /* Write execution time to kbuffer... */
    
    // Copy data from kernel to user space.
    copy_to_user(buf, kbuffer, retval + 9);
}

用字要精準，到底是

$n\ge 93$ 還是

$n>93$，另外 overflow 的空間範圍要說清楚
jserv

當 fib(n) 中的 n ≥ 93 會發生 overflow ( fib(93)=12,200,160,415,121,876,738,但 unsigned long long 可表達最大為 18,446,744,073,709,551,615)，先限制測試到 92。測時結果如下圖所示，隨著測試數字愈大，在 kernel space 耗費時間也跟著增加，從 user space 跟 kernel space 之間的差距為 200 ms，可推估在 kernel 計算完傳輸到 user space 耗費約 200 ms。

費式數列實作演算法

在你所不知道的C語言：遞迴呼運算叫篇 探討過 Fibonacci sequence 不同實作演算法的複雜度，如下表所示：

方法	複雜度
Recursive	$O(2^n)$
Iterative	$O(n)$
Tail Recursion	$O(n)$
Q-Matrix	$O(logn)$
Fast Doubling	$O(logn)$

大數運算 - Iterative

當 fib(n) 中的 n 大於 93 會發生 overflow，透過大數運算來解決這個問題。

參考 tiny-bignum-c 來實作大數運算，透過 struct bn 來存放大數運算的結果，每一個 element 大小為 32 bits，最多可以用來代表 (0xFFFFFFFF)。

#define DTYPE unsigned int
struct bn {
    DTYPE array[10]
}

排除干擾效能分析的因素

1. 限定 CPU 給特定程式使用
   增加 BootOptions isolcpus=1，reboot 後透過 cat /proc/cmdline 來驗證。
2. 關掉 CPU Turbo mode
   $ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
3. 關掉 ASLR
   $ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
4. 設定 scaling_governor 為 performance。
   $ sudo sh -c "echo performance > /sys/devices/system/cpu/cpu1/cpufreq/scaling_governor"

測量結果

$ make load
$ sudo taskset 0x2 ./client
$ make unload
$ make plot

透過大數算法來解決 overflow 問題，並採取 iterative 方式，結果如下圖。 Fib(0) 和 Fib(1) 會直接回傳結果，所以執行時間較短，其他測試隨著 n 的增加運算所需時間都有顯著的提升，符合

$O(n)$ 的線性趨勢，不過雖然我們已經排除干擾效能分析的因素，但結果仍舊有顯著的抖動。

TODO:

1. 檢查 taskset 設定;
2. 另一個命令 chrt 可搭配使用，見 Chapter 6. Affinity
   
3. 透過統計學手法，取 95% 信賴區間

jserv

大數運算 - fast doubling

fast doubling 需要實作大數運算的減法與乘法，乘法實作上較複雜，透過二層迴圈來走訪每個位數，將各位數做相乘，再將相乘結果向左位移到所屬的位數，依序計算並相加所有結果。

void bignum_mul(struct bn *a, struct bn *b, struct bn *output)
{
    struct bn row;
    struct bn tmp;

    for (i = 0; i < ARR_SIZE; i++) {
        
        for (j = 0; j < ARR_SIZE; j++) {
            if (i + j < ARR_SIZE) {
                
                BIGGER_DTYPE mul_result = (BIGGER_DTYPE) a->array[i] *
                                          (BIGGER_DTYPE) b->array[j];
                bignum_from_int(&tmp, mul_result);

                _lshift_word(&tmp, i + j);
                bignum_add(&tmp, &row, &row);
            }
        }
        bignum_add(output, &row, output);
    }
}

測量結果

如下圖，fast doubling 的運算明顯比 Iterative 法更加耗時許多，並沒有如所預期的可以達到

$O(logn)$ 的時間複雜度。

嘗試優化程式碼，可以觀察在做乘法時，雙重二層迴圈內顯然有很多次都是不必要的執行，如果執行乘法時其中一方為 0，就不必執行乘法運算。

注意用語：「雙重」和「二層」意義不同，前者是隱含有對稱的兩件人事物，後者則著重在階層 (hierarchy)，本例中，應採後者。

jserv

void bignum_mul(struct bn *a, struct bn *b, struct bn *output)
{
    struct bn row;
    struct bn tmp;

    for (i = 0; i < ARR_SIZE; i++) {  
        if (a->array[i] != 0) {
            for (j = 0; j < ARR_SIZE; j++) {
                if (i+j < ARR_SIZE && b->array[b] !=0) {
                    /* multiplication... */
                }
            }
        }
    }
}

用來存放運算結果的 array 減小到只包含3個 element，這樣的大小就足夠存放。

#define DTYPE unsigned int
struct bn {
    DTYPE array[3]
}

再次測量結果可以發現執行時間大幅減小。

優化

方法 1: 根據 你所不知道的C語言：遞迴呼運算叫篇 的 Fast doubling 演算法 psuedo code 來實作。

int fib(int n) {
    if (n == 0) return 0;
    int t0 = 1; // F(n)
    int t1 = 1; // F(n + 1)
    int t3 = 1; // F(2n)
    int t4; // F(2n+1)
    int i = 1;
    while (i < n) {
        if ((i << 1) <= n) {
            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;
}

方法 2: 參考來自 Calculating Fibonacci Numbers by Fast Doubling 中的手法實作，如同以下的 pseudo code：

uint64_t fib(unsigned int n)
{
    // The position of the highest bit of n.
    // So we need to loop `h` times to get the answer.
    // Example: n = (Dec)50 = (Bin)00110010, then h = 6.
    //                               ^ 6th bit from right side
    unsigned int h = 0;
    for (unsigned int i = n ; i ; ++h, i >>= 1);

    uint64_t a = 0; // F(0) = 0
    uint64_t b = 1; // F(1) = 1
    for (int j = h - 1 ; j >= 0 ; --j) {
        // n_j = floor(n / 2^j) = n >> j, k = floor(n_j / 2), (n_j = n when j = 0)
        // then a = F(k), b = F(k+1) now.
        uint64_t c = a * (2 * b - a); // F(2k) = F(k) * [ 2 * F(k+1) – F(k) ]
        uint64_t d = a * a + b * b;   // F(2k+1) = F(k)^2 + F(k+1)^2

        if ((n >> j) & 1) { // n_j is odd: k = (n_j-1)/2 => n_j = 2k + 1
            a = d;            //   F(n_j) = F(2k+1)
            b = c + d;        //   F(n_j + 1) = F(2k + 2) = F(2k) + F(2k+1)
        } else {            // n_j is even: k = n_j/2 => n_j = 2k
            a = c;            //   F(n_j) = F(2k)
            b = d;            //   F(n_j + 1) = F(2k + 1)
        }
    }

    return a;
}

使用一致的程式碼縮排方式: 4 個空白

jserv

分析兩組 pseudo code，執行 Fast Doubling 的次數雖然相同，但方法二在執行大數加法運算的次數則減少許多。

以 Fib(100) 為例，
方法一執行 6 次 fast doubling 的運算 (變數 i 從 1 到 64 以 2 的倍數增加共執行 6 次)，接著執行 35 次的大數加法（變數 i 從 64 到 99）。
方法二同樣執行 6 次 fast doubling 的運算，但僅執行 3 次的大數加法 （(n >> j) & 1為 true 時會執行）。

方法 3: 將方法2搭配 clz

方法 2 中其實我們就已經利用 for 迴圈來計算從 MSB 算起有多少開頭 0 位元，但透過 gcc 提供的 built-in function clz 試圖加速。

unsigned int h = 32  - __builtin_clz(k);

測量結果如下圖，不過發現測試多次後，抖動相當明顯，

處理測量結果抖動

根據老師的建議，方向為

1. 檢查 taskset 設定
2. 搭配命令 chrt 使用
3. 透過統計學方法取 95% 信賴區間

檢查 taskset 設定

在上方排除效能干擾的因素段落中確實執行，且結果均有成功寫入，透過 Ubuntu 內建的 System Monitor 觀察，CPU1 確實被保留住。

使用命令 chrt

命令 chrt 可以設定 process 的 real-time scheduling attributes，有以下 attributes 可以設定

1. SCHED_OTHER : 這是一般 Linux 預設的排程方法，並不會對 process 做任何特殊處理。
2. SCHED_FIFO :使用 First-in-first-out scheduling algorithm。
3. SCHED_RR : 使用 round-robin scheduling algorithm。
4. SCHED_BATCH :這是 Linux 獨有的（since linux 2.6.23），只有在沒有任何 process 想要使用 CPU 時，他才能夠執行，被設定成 SCHED_BATCH 的 process 比 SCHED_OTHER 還低。
5. SCHED_IDLE : 通常使用在低優先級且在背景執行的 process。

在此案例中，我們可將 scheduling policy 設定為 FIFO，任務的即時排程優先權改為 90 (不能設定為 99，否則系統很可能無法正確運作)，並且加大測試次數，這樣就可確保測試時間，被打斷的機會大幅降低，從而排除干擾。當然，還是需要將 outlier 去除，利用統計方法。

jserv

這裡我們使用 SCHED_FIFO ，根據老師建議給予優先權 90。

$ sudo taskset -c 1 chrt -f 90 ./client

這邊我有一個疑惑，其實從量測效能圖中，可以看到從 kernel space 所測得的時間就已經有明顯抖動，代表是否 kernel module 執行過程中發生被打斷的現象，但是我們使用 taskset 指令都是在確保 user space 的 process 不要被搶佔，這樣的動作是否對排除量測干擾並沒有幫助？是否能夠對 kernel module 設定較高的優先權來解決？ 或是對 kernel module 設定 Processor affinity 來排除干擾？Yu-Hao(Howard) Hsu

因為你使用 ktime 測量時間，在 Linux 核心尚有其他方法。設計實驗需要逐步排除問題，不用急著一次套用一堆方法。
注意共筆書寫，中英文間用一個半形空白字元區隔

jserv

Outlier 離群值處理

若是我們測量出來的數據近似於常態分佈的機率分佈，將會有 95% 的數值分佈在距離平均值 2 個標準差以內的範圍。透過執行 50 次的 user space program，將結果以不同標準差來去除離群值。

在 Makefile 裡重複執行測試程式50次並將結果存成不同的檔案。預期希望透過do while loop 來控制測試執行次數。

寫 Makefile 過程中，學習到以下 3 點，紀錄下來供未來參考：

1. 在 GNU Make 文件 5.3 Recipe Execution 中提到

When it is time to execute recipes to update a target, they are executed by invoking a new sub-shell for each line of the recipe, … Please note: this implies that setting shell variables and invoking shell commands such as cd that set a context local to each process will not affect the following lines in the recipe.

因此我們必須將整個 do while loop 寫成單行指令，以便達到預期成效，我們以分號（;）與換行符行 （\）來將所有指令串起。在 GNU Make 5.3.1 文件中也有提到你可以透過 .ONESHELL 來達成一樣的效果。

2. 在 GNU Make 文件 5.3.2 Choosing the shell 中提到

The program used as the shell is taken from the variable SHELL. If this variable is not set in your makefile, the program /bin/sh is used as the shell.

若是你沒有特別設定 variable SHELL，預設都是以 /bin/sh 來執行。而不會是 bash ，不能使用 bash 語法混雜其中。

3. 在 GNU Make 文件 5.1.2 Using Variables in Recipes 中提到

Variable and function references in recipes have identical syntax and semantics to references elsewhere in the makefile. They also have the same quoting rules: if you want a dollar sign to appear in your recipe, you must double it (‘$$’). For shells like the default shell, that use dollar signs to introduce variables, it’s important to keep clear in your mind whether the variable you want to reference is a make variable (use a single dollar sign) or a shell variable (use two dollar signs).

在 Recipe 中，如果使用的是 make variable，必須使用單一個 $，若是使用 shell variable，須使用兩個 $$。以下例子就是正確的使用變數的方式。

LIST = one two three
all:
        for i in $(LIST); do \
            echo $$i; \
        done

以下是在 makefile 中撰寫名為 profile 的 target，會執行程式 client 共 50 次並將依序存為檔案。

profile: all
	-rm -rf result/
	mkdir -p result
	number=1 ; while [ $$number -le 50 ] ; do \
		$(MAKE) unload ; \
		$(MAKE) load ; \
		REPORT="result/test_$$number.txt" ; \
		sudo taskset -c 1 chrt -f 90 ./client $$REPORT >/dev/null 2>&1 ; \
		$(MAKE) unload ; \
		number=`expr $$number + 1` ; \
	done

針對 kernel space 的執行時間進行觀察，以 python script 來分別以 68-95-99.7 法則來去除離群值，並將標準差範圍內的資料取平均，畫出以下圖表。

原始全部資料與以 68 法則去除離群值後的資料來對比

原始全部資料與以 95 法則去除離群值後的資料來對比

原始全部資料與以 99.7 法則去除離群值後的資料來對比

我的解讀是是 99.7 法則來去除離群值能夠將大部份 Fib(n) 的測量結果降低，會是比較符合我們預期的模型。但這部份該如何正確分析，還請老師給予指導。

至此，你不難發現，面對 GNU/Linux 和現代的電腦硬體，即便程式碼都是你自己撰寫，其行為卻無法充分掌握，你總是只能用較為迂迴的方式來分析，這也是我們為何要學習 perf, gdb, valgrind 等工具。在上述統計的實驗中，僅能適度剔除 outlier，不過資料本身的特性更為關鍵。
我們還需要排除更多干擾因素，諸如:

1. cache 的影響: 為何程式在 n 很小的時候，執行時間偏長？見討論 What does it mean by cold cache and warm cache concept?
   • 後續尚有 從 CPU cache coherence 談 Linux spinlock 可擴展能力議題 這類討論;
2. 電腦硬體實際上是 SMP，但我們做實驗的過程並未充分考量 SMP IRQ affinity 和 NUMA 一類的影響 (顯然我沒辦法全部提過後，才要求學員寫簡單的程式，於是改為「做中學」的手段);
3. 以前學演算法，通常只看時間複雜度，但並未深究經由編譯器產生的機械碼，個別指令的 latency，更是從為探討過 microarchitecture 的影響 —— 上述的數據展現讓我們不得不誠實面對自己的認知，這也是本作業要引導學員理解的事：你的電腦不是你 (想像中) 的電腦;
   • 針對 Intel 處理器，關閉 turbo mode，對於上述實驗影響就很顯著

jserv

Warm cache v.s. Cold Cache

Cold cache: Cache is empty or has irrelvant data, so it needs to read data from main memory for your program.

Warm cache: Cache has relvant data that your program needs so it only access the cache without access main memory.

SMP IRQ affinity

可以參考 ldotrg 同學的共筆來設定