2024 Homework4 (quiz3+4)

contributed by <HotMercury>

第 3 週測驗題

isqrt1: bitwise 操作

在執行第一版 i_sqrt 時嘗試使用 gcc 編譯，有以下錯誤，但如果把 n 變成常數，就可以正常執行，error In using math function in gcc? 可以知道如果使用的是 const 編譯器會最佳化成對應的值，如果要正確執行要加上 -lm link math library.

- 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

第一版的方式 可以得知

$\log n$ 與

$\sqrt{n}$ 間的大小不會影響答案。

這裡做更正我原本以為的作法是找到最靠近且略小於

$\sqrt{N}$ 的方式再繼續找，但現在發現是找到 N 向上取

$lo{g}_2-1$ 這樣可以確保最高位，之後再以 2 的冪逼近。

$${\log }_{2}n<\sqrt{n},n>=16$$

接下來思考如何不透過 log 也可以保有原有的精度，isqrt2 就是透過 shift 方式判斷 MSB 在第幾位。

直式開方

上述 isqrt1 和 isqrt2 都是逐位元搜尋，且乘法成本太高，接下來可以使用 Digit-by-digit calculation 直式開方的方法。

跟著公式實際推演

$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{array}{ll}{c}_m/2+d_m& if{a}_m=2^m\\ c_m/2& if{a}_m=0\end{array}$
• $d_{m-1}=d_m/4$

程式邏輯

• $X_{n+1}=N$
• $c_n=0$ 一開始還沒有值
• $d_n=(2^m{)}^2$

先透過 __builtin_clz 找到 msb, 在依據上述數學式完成，以下為對應代號程式碼

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

2. 使用第二周測驗用到的 __ffs 函式可以應用在 32 位元的參數
   這裡先只用 32 位元，因此先不啟用 #define BITS_PER_LONG 64，這裡用的方式是 binary search 的變形，透過 bitwise 的操作可以減少次數，以 i_sqrt1 為例子，需要一個一個右移，而 binary 只需要以 2 的冪來尋找。
   commit 2fffd11

3. 不使用到 branch，使用 bitwise 的方式
   a. 先將第一個為 1 的位置以後都設成 1
   b. 透過 bitwise 算出總共有多少個 1 bit
   c. total bit - 算出的 bit 數

block 應用到程式碼

我在 block/blk-wbt.c 中找到 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 是一個計算

$\frac{1}{\sqrt{x}}$ 的方法，

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() 之後嘗試理解

Testing 2 : 減少 mod 10 和 div 10 操作

針對字串加法，暴力法可以通過 carry bit 的方式往前累進，所以一次運算會用到一次除法(for carry) 與 mod 運算，接下來參考《Hacker's Delight》我們想用 bitwise 的方式取代 divide and mod operation。
想要透過 bitwise 計算的方式一定是

$\frac{an}{2^N}$ (因為分母要用 shift 的方式)，計算出符合

$1.9\le \frac{19}{x}\le 1.99⟹9.55\le x\le 10$ 目前 a : 13,

$2^N$ : 18，只要在範圍內就可以，( 這裡教材寫只要判定最大的不會超過就好，這個還需要理解 )。
再來我們的目標就是要乘 13 除 128，這裡我一開始想到的是直接使用乘法，但這裡將 13 拆分為 2 進位的方式，以此達到乘 13 的效果，底下為

$\frac{13tmp}{8}$

(tmp >> 3) + (tmp >> 1) + tmp) << 3)

而以下說明一個問題，即右移後，會有部分位元被捨棄，因此要另行處理。並不是很清楚為什麼是拿 q 來右移且要加三個，所以我嘗試用定點數的方式來計算。

- ((((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$

其他的還沒想出來

#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 不要太頻繁