2020q1 Homework2 (fibdrv)

contributed by < Hsuhaoxiang >

2020q1 表示 2020 年的第 1 季，即春季班課程的意思

jserv

自我檢查清單

• 研讀上述 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，到底會發生什麼問題

---

研讀上述費氏數列相關材料

費氏數列有公式解

$$\begin{gathered} a_{n+1}=a_n+b_n \\ {b}_{n+1}=a_n \end{gathered}$$

$$\left(\begin{array}{c}{a}_n\\ b_n\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{a}_0\\ b_0\end{array}\right)$$
方法是將前面的 Q-metrix 進行對角化，得到 eigenvalue

${\lambda }_1=(\frac{1+\sqrt{5}}{2})$ ,

${\lambda }_2=(\frac{1-\sqrt{5}}{2})$

$$\left(\begin{array}{c}{a}_n\\ b_n\end{array}\right)=(\frac{1}{{\lambda }_1-{\lambda }_2})\left(\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right)\left(\begin{array}{cc}{\lambda }_1^n& 0\\ 0& {\lambda }_2^n\end{array}\right)\left(\begin{array}{cc}1& -{\lambda }_2\\ -1& {\lambda }_1\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)$$

$a_0=1$ ,

$b_0=0$最後寫成上式，將上面右式的矩陣乘開便得到

$\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2}{)}^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2}{)}^n$

• 用的個公式算看似只需要常數時間便能求出答案，但其實浮點數的精確度是有限的，因此
  $\frac{1\pm \sqrt{5}}{2}$ 的次方數越大就會有更大的誤差

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}$$
我們便可以由

$F(k)$ 和

$F(k+1)$ 算出

$F(2k)$ 和

$F(2K+1)$，需

$O(\log n)$ 次計算，但

$F(50)$ 已經是 11 位數了，兩個大數相乘計算時間又會變得更長!

使用 Fast Doubling 加快計算費氏數列

• 原本的寫法所花的時間為
  $O(n)$

static long long fib_sequence(long long k)
{
    long long f[k + 2];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[k];
}

• Fast doubling ，從 MSB 開始計算
  $F(k)$ 和
  $F(k+1)$ 必須判斷目前的 bit 是否為 1，
  為了先算出他的二進位表示，我先跑了一次 while 同時算出他有幾位，這裡之後還要改成 clz / ctz 指令就不用先跑一次
  $O(log(n))$

static long long fib_fast_doub(long long k)
{
    int bin_k[10];
    int count = 0;
    while (k) {
        bin_k[count] = k % 2;
        k = k >> 1;
        count++;
    }
    long long int a = 0, b = 1;
    for (int i = count - 1; i >= 0; i--) {
        a = a * ((2 * b) - a);
        b = b * b + a * a;
        if (bin_k[i] == 1) {
            long long tmp;
            tmp = a + b;
            a = b;
            b = tmp;
        }
    }
    return a;
}

• 在 user space 進行實驗並將實驗的數據以 gnuplot 繪製成圖表

在40項之後可以看出兩種演算法所花的時間差距會越來越大

增加

$Fib(n)$ 的數值範圍

• 因為超過 long long 所能表示的資料範圍就會溢位，原本的程式

  $Fib(93)=-6246583658587674878$ 必須更改儲存數值的方式

• 目前正在參考 bignum 的做法

---

複習 C 語言 數值系統 和 bitwise operation，思考 Fibonacci 數快速計算演算法的實作中如何減少乘法運算的成本

• 大數乘法可以用 Karatsuba 演算法加速