您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> 關於.NET

範式轉移：多核時代並行程式設計的核心模式與記憶體考量

編輯：關於.NET

1986-2002 年微處理器效能年增 52%，開發者享受「免費午餐」——單靠硬體升級即得效能提升。摩爾定律紅利結束，多核普及，軟體必須顯式並行才能榨取效能。本文探討並行與並發差異、四大核心並行模式、記憶體階層對效能的影響，並展示 C++ PPL 與 .NET Parallel Extensions 程式碼範例。

並行 vs 並發

並發：處理多個邏輯獨立任務 (如 UI 回應、Web 伺服器請求)，目標為吞吐量與回應性，常用鎖協調共享資源，難點在非決定性錯誤 (死結、資料競爭)。
並行：將單一邏輯任務分解為可同時執行的子任務，目標為縮短延遲，同樣面臨共享資源同步挑戰，但強調結構化分解與排程。

核心並行模式

1. 結構化多執行緒

語法結構化的平行區塊：parallel_invoke (C++ PPL) / Parallel.Invoke (.NET) 同時執行多個 Lambda；parallel_for_each / Parallel.ForEach 迭代平行化。範例：QuickSort 遞歸分治平行化。

// C++ PPL
template<class T> void ParQuickSort(T* data, int len, T* scratch) {
    if (len < Threshold) InsertionSort(data, len);
    else {
        int mid = ParPartition(data[0], data, len, scratch, true);
        parallel_invoke(
            [=]{ ParQuickSort(data, mid, scratch); },
            [=]{ ParQuickSort(data+mid, len-mid, scratch); }
        );
    }
}

射線追蹤雙層 Parallel.For 亦屬此類。優點：演算法結構清晰、易擴展至多核、可復合。缺點：需自行處理共享資料同步。

2. 資料並行

對資料集合套用相同運算 (Map/Reduce)。PLINQ (AsParallel()) 讓 LINQ 查詢自動平行化。範例：K-means 叢類中心重算。

var q = from p in points.AsParallel()
        let center = nearestCenter(p, clusters)
        group p by center into g
        select new { index = g.Key, position = g.Aggregate(...) / g.Count() };
var newClusters = q.ToList();

Aggregate 第三參數支援部分結果合併，利於平行歸約。無副作用葉函數可避免資料競爭。

3. 管線與資料流

資料在階段間流動，Task/Future 表達依賴關係。Strassen 矩陣乘法：前 7 子任務獨立，後 4 任務依賴前者結果。ContinueWhenAll 串接依賴。

var m1 = Future.StartNew(() => (A11+B11)*(A22+B22));
var c11 = Task.ContinueWhenAll(delegate { ... }, m2, m3);

中等粒度資料流 (數百~數千運算) 平衡排程開銷與平行度。機器人技術常用事件觸發資料流模型。

4. 流式並行與記憶體階層

多核增加記憶體頻寬壓力。流式處理將資料分塊置入 L1/L2 快取，在替換前盡可能完成運算。QuickSort 改良：若子問題大小 < 快取容量則平行排序，否則循序處理。

if (sizeof(*data)*len < cache_size)
    parallel_invoke(...);
else {
    ParQuickSort(data, mid, cache_size);
    ParQuickSort(data+mid, len-mid, cache_size);
}

需顯式參數化快取大小，實務上較難通用，但揭示核心挑戰：並行排程與記憶體存取模式必須聯合優化。

平行陣列與 SPMD 模型

OpenMP parallel for 將迭代映射至執行緒團隊，屏障同步確保階段一致性。適用規則陣列運算、科學計算。挑戰：負載不平衡、非均質核心 (大核/小核) 排程困難。結構化多執行緒較靈活，犧牲部份記憶體局部性控制。

並發資料結構

標準容器非執行緒安全；全域鎖會序列化存取、消除平行度。需無鎖/細粒度鎖的並發版本：HashTable、Queue、Stack 等。範例：圖形連通元件標記，使用 atomic_claim (CAS) 以節點級鎖或無鎖原子操作並行 DFS，共享 Roots 與 EdgeTable 採並發雜湊表避免熱點。