2023q1 Homework2 (quiz2)

tags: `linux2023`

contributed by < Paintako >

測驗一

說明

考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值

原始程式碼是使用了 binary search 的概念去找出最接近且大於等於 2 的冪的值

而改寫後的版本：
首先，給的數值範圍是 64 bit, 且 unsigned
只要把給的數值的 MSB 右邊全部補 1，再 + 1 ，　這樣即可得出最接近且大於等於 2 的冪的值

例如：
數值為 00001001，MSB 之後補 1 後變成 00001111，最後 + 1 得 00010000
但是，如果情況變成原本的數值等於 2 的冪的值，則會得到比正確答案還大的數值
例如：
數值為 00001000，MSB 之後補 1 後變成 00001111，最後 + 1 得 00010000

所以針對以上情況，要結束前需要對原本的數值作 XOR 確保原本數值是 2 的冪的值的情形
例如：
數值為 00001000，MSB 之後補 1 後變成 00001111
和原本的數值做 XOR， 00001000 ^ 00001111 所以答案變成 00000111，故 +1 仍然是正確答案！
經 paulpeng 提醒後，仍然需要一個 if 來判斷原本數值是否 2 的冪的值的情形，依舊會有一個 branch 的 overhead

程式碼應該改寫成：

uint64_t next_pow2(uint64_t x)
{
    uint64_t y = x;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 8;
    y |= y >> 16;
    y |= y >> 32;
    return x%y==0?y+1:(y^x)+1; // if x%y==0 return y+1, else return (y^x)+1
}

為了解決這個 branch 的 overhead，可以把原本數值 -1 使得原本等於 2 的冪的數值不等於 2 的冪，解決了這個不必要的 branch

uint64_t next_pow2(uint64_t x)
{
    uint64_t y = x-1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 1;
    y |= y >> 8;
    y |= y >> 16;
    y |= y >> 32;
    return y + 1 ;
}

延伸問題：

使用 __builtin_clzl 改寫
此函式返回 leading 0-bits in x ，得知 leading 0 的數量後, 將 64 - leading 0-bits數 算出後再對1做算數位移，即可得此數最接近且大於等於 2 的冪的值

但同樣需要考慮此數原本就是 2 的冪的情況，如果算出的大於等於 2 的冪的值 % 原本的值＝0 的話代表此數原本就是 2 的冪

uint64_t func(uint64_t x)
{
    int lead_zero = __builtin_clz(x);
    int cmp = 1<<(64-lead_zero); 
    
    if ((cmp%x) != 0 ) 
        return cmp;
    return x;
}

在 Linux 核心原始程式碼找出類似的使用案例並解釋
使用 $ grep -r "<<" ./include/linux/ 來找出相似程式碼

有一個看起來也是跟數字處理相關的案例 ./include/linux/log2.h

#define const_ilog2(n)

這是一個定義了常數log2的C程式碼的巨集(macro)。對於給定的正整數 n，該 define 返回最大的 k，使得 2^k ≤ n，即 2 的 k 次冪不超過 n。

這個 define 使用了GCC inline function __builtin_constant_p(n) ，該函數在編譯時會計算是否為常數，如果是，則返回 true，否則返回 false。如果 n 是一個常量，那麼 define 使用二進制運算來快速找到最大的 k。如果 n 不是常量，則使用逐位檢查的方法來找到 k。

From Chatgpt

測驗二

原本的程式碼中已經有提示了，如果這個數字是 2 的冪的話，則 len++, 此 len 表示 ans 的位移量

例如：

n	2 的冪	len	rst
1	yes	1	1
2	yes	2	101
3	no	2	10111
4	yes	3	101110100

開發過程中，原本的程式碼如下：

if (!(i & (i-1)))
            len++;
        ans = (i | (ans<<(len)+1)) % M;

其中 i & (i-1） 用於判斷此數是否是 2 的冪
但是這是錯的！因為忘記了其實 1 也是 2 的冪（ $2^{0}$ )，原本的寫法中忘記了這點才 + 1 的，故正確的版本如下

if (!(i & (i-1)))
            len++;
        ans = (i | (ans<<(len))) % M;

嘗試使用 __builtin_{clz,ctz,ffs} 改寫
把 (i & (i-1) 改成 (__builtin_ffs(i) == (64 - __builtin_clzl(i)) 即可

但是這樣改寫後會變得比較快嗎？ Todo: 使用 perf 來判斷 cycle數的增減情況

測驗三

SIMD: Single Instruction Multi Data
指在同個 clock cycle 中，同時處理多個向量
例如：

沒有支援 SIMD 執行 $B * = 2$ , 其中 B 是 1*n 的向量

Vector B	Clock Cycle 1	Clock Cycle 2	Clock Cycle 3
[1,2,3,4]	[2,2,3,4]	[2,4,3,4]	[2,4,6,4]

有支援 SIMD:

Vector B	Clock Cycle 1
[1,2,3,4]	[2,4,6,8]

而 SWAR 表示在 同一個 Register 中做 SIMD

在筆記中的程式碼中，發現了一些可能是白作工的部份

static inline uint64_t bit_compound(uint32_t x, uint32_t y) {
    return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}

這裡的 (y + 0L) & (-1L >> 32)
y + 0L 還算好理解，要把 y 擴充成 64 bit
但是 -1L >> 32 這裡就匪夷所思了，即便 -1L 寫成二進位是 64個 1，對這 64 個 1 做 32次算數位移仍然是 64個 1，而且跟 y + 0L 做 and 也是白做工，因為擴充完 32 bit 的 y+0L 前半部份也全部都是 0， 0 跟任何東西做 and 都是 0 ，所以應該可以把程式碼改寫成：

static inline uint64_t bit_compound(uint32_t x, uint32_t y) {
    return ((0L + x) << 32) | (y + 0L);
}

參考以下程式：

#include <stddef.h>
#include <stdint.h>

size_t count_utf8(const char *buf, size_t len)
{
    const int8_t *p = (const int8_t *) buf;
    size_t counter = 0;
    for (size_t i = 0; i < len; i++) {
        /* -65 is 0b10111111, anything larger in two-complement's should start
         * new code point.
         */
        if (p[i] > -65)
            counter++;
    }
    return counter;
}

這段程式在做的事情是：找出一個字串中所有合法的 UTF-8 字元組
其中， magic number 為何是 -65?
因為對應到 ASCII 的規則，除了首位元組外，後續位元組皆是以 10xx xxxx 的形式存在
故只要某一個數字大於 1011 1111 的話，那此數必不會是後續位元組，~~而是一個新的 ASCII !~~ （不是新的 ASCII， ASCII 的 MSB 皆是 0)

使用 SWAR 改寫程式碼：
參考小考中的提示，如果某個 byte 可以寫成 10xx xxxx 的形式，那此 byte 必是某 ASCII 的後續位元組，並且可以將這種表達方式寫成 not bit6 and bit7，也就是第七個 bit 必 1，第六個 bit 必 0，找出所有這種特殊 pattern 的位元組

只保留把每一個 byte 中的 6、7 bit ，其餘 bit 全部設為 0 ，再使用 __builtin_popcount 即可得答案

也可參考老師上課的說法，"找到 10 交接處"

上述方式用 SWAR 的方式呈現出來
首先， qwords 代表一次讀取的 byte 數，這裡指定 uint64，代表一次讀取 8 byte，用意是配合 64 bit 系統，當 pointer ++ 時，移動的步伐等於 64 bit，也就是每一次比較的 Byte 數為 8

Note: 即便使用者的系統是 32 bit 的系統，仍存在 64 bit 的操作（例如乘法）

這邊 len 沒有更詳細的說明，只能用推測的，因為是改寫自原本的題目，從下面程式碼來推測，是整個字串的字元組（ Bytes ) 大小

len >> 3 的目的在於把無法湊到 8 個 byte的去除掉（因為無法對它做 64 bit 的運算），故減去，所以 *end 代表了傳入的字串有多少的 Byte!

const uint64_t *end = qword + len >> 3;

以上程式碼，根據 C語言規格書（ from ChatGpt )，得知符號的結合律優先度，故會先做 加法 再做 >>

>> 3 代表以 8 個 byte為單位

每一次都對 64 bit 做 SWAR，結束後統計 1 的個數即可得知這 8 Byte 中包含幾個後續位元組
當傳入的字串長度不是 Byte 的倍數時（ i.e. 字串 / 8 != 0 )，則需要考慮剩餘的 Byte 中是否含後續位元組

count = (1 << 3) * (len / 8)  - count;

首先， len/8 代表 "可以完整湊出 8 Bytes的個數"，乘上 8 bit 即可得完整的位元組數，再減去 continuation byte 即可得目前合法的 UTF-8 數

count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

這段 len & 7 很好理解，原本剩下的 Byte 數量不足 8，所以跟 7 做＆，可以得到剩餘的 Byte數
而後面的 if/ else 也很好理解，將剩下的範圍丟入 count_utf8 可得後續位元組數量

測驗四

Note:
x <<= 1 可以寫成 x = x<<1

參考： TimChen731

程式碼要的是：給定一個 pattern ，不斷向右移的過程中如果有符合該 pattern 就 return true
該 pattern 是只有MSB是 1 其餘皆是 0

字串要符合該 pattern ，並且不斷向左移動時不跳出 for 迴圈的話，那此字串必須符合:
MSB是1 且 1 後續不能有 0

先對 x 做 not，再 +1 的話，則跟原本的字串做 xor 後原本字串中最右邊的 1 會消失
例如：

原本	11111000
not	00000111
not+1	00001000
原本 xor (not+1)	11110000

在和原本的字串做比較，如果比較小的話代表它符合此 pattern

原本	11111010
not	00000101
not+1	00001010
原本 xor (not+1)	11110010

在和原本的字串做比較，如果比較大的話代表它不符合此 pattern

2023q1 Homework2 (quiz2)

tags: linux2023

測驗一

說明

測驗二

測驗三

測驗四

Read more

Assignment3: single-cycle RISC-V CPU

交接問題紀錄

2023q1 Homework7 (ktcp)

碩0

tags: `linux2023`