---
description: "contributed by `willy-liu`"
---

# 2025q1 Homework5 (assessment)
contributed by [< `willy-liu` >](https://github.com/willy-liu)

## 預期目標
* 檢視前 6 週學習狀況 (含程式碼審查和課堂討論)
* 隨堂測驗和作業回顧
* 導入客製化作業，讓學員選擇改進第 1 到第 4 次的作業或自訂題目 (例如貢獻程式碼到 Linux 核心)，隨後安排授課教師和學員的線上一對一討論

## 檢視前 6 週學習狀況 (含程式碼審查和課堂討論)
### 第一週內容
- lab0:
我將doubly linked list的函式完成，並且完成初步的優化，通過`make test`的測試。但沒有研讀shannon entropy和網頁伺服器的部分
- idea
觀看simplefs去年的成果
- 教材有全部看一遍

### 第二周內容
有觀看完大多數的教材，作業只有回顧一題第一週的課堂題目。

## 第三週內容
教材觀看至[浮點數運算](https://hackmd.io/@sysprog/c-floating-point)，kxo目前只讀了部分第一頁的內容，還不理解kernel相關的指令、程式。

## 紀錄閱讀[〈因為自動飲料機而延畢的那一年〉](https://www.opasschang.com/docs/the-story-of-auto-beverage-machine-1)的啟發

- 遇到的問題很多
- 知識嚴重不足
- 學校教的派不上用場
- 理想很美好，現實很骨感，造出來的設備會有公差，想出的解法都不work
- 茶、冰塊、流水線問題
- Peter Thiel曾說過：「我們想要一輛可以飛的汽車，得到的卻是140個字符。」
這句話表達了一種對科技進展失望的情緒。它對比了人們對未來科技的宏大期待（例如像飛行汽車這樣的革命性發明），和現實中科技產業（尤其是矽谷）發展的實際成果（例如像Twitter這樣的社交媒體平台，其早期推文限制為140個字元）。
- 葉問曾在洪師父對決拳王時說：「洪師父，不要跟他拼拳，嘗試切他中路。」
- PTT上yoyodiy大師曾說:「誰跟你直接暴力破解RAR密碼，我們要繞過去。」
我們面對問題時往往有多種解法，正面解可能很困難，但換個思路也許可以更有效率、更低成本、更容易的解決
- 現實的碰壁
自己做了一大堆嘗試，都失敗了，也聽了朋友、老師的建議，但都沒辦法說服自己投入。

- Jserv給的回應
- constrain 太多、一定有人解決類似的問題，不要被別人已經解決的問題卡住
- 太害怕失敗，不敢投入「應該學習如何處理與承受失敗，你才能變得比以前更強大。」
- 人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。------《鋼之鍊金術師》

- 故事的最後＆我的想法
看到結束，讓我覺得有點遺憾，他們付出了這麼多，學了很多知識，花了很多錢，也因為他延畢；然而，卻因為當兵、機器穩定度和各式各樣的原因沒有繼續維護下去，也沒有真正投入使用，最後只好拆掉放在那邊。
這點我覺得不只是他們，大多數的計劃、點子都因為現實的原因而停留在提案、prototype階段就胎死腹中了，包含大多數人的專題成果、產學合作，能真正被投入到生產環境的寥寥無幾，我認為最大的原因是學校裡所學的理論固然重要，但與現實脫鉤，就像是Jserv老師上課提到的，我們都知道process life cycle長這樣
然而在現實的linux實現卻是這樣
因為我們的理論在現實會因為各式各樣的因素干擾，我們必須做出妥協，但這些在正規的大學教育中卻不會告訴你，直到你碰壁了才會理解到這個道理。
另外一點是大學的理論和實操也嚴重脫鉤，理論學得再多，用不出來有什麼用?讓我們的學生出現==資工系的學生不會寫程式，機械系的學生不會做機械，現在又多一條電工系的學生不會焊電路[(22)](https://www.opasschang.com/docs/the-story-of-auto-beverage-machine-22)==。這就是Jerv老師常說的 **大學的悲哀**。
修了linux這堂課，我知道我完全跟不上課，但我開始「誠實面對自己」，正視自己學了哪些內容，還有什麼不足。老師常說「缺什麼，就補什麼」，在這篇文章中體現的淋漓盡致，這兩句話是我在課堂中學到最重要的精神。

## 研讀第 1 到第 6 週「課程教材」和 CS:APP 3/e (至少到第二章)，紀錄心得和提問。針對自訂題目，例如貢獻程式碼到 Linux 核心，也將自己的構想和規劃記錄下來，隨後與授課教師一對一討論時可運用。

### 想做的題目1 - 研讀kxo並且嘗試把mlp用定點數實現出來

想做這個是因為既然來上這堂課就想要真正寫一些kernel相關的程式，而我的專業又跟人工智慧、深度學習有關，在看過kxo的作業說明後發現目前已經用定點數實作MCTS，那我搞不好可以實作看看mlp，讓kxo不只包含ML，也能納入DL。

### 想做的題目2 - simplefs

還沒有研讀相關的教材

## 從前 6 週的測驗題選出 3 題改進

### [2025q1 第五周 測驗1](https://hackmd.io/@sysprog/linux2025-quiz5#%E6%B8%AC%E9%A9%97-1)

#### 定點數理解

這題所使用的是Q16.16定點數，意思是將`int32_t`的前16bit儲存整數，後16bit儲存小數，以下是範例。
##### 整數轉Q8.8定點數
$123_{10}$ = $01111011_2$ = $01111011|00000000_2$ (Q8.8) = $31488_{10}$ (Q8.8)
，也就是將123*$2^8$，等價於123<<8，就可以將整數轉換為定點數。
##### 浮點數轉Q8.8定點數
$23.75_{10}$ = $23.75*2^8=6080_{10}$(Q8.8) = $00010111|11000000_2$ (Q8.8)
，要注意由於浮點數無法直接使用位元運算，所以只能乘上$2^8$，另一點要注意的是rounding的問題，由於C的int會無條件捨去小數部份，這會導致精確度大幅下降，所以要根據最後的值是正數還負數，補償 +/- 0.5來做四捨五入。
所以公式會變$23.75*2^8+0.5=6080.5$(Q8.8)再無條件捨去一樣是$6080$(Q8.8)。

#### 基本運算
##### fix_16乘法

static inline fix16_t fix16_mul(fix16_t x, fix16_t y)
{
    int64_t res = (int64_t) x * y;
    return (fix16_t) (res >> 16);
}

可以直接相乘，但要注意兩個32bits的值相乘最多會需要使用64bits儲存，而且在定點數已經先做過一次位移，所以相乘時要記得shift回去

##### fix_16除法

static inline fix16_t fix16_div(fix16_t a, fix16_t b)
{
    if (b == 0) /* Avoid division by zero */
        return 0;
    fix16_t result = (((int64_t) a) << 16) / ((int64_t) b);
    return result;
}

同乘法，要記得先向左shift再相除，避免小數部分遺失

#### 問題與答案分析

##### AAAA~CCCC

fix16_t fix16_exp(fix16_t in)
{
    if (in == 0)
        return FIX16_ONE;
    if (in == FIX16_ONE)
        return AAAA /* precomputed exp(1) in fixed-point */;
    if (in >= 681391)
        return BBBB;
    if (in <= -772243)
        return 0;

    int neg = (in < 0);
    if (neg)
        in = -in;
    fix16_t result = in + FIX16_ONE;
    fix16_t term = in;
    for (uint_fast8_t i = 2; i < 30; i++) {
        term = fix16_mul(term, fix16_div(in, int_to_fix16(i)));
        result += term;
        /* Break early if the term is sufficiently small */
        if ((term < 500) && ((i > 15) || (term < 20)))
            break;
    }
    if (neg)
        result = CCCC;
    return result;
}

這個函式要實作fix16的exp(in)，前四個if用來提前處理特殊情況，
- $exp(0)=1=2^{16}$(Q16.16)
- $exp(1)=2.71828182846=2.71828182846*2^{16}+0.5=178145.81791=178145$(Q16.16)【AAAA】
- $exp(in>681391)$我們先來探討681391(Q16.16)是多少，由前面的計算方式，我們可以知道除以$2^{16}$就可以換算回float，也就是10.3972015381，$exp(10.397)=32761.194518$
那我們再看看Q16.16的最大表示法為$0x7fffffff=2147483647/2^{16}=32767.9999847$
兩者非常接近，所以當輸入的值大於他時我們就可以直接回傳Q16.16最大值0x7fffffff【BBBB】
- $exp(in<-772243)同理 $exp(-772243/2^{16})=exp(-11.783493042)=0.00000762946$ 我們可以觀察到小數點後6位才不為0。
而我們的定點數僅用16位表達小數部分，也就是我們的精確度頂多$2^{-16}=0.00001525878$，所以-772243這個值只是大概設定一個夠小的值，算出來由於Q16.16的精確度無法表示，所以可以直接回傳0

接著先來看neg的作用，由於exp(-x)=1/exp(x)，所以統一把負值轉為正的再進行運算，最後再轉成倒數，fix16_div(FIX16_ONE/result)【CCCC】

中間的迴圈部分為exp的泰勒展開式
$$
\exp(x)
= \sum_{n=0}^{\infty} \frac{x^n}{n!}
= 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \cdots
$$
可以發現每一項都是前一項乘x後除i，所以就可以用term代表當前的項，累加到result。

#### 計算tanh

fix16_t fix16_tanh(fix16_t in)
{
    fix16_t e_x = fix16_exp(in);
    fix16_t m_e_x = fix16_exp(-in);
    return fix16_div(e_x - m_e_x, e_x + m_e_x);
}

公式為：
$$tanh(x)=\frac{exp(x)-exp(-x)}{exp(x)+exp(-x)}$$

#### 改進處1 - fix16_to_float
我有注意到fix16轉回float的過程，有小數時就只能乖乖使用很慢的浮點數除法，但我們可以判斷a是否包含小數部分，如果他沒有小數部分就可以直接用位元運算加速轉換。

static inline float fix16_to_float(fix16_t a)
{
    if ((a & 0x0000FFFF) == 0)  // no fractional part
        return (float)(a >> 16);
    else
        return (float)a / 65536.0f;
}

#### 改進處2

當前計算tanh計算exp(x), exp(-x)都是呼叫fix16_exp，但其實只要呼叫一次就好，exp(-x)只要用exp(x)的倒數就好。

     fix16_t e_x = fix16_exp(in);
-    fix16_t m_e_x = fix16_exp(-in);
+    fix16_t m_e_x = fix16_div(FIX16_ONE, e_x); 

#### 改進失敗
原本嘗試改進tanh的精確度，我打算先從exp的計算下手，我嘗試使用kahan的方式進行補償

-        term = fix16_mul(term, fix16_div(in, int_to_fix16(i)));
-        result += term;
+        fix16_t y = term - c;          // 將補償誤差從 term 拿掉
+        fix16_t t = result + y;        // 嘗試加上正確的值
+        c = (t - result) - y;  // 計算誤差（用兩次減法）
+        result = t;

然而，在我測試時卻發現和原本方法算出來的誤差值一模一樣。

接著我嘗試直接去估計tanh，不經過exp來計算
我首先使用泰勒展開式直接估計tanh

$$
\tanh(x)
= x - \frac{x^3}{3} + \frac{2x^5}{15} - \frac{17x^7}{315} + \frac{62x^9}{2835} + \cdots
\quad (\lvert x\rvert < \tfrac{\pi}{2})
$$

然而，這種方式除了限制$(\lvert x\rvert < \tfrac{\pi}{2})$外，算出來的誤差反而更大了
Range of difference over [-1, 1]: min=7.45058e-08, max=0.0155462, avg=0.00174431

原因是因為分子項的x冪次方太大了，精度損失的更快。

而原本的方法不但可以更大的範圍外，還更精準。
Range of difference over [-10, 10]: min=1.78814e-07, max=4.15146e-05, avg=1.15705e-05