2023q1 Homework3 (quiz3)

contributed by < yanjiew1 >

GitHub
題目連結

實驗環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         3400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3600.00

測驗 1

可改進的地方：

• 紅黑樹實作內部使用的函式除了宣告為static 外，也可以宣告為 inline ，來改進效能，因為函式呼叫有成本。例如： cmap_rotate_left 、 cmap_rotate_right 、 cmap_l_l 、 cmap_l_r 、 cmap_r_l 、 cmap_r_r 等。

後來看了一下 Linux coding style ， Linux 不鼓勵為了加速就把函式宣告為 inline 。只有大約二到三行的函式再宣告為 inline 就好。實際上 GCC 在沒有宣告 inline 的情況下，也會為了優化去自動 inline 一些函式。

測驗 3

Linear feedback shift register (LFSR) 的運作原理

在維基百科對 LFSR 有這樣的定義：

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. 

故 LFSR 是一個在狀態改變時，會向右位移的 register ，向右位移時，最左邊的輸入位元，是由目前原本 register 內狀態取一些 bit 出來，並透過線性方式組合。

維基百科有下面這張圖：

下一個狀態是前一個狀態每一個位元向右移，最左邊輸入的 bit ，是由原本狀態中第 11 、 13 、 14 、 16 個 bit 透過 XOR 運算得到的。

最左邊輸入位元怎麼組合沒有明確定義，只要是由原本狀態的線性組合即可。

參考資料：

• Wikipedia: Linear-feedback shift register

程式碼運作原理

程式會建立 120 個初始值為 0 的 bucket ，然後跑

$2^{20}$ 次迴圈，每次迴圈會透過 LFSR 從 0 ~ 119 任選一個隨機數作為 bucket 編號，把對應的 bucket 編號值加一。

一開始程式定義了一個 LFSR 的操作：

/* Implementation of LFSR (linear feedback shift register)
 * on uint64_t using irreducible polynomial x^64 + x^61 + x^34 + x^9 + 1
 * (On 32 bit we could use x^32 + x^22 + x^2 + x^1 + 1)
 */
static void lfsr(uint64_t *up)
{
    uint64_t new_bit =
        ((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u;
    /* don't have to map '+1' in polynomial */
    *up = ((*up) >> 1) | (new_bit << 63);
    /* shift *up by 1 to RIGHT and insert new_bit at "empty" position */
}

new_bit 就是在計算要放在最左邊的輸入位元。由程式可知，輸入位元由（由右往左數，最右邊為 0）第 0 、3、30、55 位元進行 XOR 運算組成。

再把 *up 向右移一位，把 new_bit 放在最左邊空出的一位，就完成了。

下面定義了一個表格 log_table_256 ，其輸出數值為輸入 index 取

${\log }_2$ 的值。為了避免重複填寫同一個數值，這裡還定義了一個巨集 _ 巨集會把同一個數字複製 16 份，中間用 , 隔開。

static const char log_table_256[256] = {
#define _(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1,   0,    1,    1,    2,    2,    2,    2,    3,    3,    3,
    3,    3,    3,    3,    3,    _(4), _(5), _(5), _(6), _(6), _(6),
    _(6), _(7), _(7), _(7), _(7), _(7), _(7), _(7), _(7),
#undef _
};

#undef _

log2_64 函式是針對傳入的 64-bit 整數，計算其

${\log }_2$ 的值，並取其整數部份。運作原理類似二分搜尋法，找到最高位的位置。

/* ASSUME x >= 1
 * returns smallest integer b such that 2^b = 1 << b is >= x
 */
uint64_t log2_64(uint64_t v)
{
    unsigned r;
    uint64_t t, tt, ttt;

    ttt = v >> 32;
    if (ttt) {
        tt = ttt >> 16;
        if (tt) {
            t = tt >> 8;
            if (t) {
                r = 56 + log_table_256[t];  // AAAA
            } else {
                r = 48 + log_table_256[tt];  // BBBB
            }
        } else {
            t = ttt >> 8;
            if (t) {
                r = 40 + log_table_256[t];  // CCCC
            } else {
                r = 32 + log_table_256[ttt];  // DDDD
            }
        }
    } else {
        tt = v >> 16;
        if (tt) {
            t = tt >> 8;
            if (t) {
                r = 24 + log_table_256[t];  // EEEE
            } else {
                r = 16 + log_table_256[tt];  // FFFF
            }
        } else {
            t = v >> 8;
            if (t) {
                r = 8 + log_table_256[t];  // GGGG
            } else {
                r = 0 + log_table_256[v];  // HHHH
            }
        }
    }
    return r;
}

若搭配測驗 4 的 bitwise 操作，可簡化為

uint64_t log2_64(uint64_t x)
{
    uint64_t r, shift;

    r = (x > 0xFFFFFFFFL) << 5;
    x >>= r;
    shift = (x > 0xFFFF) << 4;
    x >>= r;
    r |= shift;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return (r | shift | x >> 1);
}

或是透過 __builtin_clz64 來加速：

uint64_t log2_64(uint64_t v)
{
    return 63 - __builtin_clz64(v);
}

---

bucket_number ，會透過傳入的隨機數 x 來選取一個 bucket 。

其中 mask111 ，為二進位有效位數全為 1 且位元數為 bucket 位元數的整數。 mask011 則為二進位有效位數全為 1 且位元數為 bucket 位元數少 1 的整數。故可知道 mask111 >= bucket number > mask011 。

leq 則判斷對 x & mask111 是否小於 bucket 數。針對 leq 的結果，有以下產生的方式：

• 若 x & mask111 小於 bucket 數 ，則結果為 x & mask111 ，等價於 x % N_BUCKETS 。
• 若 x & mask111 大於 bucket 數，則結果為 (x >> (N_BITS + 1)) & mask011 ，即取 x 的較高位數作為隨機數，然後再跟 mask011 做 AND 運算，確保取得的數小於 bucket 數值。

/* n == number of totally available buckets, so buckets = \{0, ...,, n-1\}
 * ASSUME n < (1 << 32)
 */
unsigned int bucket_number(uint64_t x)
{
    uint64_t mask111 = (1 << (N_BITS + 1)) - 1;
    uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */

    unsigned char leq = ((x & mask111) < N_BUCKETS);
    /* leq (less or equal) is 0 or 1. */

    return (leq * (x & mask111)) +                         // IIII
           ((1 - leq) * ((x >> (N_BITS + 1)) & mask011));  // JJJJ
    /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
     * '... & mask011' guarantees that the result is less or equal N_BUCKETS.
     */
}

雖然註解中這樣寫 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity. ，若看程式執行的結果，產生的隨機數還是會有偏差。前 64 個 bucket 明顥比較多次被選中。

---

fill_buckets 會跑 1 << 20 次迴圈（可以從 main 函式得知傳入的 iterations 值），每一次透過 bucket_number 選取一個 bucket ，把選中的 bucket 數值加 1 。之後透過 LFSR ，產生下一組隨機數，再重複進行。

void fill_buckets(unsigned int *buckets, unsigned int iterations)
{
    uint64_t x = 0x98765421b16b00b5;
    unsigned char lfsr_iter = (N_BITS << 1);

    for (uint64_t i = 0; i < iterations; i++) {
        unsigned int tmp_bucket = bucket_number(x);
        *(buckets + tmp_bucket) = *(buckets + tmp_bucket) + 1;

        // 'turn handle' on LFSR lfsr_iteration-times!
        unsigned char ell = 0;
        while (ell < lfsr_iter) {
            lfsr(&x);
            ell++;
        }
    }
}

---

測驗 4

原理解說

原理是類似 binary search 的方式實作。因為要取

$\lceil lo{g}_2(x)\rceil$ ，故一開始先對 x 減去 1 ，就能直接用

$\lfloor lo{g}_2(x-1)\rfloor$ 二進位的值，算出

$\lceil lo{g}_2(x)\rceil$ 的值。

程式中，使用 r 作為記錄總共向右移的 bits 數， shift 則是暫存要向右移多少 bits 的結果。

這段程式會先判斷 x 是否大於 0xFFFF ，若大於 0xFFFF 則代表其最高位在第 31 ~ 16 bit 之間，則需向右移 16 bits ，把接下來要檢索的部份放到右邊的 0~15 bits 之間。

在這裡 r 記錄向右移動的次數，用來推算最後

$\lceil lo{g}_2(x)\rceil$ 的值。

r = (x > 0xFFFF) << 4;                 
x >>= r;

前面已經把檢索範圍縮小到 16-bits 。x > 0xFF 成立時，代表最高位在 8 ~15 bits 之間，則要向右移 8 個 bits 。 shifts 的值就是要向右移的 bits 數，而 r 則記錄著總共向右移的次數， r |= shift; 會把先前向右移的次數和這次向右移的次數加起來。這裡用 | 是因為 r 是 1 的 bits 不會和 shift 重疊。

shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;

檢索範圍已縮小到 0 - 7 bits 。 x > 0xF 成立時，代表最高位在 4 ~ 7 bits 之間，則要再向右移 4 個 bits 。 shift 的值是要向右移的 bits 數。 r 則把先前已經向右移的 bits 數和現在的 shift 加總，為至目前為止向右移的 bits 數。

shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;

檢索範圍已縮小到 0 - 3 bits。 x > 0x3 成立時，代表最高位在 2 ~ 3 bits 之間，則要向右移 2 個 bits 。 shift 的值是要向右移的 bits 數。

shift = (x > 0x3) << 1;
x >>= shift;

檢索範圍已縮小到 0 - 1 bits 了。而前面因為 r 沒有跟 shift 做 bitwise or 運算，把向右移的次數加總，故在 return 時，要先讓 r 跟 shift 做 bitwise or 運算。而 x >> 1 則是當最高位是在第 1 位時，需要再多加上這一位數。最後 + 1 是因為我們要取的是

$\lceil lo{g}_2(x)\rceil$ ，即取上界，故還要再多加 1 。

return (r | shift | x >> 1) + 1;

讓上述程式支援 x == 0 的情況

由於

${\log }_{2}0$ 結果未定義，故我們定義此函式處理 x 為 0 時，輸出為 0 。

程式一開始先判斷是否為 0 ，把判斷結果存到 zero。

最後回傳結果時，把輸出結果乘上 !zero ，即若 x 為 0 時，則輸出結果會乘上 0 ，否則乘上 1 ，就可以確保在 x 為 0 時，輸出為 0 。

這樣子就可以達到沒有分支，又可以正確處理 x == 0 的情況。

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;
    int zero = (x == 0);

    x--;
    r = (x > 0xFFFF) << 4;
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return ((r | shift | x >> 1) + 1) * !zero;
}

Linux 核心內 ceil 和 log2 的組合，及應用