or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
2025q1 Homework5 (assessment)
contributed by <
willy-liu
>預期目標
檢視前 6 週學習狀況 (含程式碼審查和課堂討論)
第一週內容
我將doubly linked list的函式完成,並且完成初步的優化,通過
make test
的測試。但沒有研讀shannon entropy和網頁伺服器的部分觀看simplefs去年的成果
第二周內容
有觀看完大多數的教材,作業只有回顧一題第一週的課堂題目。
第三週內容
教材觀看至浮點數運算,kxo目前只讀了部分第一頁的內容,還不理解kernel相關的指令、程式。
紀錄閱讀〈因為自動飲料機而延畢的那一年〉的啟發
遇到的問題很多
這句話表達了一種對科技進展失望的情緒。它對比了人們對未來科技的宏大期待(例如像飛行汽車這樣的革命性發明),和現實中科技產業(尤其是矽谷)發展的實際成果(例如像Twitter這樣的社交媒體平台,其早期推文限制為140個字元)。
我們面對問題時往往有多種解法,正面解可能很困難,但換個思路也許可以更有效率、更低成本、更容易的解決
自己做了一大堆嘗試,都失敗了,也聽了朋友、老師的建議,但都沒辦法說服自己投入。
Jserv給的回應
故事的最後&我的想法


看到結束,讓我覺得有點遺憾,他們付出了這麼多,學了很多知識,花了很多錢,也因為他延畢;然而,卻因為當兵、機器穩定度和各式各樣的原因沒有繼續維護下去,也沒有真正投入使用,最後只好拆掉放在那邊。
這點我覺得不只是他們,大多數的計劃、點子都因為現實的原因而停留在提案、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乘法
可以直接相乘,但要注意兩個32bits的值相乘最多會需要使用64bits儲存,而且在定點數已經先做過一次位移,所以相乘時要記得shift回去
fix_16除法
同乘法,要記得先向左shift再相除,避免小數部分遺失
問題與答案分析
AAAA~CCCC
這個函式要實作fix16的exp(in),前四個if用來提前處理特殊情況,
那我們再看看Q16.16的最大表示法為\(0x7fffffff=2147483647/2^{16}=32767.9999847\)
兩者非常接近,所以當輸入的值大於他時我們就可以直接回傳Q16.16最大值0x7fffffff【BBBB】
而我們的定點數僅用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
公式為:
\[tanh(x)=\frac{exp(x)-exp(-x)}{exp(x)+exp(-x)}\]
改進處1 - fix16_to_float
我有注意到fix16轉回float的過程,有小數時就只能乖乖使用很慢的浮點數除法,但我們可以判斷a是否包含小數部分,如果他沒有小數部分就可以直接用位元運算加速轉換。
改進處2
當前計算tanh計算exp(x), exp(-x)都是呼叫fix16_exp,但其實只要呼叫一次就好,exp(-x)只要用exp(x)的倒數就好。
改進失敗
原本嘗試改進tanh的精確度,我打算先從exp的計算下手,我嘗試使用kahan的方式進行補償
然而,在我測試時卻發現和原本方法算出來的誤差值一模一樣。
接著我嘗試直接去估計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