contributed by < Kevin-Shih
>
硬體
作業系統
編譯器
依照 Fibonacci 數列的定義
\(f(i)=f(i-1)+f(i-2)\)
可以發現其實只須 3 個變數即可迭代計算出 \(f(k)\)
修正後的 fib_sequence
cpu0
隔離僅供本次要測試的程式使用
後續以
taskset
指定欲測試的程式使用cpu0
cpu0
的 scaling_governor 為 performancecpu0
作為這次運行效能測試的核心,故僅將 cpu0
調整為 performance簡單寫了個 shell script 方便後面一次執行
reboot 後執行該 shell script 的結果
在修正了 VLA 的問題後,先試著量測最基本的算法在計算時的效能。
測試的方式是挪用原先空置的 write()
當 client
以帶參數的方式呼叫後,會以測試時間的模式執行程式並以其中的 size
參數作為選擇以哪種方式計算 Fibonacci 數列。 在 kernel space 使用 ktime api 量測,user space 則使用 clock_gettime()
, kernel to user 則是透過 user space 的耗時減去 write()
回傳的 kernel space 耗時得出。
kernel 的時間量測
user space 及 kernel to user 的時間量測
以 python script 濾除極端值
參照作業要求中 用統計手法去除極端值
中的手法,在假設所得的 100 筆 nth fibonacci 的資料為常態分佈,以 Z-value 刪去大於等於 1.96 sigma (95% 信心區間) 的觀測量後,取平均值作為第 nth fibonacci 計算時間。
僅修正 VLA (v0)
kernel space
user space and kernel to user
由於 kernel space 與 user space 的耗時相差過大,只好分別畫成兩張圖方便檢視,儘管 kernel to user (以下簡稱 k to u)的時間似乎非常大,但在重複測試多次後仍然出現相同情形,且 k to u 的時間大致持平十分合理,因此結果應是正確的。
另外由於最初的實做是使用迭代的方式計算,因此隨著計算的項數增加執行時間大致成線性增加。
參考作業要求中的 fast doubling 作法
\[
\begin{split}
F(2k) &= F(k)[2F(k+1) - F(k)] \\
F(2k+1) &= F(k+1)^2+F(k)^2
\end{split}
\]
從 MSB - 1
開始(跳過 f(0) ) 這個位置可以用 __builtin_clzll
計算
效能分析
相較於原先 iterative 的實做 fast doubling 無疑快上許多,時間複雜度從 O(n) 增加轉為 O(log2(n))。
由於原先的 fast doubling 儘管省略了 f(0) 這一項,也使用了 clz
來取得 MSB 位置,但在運算時 f(2k) 時使用了 2 * f1
可以被 shift 操作取代以節省時間,且在算 f(2k + 2) 時多了不少無意義的賦值,因此做出了些許修正再重新測試。
效能分析
可以看到這些改變略為降低計算 Fabonacci sequence 的 cost。
為了可以計算 f(93) 以後的值採用下列 bigN
結構
因為實在是沒看懂作業要求中的 數字字串及SSO 的部份,因此參考 freshLiver 的作法,使用 kernel 中的 linked list 將 64 bit uint 串起來作為 big num 的結構,以 linked list 串起後在將可以計算更後面的 Fabonacci sequence,目前測試可以正確計算至 f(2000) 共 418 位數。
在加入了 bigN
這個結構後也需要實做對應的加法
將 2 個 list 相加,其中 bigN1
應為 \(f(i-1)\) ,bigN2
應為 \(f(i-2)\),算出的結果直接放入 bigN2
。
將一個 bigN
node 的上限定在 1018 方便後續 copy_to_user 時串接多個 node,且 1018 < 263 因此 a, b 可以直接相加而不 overflow 方便加法實做,但會造成空間的浪費。
因 MSB 存放在最後一個 node,而 LSB 在第一個 node,只要倒著走訪 list 中的節點並串接到要回傳的 result
字串即可最後的答案。
先一樣採用單純的遞迴計算,可以正確的計算出 93 項以後的數
採用與先前相同的方法進行效能量測。
這次計算的相當慢,估計是先前 bigN
的結構及加法設計上浪費了 uint64_t
不少"範圍"(上限被定在 1018),且每次 kmalloc 一個新的 node 都是很大的 cost。
在查看 perf 所紀錄的 caller graph 不意外的發現 kmalloc 佔用了近一半的時間,接下來該考慮改用不會浪費那多間的大數結構並希望能減少 kmalloc 造成的 cost。
改用數字字串來實做 bignum
先以 iterative 的方式實做修改過的 bignum,數字字串的部份採用固定 1024Byte 的 char array,數字依倒序儲存方便進行相加,並依作業要求中的介紹實做數字字串的相加,最後在將字串反轉回正序並 copy_to_user
即可。
將 expected.txt
改為 The first 500 Fibonacci numbers 中的答案後,將 client.c
的輸出格式調整好,並將 MAX_LENGTH
設為 500 後,以 make check
檢查實做的正確性。
省略部份輸出:
接著進行效能分析:
比較的是兩者的 kernel time
可以發現在前 200 項相較前一個實做無疑快上不少,然而受使用 strncpy()
的拖累在後續項次數字變長後,反而比原先的實做還慢。
前一個版本受 strncpy
的拖累效能不佳,這個版本透過使用 indirect pointer 省去複製字串的消耗,也節省先前需要一個 temporary buffer 存放 ADD
運算的結果的空間。
同樣使用 make check 檢查前 500 項的結果
效能分析
比較的是兩者的 kernel time
儘管還是完全比不上 fast doubling 但比起前兩次實做,在擺脫耗時的 strncpy
後快上不少。
TODO
為 big number 實做 乘法 等運算,以實做 big number 版本的 fast doubling