2024q1 Homework5 (assessment)

contributed by < YiChiChao >

Quiz 1

測驗 1

利用 Linux Kernel API 改寫

測驗 2

Quiz 2

測驗 2

實作測試之相關程式

觀察實作

在當前的程式中，hhead[] 的大小和快取的最大存量等大。我修改 lRUCacheCreate 的參數，將 hhead 的大小和 capacity 作區隔，去測試觀察看縮減 hash table 的大小對搜尋時間的影響。

單就 cache capacity = 1000 的情形來觀察，hlist 的大小在500之後趨於平緩，可認 hlist 的大小設定宜做調整。

參考 Linux 核心的 hash table 實作 將 hash function 改以 Multiplication Method 計算，從搜尋時間來看並無太大的差異。

Quiz 3

測驗 4

$$S_t=\{\begin{array}{l}\begin{array}{rlcr}& Y_0& & t=0\\ & \alpha Y_t+(1-\alpha )\cdot S_{t-1}& & t>0\end{array}\end{array}$$

struct ewma{
    unsigned long internal;
    unsigned long factor;
    unsigned long weight;
}

• internal 是紀錄當前時間之計算出的
  EWMA
• factor 的定義我不清楚作用，按照老師給的註解，是用於對 internal 數值的縮放
• weight 為 EWMA 中的衰變率，從後面的程式碼回推weight 和 公式中
  $\alpha$ 的關係為
  $\alpha =\frac{1}{weight}$

 /* Add a sample to the average.*/
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
    avg->internal = avg->internal
                        ? (((avg->internal << EEEE) - avg->internal) +
                           (val << FFFF)) >> avg->weight
                        : (val << avg->factor);
    return avg;
}

將函式拆解會變成這樣

$$avg\to internal=\{\begin{array}{l}\begin{array}{rlcr}& (avg\to val)\cdot 2^{avg\to factor}& & avg\to internal=0\\ & \frac{1}{weight}\cdot (avg\to val)\cdot 2^{avg\to factor}+(1-\frac{1}{weight})\cdot avg\to internal& & avg\to internal\ne 0\end{array}\end{array}$$

為了在程式碼中用shift來實現除法運算，程式碼加了對 factor 以及 weight 必須是2的冪的限制。將

$1$ 用

$\frac{weight}{weight}$ 替代。

$$avg\to internal=\{\begin{array}{l}\begin{array}{rlcr}& (avg\to val)\cdot 2^{avg\to factor}& & avg\to internal=0\\ & \frac{1}{weight}\cdot (avg\to val)\cdot 2^{avg\to factor}+(\frac{weight}{weight}-\frac{1}{weight})\cdot avg\to internal& & avg\to internal\ne 0\end{array}\end{array}$$

再將

$\frac{1}{weight}$ 提出，以 >> weight 表示。

$$avg\to internal=\{\begin{array}{l}\begin{array}{rlcr}& (avg\to val)\cdot 2^{avg\to factor}& & avg\to internal=0\\ & \frac{1}{weight}\cdot [(avg\to val)\cdot 2^{avg\to factor}+(weight-1)\cdot avg\to internal]& & avg\to internal\ne 0\end{array}\end{array}$$

觀察實作

在 drivers/net/virtio_net.c 透過 DECLARE_EWMA(pkt_len, 0, 64) 來定義一個結構體 struct ewma_pkt_len 來利用 EWMA 調整 mergeable receive buffer 的封包大小。

閱讀學習資料問題

Data Alignment

uint32_t v = *(uint32_t*) (csrc & 0xfffffffc);

執行時，透過 gdb 觀察：

Program received signal SIGSEGV, Segmentation fault.
unaligned_get8 (src=0x7fffffffd600) at unaligned_get32.c:9
uint32_t v = *(uint32_t*) (csrc & 0xfffffffc);

POSIX.1-2017, "References to unmapped addresses shall result in a SIGSEGV signal."

不要參照中文 Wikipedia，其資訊通常過時，參照 IEEE / Open Group 的 POSIX 規範文件。

了解YiChi Chao

當在使用遮罩取最後兩位以外的位元後，由於取得的指標未初始化，在此情況下對指標取值 （*(uint32_t*))，為無效的記憶體訪問 。

注意用語，參見資訊科技詞彙翻譯及詞彙對照表

即使此強置轉型沒有 SIGSEGV 報錯，這個取值在此程式中也不合理。

改進方式是直接將 csrc & 0xfffffffc 強置轉型為 (uint32_t)

中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

---

x86-64 ABI

IEEE 754, Assume float is 32-bit

float float_div2(float x)
{
    if(x == 0)return 0;
    // using bitwise operations. No mul, div
    __uint32_t calculate = *(__uint32_t*) &x;
    __uint32_t exponent = calculate & 0x7F800000;
    calculate &= 0x807FFFFF;
    exponent -= 0x800000;
    exponent &= 0x7F800000;
    calculate |= exponent;
    return *(float*) &calculate;
}

TODO: 實作程式碼並解釋

實作程式碼：445afd8

按照 IEEE-754 對浮點數的表示方法：

$$(-1{)}^{sign}\times 1.mantissa\times 2^{exponent-bias}$$

在不使用除法和乘法的前提下，透過位元操作將 exponent 的數值減一便能完成浮點數除以二的運算。

首先透過位元遮罩將 exponent 的部份單獨取出，

$$\begin{array}{cc}& 01110000110000000000000000000000\\ \mathrm{\&}& 01111111100000000000000000000000\\ =& 01110000100000000000000000000000\end{array}$$

並且將 calculate 中的 exponent 部份先清零：

$$\begin{array}{cc}& 01110000110000000000000000000000\\ \mathrm{\&}& 10000000011111111111111111111111\\ =& 00000000010000000000000000000000\end{array}$$

再來將 exponent 部份減一，也就是對此浮點數表示方式減 0x800000 ：

$$\begin{array}{cc}& 01110000100000000000000000000000\\ -& 00000000100000000000000000000000\\ =& 01110000000000000000000000000000\end{array}$$

最後將 calculate 和計算好之 exponent OR 在一起。

值得注意的部份，在 IEEE-754 對特定數值有特例的表示方法，像是 INF 的表示為 exponent 全為一，mantissa 全為 0 。在測試我寫的函式是否正確時，發現當輸入值為 0 時，運算出的結果為 INF 。

x =  0.000000
float_div2(x) =    inf
x/2 =  0.000000

所以在函式中單獨對 0 作判斷。

參考資料：IEEE-754 與浮點數運算
TODO: quiz3+quiz4