Try   HackMD

2025q1 Homework4 (quiz3+4)

contributed by < HeatCrab >

第三周測驗一

  • 解釋上方程式碼運作原理

    首先定義 mpi 的資料型別 mpi_t ,接著定義以下四個記憶體操作函式:

    1. mpi_init:初始化 mpi_t,將 data 設為 NULL,容量設為 0。
    2. mpi_clear:釋放 data 的內存。
    3. mpi_enlarge:擴展 data 數組到指定容量,並填充新分配的區域為 0。
    4. mpi_compact:去除高位為 0 的冗餘空間,縮減容量並重新分配記憶體空間。

    接下來是4個基本操作的函式:

    1. mpi_set_u64

      首先呼叫 ceil_div 函式,作向上取整除法,原理如下:
      在整數除法中,

      n/d 是向下取整。例如:
      5/2=2
      (實際是
      2.5
      )。
      要向上取整,必須補償餘數部分。公式是
      (n+d1)/d
      ,原因是

      • 如果
        n
        能被
        d
        整除,則
        n+d1
        還是會落在
        n/d
        的範圍中。
      • 如果有
        n
        除以
        d
        有餘數,則
        n+d1
        會被推到下一個整數。

      接著回傳 n = 64d = 31 。 選擇 d = 31 的理由是 uint32_t 是32位元,為了防止未來在實作乘法時有溢位的情況發生,所以減少一位元,以方便計算。
      再來進入第一個 for 迴圈,透過定義好的 INT_MAX ,對 op 實作 mask 的動作,位數同樣是31位。將 mask 好的資料儲存至 data 後,再把 op 右移 31 位元,重複此動作,直到沒有容量(capacity)。
      最後再使用第二個 for 迴圈將 rop 剩下 capacity 中的 data 賦值為

      0

    2. mpi_mul_naive

      這個函式使用的是樸素乘法,也就是我們最一開始學的乘法。
      首先定義 capacity 變數為被乘數(op1)與乘數(op2)兩個數的 capacity 總和。這樣定義由樸素乘法可以知道,舉例二位數最大

      99
      ×
      三位數最大的
      999

      ​​​​​​​​   99
      ​​​​​​​​× 999
      ​​​​​​​​------
      ​​​​​​​​  891  (99 × 9)
      ​​​​​​​​ 891   (99 × 9, 左移一位)
      ​​​​​​​​891    (99 × 9, 左移兩位)
      ​​​​​​​​------
      ​​​​​​​​98901
      

      可以得到最大值

      98901 ,共五位數。那在我們 mpi_mul_naive 函式實作中的差別在於,我們一個 capacity 中存放的有31位元,但這不影響兩者乘積的位數最多就是兩者 capacity 相加的值。
      在初始化 tmp 之後,進入雙重 for 迴圈,首先使用被乘數的第1位,有就是 data[0],依序乘上乘數的每一位,並將結果存到變數 r 中。接著再使用一個 for 迴圈來將 r 切分成每31位元儲存。若是有進位的情況發生,就將進位值存放到 c 變數裡。重複此動作,直到乘法完成。過程就如同我們小學學的,以及上圖的
      99×999
      一樣。
      最後使用 mpi_set 將 tmp 的值複製給 rop 完成乘法操作,並使用函式將記憶體釋放。

    3. mpi_fdiv_qr

      實作上類比長除法。首先將被除數 n 與除數 d 使用函式複製為 n0d0 防止更改到原本的變數。定義商數 q 與餘數 r
      透過 mpi_sizeinbase 函式找到被除數 n0 的最高位數,因為要如同我們學的長除法一樣,從最左邊,也就是最高位數開始做。接著進入 for 迴圈,透過定義餘數 r 的值,與判斷 r 跟除數 d 的關係來決定商數,過程上使用位元計算來模擬實作長除法時,判斷要重哪一位開始除的過程。
      為了更具體的說明,以下舉例 n = 0b1101d = 0b11 為例子:

      嘗試過使用 graphviz 說明,但是做的圖片不是很理想,所以最後還是決定使用文字說明。

      因為 start = 3 ,所以迴圈從 i = 3 開始。

      1. i = 3
        一開始 r
        0b0
        ,所以在移項(乘二)後,仍舊為零。
        因為 n 的第三位不為零,所以將 r 的第0位設為1,變成
        0b1

        比較餘數與除數的大小,因為餘數沒有大於除數,所以不做任何動作,繼續迴圈。
      2. i = 2
        此時 r
        0b1
        ,在移項(乘二)後,變成
        0b10

        因為 n 的第二位依舊不為零,所以將 r 的第0位設為1,此時 r
        0b11

        比較餘數與除數的大小,因為餘數大於等於除數,所以將餘數 r 扣去除數,並將 q 的第二位設為1。
        此時 r
        0b00
        q
        0b0100
      3. i = 1
        r 現在又為
        0b0
        ,所以在移項(乘二)後,仍舊為零。
        因為 n 的第三位為零,所以無動作。
        再比較餘數與除數的大小,餘數沒有大於除數,不做任何動作,繼續迴圈。
      4. i = 0
        r 依舊為
        0b0
        ,所以移項(乘二)後,仍舊為零。
        因為 n 的第零位不為零,所以將 r 的第0位設為1,此時 r
        0b1

        比較餘數與除數的大小,因為餘數沒有大於除數,所以不做任何動作,繼續迴圈。
      5. 迴圈結束,得到以下結果:
        r =
        0b1

        q =
        0b100

      用十進位除法驗證一下結果:

      13÷4=3 ...1結果正確。

    4. mpi_gcd

      透過遞迴呼叫的方式實作輾轉相除法來找最大公因數。
      在程式碼的一開始確認 op2 是否為零,若是 op2 為零,則表示輾轉相除法完成,此時的 op1 即為所求,將 op1 賦值給 rop 結束函式。
      除法的部分是透過 mpi_fdiv_qr 來計算。

 

  • 這項實作依賴遞迴呼叫,請避免使用並降低記憶體開銷

 

  • 改進最大公因數的運算效率

 

第三周測驗二

  • 解釋上方程式碼運作原理

    程式上使用了 SWAR 的手法,來實現 memchr 函式要做的事情。memchr 的原理十分簡單,就是透過 while 迴圈來找到目標 c 。那 SWAR 簡單來說,就是透過並行處理的方式,來減少運算上的成本。先使用測驗題說明中提供的程式碼來理解。
    原先的 both_odd 函式就是跟將 xy 兩個要比較的變數,先跟1作位元運算 and ,透過判斷最小位數是否為1,來決定是否為奇數。再使用邏輯運算 and 來判斷是否都是奇數。
    使用 SWAR 方法則是透過 bit_compound 函式,使用以下的位元運算式,將 xy 這兩個32位元的變數結合在一起。

    ​​​​    return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
    

    以下是 0L 的示意圖,L 表示的是 long 數據型別。圖片中將4個 bits 劃分為一位元。總共有64個0。

    
    
    
    
    
    
    step1_0L
    
    
    
    n0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    
    
    

    先加上變數 x ,接著左移32位元,得到上32位元等於 x 變數,下32位元為0的64位元數。

    
    
    
    
    
    
    step2_0L_plus_x
    
    
    
    n0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    x0
    
    x1
    
    x2
    
    x3
    
    x4
    
    x5
    
    x6
    
    x7
    
    
    
    n1
    
    x0
    
    x1
    
    x2
    
    x3
    
    x4
    
    x5
    
    x6
    
    x7
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    
    
    n0->n1
    
    
      shift
    
    
    
    

    接著是先以同樣的動作操作 y 變數,得到如下圖:

    
    
    
    
    
    
    step_1y
    
    
    
    n0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    y0
    
    y1
    
    y2
    
    y3
    
    y4
    
    y5
    
    y6
    
    y7
    
    
    
    

    這邊使用 -1L , 表示的是64位元全1,如圖所示:

    
    
    
    
    
    
    step1_minus_oneL
    
    
    
    n0
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    1
    
    
    
    

    透過右移32位元,並且與 y 變數做位元運算 and ,就可以得到一個上32位元為零,下32位元為 y 的64位元數。

    
    
    
    
    
    
    step_y_result
    
    
    
    n0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    y0
    
    y1
    
    y2
    
    y3
    
    y4
    
    y5
    
    y6
    
    y7
    
    
    
    

    最後將新的 xy 變數做位元運算 or ,實現加法的動作,就得到一個上32位元為 x ,下32位元為 y 的64位元數 xy
    在使用 both_odd_swar 函式前,先定義 SWAR_ODD_MASK 變數。首先使用 1L ,表示的是前63位元為0,最低位,也就是第0位為1。

    
    
    
    
    
    
    step1_1L
    
    
    
    n0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0001
    
    
    
    

    透過左移32位元,將1的位置移到 xy 中上32位元 x 的第0位,來判斷 x 是否為奇數,接著加上1,來判斷 xy 中下32位元 y 是否為奇數。

    
    
    
    
    
    
    step_SWAR_ODD_MASK
    
    
    
    n0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0001
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0
    
    0001
    
    
    
    

    在函式中使用位元運算 and ,如果是奇數,那經過運算後的 xy 會跟 SWAR_ODD_MASK 一致,此時回傳1,表示 true ,否則回傳0表示 false。

    回到函式 memchr_opt , 首先先轉換 str 的型別變成 unsigned char (一位元組),並將其記憶體位置定義為變數 src。同樣將 c 轉換成 unsigned char 資料型別的 d
    透過 while 迴圈與 UNALIGNED 函式判斷 src 變數是否有對齊 long 這個資料型別。透過位元運算 and 判斷傳入的變數 X 是否是 (sizeof(long) - 1) 的倍數,若是有對齊則位元運算結果會是0,否則回傳1,繼續 while 迴圈,直到 src 對齊。
    接下來即是我們實作 SWAR 的部分。先判斷字串長度是否有足夠的必要使用 SWAR 來實作。確認字串長度夠大後,定義一個 unsigned long 的變數 asrc 來加快尋找與判斷的字串位元數。然後將 d 變數依據 LBLOCKSIZE 大小的不同擴充,舉例 d

    0x87,根據程式碼步驟:

    1. d 先左移8位,d =
      0x8700
    2. d 作位元運算 or , 得到 mask =
      0x0000000000008787
    3. mask 再左移32位,接著與自己做位元運算 or ,得
      0x0000000087878787
    4. 依據 LBLOCKSIZE 的大小繼續左移,假設依據規格書, long 的資料型別大小是8,mask 擴充至64位,我們得到 mask
      0x8787878787878787

    如果字串長度比 LBLOCKSIZE 大,那麼呼叫 DETECT_CHAR 函式。
    DETECT_CHAR 函式會先將傳入的變數 Xmask 作 XOR,如果 X 字串包含要尋找的 d 字串的話,那 XOR 的結果就會有0位元組。接著將這個包含0位元組的結果傳入 DETECT_NULL 函式中判斷是否有零位元組。

    TBD

 

  • 比較 Linux 核心原本 (與平台無關) 的實作和 memchr_opt,設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響

 

  • 研讀 2022 年學生報告,在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作,跟上述程式碼比較,並嘗試舉出其中的策略和分析

 

第四周測驗一

  • 在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處,並探討其原始程式碼

 

  • 設計實驗來分析 Fast CRC32 提出的手法 (要涵蓋 branchless 和查表的變形),並與硬體的 CRC32 指令效能進行比較。

 

  • 以 x86-64 或 Arm64 為探討標的,說明 Linux 核心如何使用硬體加速的 CRC32 指令

 

第四周測驗二

 

  • 探討定點數的使用和其精確度

 

  • 改進 MIDI 一閃一閃亮晶晶的音效輸出

 

第四周測驗三

  • 解釋上述程式碼運作原理

 

  • 學習 jserv/ttt 程式碼,在不使用 (n)curses 一類現成的函式庫前提下,改進網路聊天室的文字呈現介面

 

  • 在既有的程式碼之上,實作帳號登入 (login) 及基本管理功能,並該有線上與否的提示,留意 ping value 的處理機制