contributed by < rwe0214
>
Linux
, rwe0214
, NCKU
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,到底會發生什麼問題Fibonacci 數定義為
但是此種遞迴計算的成本太高,而 Nikolai. N. Vorobev 揭露了 Fibonacci 擁有以下性質 (可由數學歸納法證明之)
若將 和 代入上式可得
再將 可得
如此一來可以整理出當 分別是偶數和奇數的演算法:
不過此種遞迴方式會比較快嗎?以 來說,
可以看出遞迴的次數減少非常多,那還能再更快嗎?
再觀察到 被分成 和 兩個部分,其中 ,可以利用 和遞迴 時所得到的 去計算 ,這樣可以再次降低運算的次數,如下:
接著再將這兩種想法以 bottom-up 的實作方式來比較,可以看到相當大的差距。
由於受限 unsigned long long
只有 64 bits 的表達範圍 ( i.e., Max value = ),且 的值大於 ,在尚未實作大數運算前,只設計了數值範圍到 的實驗。
程式碼如下:
實驗結果:
明顯看到 Fast doubling
明顯優於 Adding
方法。
接著比較在 fast doubling
上使用硬體指令 clz
的差別,
和
執行實驗程式碼
每個 取樣 次取 95% 的信賴區間來統計結果:
可以看到有無使用 clz
的結果非常相近, 而 clz
在 n 值越大的時候表現略優 ( 紫色線 ),推測是因為硬體加速在數字越大 ( i.e., bits 數越多 ) 效果越顯著。
但是這個 clz
是使用 builtin 的編譯器優化,並不是使用 Linux 核心 API,結果可能會有所誤差。
接著進行使用 memorization 的方法,將之前計算過得 保存在 LUT 中,觀察是否有獲得更佳的效能,因為範圍只到 所以只建立的 至 來查表,實驗結果如下:
可以看到當 n 越大時,使用 LUT 的速度越快,但是同時也損失了 memory 空間去儲存 LUT。
考慮需要更多的位元空間來儲存 以後的數值,定義了一個結構,
為何不採用變動長度的數值表示法?一如 quiz2 採用的策略
目前這個部分仍在思考,只是目前還沒有完整的想法,所以先實作固定長度,之後再做修改
rwe0214Fri, Mar 6, 2020 11:08 AM
在比較完計算 的方法後,決定採用 fast_doubling
的方式來實作。
因為在 fast doubling
中需乘法、加法和減法的操作,其中加減法方法較為簡單,乘法則是模擬計算機的乘法器的行為,方式如下
將結果印出並和 Fibonacci numbers 做確認相同
試著利用 quiz2 的方法實作可變長度的大數,定義以下的結構 ubgi
,大小為 128 bits ( i.e., 16 bytes ),
接著利用 new_ubgi
函式定義一個新的大數,因為是以十進位的字串輸入數值,而一個 63 bits 的 unsigned long long
的最大值在十進位中恰為 19 位數,所以以 19 當作數值位數的分界。
完成了數值的新增後,雖然數值可以儲存的非常大,而且可以達到作業要求,比對 Fibonacci numbers 300 後結果為正確的。
但是在計算上總覺得非常沒有效率,以 c = a + b
加法來說,需要判斷 a 和 b 的種類,共有四種狀況,如此會在程式碼中有著大量的條件判斷式如下,
接著是減法、乘法,所以目前還想嘗試思考有無其他做法,或是改變結構體來達到精簡化。
後來將結構體改為
加法在實作上仍然採用傳統的直式加法,而乘法則以硬體乘法器的模型去完成,
只是我將 product 中的位數個數以乘數及被乘數的位數來決定,並把乘數放入低位,判斷 LSB 決定是否將乘數用大數加法累加進 product 的高位。
上面的儲存數值的方法是單純的二進位制,但是如果要將二進位制的大數以十進位的方式印出,不能單除用數學的方法將數值累加,我參考了 Double dabble(1) 和 Double dabble(2) 的方法轉換二進位成十進制。
假設數字是 01101011
,其十進位是 107
以下是 double dabble 進行的步驟,
以上面的手法修改後,在記憶體運許的狀況下,可以將 Fib
數印出,為了驗證正確性,寫了一個 verify.py 的小程式去驗證 Fib
的計算