# 2024 Homework4 (quiz3+4) contributed by <HotMercury> ## 第 3 週測驗題 ### isqrt1: bitwise 操作 在執行第一版 `i_sqrt` 時嘗試使用 `gcc` 編譯，有以下錯誤，但如果把 n 變成常數，就可以正常執行，[error In using math function in gcc?](https://stackoverflow.com/questions/15737932/error-in-using-math-function-in-gcc) 可以知道如果使用的是 const 編譯器會最佳化成對應的值，如果要正確執行要加上 `-lm` link math library. ```diff - int msb = (int)log2(n); + int msb = (int)log2(16); ``` ``` $ gcc sqr_t.c /usr/bin/ld: /tmp/ccmYLpqw.o: in function i_sqrt: sqr_t.c:(.text+0x23): undefined reference to log2 ``` [第一版的方式](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-1) 可以得知 $\log{n}$ 與 $\sqrt{n}$ 間的大小不會影響答案。 > 這裡做更正我原本以為的作法是找到最靠近且略小於 $\sqrt N$ 的方式再繼續找，但現在發現是找到 N 向上取 $log_2 -1$ 這樣可以確保最高位，之後再以 2 的冪逼近。 $$ \log_2{n} < \sqrt{n}, n >= 16 $$ ![image](https://hackmd.io/_uploads/SygUE2HBRp.png) 接下來思考如何不透過 `log` 也可以保有原有的精度，isqrt2 就是透過 shift 方式判斷 MSB 在第幾位。 #### 直式開方 上述 isqrt1 和 isqrt2 都是逐位元搜尋，且乘法成本太高，接下來可以使用 [Digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 直式開方的方法。 跟著[公式](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-1)實際推演 $P_0$ 及為我們想要求的平方根，所以我們從最高位慢慢遞減 $P_m$。 $$ P_0 = a_n + a_{n-1} + ... + a_0 $$ 但不想要透過成本過高的乘法，因此使用上一輪差值 $X_{m-1}$ 減去($P_m^2 - P_{m+1}^2$) : $Y_m$ $Y_m$ 又由以下組成 - $c_{m-1} = \begin{cases} c_m/2 + d_m & if \ a_m = 2^m \\ c_m/2 & if \ a_m = 0 \end{cases}$ - $d_{m-1}= d_m/4$ 程式邏輯 - $X_{n+1} = N$ - $c_n = 0$ 一開始還沒有值 - $d_n = ({2^m})^2$ 先透過 `__builtin_clz` 找到 msb, 在依據上述數學式完成，以下為對應代號程式碼 ```c int i_sqrt3(int n) { if (n <= 1) /* Assume n is always positive */ return n; int c = 0; for (int d = 1UL << ((31 - __builtin_clz(n)) & ~1UL); d; d >>= 2) { int y = c + d; c >>= 1; if (n >= y) n -= y, c += d; } return c; } ``` #### 改寫第三版程式 1. 直接透過 C library 的方式呼叫 `ffs` [commit 575c64b](https://github.com/HotMercury/2024_linux_quize/commit/575c64bd18918b7263775221282c5882511ea94a) 2. 使用[第二周測驗](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)用到的 `__ffs` 函式可以應用在 32 位元的參數 這裡先只用 32 位元，因此先不啟用 #define BITS_PER_LONG 64，這裡用的方式是 binary search 的變形，透過 bitwise 的操作可以減少次數，以 `i_sqrt1` 為例子，需要一個一個右移，而 binary 只需要以 2 的冪來尋找。 [commit 2fffd11](https://github.com/HotMercury/2024_linux_quize/commit/2fffd11fe8dc6d897a86ed66c012efa6d289f8b7) 3. 不使用到 branch，使用 bitwise 的方式 a. 先將第一個為 1 的位置以後都設成 1 b. 透過 bitwise 算出總共有多少個 1 bit c. total bit - 算出的 bit 數 #### [block](https://github.com/torvalds/linux/tree/master/block) 應用到程式碼 我在 [`block/blk-wbt.c`](https://elixir.bootlin.com/linux/latest/source/block/blk-wbt.c#L409) 中找到 `rwb_arm_timer` 會使用到 `int_sqrt`，接下來要嘗試理解這個 function 在做什麼。為了測試我能不能有觀察 linux kernel 的 sense，我先單純看 function 來猜測，以 block 底下來說 rwb 可能就是 request write back，接下來 arm 跟 timer 就是 arm 架構下 write back 的時間，以上猜測時間結束。 **trace code** 第一步嘗試去找誰呼叫了這個 function，`wb_timer_fn` and `wbt_wait`但可惜的是資料結構太多且不熟悉用途，所以從 `rwb_arm_timer` 程式碼下手，先拿到 `struct rq_depth` 可以從裡面得知會有兩種情況來調整 window size(這裡還不知道是什麼，目前猜是時間) - 當 scale_step > 0 ：會算出新的 window size - 否則照舊 在計算新的 window size 裡註解有提到 `We should speed this up` 所以目前是認為這個是特定方式的運算，之後提到 [fast integer inverse square](https://en.wikipedia.org/wiki/Fast_inverse_square_root) 是一個計算 $\frac{1}{\sqrt{x}}$ 的方法， ```c static void rwb_arm_timer(struct rq_wb *rwb) { struct rq_depth *rqd = &rwb->rq_depth; if (rqd->scale_step > 0) { /* * We should speed this up, using some variant of a fast * integer inverse square root calculation. Since we only do * this for every window expiration, it's not a huge deal, * though. */ rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4, int_sqrt((rqd->scale_step + 1) << 8)); } else { /* * For step < 0, we don't want to increase/decrease the * window size. */ rwb->cur_win_nsec = rwb->win_nsec; } blk_stat_activate_nsecs(rwb->cb, rwb->cur_win_nsec); } ``` 看到一個很有趣的 patch [blk-wbt: fix a divide-by-zero error in rwb_arm_timer()](https://lkml.indiana.edu/hypermail/linux/kernel/2104.2/01733.html) 之後嘗試理解 ### Testing 2 : 減少 mod 10 和 div 10 操作 針對字串加法，暴力法可以通過 carry bit 的方式往前累進，所以一次運算會用到一次除法(for carry) 與 mod 運算，接下來參考《[Hacker's Delight](http://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf)》我們想用 bitwise 的方式取代 divide and mod operation。 想要透過 bitwise 計算的方式一定是 $\frac{an}{2^N}$ (因為分母要用 shift 的方式)，計算出符合 $1.9 \leq \frac{19}{x} \leq 1.99 \Longrightarrow 9.55 \leq x \leq 10$ 目前 a : 13, $2^N$ : 18，只要在範圍內就可以，( 這裡教材寫只要判定最大的不會超過就好，這個還需要理解 )。 再來我們的目標就是要乘 13 除 128，這裡我一開始想到的是直接使用乘法，但這裡將 13 拆分為 2 進位的方式，以此達到乘 13 的效果，底下為 $\frac{13tmp}{8}$ ```c (tmp >> 3) + (tmp >> 1) + tmp) << 3) ``` 而以下說明一個問題，即右移後，會有部分位元被捨棄，因此要另行處理。並不是很清楚為什麼是拿 q 來右移且要加三個，所以我嘗試用定點數的方式來計算。 ```diff! - ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) // 使用 Q3 的方式 + q = n + (n << 2) + (n << 3); + q = q + (1 << (3 - 1)); ``` 如何解出以下的 code - $x = \frac{4}{5} \times in$ - $q = \frac{17}{16} \times x$ 其他的還沒想出來 ```c #include <stdint.h> void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod) { uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */ uint32_t q = (x >> 4) + x; x = q; q = (q >> 8) + x; q = (q >> 8) + x; q = (q >> 8) + x; q = (q >> 8) + x; *div = (q >> CCCC); *mod = in - ((q & ~0x7) + (*div << DDDD)); } ``` #### 解析 CPU 週期數量 ## 第 4 週測驗題 ### Testing 3 #### rbtree `udpate` 不要太頻繁