2023q1 Homework3 (fibdrv)

contributed by < paulpeng-popo >

Github: paulpeng-popo

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ 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):                  12
On-line CPU(s) list:     0-11
Thread(s) per core:      2
Core(s) per socket:      6
Socket(s):               1
NUMA node(s):            1
Vendor ID:               GenuineIntel
CPU family:              6
Model:                   158
Model name:              Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Stepping:                10
CPU max MHz:             4600.0000
CPU min MHz:             800.0000
BogoMIPS:                6399.96
Virtualization:          VT-x
L1d:                     192 KiB (6 instances)
L1i:                     192 KiB (6 instances)
L2:                      1.5 MiB (6 instances)
L3:                      12 MiB (1 instance)
NUMA node0 CPU(s):       0-11

開發紀錄

頭腦暖身操

費氏數列推導

假設成年兔子為 a，幼年兔子為 b，且兔子不死亡

a_{n + 1} = a_{n} + b_{n}

b_{n + 1} = a_{n}

一般遞迴

a_{n + 1} = a_{n - 1} + a_{n}, n \geq 1

a_{0} = 0, a_{1} = 1

矩陣運算 Q-matrix

[\begin{matrix} a_{n + 1} \\ b_{n + 1} \end{matrix}] = [\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} a_{n} \\ b_{n} \end{matrix}]

又可改寫成

[\begin{matrix} a_{n + 1} \\ a_{n} \end{matrix}] = [\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} a_{n} \\ a_{n - 1} \end{matrix}]

[\begin{matrix} a_{n + 1} & a_{n} \\ a_{n} & a_{n - 1} \end{matrix}] = {[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}]}^{n}

Fast Doubling

F (0) = a_{0} = 0

F (1) = a_{1} = 1

\begin{aligned} [\begin{array}{c} F (2 n + 1) \\ F (2 n) \end{array}] & = {[\begin{array}{c} 1 & 1 \\ 1 & 0 \end{array}]}^{2 n} [\begin{array}{c} F (1) \\ F (0) \end{array}] \\ = {[\begin{array}{c} 1 & 1 \\ 1 & 0 \end{array}]}^{n} {[\begin{array}{c} 1 & 1 \\ 1 & 0 \end{array}]}^{n} [\begin{array}{c} F (1) \\ F (0) \end{array}] \\ = [\begin{array}{c} F (n + 1) & F (n) \\ F (n) & F (n - 1) \end{array}] [\begin{array}{c} F (n + 1) & F (n) \\ F (n) & F (n - 1) \end{array}] [\begin{array}{c} 1 \\ 0 \end{array}] \\ = [\begin{array}{c} F (n + 1)^{2} + F (n)^{2} \\ F (n) F (n + 1) + F (n - 1) F (n) \end{array}] \end{aligned}

其中

F (n - 1) = F (n + 1) - F (n)

最後得到

F (2 k) = F (k) [2 F (k + 1) - F (k)]

F (2 k + 1) = F (k + 1)^{2} + F (k)^{2}

Fast Doubling

F (2 k) = F (k) [2 F (k + 1) - F (k)]

F (2 k + 1) = F (k + 1)^{2} + F (k)^{2}

作業說明中的虛擬碼

Fast_Fib(n)
    a = 0; b = 1;       // m = 0
    for i = (number of binary digit in n) to 1
        t1 = a*(2*b - a);
        t2 = b^2 + a^2;
        a = t1; b = t2; // m *= 2
        if (current binary digit == 1)
            t1 = a + b; // m++
            a = b; b = t1;
    return a;

原理

這裡 Fast Doubling 利用比

$n$ 兩倍小的
$n^{'}$ 來算出

F (n)

，遞迴的深度則被限制在

O (\log n)

內，這可以大幅減少重複的計算

參考：Calculating Fibonacci Numbers by Fast Doubling

/* FILE: fibdrv.c */

static long long fib_fastd(long long n)
{
    if (n < 2)
        return n;

    long long a = 0;
    long long b = 1;
    for (int j = 63 - 1; j >= 0; j--) {
        long long c = a * ((b << 1) - a);
        long long d = a * a + b * b;
        a = c;
        b = d;

        if ((n >> j) & 1LL) {
            a = d;
            b = c + d;
        }
    }

    return a;
}

n 小於 2，直接回傳，不會經過迴圈
從 n 的 MSB 開始，依序計算該數的費氏數，直到 n 的 LSB 或剩下之 bit 皆為 0，則提前跳出迴圈

先用 h 記錄實際的數字共有幾個 bit (不含 leading 0s)，接著從 MSB 開始計算首項費氏數，再藉由迴圈依次增加 n >> j 的 bit 數，以計算後續的費氏數

複雜度分析

每次迭代使用 3 個乘法跟 2 個加法，時間複雜度為
$O (1)$
根據輸入的 n 大小決定迭代次數，即最多做
$O (l o g n)$ 次遞迴
總共時間複雜度為
$O (1) * O (l o g n) = O (l o g n)$

解釋 fast doubling 為什麼用 2k 跟 2k + 1

例如：長度為 n 個 bit 的數字

$α$ 與長度為 n+1 個 bit 的數字
$β$ 具有以下關係：

if
$β$ 要為偶數，則
$β = 2 α$ ，也就是
$β$ =
$α$ << 1
if
$β$ 要為奇數，則
$β = 2 α + 1$ ，也就是
$β$ =
$α$ << 1 + 1

剛好就是 binary number 的進位規則

使用 __builtin_clzll function 做硬體上的計算加速
clz (Count Leading Zero) 可以計算數字 n 前面有幾個 0，加速取得 h 的速度

- for (int j = 63 - 1; j >= 0; j--) {
+ long long mask = 1LL << (63 - __builtin_clzll(n));
+ for (; mask; mask >>= 1) {

- if ((n >> j) & 1LL) {
+ if (mask & n) {

實作大數運算前的效能比較

VLA 改進

Linux kernel 不支援 VLA，因此使用 Dynamic Programming 與空間重複利用的技巧，避免動態陣列的使用，同時將 space complexity 從

O (n)

降到

O (1)

Linux 核心限制使用 VLA 的因素
在 The Linux Kernel is now VLA-Free 有提到 Linux kernel 不再允許 VLA 的使用

C99 具有 VLA (Variable-Length Array) 的特性，允許執行時期再決定陣列佔用的空間大小，但可能會造成 stack overflow 等安全疑慮
根據教材你所不知道的 C 語言：函式呼叫篇，攻擊者可以利用 stack-based-buffer-overflow 來執行惡意程式碼，從而對系統造成威脅

此外，Linus Torvalds 也說過：『USING VLA'S IS ACTIVELY STUPID! It generates much more code, and much slower code (and more fragile code), than just using a fixed key size would have done.』

/* FILE: fibdrv.c */

static long long fib_sequence(long long k)
{
    long long f[2] = {0, 1};

    if (k < 2)
        return f[k];

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

    return f[k & 1];
}

時間測量功能

參考時間測量與效能分析的說明與 qwe661234 的解釋

High resolution timers and dynamic ticks design notes

hrtimers - subsystem for high-resolution kernel timers

在 Linux kernel 中具有兩種計時方式

jiffies 是 Linux kernel 較早期存在的計時方法，使用作業系統從開機以來的計時器中斷發生的次數作為計時的依據，此全域變數稱作 ticks 數。計時器中斷為週期性的中斷事件，以固定的時間間隔觸發，利用間隔固定的特性便能達到測量時間的目的。

通常情況下，jiffies 的精度為毫秒級別，具體的精度取決於 tick rate 的大小。例如 1000Hz 表示每秒觸發 1000 次的 timer interrupt，因此 jiffies 的增加速度為每毫秒一次。

jiffies 轉換為秒的公式為

(unsigned long long)(jiffies - INITIAL_JIFFIES) / HZ;

由以上程式碼可知, 假如系統原先設定的 tick rate (HZ) 不大於

10^{9}

，其時間精度是無法達到 ns 等級的。

hrtimer 是在 2.6.16 開始有的新的計時機制，裡面使用了 ktime_t 這個資料結構來進行計時。書中提到，原本基於 jiffies 的計時機制 timer wheel 在許多層面上有許多缺失，並幾乎無法再優化/整合了，包括：

The forced handling of low-resolution and high-resolution timers in the same way leads to a lot of compromises, macro magic and #ifdef mess.

The unpredictable [O(N)] overhead of cascading leads to delays which necessitate a more complex handling of high resolution timers, which in turn decreases robustness.

The timer wheel data structure is too rigid for high-res timers.

因此實作 hrtimer 的設計考量包括

simplicity
data structure not bound to jiffies or any other granularity. All the kernel logic works at 64-bit nanoseconds resolution - no compromises
simplification of existing, timing related kernel code

ktime_t 結構定義如下

union ktime {
	s64	tv64;
};

typedef union ktime ktime_t;

其結構有一型態為 64 位元的有號整數 tv64，單位為奈秒 (ns)

透過調用 Linux kernel API ktime_get()，可以取得相對於系統啟動時間的偏移量，因此藉由計算出兩次 ktime_get() 的時間差異，便可知其之間的程式碼執行時間花費

/* FILE: fibdrv.c */

static ktime_t kt;

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;
}

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    return (ssize_t) fib_time_proxy(*offset);
}

static ssize_t fib_write(struct file *file,
                         const char *buf,
                         size_t size,
                         loff_t *offset)
{
    return ktime_to_ns(kt);
}

在 read 的時候，計算 fib，並同時將所花時間儲存在 kt 中
接著 write 的時候，將 kt 的值轉換成 nanoseconds 再回傳給 client

client 中順序調用 read 和 write，即可取得所花費的 kernel time

/* FILE: client.c */

for (int i = 0; i <= offset; i++) {
    lseek(fd, i, SEEK_SET);
    sz = read(fd, buf, 1);
    kt = write(fd, write_buf, 1);
}

執行 sudo ./client 後，成功輸出計算費氏數時間，輸出如下

Reading from /dev/fibonacci at offset 0, returned the sequence 0.
Time: 331 (ns).
Reading from /dev/fibonacci at offset 1, returned the sequence 1.
Time: 197 (ns).
Reading from /dev/fibonacci at offset 2, returned the sequence 1.
Time: 183 (ns).
Reading from /dev/fibonacci at offset 3, returned the sequence 2.
Time: 113 (ns).
Reading from /dev/fibonacci at offset 4, returned the sequence 3.
Time: 123 (ns).
Reading from /dev/fibonacci at offset 5, returned the sequence 5.
Time: 120 (ns).
Reading from /dev/fibonacci at offset 6, returned the sequence 8.
Time: 81 (ns).
Reading from /dev/fibonacci at offset 7, returned the sequence 13.
Time: 78 (ns).
Reading from /dev/fibonacci at offset 8, returned the sequence 21.
...

選擇演算法

參考 yanjiew1 的做法，利用 read 傳入 size 作為使用不同演算法的條件

/* FILE: fibdrv.c */

switch (size) {
case 1:
    result = fib_sequence(k);
    break;
case 2:
    result = fib_fastd(k);
    break;
case 3:
    result = fib_fastd_clz(k);
    break;
default:
    return -EINVAL;
}

使用 gnuplot 製圖，確認 fast doubling 確實加速了費氏數的計算，同時發現 __builtin_clzll 大幅降低了時間開銷

NOTE: 此處時間為 kernel mode 中計算的時間，還未加入 user space 的時間開銷比較

排除效能干擾因素

使用 taskset 預留 cpu 給效能測試使用

$ sudo vim /etc/default/grub
修改此行 GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=5"
$ sudo update-grub
$ sudo init 6

將作業說明提到的方法寫成一個 script

#!/bin/sh

CPUID=5
MASK=$((1 << $CPUID))
MASK=$((0xfff & ~$MASK))
MASK=`printf "%x" $MASK`
ORIG_ASLR=`cat /proc/sys/kernel/randomize_va_space`
ORIG_GOV=`cat /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor`
ORIG_TURBO=`cat /sys/devices/system/cpu/intel_pstate/no_turbo`
ORIG_IRQ=`cat /proc/irq/$CPUID/smp_affinity`

sudo sh -c "echo 0 > /proc/sys/kernel/randomize_va_space"
sudo sh -c "echo 1 > /sys/devices/system/cpu/intel_pstate/no_turbo"
sudo sh -c "echo performance > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"

for file in /proc/irq/*/smp_affinity; do
    var=0x$(cat "$file")
    var=$((var & 0xfdf))
    var=`printf "%x" $var`
    sudo sh -c "echo $var > $file" 2> /dev/null
done
sudo sh -c "echo $MASK > /proc/irq/$CPUID/smp_affinity"

# Load the module and run the client
make unload
make load
python3 scripts/statisic_plot.py -cpu=$CPUID
gnuplot -e "filename='scripts/data.txt'" scripts/draw.gp
make unload

# Restore original settings
sudo sh -c "echo $ORIG_ASLR > /proc/sys/kernel/randomize_va_space"
sudo sh -c "echo $ORIG_GOV > /sys/devices/system/cpu/cpu$CPUID/cpufreq/scaling_governor"
sudo sh -c "echo $ORIG_TURBO > /sys/devices/system/cpu/intel_pstate/no_turbo"
sudo sh -c "echo $ORIG_IRQ > /proc/irq/$CPUID/smp_affinity"

最後使用 taskset -c 5 ./client 指定 client 使用 cpu 5 進行費氏數計算

去除極端值

參考時間測量與效能分析

計算 50 次費氏數的平均，並將離散值做處理，用以得到較平滑的效能比較圖
程式碼 4b6a40c

2023q1 Homework3 (fibdrv)

開發環境

開發紀錄

頭腦暖身操

費氏數列推導

Fast Doubling

原理

實作大數運算前的效能比較

VLA 改進

時間測量功能

選擇演算法

排除效能干擾因素

去除極端值

Read more

筆記

Leetcode

Assignment3: Single-cycle RISC-V CPU

Assignment2: RISC-V Toolchain