2024q1 Homework5 (assessment)

contributed by < csotaku0926 >

測驗表單紀錄

由於這題我想了很久，因此特地紀錄解題過程
可見我缺乏正確地尋找資源的能力

Q: 第三週的測驗提及 Exponentially Weighted Moving Average (EWMA)，Linux 核心的 CPU 排程器 (CFS 和其後繼的 EEVDF) 程式碼 (於 kernel/sched 目錄) 採用 EWMA 做什麼用途？用美式英語簡述

• EWMA

EWMA 是取平均的方式，有以下公式

$\begin{array}{c}{S}_t=\{\begin{array}{l}{Y}_{0}t=0\\ \alpha Y_t+(1-\alpha )S_{t-1}t>0\end{array}\end{array}$

$S_t=\alpha \sum _{i=0}^t(1-\alpha {)}^i{Y}_i$

• CFS

確保行程平等的共享 CPU ，定義不公平值，由虛擬執行時間測量
一個行程虛擬執行時間定義為，其真正執行時間由行程正規化
在查閱資料的過程中我犯了個錯誤，就是直接從 c 程式碼開始閱讀，但正確的流程應先閱讀標頭檔
也就是 kernel/sched.h
便能清楚發現，CFS 會將 EWMA 用於平均 CPU 使用率的計算上 ( ref )

揣摩並列出考量因素

改進作業

1. 完成第三週的 coroutine 實作

參考: 第三週共筆

身為未來的開發者，我有個缺點，就是遇到不會的問題就習慣逃避
在第三週結合 ttt 與 coroutine 的部份，我很擔心自己結合過程中出現問題，也不知道怎麼處理鍵盤事件監聽等步驟，這些對我來說都是第一次遇到的問題

重新理清原先程式的思路，可以整理出以下流程:

schedule()                    tasks[i]                    task_switch()
------------------------------------------------------------------------
setjmp(sched)    
tasks[i](args[i])       -->   
                              setjmp(tasks[i]->env)
                        <--   longjmp(sched, 1)
tasks[i+1](args[i+1])   -->   
                              setjmp(tasks[i+1]->env)
                        <--   longjmp(sched, 1)
tasks[i](args[i])       -->   
                              task_switch()           -->
                                                          longjmp(t->env, 1)

面對諸如 setjmp/longjmp, goto 這種非線性流程時，最好還是把流程圖整理出

專題題目簡述

適用於 C 的 LLM

Andrej Karpathy 最近在 github 釋出一份 repos，裡面包含不需依賴 Pytorch 等深度學習框架的 GPT-2 實作。雖說我曾接觸過深度學習，卻也僅止於呼叫這些已經實作好的框架，沒有理解其底層邏輯。
我希望透過這項專案，更加理解諸如 Pytorch 這類深度學習框架，實際是如何處理深度學習的實作細節，以及理解這些框架的限制為何 (正如老師第一堂課提到的，我們每天都在用 Pytorch ，但能不能說出 Pytorch 的限制在哪裡？) ，甚至我希望透過這次經驗，做出為開源專案做出貢獻的機會

目前可能的改進方向為:

• 更現代的模型架構，包含 Llama，Gemma 等
• 以 SIMD 指令加速 CPU 版本的實作
  • 然而我沒有學過 SIMD 指令，應補足相關知識
• 結合 CMWQ，主動分配 CPU

目前我將我的看法與洞見整理於 這篇文章 中