2022q1 Homework3 (fibdrv)

contributed by < SmallHanley >

作業說明
GitHub

開發環境

$ cat /proc/version
Linux version 5.13.0-37-generic (buildd@lcy02-amd64-111)
(gcc (Ubuntu 9.4.0-1ubuntu1~20.04) 9.4.0, GNU ld (GNU Binutils for Ubuntu) 2.34)
#42~20.04.1-Ubuntu SMP Tue Mar 15 15:44:28 UTC 2022

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping:                        10
CPU MHz:                         1800.000
CPU max MHz:                     3400.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3600.00
Virtualisation:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

fibdrv

file_operations include/linux/fs.h

TODO

Linux 效能分析的提示

首先，根據不同的算法，畫出折線圖，橫軸是費氏數列第 n 項，縱軸是計算該項所花費的時間：

gnuplot script

set title "Time cost"
set xlabel "n th sequence of Fibonacci number"
set ylabel "time cost (ns)"
set terminal png font " Times_New_Roman,12 "
set output "time.png"
set xrange [0:100]
set xtics 0, 20, 100
set key left

plot \
"time" using 1:2 with linespoints linewidth 2 title "original", \
"time" using 1:3 with linespoints linewidth 2 title "fast-exp", \
"time" using 1:4 with linespoints linewidth 2 title "fast-doubling", \

執行多次運算取平均

為了減少誤差，我嘗試將執行 10 次的結果取平均，再重新繪製，執行方式：

$ make plot

以特定的 CPU 執行程式

一個在 userspace 的程式，我們可以使用 taskset 命令，將指定的行程透過 PID 和 cpumask 固定在指定的 CPU 上執行，又或是將給定的新的程式或命令固定在指定的 CPU 上執行，用法如下：

taskset [options] [mask | cpu-list] [pid|cmd [args...]]

至於 kernel module，在閱讀 Kernel_modules tutorial 後，發現 kernel module 可以使用 current 變數 (需要 include linux/sched.h)，該變數代表的是一個指標指向該行程的 struct task_struct，這意味著 kernel module 是一個獨立且可以被排程的一個單位 (task)，並用有自己的 PID，我們可以使用 taskset 根據 PID 固定在指定的 CPU 上執行。

不過我們又面臨一個問題，我們需要程式執行以後才會知道行程的 PID，因此我嘗試使用 linux/sched 的 sched_setaffinity()，不過遇到以下問題，目前還沒解決：

ERROR: modpost: "sched_setaffinity" [.../fibdrv/fibdrv.ko] undefined!

後來改成在 client.c 使用系統呼叫 sched_setaffinity(2)，先將 fibdv 的 PID 透過 write 傳至 client.c，再呼叫 sched_setaffinity() 將行程固定在 CPU 0。

限定 CPU 給特定的程式使用

taskset 可指定行程所使用的 CPU 核心，但不代表其他的行程不會使用這些被指定的 CPU 核心，如果你不想讓其他的行程干擾你要執行的程式，讓指定的核心只能被自己設定的行程使用，可以使用 isolcpus 這個 Linux 核心起始參數，這個參數可以讓特定的 CPU 核心在開機時就被保留下來。

我在開機時使用 boot loader 所提供的自訂開機參數功能，手動加入 isolcpus=cpu_id 參數：

1. 開機時進入 GRUB。
2. 按 e 編輯開機參數。
3. 往下到 linux 開頭這行，加上 isolcpus=0。
4. 按 Ctrl-x 或是 F10 以修改過後的設定開機。

觀察 CPU 0 是否在開機後被保留下來：

$ taskset -cp 1
pid 1's current affinity list: 1-7

$ cat /sys/devices/system/cpu/isolated
0

使用 htop 觀察 CPU 0，不過 CPU 0 的使用率並不是一直維持在 0，推測有其他程式也有使用到 sched_setaffinity()，或是中斷處理 (?)，不過可以大幅減低干擾：

排除干擾效能分析的因素

• 抑制 address space layout randomization (ASLR)

  ​​​​$ sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
  

• 設定 scaling_governor 為 performance。準備以下 shell script，檔名為 performance.sh:

  ​​​​for i in /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
  ​​​​do
  ​​​​    echo performance > ${i}
  ​​​​done
  

  之後再用 $ sudo sh performance.sh 執行

• 針對 Intel 處理器，關閉 turbo mode

  ​​​​$ sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
  

用統計手法去除極端值

引入 bignum

資料結構

• 目前只有使用 unsigned long 陣列，後續可以加入 size 來做優化。
• 後續更新添加 size 來做優化，更該於 commit 61cad9e 。一是降低運算成本，二是方便於乘法引入 ctz 加速手段。
• size 為表示此一數字所需的陣列大小 (即表示此數需要多少個 unsigned long 的空間)， size 為 0 代表數字為 0。

typedef struct {
    unsigned long val[BN_LENGTH];
    unsigned size;
} bn_t;

bn_init()

• 將陣列初始化為 0。
• size 設成 0。

static inline void bn_init(bn_t *a)
{
    memset(a->val, 0, sizeof(a->val));
    a->size = 0;
}

bn_set_with_pos()

• 傳入三個參數，分別為 bn_t 變數的位址、num 和pos。
• 將 pos 作為陣列的 index，賦值成 num。
• 如果此數原本 size 為 1，我們又想要將陣列第 0 位置設成 0，則將 size 歸零。

static inline void bn_set_with_pos(bn_t *a, uint64_t num, unsigned pos)
{
    a->val[pos] = num;
    if (unlikely(!pos && !num && a->size == 1)) {
        a->size = 0;
    } else if (pos + 1 > a->size) {
        a->size = pos + 1;                                                                                                         
    }
}

bn_swap()

• 將給定的兩物件交換。

static inline void bn_swap(bn_t *a, bn_t *b)
{
    bn_t tmp = *a;
    *a = *b;
    *b = tmp;
}

bn_srl()

• 將大數作邏輯右移。
• 考慮到後續大數乘法可能會使用 ctzl 優化，目前實作是使用位移運算子 (<<、>>)，只能處理小於等於 63 的右移，當 n 超過 64 (包含) 是未定義行為。

static void bn_srl(bn_t *a, bn_t *res, unsigned n)
{
    if (!a->size) {
        bn_init(res);
        return;
    }
    if (!n) {
        *res = *a;
        return;
    }
    for (int i = 0; i < a->size - 1; i++) {
        res->val[i] = a->val[i] >> n | a->val[i + 1] << (64 - n);
    }
    res->val[a->size - 1] = a->val[a->size - 1] >> n;
    res->size = (res->val[a->size - 1]) ? a->size : a->size - 1;
}

bn_sll()

• 將大數作邏輯左移。
• 同理，目前只能處理小於等於 63 的左移。
• 要注意的是，此處有關 size 的實作還是有瑕疵，如果左移超過儲存資料的上限，得到的 size 很可能是錯的。

static void bn_sll(bn_t *a, bn_t *res, unsigned n)
{
    if (!a->size) {
        bn_init(res);
        return;
    }
    if (!n) {
        *res = *a;
        return;
    }
    unsigned sz = (a->size > BN_LENGTH - 1) ? BN_LENGTH - 1 : a->size;
    for (int i = sz; i > 0; i--) {
        res->val[i] = a->val[i] << n | a->val[i - 1] >> (64 - n);
    }                                                                                                                              
    res->val[0] = a->val[0] << n;
    res->size = (res->val[sz]) ? sz + 1 : sz;
}

bn_add()

• 將 a 和 b 相加的結果存至 res。
• 這裡使用 GNU Built-in Functions to Perform Arithmetic with Overflow Checking 的 __builtin_uaddl_overflow() 來檢查是否產生溢位，從最低位加到最高位，並將 carry 加至高一位。
• 嘗試改寫，使得大數加法成功在編譯器優化開啟時生成出 x86 指令集 的 ADC 或是 ADCX，不過沒有成功。

static void bn_add(bn_t *a, bn_t *b, bn_t *res)
{
    unsigned c = 0;
    unsigned sz = (a->size > b->size) ? a->size : b->size;
    for (int i = 0; i < sz; i++) {
        unsigned c1 =
            __builtin_uaddl_overflow(a->val[i], b->val[i], &res->val[i]);
        unsigned c2 = __builtin_uaddl_overflow(res->val[i], c, &res->val[i]);
        c = c1 | c2;
    }
    if (sz < BN_LENGTH) {
        res->val[sz] = c;
        res->size = (res->val[sz]) ? sz + 1 : sz;
    } else {
        res->size = BN_LENGTH;
    }
}

bn_sub()

• 將 a 和 b 相減的結果存至 res。

static void bn_sub(bn_t *a, bn_t *b, bn_t *res)
{
    unsigned c = 0;
    for (int i = 0; i < a->size; i++) {
        unsigned c1 =
            __builtin_usubl_overflow(a->val[i], b->val[i], &res->val[i]);
        unsigned c2 = __builtin_usubl_overflow(res->val[i], c, &res->val[i]);
        c = c1 | c2;
    }
    for (int i = a->size - 1; i >= 0; i--) {
        if (res->val[i]) {
            res->size = i + 1;
            return;
        }
    }
    res->size = 0;
}

bn_mul()

• 將 a 和 b 相乘的結果存至 res。
• 目前採用 O(n) 的乘法，使用位移運算子和大數加法實作，後續可以增加 ctzl 或是不同演算法優化。

static void bn_mul(bn_t a, bn_t b, bn_t *res)
{
    bn_init(res);
    unsigned sz = b.size;
    for (int i = 0; i < 64 * sz; i++) {
        if (b.val[0] & 1) {
            bn_add(res, &a, res);
        }
        bn_sll(&a, &a, 1);
        bn_srl(&b, &b, 1);
    }
}

乘法除了加上 size 來優化，後續也增加 ctzl 的優化。原本的實作方式是模擬計算機組織教科書有關乘法器的實作方式，每次都只位移一個 bit。當除數的 bits 為 set 的數量很少的時候，這種作法的位移運算成本會高很多，於是我使用 ctzl 加速，可以一次位移多個 bits，實作如下：

static void bn_mul(bn_t a, bn_t b, bn_t *res)
{
    bn_init(res);
    while (b.size) {
        if (b.val[0]) {
            unsigned z = __builtin_ctzl(b.val[0]);
            bn_sll(&a, &a, z);
            bn_srl(&b, &b, z);
            bn_add(res, &a, res);
            b.val[0] &= ~(1ul);
        } else {
            bn_sll(&a, &a, 63);
            bn_srl(&b, &b, 63);
        }
    }
}

對應的實驗和效能分析可以參考下面圖表。

bn2string()

static char *bn2string(bn_t *a)
{
    char str[64 * BN_LENGTH / 3 + 2];

    memset(str, '0', sizeof(str) - 1);
    str[sizeof(str) - 1] = '\0';

    unsigned sz = a.size;
    for (int i = 0; i < 64 * sz; i++) {
        unsigned carry = a.val[sz - 1] >> 63;
        for (int j = sizeof(str) - 2; j >= 0; j--) {
            str[j] += str[j] - '0' + carry;
            carry = (str[j] > '9');
            if (carry)
                str[j] -= 10;
        }
        bn_sll(&a, &a, 1);
    }

    // search for numbers
    int i = 0;
    while (i < sizeof(str) - 2 && str[i] == '0')
        i++;

    // passing string back
    char *p = kmalloc(sizeof(str) - i, GFP_KERNEL);
    memcpy(p, str + i, sizeof(str) - i); 

    return p;
}

效能分析

引入 bignum 後，根據 Linux 效能分析的提示，繪製出不同實作方式對於不同輸入參數所花的時間比較：

將輸入參數擴增至 1000，發現 fast-doubling 和 exponentiating by squaring 與原本

$O(n)$ 時間複雜度相比，花費時間高很多，可見目前採用的乘法實作方式還有很大改進空間：

後續改進加入 size 和 ctzl 優化，前者優化各種運算的次數 (包含加法、減法、位移運算)，後者大幅減少位移運算次數，實驗結果如下：

發現 exponentiating by squaring 的乘法運算量還是過大，fast-doubling 和 sequence 較為接近，不過在前 1000 項還是 sequence 的方式花費時間最少 (後續實驗發現輸入參數數量級要到

${10}^5$，fast-doubling 才會追過 sequence)。

下圖以 fast-doubling 的實作方式，分析加上 size (不含 ctzl) 前後花費時間的比較：

在大數乘法的實作中加入 ctzl 優化，可以大幅減少位移運算的次數，下圖是實驗有無 ctzl 的比較，發現採用 ctzl 的程式碼執行時間大幅縮短：

進一步觀察整體程式 (fast-doubling 從 0 執行到 1000) 呼叫大數運算的次數，確實大幅減少 bn_sll() 、bn_srl() 的呼叫次數：

no-ctz	add	sub	sll	srl
times	541118	8987	2316635	2307648

with-ctz	add	sub	sll	srl
times	541118	8987	562141	553154

Reference

矩陣快速冪
Fast-doubling
The high-resolution timer API
Message logging with printk
oscarshiang 共筆
Other Built-in Functions Provided by GCC
Kernel modules
rt:labs Real-time properties of Linux
Built-in Functions to Perform Arithmetic with Overflow Checking