contributed by < YSRossi
>
參考作業說明所提供 Fast Doubling 的虛擬碼,搭配 bitwise 實作。
n
的型態為 long long
,使用 sizeof(long long) << 3
計算 long long
所佔有的位元數,減去 n
的 leading 0-bits
數量,得到 n
實際上有用到的位元數。其中 n
的 leading 0-bits
數量,使用 __builtin_clzll(n)
獲得。n & (1 << (i - 1))
表示,將 1 左移 i - 1
把對應目前位元的位置設成 1 ,與 n
做 and
判斷目前位元是否為 1 。TODO : 嘗試解決在 GRUB 的設定檔中加入 isolcpus=7
重新開機後仍無法起作用的問題。
已解決,使用
sudo update-grub
更新 GRUB 設定檔
實驗比較 Fast Doubling 與原始方法在 kernel space 所花費的時間(已排除干擾效能分析的因素)
若將上方程式碼的第 5 行改成下方程式碼,計算 fib(0) 在 user space 會花費大量時間。
write
回傳 Fast Doubling 版本的 kernel space time
read
回傳 Fast Doubling 版本計算的 Fibonacci 值
在計算 fib(0) 會有異常的原因是 __builtin_clzll 的參數不可以為0,因此在計算 fib(0) 時,直接回傳 0 即可解決問題。
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
限定 CPU 給特定的程式使用
使用 isolcpus
Linux 核心起始參數,讓特定的 CPU 核在開機時就被保留下來,設定完成後使用 sudo update-grub
更新 grub 設定檔
設定 NO_HZ 減少影響程式執行的中斷,設定完成後使用 sudo update-grub
更新 grub 設定檔
抑制 address space layout randomization (ASLR)
設定 scaling_governor 為 performance。準備以下 shell script,檔名為 performance.sh
:
之後再用 $ sudo sh performance.sh
執行
設定 SMP IRQ Affinity ,減少目標 cpu 處理 interrupt request ,使用 cpu7 來做此實驗,所以 mask 為 0x7f
設定完成後,雖然還是有些浮動,但可以測量到相對穩定的實驗結果
uppper
紀錄大數較高的 64
位元,lower
紀錄大數較低的 64
位元
依照前面實作, Fast-doubling 需要加法、減法、乘法、左移一位運算,其中大數乘法運算還會使用右移一位運算。
bn_add
加法兩數 upper
與 lower
分別相加,判斷 lower
相加後是否溢位,溢位的話將 upper
加一。
bn_sub
減法兩數 upper
與 lower
分別相減,若 a.lower < b.lower
,代表需要跟 upper
借位,所以 upper
減一。
bn_lshift
左移一位 / bn_rshift
右移一位實作左移一位,將兩數 upper
與 lower
分別左移一位,若 lower
在位移前的最高有效位元為 1
,則 upper
的最低有效位元設為 1
。實作右移一位與左移相似,兩數 upper
與 lower
分別右移一位,若 upper
在位移前的最低有效位元為 1
,則 lower
的最高有效位元設為 1
。
bn_mul
乘法每次將 a
左移一位,並將 b
右移一位,找出 b
中值為 1
的位元,若找到為 1
的位元,則將目前 a
的值累加到 result
,達到類似乘法直式的運算方式。
例如 : a = 0b1010, b = 0b101
a * b = 0b1010 * 0b101 = 0b1010 + 0b101000 = 0b110010
bn_to_str
將大數轉成字串input
為要轉換成字串的大數, num
為最靠近且小於等於 input
的 10
的冪,將 input
不停減掉 num
直到 input < num
,減去的次數即目前 input
最高位的十進位數。
例如 : input = 3021
, 最靠近且小於等於 input
的 10
的冪為 num = 1000
, input
需要減掉 num
3
次才會滿足 input < num
的條件,因此得到最高位的十進位數為 3
,後面的位數以此類推。
digits
紀錄大數的數值,size
紀錄大數使用幾個 uint64_t,alloc
配置幾個 uint64_t 空間。
若 size
超過 alloc
時,代表配置的空間不夠,需要 realloc,BN_MIN_ALLOC(n, s)
將大數 n
重新配置成 s
個 uint64_t 的大小,並確保配置的大小為 4 的倍數個 uint64_t。
BN_SIZE(n, s)
的功能類似,會額外將大數 n
的 size
設為 s
。
bn_add
加法將大數 a
與大數 b
對應的位數相加,若有進位會累加到下一位。為了確保 a = c 與 b = c 時能正確運算不改到 a
或 b
的值,使用 tmp
紀錄結果,最後再將 tmp
複製到 c
。
bn_lshift
左移一位從低位到高位尋訪大數的 digits
,每次左移 1 位,藉由將 digits
右移 63 位獲取該 digits
的最高位,並與下一個 digits
做 OR 運算,將下一個 digits
的最低位設成目前 digits
的最高位。
bn_mul
乘法大數 a
的每個位數與大數 b
的每個位數相乘,將結果紀錄在 tmp
,二個 64-bit 整數相乘會需要 128-bit ,所以使用 GCC Extension __uint128_t
,透過右移 64 位,將較高的 64-bit 存在 tmp
目前位數的下一位,最後再將 tmp
複製到 c
。
bn_to_str
將大數轉成字串基本想法為對大數除以 10 取餘數,反覆對其商除以 10 取餘數,將取得的餘數逐一串接起來,最後所得到的就是該數的十進位表示法。
max_radix
為 1019,相當於 uint64_t 可表示值的範圍中,最大的 10 的冪的值,max_power
為 19,紀錄 10 的冪次。max_radix
,獲得一個 uint64_t 可表示的餘數,再用方法一來取得最終的餘數,重複上述操作直到商等於 0 時停止迴圈。在 sysprog21/bignum 中,初始化大數所 malloc 的大小皆相同,在計算 fib(k) 時,k 越大,所需的空間越多,realloc 的次數也越多。
透過預估 fib(k) 所需的位數,在初始化時就分配足夠的空間,降低 realloc 次數。
根據作業說明,當 為足夠大的正整數時,
將近似值取 2 為底的對數,可得到需要使用的位元數
除以 64 可得到需要使用的 uint64
數量
由下圖能觀察到隨著數字增加,預先分配足夠空間的效果越明顯。
在 sysprog21/bignum/bignum.c 中,macro 使用 do while(0) 將多行內容框起來,我想原因是減少語法錯誤,像是下方在 if 中呼叫 macro,且沒有用大括號括住的情形依舊能正確執行,若 macro 沒有 do while(0) 則會出錯。
在 macro 中不用 if(1) { … } 而是使用 do while(0) 將內容框起來的原因是單純 do while(0) 後可以加分號,因此使用該 macro 時可以較直觀的在後面加分號,還是有其他考量?
在 sysprog21/bignum/format.c 中,為什麼當 radix 不是 2 的冪時,結果需要額外加 2,而不是加 1?