L04: fibdrv

請務必詳閱作業描述 (一), (二), (三), (四), (五) 及 (六)

主講人: jserv / 課程討論區: 2023 年系統軟體課程

返回「Linux 核心設計/實作」課程進度表

作業說明錄影 / Code Review 錄影

2023 年已變更作業要求

預期目標

• 撰寫適用於 Linux 核心層級的程式
  • 學習 ktimer, copy_to_user 一類的核心 API
• 複習 C 語言 數值系統, bitwise 操作, List API, alignment, 遞迴呼叫
• 運算成本分析及其改進策略
• 初探 Linux VFS
• 透過工具進行效能分析
• 初探並行和多執行緒程式設計

費氏數列

參照以下材料理解 Fibonacci 數列和對應的計算手法:

• 費氏數列分析
• 「什麼是費氏數列」短片: Part I, Part II, Part III, Part IV
• TED: The magic of Fibonacci numbers (有繁體中文字幕)

依據 Fibonacci and Golden Ratio Formulae，考慮 Fibonacci 最初提到不會死亡的兔子繁衍總量問題，假設成年兔子為 a ，幼年兔子為 b ，我們可得到以下關係:
$$\begin{gathered} a_{n+1}=a_n+b_n \\ {b}_{n+1}=a_n \end{gathered}$$

將上述推導寫成矩陣的形式就會變成
$$\left(\begin{array}{c}{a}_{n+1}\\ b_{n+1}\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{a}_n\\ b_n\end{array}\right)$$

則 $\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$ 就是所謂的 Q-matrix，可進一步改寫為:
$$\begin{gathered} Q=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}{F}_2& F_1\\ F_1& F_0\end{array}\right) \\ {Q}^n=\left(\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right) \end{gathered}$$

解說短片: The Fibonacci Q-matrix

接著談及 Fast Doubling 手法，繼續整理:
$$\begin{array}{rl}\left[\begin{array}{c}F(2n+1)\\ F(2n)\end{array}\right]& ={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{2n}\left[\begin{array}{c}F(1)\\ F(0)\end{array}\right]\\ \\ & ={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n{\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\left[\begin{array}{c}F(1)\\ F(0)\end{array}\right]\\ \\ & =\left[\begin{array}{cc}F(n+1)& F(n)\\ F(n)& F(n-1)\end{array}\right]\left[\begin{array}{cc}F(n+1)& F(n)\\ F(n)& F(n-1)\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\\ \\ & =\left[\begin{array}{c}F(n+1{)}^2+F(n{)}^2\\ F(n)F(n+1)+F(n-1)F(n)\end{array}\right]\end{array}$$

因此可得:
$$\begin{array}{rl}F(2k)& =F(k)[2F(k+1)-F(k)]\\ F(2k+1)& =F(k+1{)}^2+F(k{)}^2\end{array}$$

根據 Fibonacci 數列原始定義 F(0) = 0, F(1) = 1, F(2) = 1我們就可用這三個值，依據上述公式推導出隨後的數值。

對應的虛擬碼如下:

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;

以 $F(6)$ 為例:

• 第 1 次遞迴

• 第 2 次遞迴

可見遞迴次數縮減，還能再更快嗎？再觀察到 $F(6)$ 被分成 $F(3)$ 和 $F(4)$ 兩個部分，其中 $F(4)=F(2)+F(3)$ ，可以利用 $F(3)$ 和遞迴 $F(3)$ 時所得到的 $F(2)$ 去計算 $F(4)$，這樣可以再次降低運算的次數，如下：

• 第 2 次遞迴

和最初的 Fibonacci 數列定義相比，可見相當大的差距。

示範案例:
求解 $F(10)$:
10₁₀ = 1010₂

i	start	4	3	2	1	result
n	-	1010	1010	1010	1010	-
F(m)	F(0)	F(0*2+1)	F(1*2)	F(2*2+1)	F(5*2)	F(10)
a	0	1	1	5	55	55
b	1	1	2	8	89	-

對照 $F(11)$
11₁₀ = 1011₂

	1	0	1	1	result
F(n)	F(0*2+1)	F(1*2)	F(2*2+1)	F(5*2+1)	F(11)
a	1	1	5	89	89
b	1	2	8	144

考慮到硬體加速 $F(n)$ 的手法

許多現代處理器提供 clz / ctz 一類的指令，可搭配上述 Fast Doubling 手法運用:

1. 省略 $F(0)$，直接從 $F(1)$ 開始;
2. clz/ffs: 先去除數字 MSB 起算的開頭 0 位元，因為真正的數字不包含 leading 0s，所以計算它也沒用，因此需要 clz 計算有多少 leading 0s
   • 遇到 0 $\to$ 進行 fast doubling，也就是求 $F(2n)$ 和 $F(2n+1)$
   • 遇到 1 $\to$ 進行 fast doubling，也就是先求 $F(2n)$ 和 $F(2n+1)$，再求 $F(2n+2)$

可對照 你所不知道的 C 語言: 遞迴呼叫篇。

Fibonacci 數的應用

電腦在計算亂數時，常以新產生出來的數值作為下一次計算的依據，這就是為什麼計算機隨機數大部分都會表示成遞迴定義的數列。

這裡只探討 Pseudo-Random Number Generators (PRNG)

這是一般的 Fibonacci 數列

f[0] = 0;
f[1] = 1;
f[i] = f[i - 1] + f[i - 2];

數列呈現單調遞增

1, 1, 2, 3, 5, 8, 13, 21, ...

如果我們強迫 Fibonacci 數列的數值超出 100 之後折回來

f[0] = 0;
f[1] = 1;
f[i] = (f[i - 1] + f[i - 2]) % 100;

一開始雖然還是看得到規則，不過整體趨勢已經不再是單調遞增，當數值折回之後規律變得不太明顯

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
89, 44, 33, 77, 10, 87, 97, 84, 81, 65,
46, 11, 57, 68, 25, 93, 18, 11, 29, 40,
...

甚至可將 Fibonacci 的遞迴數列改成:

f[0] = 18;
f[1] = 83;
f[2] = 4;
f[3] = 42;
f[4] = 71;
f[i] = (f[i - 2] + f[i - 5]) % 100;

這個數列的規則已不容易看穿

18, 83, 4, 42, 71, 60, 54, 64, 96, 35,
56, 89, 20, 85, 55, 41, 44, 61, 29, 16,
70, 60, 31, 89, 47, 59, 7, 90, 96, 37,
...

這種產生隨機數的方法，稱為 Lagged Fibonacci generator (LFG)，是電腦產生隨機數的一種方法。

〈Linux 核心的 hash table 實作〉提到，Linux 核心採用的雜湊函數稱為 Fibonacci hashing，其精神也依循上述，從而降低碰撞。

延伸閱讀:

• For The Love of Computing: The Lagged Fibonacci Generator — Where Nature Meet Random Numbers
• 3blue1brown 的影片提到費氏數列也可寫成 Generating Function