2024q1 Homework5 (assessment)

contributed by < ssheep773 >

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

閱讀文章時作者說「資訊工程系的學生不懂寫程式，機械工程系的學生不懂做機械」，看到這句話讓我聯想到老師說「修完一學期的作業系統課程，我們的學生也無法寫出一個作業系統」，我們常常都只學理論或者是說好考試的理論，而實作經驗卻寥寥無幾，即使許多課程都會有期末專題來考驗學生的實作能力，而我們只需做到寫對程式功能，就足以應付專題報告以及功能展示，並沒有實際的使用者，當然也不存在程式的優化或重用。

jserv 在文中跟作者說「你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已」
「你最大的問題在太害怕失敗了，你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大」
這兩句話讓我感觸很深，因為過去考試時會有只寫確定的答案，不確定的就不要寫，免得寫多錯的想法，這樣的想法常常會延續到現在，使我害怕失敗而畫地自限，看到這句話才真正了解到自身的問題，我們不應該再遇到問題時就放棄，就像我的指導教授說的 dirty your hands ，縱使嘗試後失敗了也無妨，至少我們努力過了，畢竟沒有人一開始就很厲害，誰不曾失敗呢 ?
就如同文中提到的從現在開始我應把珍貴的時間拿來做真正重要的事情，如果生活還過得去，努力過濾掉 80% 的雜事，專心做那最重要的 20% 就好。

研讀課程教材和 CS:APP 3/e

提問

問題一：
Concurrency-Primer

$10.1Acquireandrelease$
acquire operation permits other reads and writes to move past it, but only in a

$before\to after$ direction. (這裡就不太懂，可能是說明

$9.$ 提到說可以將非相關的指令重排也不影響)

不了解為何 acquire 只需要一個 dmb ，如何確保 line 2 跟 line 3 的執行順序 ?

參閱 DMB, DSB, and ISB，注意 C11 Atomics 僅提供語意 (semantics) 的規範，這裡我們只在意 side effect，你要思考指令的重排是否會有影響程式執行的正確。

jserv

感謝老師，我原以為是將 r3 的值配置給 r0 ，經過查詢後 ldr r0, [r3, #0] 是將 r3 的地址配置給 r0 ，所以 r0 是指標的指標，這樣就交換順序也不影響正確性，可以不需要中間的 dmb 。

acquireFoo :
    ldr r3, <&foo >
    // dmb
    ldr r0, [r3, #0]
    dmb
    bx lr

課堂習題改進

第一週習題

想投入的專案

第九周的測驗題 2

1. 考慮我們即將為 llama.cpp 撰寫 Linux 核心的加速運算模組，名為 matmul.ko
2. 以 CMWQ 重寫，並針對批次的矩陣乘法運算，提出有效的存取模型
3. 在 GitHub 找出矩陣乘法相關專案，如 matmul, matmul-bench, matmul-cpu, libxsmm, Matrix_Multiply_using_Arm_Neon_and_Avx，並進行效能比較和實作分析，從而歸納出提升矩陣乘法的手法
4. 嘗試在 Linux 核心模組使用 SSE/AVX/NEON 等 SIMD 指令集並降低資料存取的延遲
5. 研讀 LLaMA Now Goes Faster on CPUs 並歸納加速矩陣乘法的手段

第九周的測驗題 3

1. 研讀程式碼註解提及的論文〈Cilk: An Efficient Multithreaded Runtime System〉，解釋程式碼運作原理
2. 指出上述程式碼可改進之處並著手進行，如記憶體釋放和量化分析性能和延展性 (scalability)
3. 利用 work stealing 改寫第 6 次作業提及的並行化快速排序程式碼，在 Linux 使用者層級實作，並確保能充分運用硬體資源
4. 研讀 Linux 核心的 CMWQ，討論其 work stealing 的實作手法

---

RCU: scalability
lock-free
process core -> throughput
RCU: 在 read side 沒有 lock
確保給予足夠的時間，至少有一個執行緒有進展 (progress)

TODO: Quiz 9 / work-stealing
TODO: https://en.wikipedia.org/wiki/Work_stealing 並紀錄問題
TODO: Linux kernel module / ftrace (Linux CPU sched book Chapter 6)

page fault, exception, cache coherence, …

正常的情況的下，每個處理器都會逐步執行執行緒中的指令，直到遇到以下四個中的一個「特殊」指令

1. A spawn instruction causes a new thread to be created. 會產生新的執行緒，處理器會將目前的執行緒放到雙向佇列的底部，並開始執行新的執行緒，
2. A stalling instruction is one that temporarily halts execution of its thread. 會暫停目前執行緒執行的指令，然後執行雙向佇列底部的執行緒，若底部無執行緒則會去偷別人的執行緒
3. An instruction may cause a thread to die. 執行緒中的一條指令可能會導致執行緒死亡或是停滯。這種情況下處理器會做與 stalling instruction 相同的事情（也就是會暫停目前執行緒執行的指令，然後執行雙向佇列底部的執行緒，若底部無執行緒則會去偷別人的執行緒）
4. An instruction may enable another thread. 另一個執行緒被放到雙向佇列的底部，但處理器繼續執行其當前執行緒。

Child stealing vs. continuation stealing