Parallel Programming 相關筆記

Rain November 12, 2026

1. 考量重點:top

Parallelization 的第一步是找到可以獨立執行的工作，讓每個 Thread 處理自己的資料範圍，甚至不需要共享可變動的資料，就能大幅降低 Synchronization 的需求。

• 無需 mutex、lock
• Join() 是必須的，等待指定的 thread 完成

成本: 儘管不需要 mutex 和 lock，仍有可能以下成本:

• Thread Creation: 建立 Thread 需要成本，通常 Thread 在建立完成之後，會存放在 Thread Pool 中。
• Synchronization: Thread 之間可能需要同步。
• Memory Bandwidth: 多個 Thread 同時讀取資料，可能搶占記憶體頻寬。
• Load Imbalance: 每個 Thread 工作量可能不平均。
• Scheduling Overhead: 作業系統需要排程 Thread。

2. 效能評估:top

Amdahl’s Law 平行化的理論限制。假設一個程式有90%的工作可以平行化，另外10%必須依序執行，即使無限多個 Thread，仍然無法消除那10%的 Sequential Work。

公式: Speedup = 1 / ((1-P) + P/T)，其中 P 為可以平行化的比例，T 為 Thread 的數量

Speedup = 1 / (0.1 + 0.9/4) ≒ 3.08

3. Lambda Expression:top

Lambda 可以理解為一種匿名函式 (Anonymous Function)，不需要事先宣告名稱，就能直接建立一個可呼叫的物件。

形式: [Capture List] (Parameter List) { // Function Body }

• []: Capture List，決定如何取得外部變數，ex: [&, val], & 表示以 Variable Reference 方式存取其他外部，val 表示指定 val 變數以 Value Capture 方式存取。
• (): Parameter List，定義函式參數
• {}: Function Body，執行內容

4. std::function()top

可以用來保存不同種類的 Callable Object:

• Ordinary Function (普通函式)
• Lambda Expression
• Function Pointer
• Functor (Function Object)
• Member Function Wrapper (透過適當的綁定)
• 缺點: 可能有額外的間接呼叫成本

5. Race Condition:top

• 基本例子: 多執行緒對同一個 Vector 進行 Push Back。
• 解決方法: 使用 std::mutex，同一時間只允許一個 Thread 進入受保護的 Critical Section。

效能問題: 4個 Thread 各自找到1000萬筆符合條件的 Rectangle。

• 每個 Thread 都需要頻繁取得 Mutex
• 一次只有一個 Thread 能執行 Push Back
• 其他 Thread 必須等待
• Mutex 競爭可能讓平行化效益大幅降低
• 以上稱之為 Lock Contention

6. std::lock_guard 的特性: (RAII 特性)top

• 建立物件時，自動呼叫 Mutex 的 lock()
• 離開 Scope 時，自動呼叫 Mutex 的 unlock()
• 即使發生 Exception，也能夠過 Destructor 釋放鎖

7. std::unique_lock 的特性:top

• 可以在 Scope 尚未結束時，主動釋放 Mutex，之後再重新取得，因此仍可手動 lock() 和 unlock()。
• 可以搭配 defer_lock，意思是先建立 Lock Object，但暫時不取得 Mutex，稍後才決定何時取得鎖。

8. Deadlock 範例:top

不同 Thread 使用相反的鎖定順序:

std::mutex geometry_mutex;
std::mutex connectivity_mutex;

void update_geometry() {
    std::lock_guard<std::mutex> lock1(geometry_mutex);
    std::lock_guard<std::mutex> lock2(connectivity_mutex);
    …
}

void update_connectivity() {
    std::lock_guard<std::mutex> lock2(connectivity_mutex);
    std::lock_guard<std::mutex> lock1(geometry_mutex);
    …
}

Thread A: 持有 Geometry、等待 Connectivity
Thread B: 持有 Connectivity、等待 Geometry

• 解法一: 兩函式使用相同順序的 Lock。
• 解法二: 使用 std::scoped_lock，可以同時取得多把 Mutex，其使用的是 Deadlock Avoidance Algorithm 避免因這次多鎖取得而產生 Deadlock。

優點:

• 不需要手動決定取得多把 Mutex 的順序
• RAII 自動釋放所有鎖
• 程式碼簡潔
• 適合需要同時存取多個共享資源的情境

如果其他地方有不同的同步依賴，仍然可能 Deadlock。

9. Condition Variable: 讓 Thread 等待工作top

• 例如: 當 Queue 沒有工作時，Thread 仍然不斷 Polling，浪費 CPU 資源，更好的方式是使用 std::condition_variable
• 基本: std::mutex, std::condition_variable

常見操作:

• cv.wait: 等待通知，等待期間會釋放 Mutex
• cv.notify_one: 喚醒一個等待中的 Thread
• cv.notify_all: 喚醒所有等待中的 Thread

範例:

void producer(int task) {
    {
        std::lock_guard<std::mutex> lock(queue_mutex);
        task_queue.push(task);
    }
    cv.notify_one();
}
void worker() {
    {
        std::unique_lock<std::mutex> lock(queue_mutex);
        cv.wait(lock, [] {    // Predicate避免Spurious Wakeup
            return !task_queu.empty();
        });
        task = task_queue.front();
        task_queue.pop();
    }
    process_task(task)
}

10. Recursive Mutex 和 Reentrant Lockingtop

Self-Deadlock 範例:

std::mutex mtx;
void update_geometry() {
    std::lock_guard<std::mutex> lock(mtx);
    …
}
void rebuild_layout() {
    std::lock_guard<std::mutex> lock(mtx);
    …
    update_geometry();
}

同一個 Thread 已持有 Mutex，又試圖取得同一把不可遞迴的 Mutex。
std::recursive_mutex 允許同一個 Thread 重複取得同一把 Mutex:

• 每次 unlock() 都會讓計數減一，只有計數歸零，其他 Thread 才能取得這把 Mutex。
• 這也是為什麼實務上通常搭配 std::lock_guard 或 std::unique_lock，讓 RAII 管理。
• 缺點: 可能會讓 Synchronization Behavior 更難理解。更好的設計是 Public API + Internal Helper，讓外部 API 負責 Lock，內部 Helper 不再重複取的 Lock。
• Reentrant Function 函式執行過程中，可以再次進入該函式，而不破壞正確性。
• unique_lock vs. shared_lock 概念和 Smart Pointer 一樣，shared_lock 必須搭配 shared_mutex。

Last updated: November 12, 2026