contributed by < ganoliz >
目前先針對在 kernel 計算 fib(1) ~ fib(100) 分別所需的計算時間,以分佈的方式作圖看看:
若我們再加上 user time 與 kernel to user 的轉換時間則如圖所示:
根據 Fast Doubling 這篇文章所述
使用這兩個公式,當我們在計算費波那契數列時,就不須用一個一個數列值往後推,只需要知道他的 f(n/2+1) , f(n/2) , f(n/2-1) 的值就好。 這說明我們的計算量可以比累加的方法減少至少從 f(n-1) ~ f(n/2+1) 的計算量,時間複雜度為 O(log(n))。
當然根據文章所述,我們還能更進一步優化程式碼(Top-down)變成如下:
根據 n 是奇數或偶數決定計算 F((n-1)/2) 或是 F(n/2) 。
n(=) | 10 | 5 | 2 | 1 | 0 |
n is odd | v | v | |||
binary | 1010 | 1010 | 1010 | 1010 |
可以看到 n 為偶數時,我們可以找到 的 k = n/2 ,這樣我們能用 來計算
反之當 n 為奇數時,我們可以找到 的 k = (n-1)/2 。我們能用 來計算 然後我們再多做一個加法 因此可以得到
由於除2可以看作是進行 binary code 右移,因此我們可以根據老師所述,結合 clz / ctz 的指令搭配 Fast Doubling(先去除數字 MSB 起算的開頭 0 位元,因為真正的數字不包含 leading 0s)。
以下是 bignum 的 fast doubling 實作:
首先閱讀完 《The Linux Kernel Module Programming Guide》 的 character driver 後,可以知道幾件事:
於是我開始動手修改 fibdrv.c 程式碼:
將 fib_sequence 改成 big_number 的形式,並回傳指定要的 fibonacci number 編號的 BigN 結構。
接著我們將 upper 與 lower 複製到 user_space 的 buffer 。 copy_to_user 會回傳未成功複製的位元的值, 若所有位元的值都成功複製,預期回傳應為 0 。
接著我們可以使用終端機至 /var/log 開啟 kern.log 或 使用命令 tail -200 kern.log 來觀察我們剛剛使用 printk() 輸出的訊息:
如上所示,這使得要 Debug 稍微方便一點。
接著我們來看看 client.c :
我目前遇到的問題是如何將 upper 的值與 lower 的值加在一起,百思不得其解。 我目前在想轉成 character ,但是那就跟 Small/Short String Optimization 程式碼 的方法一致了。一方面我把 character 實做的程式碼看了一下並 clone 下來跑跑看,另一方面試圖在 user space 將 __int128_t 的資料型態定義並能夠使用 print 輸出。
目前依據老師指示參看 bignum範例 如何從底層實作大數字運算。由高層次 bignum.c 到底層 bitwise 的實作 apm.c ,處處都藏著能夠加速運算的細節。
首先我們先看看底層的實作:
底層實作都是以二進位來思考,當加 1 時指標就需要依序從低位元往高位元走。直到我們加 1 之後不等於 0 (沒有進位的時候才停止) 接著回傳進位。接著有一些類似組合語言的 immediate 加法命名方式 addi 是省略一些變數的儲存。 最主要的想法我們來看 apm_add() : 藉由兩個變數 u, v 我們需要知道它的 bits size 大小才方便做處理,若 usize > vsize 則我們把高位元直接複製 (usize - vsize)
個 bits 值就好,反之亦然。
若 usize == vsize 則使用 apm_add_n() 來計算。
看完程式碼想要測試看看 bn.h ,結果發現不太曉得如何在 Linux Kernel include "bn.h" ,目前重新回去看 Makefile 怎麼樣能 include 到。
$(MAKE)
而非 make另外還有比如 Makefile 裡的這行
all: $(GIT_HOOKS) client
<Tab>$(MAKE) -C $(KDIR) M=$(PWD) modules
意思就是當 make 的目標爲 all
時, -C $(KDIR)
指明切換到 Linux 核心原始程式碼目錄下讀取其中頂端的 Makefile
; M=$(PWD)
( M= 的原本意思是 pass 參數讓 Makefile 能看見)。
因此我們看看在 KDIR=/lib/modules/$(shell uname -r)/build 下的 Makefile 可以看到以下註解:
因此敘述表明這一段 make modules 在 KDIR 位置下的 Makefile 並傳遞我們 Character device 的位置給這個 Makefile。
可參見 0xff07/bignum,注意要是
fibdrv
分支,這是移植到 Linux 核心模組的嘗試。
:notes: jserv
無使用fast doubling 技巧:
使用 fast doubling技巧:
效能差異並不明顯,
但當我們把結果拉到F(1000):
fast doubling:
效能相差就很大了。
研讀 KYG-yaya573142 的報告
修改 /etc/default/grub
的 GRUB_CMDLINE_LINUX_DEFAULT
,在裡面加上 isolcpus=(要獨立的 cpu 編號)
重新開機啟動後,我們可以就能將程式(Process ,Task)固定在這個 CPU 執行。
我們可以透過 /sys/devices/system/cpu/isolated
查看被 isolated 的 CPU 編號。
抑制 address space layout randomization (ASLR)
設定 scaling_governor 為 performance 。準備一個 shell script
關閉 Intel 處理器的 turbo mode:
當我們做把 CPU 編號 7 隔出來只做我們的 ./client.c 就能見到較為下圖平整的效能圖:
但是還是有一些 Timer 的中斷。根據我們查看 cat /proc/interrupts
:
SMP IRQ affinity 設定: 在 /proc/irq 下面做 smp affinity 的設定
設定完之後再次查看 interupts 次數:
整體來說 local timers interrupts 又變得更少了。
當我們使用 bignum 大數運算得到的二進制值,會透過 bn_sprintf() 將結果存為十進制的 char * ,接著我們透過 buffer 將結果透過 copy_to_user 傳遞回 user space 。由於每個 char 只存一個 10 位數的 digits ,因此傳遞效率是挺差的。
我們甚至以 BCD 碼來做編碼還比直接使用 char 省了一半的空間( BCD 碼八位元可以放兩個 digits )
這邊先看看在 User Space 才轉換的 BignumBinary 直接 copy_to_user 與原本直接在 Kernel Space 就轉換的 BignumChar copy_to_user 的效能差異:
雖然差距只有個 ns (約 77ns 與 65ns)的差距,但也顯示出 copy_to_user 的 傳輸 Bytes 數是有優化空間的。
研讀老師提供的教材Integer Encoding Algorithm 筆記 與 invertedtomato/integer-compression 來進行整數壓縮編碼:
Variable Byte 的方式是企圖採用最少的 Bytes 數來存取,使用最前面的 1 個 bit 當作 flag 來確認資料是否串聯下一個 bytes (若為 0 代表這是 LSB least sinificant bytes) 剩下 7 個 bits 拿來存資料:
數值(unsigned long) | binary(32 bits) | Encode Variant |
---|---|---|
0 | 00000000 00000000 00000000 00000000 | 00000000 |
127 | 00000000 00000000 00000000 01111111 | 01111111 |
128 | 00000000 00000000 00000000 10000000 | 10000001 00000000 |
4294967295 | 11111111 11111111 11111111 11111111 | 10001111 11111111 11111111 11111111 01111111 |
這個方法採用最少 bytes 去編碼,但因為每 32-bits 使用 4 個 bits 去判斷是否為 LSByte 因此造成 當我們要編碼的數值 超過 的時候,編碼的 bytes 數反而會比沒編碼的 Bytes 數要多一個。
根據第一個數字來判定後一個整數的重複次數來做壓縮,比如:
可被壓縮成:
若連續都為不同的數:
則會用一個負數來代表連續不同數的個數:
這種編碼壓縮的方法特性很明顯:就是在數字間 熵值 (entropy) 大時 (數字幾乎都不重複) 時,壓縮率很差。做為 fibdrv bignum 計算數值的壓縮來說,不是一個很好的選擇。
Delta 也是一個編碼常用的技巧,比如一個整數陣列為 [ 100, 109, 105, 117, 93] 根據我們的 delta 就可以編碼為 : [100, 9, 5, 17, -7]。再者繼續編成 delta of delta (DoD) : [100, 9, -4, 12, -24]。當我們產生出這種 DoD 格式的編碼之後,我們需要使用 Variable length coding (VLC) 的方法產生出 tag bits 才能在 Decode 階段正確的把 DoD 格式還原成原本的整數數值陣列, VLC 的方法用以下表格舉例:
DoD | tag bits | following bits |
---|---|---|
0 | 0 | 0 |
[-64,63] | 10 | 7 bits |
[-512,511] | 110 | 10 bits |
[-4096,4095] | 1110 | 13 bits |
[-32768,32767] | 11110 | 16 bits |
else | 11111 | 64 bits |
使用 DoD 的好處是:由於是目前這個整數數值與上一個整數數值的相差大小,因此即便一開始找的數值很差,對於 DoD 的影響就比單純使用 Difference 方法小。然後因為 tag bits 由左開始連續個 1 ,所以解碼是唯一不會有混淆的情況發生。這裡壓縮的效率與數值的變化是否很大有關。以 fib_drv bignum 而言,每個 apm_digits 的大小為 64-bits (根據我的電腦) 。因此分析最差的情況是 DoD 為需要 69 bits 去儲存下一個數。實際情況則要再分析是否能有效壓縮。
Binary Packing 技巧是判斷整數陣列裡面最大的值需要用幾個 bits 去儲存,其他數值也用相同的 bits 數去儲存即可。
可以看到我們的最大值為 65535 (),代表我們每一個整數都用 16 bits 去儲存。這裡也有一個問題就是這個陣列的數值最大值是否與我們原先編碼的 bytes 數有足夠的優化空間(比如我們最大值預期為原先編碼 bytes 數的 1/2 以下)。由於我們可壓縮的 bytes 數與我們的最大值相關,因此我認為 fibdrv bignum 使用這個編碼的壓縮效果會不甚滿意,可能會需要額外的輔助限制條件與規則 ( 文章提到的 Patched coding 方法 )。
根據以上方法,我們決定先以 Variable Byte 的來實作看看。因為這個方法比較簡單,根據我們 fibdrv bignum 效果也比較容易想像。
以下為 encoder 程式碼試作 :
以及我的 Decoder :
目前把 encoder 套用到 fibdrv.c 上出現了錯誤,已修改型別使的以每個 32-bits digits 來做 BytesModify 處理,但我觀察核心 log 還是出現記憶體存取的錯誤如下(1~6行):
已解決,在 fib_size = 0 的情況下還是要 kmalloc 一個 char * 來存放數值 0x00
解決問題後透過 encoder 將資料複製到 buffer 裡傳送到 user space 做 decode ,但是經過分析 Bytes 數後發現白忙一場 , 因為需要複製的 Bytes 數在費波那契數列值大的時候甚至比一開始未 encode 的 Bignum_64bits 還多,如下圖所示 :sweat_smile: :
performance 則是如下圖:
看起來這個編碼並沒有發揮他的優勢,大部分的情況一個 32 bits 的 digits 數值都會超過 ,這樣的情況下 4 個 Bytes 的資料就需要用 5 個 Bytes 去做儲存。在數列約為fib(800)之後需要使用的 Bytes 數就越差越大。看起來不太適合費波那契數列數值壓縮,要再試試其他數值壓縮方法。
加入 BCD 編碼出來的 Bytes 數來看,使用 BCD 來表示既簡單而且壓縮率(為CharBytes 的 ) 發現與 VariableBytes 相仿重疊:
Fib(n) | BignumBinary | BCDcode | VariableBytes |
---|---|---|---|
n=10 | 8 | 1 | 2 |
n=50 | 8 | 5 | 6 |
n=100 | 16 | 10 | 12 |
n=200 | 24 | 21 | 23 |
n=300 | 32 | 31 | 34 |
n=400 | 40 | 42 | 44 |
目前暫時想不到如何更有效的壓縮 BignumBinary , 因為目前直接將 BignumBinary 傳送到 UserSpace 之後再做十進位解碼即可。至於有觀摩 scottxxxabc 使用 clz 來計算 bignum[max_idx] 來減少 copy_to_user 的 bytes 數,這樣的確會減少 bytes 數,但是依照遞增差不多就是減少 ( 0 ~ 7個 Bytes ; uint_64t ) 效益並不是很大。
由於目前的 Bignum 都是以 fast doubling 計算並透過 copy_to_user 回傳至 buffer 陣列,所以各執行緒之間並沒有共享變數。
以下透過 pthread 來建立五個執行緒:
所以結果跟我們想的一樣,值得一提的是假如我們將程式 taskset 固定在單個 CPU 上則每個 Thread 就會按照列隊順序執行 fib_count :
一旦可有效處理多執行緒的 client 端要求,接著就能在 fibdrv 實作 LRU,將之前的計算結果保存下來,並利用 fast doubling 的特性 (用第 N 項快速計算第 2N 項),從而省去大量的計算。不過,使用 LRU 的話,就要解決同步處理議題。
:notes: jserv
LRU(Least Recently Used Cache),是一種快取策略,將最近用到的資料放在串列前面,最近越沒用到的放在快取串列後面,當快取串列滿的時候就會將最後一個資料移除,接著把新的資料存在串列第一個 。 LeetCode 參考
由於 double linked list 的搜尋存取效率為 效率不好,因此常常會透過一個 hash maps 來達到好的存取效率。
因此,我們可以從 第一周練習題的 hlist_node 的想法來建構一個 hash map ,再透過 list_head 建立雙向鏈結串列實作。
然後目前我在思考我的 cache 大小要設多大比較好,目前設為 50 個 fib 數值 。
debug 的時候遇到問題,就是掛載上 kernel 之後導致系統 crash ,我猜是記憶體釋放或是存取到其他不該存取的位置,但這邊不曉得要怎摸 debug 比較好 :sweat_smile: