2025q1 Homework5 (assessment)

contributed by < willy-liu >

預期目標

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

檢視前 6 週學習狀況 (含程式碼審查和課堂討論)

第一週內容

lab0:
我將doubly linked list的函式完成，並且完成初步的優化，通過make test的測試。但沒有研讀shannon entropy和網頁伺服器的部分
idea
觀看simplefs去年的成果
教材有全部看一遍

第二周內容

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

第三週內容

教材觀看至浮點數運算，kxo目前只讀了部分第一頁的內容，還不理解kernel相關的指令、程式。

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

遇到的問題很多
- 知識嚴重不足
- 學校教的派不上用場
- 理想很美好，現實很骨感，造出來的設備會有公差，想出的解法都不work
- 茶、冰塊、流水線問題
  - Peter Thiel曾說過：「我們想要一輛可以飛的汽車，得到的卻是140個字符。」
    這句話表達了一種對科技進展失望的情緒。它對比了人們對未來科技的宏大期待（例如像飛行汽車這樣的革命性發明），和現實中科技產業（尤其是矽谷）發展的實際成果（例如像Twitter這樣的社交媒體平台，其早期推文限制為140個字元）。
  - 葉問曾在洪師父對決拳王時說：「洪師父，不要跟他拼拳，嘗試切他中路。」
  - PTT上yoyodiy大師曾說:「誰跟你直接暴力破解RAR密碼，我們要繞過去。」
    我們面對問題時往往有多種解法，正面解可能很困難，但換個思路也許可以更有效率、更低成本、更容易的解決
  - 現實的碰壁
    自己做了一大堆嘗試，都失敗了，也聽了朋友、老師的建議，但都沒辦法說服自己投入。
Jserv給的回應
- constrain 太多、一定有人解決類似的問題，不要被別人已經解決的問題卡住
- 太害怕失敗，不敢投入「應該學習如何處理與承受失敗，你才能變得比以前更強大。」
- 人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。–––《鋼之鍊金術師》
故事的最後＆我的想法
看到結束，讓我覺得有點遺憾，他們付出了這麼多，學了很多知識，花了很多錢，也因為他延畢；然而，卻因為當兵、機器穩定度和各式各樣的原因沒有繼續維護下去，也沒有真正投入使用，最後只好拆掉放在那邊。
這點我覺得不只是他們，大多數的計劃、點子都因為現實的原因而停留在提案、prototype階段就胎死腹中了，包含大多數人的專題成果、產學合作，能真正被投入到生產環境的寥寥無幾，我認為最大的原因是學校裡所學的理論固然重要，但與現實脫鉤，就像是Jserv老師上課提到的，我們都知道process life cycle長這樣

然而在現實的linux實現卻是這樣

因為我們的理論在現實會因為各式各樣的因素干擾，我們必須做出妥協，但這些在正規的大學教育中卻不會告訴你，直到你碰壁了才會理解到這個道理。
另外一點是大學的理論和實操也嚴重脫鉤，理論學得再多，用不出來有什麼用?讓我們的學生出現資工系的學生不會寫程式，機械系的學生不會做機械，現在又多一條電工系的學生不會焊電路(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

定點數理解

這題所使用的是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用來提前處理特殊情況，

$e x p (0) = 1 = 2^{16}$ (Q16.16)
$e x p (1) = 2.71828182846 = 2.71828182846 * 2^{16} + 0.5 = 178145.81791 = 178145$ (Q16.16)【AAAA】
$e x p (i n > 681391)$ 我們先來探討681391(Q16.16)是多少，由前面的計算方式，我們可以知道除以
$2^{16}$ 就可以換算回float，也就是10.3972015381，
$e x p (10.397) = 32761.194518$
那我們再看看Q16.16的最大表示法為
$0 x 7 f f f f f f f = 2147483647 / 2^{16} = 32767.9999847$
兩者非常接近，所以當輸入的值大於他時我們就可以直接回傳Q16.16最大值0x7fffffff【BBBB】
$exp(in<-772243)同理
$e x p (- 772243 / 2^{16}) = e x p (- 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!} + \dots

可以發現每一項都是前一項乘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);
}

公式為：

t a n h (x) = \frac{e x p (x) - e x p (- x)}{e x p (x) + e x p (- 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{2 x^{5}}{15} - \frac{17 x^{7}}{315} + \frac{62 x^{9}}{2835} + \dots (| x | < \frac{π}{2})

然而，這種方式除了限制

(| x | < \frac{π}{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