TonyLinX (林儀承)
簡介
2025 Linux 核心設計 自我評量
1.成果發表和貢獻：
我認為自己在本課程中最主要的成果與貢獻，來自於期末專題中對 lock-free thread pool 架構的實作與分析。並行程式設計涉及的知識面向極廣，從最初的 lock-based 設計出發，就需要理解 mutex、condition variable、atomic operation 以及 thread pool 的整體運作邏輯。在此基礎上，若要進一步實作 lock-free 的版本，必須對效能瓶頸進行具體分析與定位，特別是在任務分配與多個執行緒同時操作同一個共享佇列時，會因爭用 queue 的 head/tail 指標導致執行緒頻繁等待、atomic operation 失敗重試，進而造成整體效率下降。
在本專題中，我從分析 thread pool 的 work queue 設計著手，意識到 lock contention 與任務分配不均是造成效能瓶頸的主因之一。因此，我採用了以 ring buffer 為基礎的 lock-free work queue 設計，並結合 semaphore 與 spin-wait 的兩段式等待策略，以降低 busy-wait 帶來的資源浪費。然而，僅靠 ring buffer 雖可降低 contention，但無法完全解決任務分配不均的問題。為此，我進一步設計了 batch-based work stealing 機制，透過每個執行緒在任務不足時主動嘗試從其他佇列中偷取多筆任務，以改善負載平衡並提升 thread utilization。
本專題最終呈現出一個可實際執行、效能優於傳統 lock-based 設計的 lock-free thread pool 平行矩陣乘法系統，並針對其中的結構設計與效能數據進行紀錄與驗證。我相信這份開發紀錄與實作成果，可作為後續學習者的參考基礎，有助於他人更快速掌握並行系統中的關鍵設計挑戰與對應解法。
評分 : 2 分
2.作業/隨堂測驗：
- 透過第一個作業，我重新學習 C 語言，從完全忘記 linklist 怎麼寫，到實作出 linux 風格的 linklist。
- 透過第二個作業，我學習到，linklist 到 BST、Quicksort、bit-wise 操作、hash table。
評分 : 1 分
3.期末專題
我的期末專題是設計一個高效能的 CPU-based 矩陣乘法系統，目標是從並行程式設計的角度深入理解矩陣乘法的效能瓶頸與優化策略。老師提供了 baseline 實作，包括單執行緒版本與多執行緒的 lock-based thread pool。我主要負責分析其效能問題並進行優化改進。 我首先觀察到，在原本的 lock-based thread pool 架構中，所有 worker threads 共享同一個任務佇列（queue），造成明顯的 contention（爭用）：每次任務的 enqueue/dequeue 都必須競爭同一把鎖，導致效能瓶頸與擴展性不佳。 為了解決這個問題，我設計並實作了一個 lock-free 的 thread pool 架構，採用 per-thread ring buffer，每個 worker 維護自己的 queue，避免共享鎖競爭與頻繁的同步延遲。我也結合了 semaphore 與 busy spin 的機制，讓 thread 在等待任務時先短暫 spin，若持續無任務再進入休眠，兼顧反應速度與資源效率。 不過這樣的設計仍可能出現負載不均問題，例如 round-robin 分派會導致某些 thread 忙碌、其他閒置。為此，我進一步導入 work stealing 技術，讓閒置 thread 能主動從其他 worker 的 ring buffer 偷取任務，達到動態負載平衡，提升整體 CPU 利用率。 在 thread 數從 1 到 16 的測試中，與原本的 lock-based 架構相比，lock-free + work stealing 設計平均提升約 6% 整體效能。雖然提升幅度不大，但這段過程讓我深入理解了 thread pool 架構、鎖競爭對效能的影響，以及實作 lock-free 結構時所需面對的記憶體一致性與 atomic 操作等問題。 除了 thread pool 架構優化外，我也針對矩陣乘法核心的每個 tile 進行 SIMD 向量化優化。原始實作將大矩陣切分為 64×64 的 tile，再切成 8×8 的 micro tile 進行乘加運算，但計算是以巢狀迴圈逐筆處理，無法充分利用現代 CPU 的 SIMD 能力。 因此我改用 AVX2 256-bit 向量指令集，將 8 個 float 載入 __m256 暫存器，並以 _mm256_fmadd_ps 執行 fused multiply-add（FMA）運算，一次完成 8 筆乘加操作。進一步地，我手動展開迴圈（loop unrolling），將原本一次處理一列的流程改為一次處理 8 列，同時計算 64 筆浮點數，加強了暫存器與 pipeline 的使用效率。 在整體實驗中，這個 SIMD + loop unrolling 優化版本，結合前述的 lock-free 架構，在同樣硬體下比原始 lock-based 多執行緒實作提升約 50% 的矩陣乘法效能。
評分 : 2 分
4.與授課老師的互動
一對一面談：
2025 年 5 月 29 日
這是本學期第一次面談，主要是討論自己的學習情況，老師也給了我一個測驗題，要 “如何在沒有FPU的情況下計算幾何平均” 。當時的我不知道什麼是定點數，也不知道如何求近似值。在後續，回家研讀先關的教材後，我學習到了定點數以及牛頓法。
2025 年 6 月 9 日
這是本學期第二次面談，我當時完成了老師提出的測驗題，但被說沒有討論 overflow 的問題，後續我改了設計方式，從先計算出最後的乘積 (product)，再去做牛頓法開 n 次方根，改成分成 P ^{E}，這樣就可以控制使否落在範圍內，這樣的設計不僅克服了 overflow ，還可以使誤差率都可壓在1%以下。
2025 年 6 月 18 日
這是本學期第三次面談，這次主要是討論我的期末專題的主題，由於我對並行程式有興趣，所以老師派發給我關於並行程式的專題。
評分 : 2 分
5.所見所聞所感，務必提及閱讀〈因為自動飲料機而延畢的那一年〉和回顧自身在本課程的投入狀況
從這個故事中，我學到了一件非常重要的事——知識就是力量。光有熱情與努力，並不足以讓事情真正推動起來。這個故事也讓我回想起大學時，和朋友們一起進行的各種計畫。那時候，我們常因為不熟悉其他領域的知識，導致許多問題處理起來格外吃力。久而久之，這些困難逐漸消磨了大家的熱情，最終許多計畫都不了了之。 回顧這堂課的學習歷程，我投入最多心力的是期末專題。在設計整個 lock-free thread pool 架構時，我深刻體會到：若想真正解決一個系統層級的問題，僅有直覺遠遠不夠，必須建立在充分的知識理解與實驗驗證之上。一開始我對於多執行緒相關的概念如 mutex lock、semaphore、thread pool、甚至 work stealing 幾乎完全陌生，面對問題時無從下手。但透過仔細研讀老師提供的並行程式設計教材、逐步實作、搭配對執行結果的觀察與分析，我才逐漸建立起這些機制背後的邏輯與使用時機。設計過程中，我也不斷面對新的挑戰：例如資料競爭、負載不均等問題，這些都驅使我學會使用 atomic operation、設計 ring buffer 以實現 lock-free 結構，並嘗試引入 batch stealing 來減少高頻率的 steal cost。此外，我也學會如何進行效能分析，包含以 perf stat 測量 cache miss 與 context switch 數量，來佐證我所提出的設計是否真的達到效能提升。每次的修改與驗證都是一次新的學習，也讓我認知到在多執行緒環境下，正確性與效能之間的平衡極為關鍵。這堂課不只是讓我補足了過去對系統程式設計的理解盲點，更讓我第一次真正感受到「設計一個能動的系統」背後所需的細節與思維深度。
評分 : 2 分
