2024q1 Homework5 (assessment)

contributed by < yourui1017 >

〈因為自動飲料機而延畢的那一年〉的啟發

「資工系的學生不會寫程式，機械系的學生不會做機械」

人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。–––《鋼之鍊金術師》

對於這兩句話特別有感受。雖然目前已經修習過許多課程，但往往都只是把課本上的知識死背硬背，求的就只是課程的高分，雖然成績單上有好看的成績，但根本不了解學習這些課程背後的意義，在面對真實世界的考驗時，無法應用學習的知識解決當前的問題。

若想要貫通學習課程的意義必須要擁有獨立思考的能力並解決實作時遇到的困難，沒有付出犧牲是無法解決面對的問題的，只有絞盡腦汁不被問題擊敗，才能夠一步一步慢慢成長。

前陣子因為在忙於實驗室的比賽的部份，對於本課程的投入時間非常不足，根據等價交換的基本原則，付出多少時間就只能得到等價的回報。另外，在觀摩其他學員的成果時，發現學員對於整體系統的開發到微小的細節都有充分的理論與實驗佐證，在進行實驗時也會考慮到不同的資料測試結果（如：最差狀況、最佳狀況、隨機資料等等），讓我了解到想要開發完整的專案必須留意各式細節，仔細思考實驗應考慮的情況，認真對待面對的問題。

檢視前六周學習狀況

M01: lab0

M01: lab0 共筆

首次認識 Linux 核心 API 的相關實作，針對佇列實作不同的操作方法。
研讀論文 Dude, is my code constant time? ，改進 lab0-c 的自動評分方式，
引入 Linux 核心原始碼 list_sort 到 lab0-c ，比較自己實作的排序驗算法與 list_sort 的效能差異。

尚未在 qtest 提供新的命令 shuffle 。
尚未確保 qtest 提供的 web 命令得以搭配上述佇列實作使用。
精簡 lab0-c 的程式碼，提出更有效率的實作方法，並以實驗佐證。

M02: quiz1+2

M02: quiz1+2 共筆

分析 quick_sort 的運作原理，改善演算法使用到的記憶體大小與最差狀況的快速排序實作，並使用實驗佐證。
Timsort 演算法運作原理，加入 minrun 的判斷，並實作插入排序保證達成 minrun ，進行效能測試的實驗，最後將 Timsort 引入 lab0-c 作為另一個有效的排序命令。
分析 Construct Binary Tree from Preorder and Inorder Traversal。
分析 Least Recently Used (LRU) 。
分析 find_nth_bit 。

在 Linux 核心的 cgroups 相關原始程式碼，找出 pre-order walk 程式碼並探討。
將 quiz2_test2 的 hash function 改成 Multiplication Method 。
在 Linux 核心找出 LRU 相關程式碼並探討。
在 Linux 核心原始程式碼找出 find_nth_bit 的應用案例，並予以解說和分析，需要涵蓋 CPU affinity 相關的原始程式碼。

M03: ttt

M03: ttt

尚未開始，需要投入更多時間。

M04: quiz3+4

M04: quiz3+4

尚未開始，需要投入更多時間。

想投入的專案 (亦可建立新專案)，至少選出 (或訂出) 二個

目前想要做的期末專案為以下：

~~補完前面積欠的作業~~ 高估自己
並行程式設計
高效網頁伺服器（但是對於~~網頁 0 基礎~~ ，會需要從頭學習）
紅黑樹實作改進

https://hackmd.io/@sysprog/linux2024-quiz8

stackful vs. stackless
A => A1 + A2 + A3
B => B1 + B2

A1, A2, A3 -> B1, B2 -> A1, ..

A1 -> B1, B2 -> A2, A3
保存狀態: 用到 stack
使用 global

IEEE 754, assume float is 32-bit width

float float_mul10(float x)
{
    // using bitwise operation; No mul/div
}

10 = 8 + 2 = (2 << 3) + (2 << 0)
誠實面對自己
TODO: 撰寫程式碼並測試，附上你的分析

在做 float_mul10 之前，需要先了解浮點數的運作方式，參考自你所不知道的 C 語言: 浮點數運算和浮點數運算和定點數操作，在 C 語言中 float 是遵照 IEEE 754 的規定進行設計的， float 存放方式分為三種：

Signed bit
Exponent
Mantissa
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →

為了使數值表達範圍更廣，才使用這種表達方式，但相對的這種方式會導致數值運算變得更加複雜，普通的四則運算就要考慮到三種不同的模式：

Normalize 模式，普通模式，表
$1. x * 2^{e x p}$
Denormalize 模式，表
$0. x * 2^{e x p}$
NaN 與 INF 模式
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →

Denormalize 是為了解決 underflow 的問題，在 denormalize 模式下可以表達更小的數值範圍。

Denormalize 能表達的最小的數值為0x00000001，在十進位下約為 1e-45。
Normalize 能表達的最小的數值為 0x00800001，在十進位下約為 1.1754945e-38。

underflow，意思是運算出來的數值非常接近 0，近到無法用正規的浮點數來表示
並因為此種表示方式延伸出誤差和精度問題。

underflow 會有什麼麻煩呢？明明
$A > B$ ，但是
$A - B$ 的運算結果卻成為 0

NaN 用以表達未定義或不可表示的情況。

根據 IEEE 754 2008 年版本 6.2 節
有兩種不同的 NAN
X111 1111 1AXX XXXX XXXX XXXX XXXX XXXX
如果在 A 的位置為 1 ，則為 quiet NAN
反之如果 A 的位置為 0 ，其他的位置為非 0 ，則為 signal NAN
6.2 節也提到當要傳送這個 NAN 時，應採取 quiet NAN 的形式，當要送給系統信號時，應當採取 signal NAN
INF 模式則是用以表達接近無限大的數值。

誤差
浮點數表示法會隨著數值愈來愈大，誤差也愈來愈大。
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
精度
- 24 because: 23 bits for mantissa + 1 implicit bit
- implicit bit 指的是
  $1. x * 2^{e x p}$ 表示法中的 1。
$l o g_{10} 2^{24} \approx 7.224719$

了解浮點數的表示法後，就可以開始實作函式 float_mul10。

IEEE 754, assume float is 32-bit width

float float_mul2 (float f) 
{
    unsigned int uf = *(unsigned int*) &f;
    unsigned int uf_sgn = (uf >> 31) & 0x01;
    unsigned int uf_exp = (uf >> 23) & 0xff;
    if (uf_exp == 0) {
        uf <<= 1;
        uf += (uf_sgn << 31);
    } else if (uf_exp != 0xff) {
        uf_exp += 1;
        if (uf_exp == 0xff) {
            uf &= 0x80000000;
        } else {
            uf &= 0x807fffff;
        }
        uf = uf + (uf_exp << 23);
    }

    float result = *(float*) &uf;
    return result;
}

float float_mul8 (float f) 
{
    unsigned int uf = *(unsigned int*) &f;
    unsigned int uf_sgn = (uf >> 31) & 0x01;
    unsigned int uf_exp = (uf >> 23) & 0xff;
    if (uf_exp == 0) {
        uf <<= 3;
        uf += (uf_sgn << 31);
    } else if (uf_exp != 0xff) {
        uf_exp += 3;
        if (uf_exp == 0xff) {
            uf &= 0x80000000;
        } else {
            uf &= 0x807fffff;
        }
        uf = uf + (uf_exp << 23);
    }
    float result = *(float*) &uf;
    return result;
}

float float_mul10(float f)
{
    // using bitwise operation; No mul/div
    return float_mul2(f) + float_mul8(f); 
}

首先，先把 float_mul10 拆解成 float_mul2 + float_mul8，這樣一來就可以針對 exponent 的部份進行左移得到 float_mul2 和 float_mul8。

至於在 float_mul2 函式中，需要先使用 unsigned 解釋浮點數的資料，並且藉由 bitwise operetion 得到 sign bit 和 exponent 。

接下來針對三種模式進行運算

Denormalize : 直接針對浮點數進行左移進行乘法，並在最後補上原本的 sign bit
Normalize : 取出 exponent 的部份進行運算，判斷運算後的浮點數是否是 INF ，把 mantissa 歸零，否則留下 mantissa ，並把運算後的 exponent 補回去
NaN & INF : 直接回傳

最後把無號數的表示方式使用浮點數資料型態解釋並回傳。

注意：
*(float *) &uf 和 (float) uf 的差別

*(float *) &uf 代表使用浮點數的方式解讀 uf
(float) uf 則是會把當前 uf 的資料使用 IEEE 754 的規定轉型成浮點數，導致資料會有變化

結果：將自己實作的 float_mul2、float_mul8、float_mul10 和內建的浮點數乘法使用 perf 進行比較，測資個數皆為 100000 筆。

Normalize

int main()
{
    srand(42);
    float x[NUM_FLOATS];
    float result;
    for (int i = 0; i < NUM_FLOATS; i++) {
        x[i] = generate_random_float(LOWER_BOUND, UPPER_BOUND);
        result = float_mul10(x[i]);
    }
    // for (int i = 0; i < NUM_FLOATS; i++) {
    //     x[i] = generate_random_float(LOWER_BOUND, UPPER_BOUND);
    //     result = x[i] * 10;
    // }
    printf("%f\n", result);
    return 0;
}

自己實作的：

內建的浮點數乘法：

Denormalize

int main()
{
    srand(42);
    float x[NUM_FLOATS];
    float result;
    unsigned int a = 0x00000ff1;
    for (int i = 0; i < NUM_FLOATS; i++) {
        x[i] = *(float*) &a;
        result = float_mul10(x[i]);
    }
    // for (int i = 0; i < NUM_FLOATS; i++) {
    //     x[i] = *(float*) &a;
    //     result = x[i] * 10;
    // }
    printf("%f\n", result);
    return 0;
}

自己實作的：

內建的浮點數乘法：

int main()
{
    srand(42);
    float x[NUM_FLOATS];
    float result;
    unsigned int a = 0x7F800001;
    for (int i = 0; i < NUM_FLOATS; i++) {
        x[i] = *(float*) &a;
        result = float_mul10(x[i]);
    }
    // for (int i = 0; i < NUM_FLOATS; i++) {
    //     x[i] = *(float*) &a;
    //     result = x[i] * 10;
    // }
    printf("%f\n", result);
    return 0;
}

自己實作的：

內建的浮點數乘法：

TODO: quiz10, quiz12 + extra

quiz10 開發紀錄請看:2024q1 Homework(quiz10)

2024q1 Homework5 (assessment)

〈因為自動飲料機而延畢的那一年〉的啟發

檢視前六周學習狀況

想投入的專案 (亦可建立新專案)，至少選出 (或訂出) 二個

Read more

2024q1 Homework(quiz10)

2024q1 Homework2 (quiz1+2)

2024q1 Homework4 (quiz3+4)

Timsort 筆記