# 平行程式 Lec2：簡介平行化硬體與軟體

本課深入探討平行計算的基石：硬體架構與軟體模型。我們將從單一處理器內部的平行化技術開始，逐步擴展到多處理器、多電腦的複雜系統，並最終了解程式設計師如何駕馭這些系統以實現高效能運算。

---

## 單一處理器的平行化 (Uniprocessor Parallelism)

即使在單一處理器 (Uniprocessor) 的時代，平行化也早已無所不在。現代處理器由數十億甚至上兆個電晶體 (Transistor) 組成，這些微小的硬體元件本身就是平行運作的。然而，對於高階程式設計師而言，這種電晶體層級的平行度是完全透明的，由硬體設計師負責管理。

在 2002 年多核心處理器普及之前，計算機架構師的主要目標是挖掘並利用 **指令層級平行化 (Instruction Level Parallelism, ILP)**，也就是在單一的指令流 (Instruction Stream) 中找出可以同時執行的指令，並讓硬體自動完成這項工作，而不需要程式設計師、編譯器或作業系統的介入。

### 方法一：指令層級平行化 (ILP)

以下將回顧幾種在計算機組織與結構課程中學到的關鍵 ILP 技術。這些概念不僅適用於單一處理器，其核心思想也將延伸至未來探討的多核心平行程式設計中。

#### 管線化 (Pipelining)

管線化是最經典的 ILP 技術之一，它將一個指令的執行過程切分成數個獨立的階段 (Stages)，例如 MIPS 架構中的五個階段：指令擷取 (Instruction Fetch)、指令解碼 (Instruction Decode)、執行 (Execute)、記憶體存取 (Memory Access)、寫回 (Write Back)。

透過讓多個指令的不同階段重疊執行，處理器可以大幅提升 **吞吐量 (Throughput)**，也就是單位時間內完成的指令數。

* **經典比喻：洗衣流程**
* **循序執行 (Sequential)**：洗完一籃衣服 (洗衣 -> 烘衣 -> 摺衣)，再開始下一籃。若處理四籃衣服，每籃 90 分鐘，總共需要 6 小時。
* **管線化執行 (Pipelined)**：當第一籃衣服在烘乾時，第二籃就可以開始洗衣。所有資源 (洗衣機、烘衣機、摺衣的人) 都被充分利用。處理四籃衣服僅需 3.5 小時。<center><img src="https://hackmd.io/_uploads/rJxcBbO2gl.png" alt="image" width="50%" /></center>
* **重點**
* Pipelining 改善的是整體的 Throughput，但單一指令的 **延遲 (Latency)** 並沒有縮短 (一籃衣服仍需 90 分鐘)。
* 整體效能會受限於最慢的那個管線階段。

#### 管線化的限制：危障 (Hazards)

理想情況下，管線可以讓 Cycles per instruction (CPI) 趨近於 1。然而，現實中存在多種「Hazards」，會導致管線停頓 (Stall)，從而降低效率。

1. **結構危障 (Structural Hazards)**：當兩個或多個指令在 **同一時間需要相同的硬體資源** 時發生。例如，處理器只有一個記憶體存取單元，但多個指令都想同時存取記憶體。
2. **資料危障 (Data Hazards)**：當後續指令 **需要用到前一個尚未完成指令的計算結果** 時發生。這也是最常見的 Hazard 類型。
3. **控制危障 (Control Hazards)**：當遇到分支 (Branch) 或跳躍 (Jump) 指令時，處理器 **無法立即確定下一個要執行的指令位址**，導致需要等待判斷結果。

#### 資料依賴性 (Data Dependencies)

Data Hazards 的根源是指令間的資料依賴性，主要分為三種類型：

1. **Read-after-Write (RAW) / Flow Dependence (資料流動依賴)**
* **定義**：後續指令需要讀取先前指令寫入的結果。
* **特性**：這是 **真正的依賴關係 (True Dependence)**，無法被消除，只能透過等待或資料前饋 (Forwarding) 等技術來解決。
2. **Write-after-Read (WAR) / Anti-Dependence (反依賴)**
* **定義**：後續指令要寫入的目標，是先前指令需要讀取的來源。
* **特性**：這是 **假的依賴關係 (False Dependence)**，通常是因為共用同一個暫存器導致的。可以透過 **暫存器重命名 (Register Renaming)** 技術來消除。
3. **Write-after-Write (WAW) / Output Dependence (輸出依賴)**
* **定義**：兩個指令寫入同一個目標。
* **特性**：這同樣是 **假的依賴關係**，也可以透過暫存器重命名來消除。

#### 亂序執行 (Out-of-Order Execution, OOO)

為了解決因 Data Hazards 導致的管線停頓，現代處理器引入了亂序執行機制。其核心思想是：當一個指令因為依賴關係而卡住時，允許其後方沒有依賴關係的指令「插隊」先執行。
硬體 (如 Tomasulo 演算法中的 Reservation Station) 會動態檢查指令的依賴關係，只要一個指令所需的操作數 (Operands) 都準備好了，就將其分派到對應的功能單元 (Functional Unit) 執行，而無需按照程式碼的原始順序。

#### ILP 技術的現代應用與挑戰

* **超純量 (Superscalar)**：處理器內建多個功能單元 (如整數運算單元、浮點運算單元)，使其能夠在一個時脈週期內同時執行多個指令，進一步降低 CPI 至小於 1。
* **預測執行 (Speculative Execution)**：為了解決 Control Hazards，處理器會「猜測」分支指令的走向 (例如，透過 Branch Prediction)，並預先執行猜測路徑上的指令。
* **猜對了**：效能大幅提升，避免了停頓。
* **猜錯了**：必須撤銷 (Undo) 已經執行的指令，並回復到正確的狀態，這會浪費時間和功耗。

#### Superscalar vs. VLIW 架構

決定「哪些指令可以同時執行」這件事，可以在硬體或軟體層面完成，從而衍生出兩種主流架構：

1. **Superscalar (超純量)**
* **決策者**：**硬體 (Hardware)**。
* **運作方式**：Compiler 產生循序的指令碼，由處理器內部的動態排程器 (Dynamic Scheduler) 在執行期間分析依賴關係，並決定如何將指令分派到不同的功能單元平行執行。
* **優點**：對 Compiler 較為簡單。
* **缺點**：硬體設計非常複雜。
2. **VLIW (Very Long Instruction Word, 超長指令字)**
* **決策者**：軟體 (Software)，通常是 **Compiler**。
* **運作方式**：Compiler 在編譯時期就分析完依賴關係，並將可以平行執行的指令打包成一個「超長指令」。硬體只需無腦地按照這個打包好的指令來執行即可。
* **優點**：硬體設計相對簡單。
* **缺點**：對 Compiler 的要求極高，且程式碼的可移植性較差。

### 方法二：向量處理與 SIMD (Vector Processing/SIMD)

前述的 ILP 技術大多對程式設計師是透明的，但 **向量處理** 和 **SIMD** 是一個重要的轉折點：**程式設計師可以透過程式碼來顯式地表達這一層級的平行度**。這也是本課程第一次作業的核心主題。

#### 向量處理器 (Vector Processor)

傳統處理器處理的是 **純量 (Scalar)** 資料，一次處理一個數值。而向量處理器擁有 **向量暫存器 (Vector Registers)**，一個暫存器可以容納一整個向量 (一組數據)。

* **範例：向量加法 `C[i] = A[i] + B[i]`**
* **純量作法**：使用迴圈，一次處理一個 `i`。
* **向量作法**：一條 `ADDV.D V3, V1, V2` 指令，就可以將整個向量 `A` (存於 `V1`) 和向量 `B` (存於 `V2`) 的對應元素相加，結果存入向量 `C` (`V3`)。硬體會平行地完成所有元素的加法運算。

#### SIMD 架構 (Single Instruction, Multiple Data)

SIMD 可以視為向量處理器的一個簡化版、更具成本效益的變體。它同樣遵循「一條指令處理多筆資料」的原則，但其向量寬度是固定的，不像向量處理器那樣靈活可變。
* **特性**：
* 一個中央控制器向多個處理單元 (Processing Elements, PE) 廣播同一條指令。
* 所有運算是 **完全同步 (Fully Synchronized)** 的。
* 硬體成本相較於向量處理器更低，因此在現代 CPU 中被廣泛應用。

#### SIMD 的應用：多媒體擴充指令集

SIMD 最初是為了解決多媒體處理效能不足的問題而被提出的。當時，許多多媒體資料 (如影像、音訊) 的精度不高 (例如 8-bit 或 16-bit)，而 CPU 卻是 32-bit 的。用一個 32-bit 的暫存器只處理一個 8-bit 的資料，造成了硬體資源的浪費 (Underutilized)。

* **次字組平行化 (Sub-word Parallelism)**：這個概念的核心是將一個 32-bit 的暫存器視為多個較小的資料單位的集合。
* 一個 32-bit 暫存器可以看作是：
* 2 個 16-bit 的資料。
* 4 個 8-bit 的資料。
* **指令擴充**：CPU 廠商為此設計了新的指令，如 `add.q` (quad-add)，可以一條指令同時完成 4 組 8-bit 資料的加法運算。
* **演進**：從 Intel 的 MMX，到後來的 SSE、AVX，再到現在的 AVX-512，SIMD 暫存器的寬度越來越大，平行處理的能力也越來越強。
<center><img src="https://hackmd.io/_uploads/SkgtaG_3xg.png" alt="image" width="70%" /></center>

#### 如何在程式中實現 SIMD：迴圈向量化 (Loop Vectorization)

由於 C/C++ 等高階語言本身沒有原生的向量資料型別，要利用 SIMD 的威力有以下幾種主要方式：

1. **Compiler 自動向量化 (Auto-Vectorization)**
* **方式**：讓 Compiler 自動分析循序的迴圈程式碼，並將其轉換成使用 SIMD 指令的向量化版本。
* **挑戰**：Compiler 的能力有限。尤其在 C/C++ 中，**指標別名 (Pointer Aliasing)** 問題（即兩個不同的指標可能指向同一個記憶體位置）會讓 Compiler 無法 100% 確定迴圈的每次迭代 (Iteration) 之間是否獨立。為了保證程式的**正確性**，只要有任何不確定的依賴關係存在，Compiler 就會放棄向量化。
* **對策**：程式設計師可以提供提示 (Hints)，或修改寫法來幫助 Compiler 進行分析。
2. **使用內建函式 (Intrinsic Functions)**
* **方式**：當 Compiler 無法自動向量化時，程式設計師可以主動呼叫由 Compiler 提供的、與特定 SIMD 指令一對一對應的內建函式。
* **優點**：可以精確控制 SIMD 的使用，且比直接寫組合語言有更好的可移植性。
* **範例**：呼叫一個名為 `_mm_add_ps` 的 Intrinsic，Compiler 就會將其轉換成一條 SSE 的 4-float 加法指令。
3. **撰寫行內組合語言 (Inline Assembly)**
* **方式**：在 C/C++ 程式碼中直接嵌入特定平台的組合語言。
* **缺點**：可移植性極差，且需要深入了解底層硬體指令集，通常不建議使用。

> 延伸閱讀：
> * [Programming Assignment I: SIMD Programming](https://nycu-sslab.github.io/PP-f25/assignments/HW1/)
> * [平行程式 Parallel Programming HW 1](https://hackmd.io/@Jaychao2099/PP-2025-HW1)

#### 通用圖形處理器 (GP-GPU) 與 SIMT

GPU 的架構也具有 SIMD 的特性，但又有所不同。NVIDIA 稱其為 **SIMT (Single Instruction, Multiple Thread)** 架構。

* **概念**：在 GPU 中，大量的執行緒 (Threads) 會被分組 (稱為 Warp 或 Wavefront)。在同一組內的 thread 會同時執行相同的指令，但處理的是不同的資料。這就像 SIMD，但操作的單位從「資料」變成了「thread」。
* **應用**：這種架構非常適合處理高度平行化的任務，如圖學渲染、科學計算與人工智慧。將在後續課程中詳細介紹 CUDA 程式設計模型。
<center><img src="https://hackmd.io/_uploads/HJBhAfu3gx.png" alt="image" width="40%" /></center>

### 方法三：多執行緒 (Multithreading)

除了在指令層級尋找平行度 (ILP)，也可以在更高的層次上建立平行度，就是 **執行緒層級平行化 (Thread-Level Parallelism, TLP)**。

#### 執行緒層級平行化 (TLP)

TLP 的核心是透過建立多個執行緒 (Threads of execution)，讓它們在多個處理器上 **真正地平行 (Parallel)** 執行，或在單一處理器上 **併發 (Concurrent)** 執行，以提升系統吞吐量或縮短單一程式的執行時間。

* **應用場景**：
* 提升執行多個程式時的系統吞吐量。
* 加速單一多執行緒程式的執行時間，特別是當某些 thread 在等待 I/O 時，其他 thread 可以繼續使用 CPU 進行計算，實現 I/O 和計算的重疊 (Overlapping)。

#### 行程 vs. 執行緒：記憶體佈局

* **單執行緒行程 (Single-threaded Process)**：擁有獨立的程式碼 (Code)、資料 (Data)、檔案 (Files) 資源，以及自己的暫存器 (Registers) 和堆疊 (Stack)。
* **多執行緒行程 (Multi-threaded Process)**：同一個 process 內的所有 thread 共享程式碼、資料區 (如全域變數) 和檔案資源。但是，**每個 thread 都擁有自己私有的暫存器和堆疊空間**，以確保它們可以獨立執行函式呼叫。

#### Thread 的建立與管理

* **常見模型**：
* **cobegin/coend**：區塊內的程式碼可以平行執行，語法結構較清晰。
* **fork/join**：`fork` 會建立一個新的 thread 去執行特定任務，而主 thread 可以繼續執行。`join` 則是用來等待被 `fork` 出去的 thread 完成工作。這是 `Pthreads` 等函式庫採用的模型。
* **效能考量：避免過多的 thread**
* Thread 的建立是有 **成本 (Overhead)** 的，它涉及到系統呼叫 (System Call)。
* 過多的 thread 會導致頻繁的 **Context Switch**，其成本（儲存和回復暫存器狀態）可能抵銷平行化帶來的好處。
* **通用準則**：建立的 thread 數量通常等於或接近底層硬體的核心數或硬體 thread 數。

#### 軟體執行緒 與 硬體執行緒

* **軟體執行緒**：由作業系統 (OS) 排程管理。程式設計師無法精確控制哪個 thread 在何時何地執行。但可以透過 **CPU Affinity** 或 **CPU Pinning** 技術，建議 OS 將特定 thread「綁定」到特定的 CPU 核心上執行。
* **硬體多執行緒 (Hardware Multithreading)**：為了解決軟體 Context Switch 成本過高的問題，硬體層面也提供了支援。
* **核心思想**：在處理器內部複製多份 thread 的狀態（主要是暫存器組）。
* **運作方式**：當一個 thread 因為 Cache Miss 或其他原因停頓時，硬體可以 **幾乎零成本地** 切換到另一個硬體 thread 繼續執行，而無需將暫存器內容存到記憶體中。

#### Threaad 切換方式
* **Fine-Grained (細粒度)**：每個 cycle 切換。
* **Coarse-Grained (粗粒度)**：當 thread 停頓 (stall) 時，切換 thread。

#### 結合 ILP 與 TLP：同步多執行緒 (Simultaneous Multithreading, SMT)

SMT 是硬體多執行緒的極致展現，Intel 將其商業化並命名為 **Hyper-Threading**。

* **動機**：即使在一個 Superscalar 處理器中執行單一 thread，也很難讓所有的功能單元 (Functional Units) 時時刻刻都保持忙碌。總會有一些功能單元因為資料依賴或指令類型等原因而閒置。
* **核心概念**：SMT 允許 **兩個或多個硬體 thread** 在 **同一個時脈週期內**，**共享並競爭同一個核心的所有功能單元**。
* **運作方式**：
* 如果兩個 thread 剛好需要使用不同的功能單元（例如，一個需要整數運算，另一個需要記憶體讀取），它們就可以 **真正地平行執行**，就像有兩個核心一樣。
* 如果兩個 thread 需要競爭同一個功能單元，硬體排程器會進行仲裁，讓它們交錯使用。
* **結果**：一個 `4 core 8 thread` 的 CPU，意味著它有 4 個物理核心，但每個核心支援 2 個 SMT 硬體 thread，能夠更有效地利用核心內部的運算資源。
<center><img src="https://hackmd.io/_uploads/Sy2r0eYheg.png" alt="image" width="70%" /></center>

#### 比較

### 方法四：單一處理器記憶體系統 (Uniprocessor Memory Systems)

平行化不僅僅是運算的問題，記憶體存取更是效能的關鍵瓶頸。

#### CPU 與記憶體效能的差距

數十年來，CPU 的效能成長速度遠遠超過 DRAM 的速度，形成了所謂的 **記憶體高牆 (Memory Wall)**。即使 CPU 運算能力再強，如果大部分時間都在等待從慢速記憶體中獲取資料，整體效能依然會很差。

#### 局部性原則 (Principle of Locality)

幸運的是，程式的記憶體存取行為並非完全隨機，而是遵循局部性原則，這是現代記憶體系統設計的基石。

1. **時間局部性 (Temporal Locality)**：如果一個資料被存取了，它在不久的將來很可能會被再次存取 (例如，迴圈中的變數)。
2. **空間局部性 (Spatial Locality)**：如果一個記憶體位置被存取了，它附近的記憶體位置也很可能在不久的將來被存取 (例如，循序存取陣列中的元素)。

#### 記憶體階層 (Memory Hierarchy)

為了利用局部性原則來彌補 CPU 與記憶體的速度鴻溝，計算機架構師設計了記憶體階層：

* **結構**：在快速但小容量的 CPU 暫存器和慢速但大容量的主記憶體 (DRAM) 之間，插入了多層級的 **快取記憶體 (Cache Memory)**，如 L1, L2, L3 Cache。
* **原理**：
* 離 CPU 越近的層級，速度越快，容量越小，成本越高。
* 當 CPU 需要資料時，會先從最快的 L1 Cache 開始尋找。
* 如果 L1 Cache 中有 (稱為 Cache Hit)，則直接高速存取。
* 如果沒有 (稱為 Cache Miss)，則往下一層級 (L2, L3, ...) 尋找，直到在主記憶體中找到。
* 一旦找到，會將該資料及其附近的一塊資料 (稱為一個 Cache Line) 一起載入到上層 Cache 中（根據 Spatial Locality），以備將來（根據 Temporal Locality）使用。

這個階層結構成功地讓單一處理器在大多數情況下都能夠以接近 Cache 的速度運作。**然而，當我們進入多核心世界時，這個設計將引發新的、更複雜的問題**。

---

## 顯式平行計算機架構 (Explicit Parallel Computer Architectures)

現在，將焦點從 **單一處理器內部** 轉向由 **多個處理單元構成** 的顯式平行系統。

### 平行架構的基礎

#### Flynn's Taxonomy

這是一個經典的平行計算機分類法，根據 **指令流 (Instruction Stream)** 和 **資料流 (Data Stream)** 的數量進行劃分：

* **SISD (Single Instruction, Single Data)**：傳統的單一處理器循序電腦。
* **SIMD (Single Instruction, Multiple Data)**：單一指令作用於多個資料，如前述的向量處理器和 SIMD 擴充。
* **MIMD (Multiple Instruction, Multiple Data)**：最通用的平行架構。多個處理器可以同時執行不同的指令來處理不同的資料。現代的多核心 CPU 和電腦叢集都屬於此類。
* **MISD (Multiple Instruction, Single Data)**：多個指令處理同一個資料流。較為罕見，例如容錯系統中的設計。

本課程的後續內容將主要圍繞 **MIMD** 架構展開。

### 架構一：共享記憶體架構 (Shared-Memory Architectures)

在共享記憶體架構中，所有的處理器 (或核心) 共享同一個全域位址空間 (Global Address Space)，可以像存取本地記憶體一樣直接存取系統中的任何記憶體位置。處理器間的溝通是 **隱式 (Implicit)** 的，透過對共享變數的讀寫操作來完成。

#### UMA (Uniform Memory Access)

* **定義**：所有處理器存取任何記憶體位置的延遲都是相同的。
* **典型實現**：早期的對稱式多處理器 (Symmetric Multiprocessor, SMP) 系統，多個核心透過共享的匯流排 (Bus) 連接到同一個記憶體控制器。
<center><img src="https://hackmd.io/_uploads/H1OD7Wtnxe.png" alt="image" width="50%" /></center>

#### NUMA (Non-Uniform Memory Access)

* **定義**：處理器存取不同記憶體位置的延遲是不同的。通常，存取離自己較近的「本地」記憶體會比較快，而存取離其他處理器較近的「遠端」記憶體會比較慢。
* **典型實現**：現代的多路 (Multi-socket) 伺服器或單一晶片上的多核心處理器。每個 CPU 或核心群組都有自己的記憶體控制器和本地記憶體。
* **事實**：**現今幾乎所有的多核心系統，本質上都是 NUMA 架構**，因為每個核心都有自己的私有 L1/L2 Cache，存取自己 Cache 中的資料遠比存取其他核心的 Cache 或主記憶體要快得多。
<center><img src="https://hackmd.io/_uploads/HyiOQZtngx.png" alt="image" width="50%" /></center>

#### 快取帶來的挑戰：快取一致性 (Cache Coherence)

當多個核心都擁有自己的私有 Cache 時，一個嚴重的問題出現了：**如果多個核心的 Cache 中都存有同一個共享記憶體位置的副本，當其中一個核心修改了它的副本時，如何確保其他核心不會讀到過期 (Stale) 的舊資料？**

* **範例**：
1. 變數 `U` 在主記憶體中的值為 `5`。
2. P1 和 P3 都讀取了 `U`，因此它們各自的 Cache 中都有了一份值為 `5` 的副本。
3. P3 將 `U` 的值修改為 `7`。如果採用 **Write-Back Cache** 策略，P3 只會更新自己 Cache 中的副本，而不會立即寫回主記憶體。
4. 此時，若 P1 或 P2 再次讀取 `U`，它會從自己的 Cache 中讀到過期的值 `5`，導致程式錯誤。
* **解決方案：快取一致性協定 (Cache Coherence Protocol)**
* 由 **硬體** 自動執行的機制，用來維護所有 Cache 副本的一致性。
* 常見的作法是基於 **窺探 (Snooping)** 的 **Write-Invalidate** 協定：當一個處理器要寫入某個 Cache Line 時，它會 **透過共享匯流排發出一個「作廢」訊號**。其他所有擁有該 Cache Line 副本的處理器在「窺探」到這個訊號後，會將自己的副本標記為無效 (Invalid)。下次它們需要讀取該資料時，就會因為副本無效而觸發 Cache Miss，從而被迫去讀取最新的值。
* **對程式設計師的意義**：你不需要親自處理快取一致性，硬體會保證 **對於同一個記憶體位址，你讀到的永遠是最近一次被寫入的值**。

#### NUMA 帶來的挑戰：記憶體一致性 (Memory Consistency)

快取一致性協定只解決了「單一記憶體位址」的讀寫問題。但在 NUMA 架構中，由於存取不同記憶體位置的速度差異，會引發一個更微妙的問題：**對「不同記憶體位址」的讀寫操作，其完成的順序是否會和程式碼的順序一致？**

* **範例：基於 Flag 的同步**

    // 初始值: A = 0, flag = 0
    // 處理器 P1 執行:         // 處理器 P3 執行:
    A = 1;                     while (flag == 0); /*spin idly*/
    flag = 1;                  print(A);

* **程式設計師的預期**：P1 先完成 `A = 1`，再完成 `flag = 1`。P3 看到 `flag` 變為 `1` 後，跳出迴圈，此時 `A` 應該已經是 `1` 了，所以應該印出 `1`。
* **實際可能發生的情況**：在 NUMA 系統中，變數 `A` 和 `flag` 可能位於物理上不同的記憶體模組。假設 P1 寫入 `A` 的路徑很長（例如 `A` 在遠端記憶體），而寫入 `flag` 的路徑很短。這可能導致 `flag = 1` 這個操作比 `A = 1` **更早完成並被 P3 看到**。結果 P3 跳出迴圈去讀取 `A` 時，`A` 的值仍然是舊的 `0`，最終印出 `0`。
* **問題根源**：快取一致性只保證了在任一時間點，所有處理器看到的 `A` 是一致的，看到的 `flag` 也是一致的。但它 **不保證** `A` 和 `flag` 這兩個 **不同變數** 之間的操作順序。
* **解決方案：記憶體一致性模型 (Memory Consistency Model)**
* 這是一個 **程式設計師與硬體系統之間的契約 (Contract)**，它定義了記憶體操作（特別是跨處理器的操作）可以被重新排序的規則。程式設計師必須了解並遵守這個模型，才能寫出正確的平行程式。
* **循序一致性 (Sequential Consistency)**：
* 這是最直觀、最嚴格的記憶體模型。
* **保證**：
1. 每個處理器內部的記憶體操作，其執行順序與程式碼順序完全一致 (維持 Program Order)。
2. 所有處理器的操作看起來像是以某種全域的、交錯的 (Interleaving) 順序在單一記憶體上 **原子地 (Atomically)** 執行。
* 在 Sequential Consistency 模型下，上述範例可以保證印出 `1`。但由於其嚴格的順序限制會嚴重影響效能，現代處理器大多採用更寬鬆的 **Relaxed Consistency Models**。

### 架構二：分散式記憶體架構 (Distributed-Memory Architectures)

在分散式記憶體架構中，系統由多個獨立的 **節點 (Node)** 組成，每個節點都有自己的處理器和 **私有記憶體 (Private Memory)**。一個節點無法直接存取另一個節點的記憶體。

* **溝通方式**：處理器間的溝通必須是 **顯式 (Explicit)** 的，通常是透過網路進行 **訊息傳遞 (Message Passing)**。
* **典型實現**：
* **MPP (Massively Parallel Processor)**：使用客製化、高效能的專用網路連接大量節點的超級電腦。
* **COW (Cluster of Workstations)**：使用標準化的網路（如乙太網路 Ethernet）將多台商用電腦連接起來的電腦叢集。
* **超級電腦 (Supercomputers)**：現今 Top500 排行榜上的超級電腦，絕大多數都屬於分散式記憶體架構，它們整合了數萬到數百萬個 CPU 核心，並經常搭配 GPU 來進行加速。

---

## 平行軟體 (Parallel Software)

了解了底層硬體後，接著來探討如何在這些硬體上進行程式設計。

### 模型一：共享記憶體模型 (Shared-Memory Model)

* **核心**：程式設計師透過多執行緒 (Multithreading) 來開發。
* **資料劃分**：
* **共享變數 (Shared Variables)**：所有 thread 都可以讀寫，是溝通的媒介。
* **私有變數 (Private Variables)**：每個 thread 獨有一份，通常是函式內的區域變數（位於各自的 Stack 上）。
* **主要挑戰：非確定性 (Nondeterminism) 與 競爭條件 (Race Condition)**
* 由於 OS 排程的不確定性，多個 thread 的執行順序是不可預測的。
* 如果多個 thread 在沒有適當保護的情況下，同時存取（其中至少有一個是寫入）同一個共享變數，就會發生 **Data Race**，導致程式結果不可預測且通常是錯誤的。
* **解決方案：同步 (Synchronization)**
* 為了避免 Data Race，必須使用同步機制來確保對共享資源的 **互斥存取 (Mutual Exclusion)**。我們將在後續課程中學習 Mutex, Semaphore, Monitor 等同步原語 (Primitives)。
* **執行緒安全 (Thread Safety)**
* 一個函式或函式庫如果是 Thread-Safe，意味著它 **可以被多個 thread 同時安全地呼叫，而不會產生 Data Race**。
* 一個常見的陷阱是使用了 **`static` 區域變數**的 C 函式。`static` 變數實際上是存放在全域資料區，等同於一個被所有 thread 共享的變數。如果函式內有對其的寫入操作，而沒有同步保護，那麼這個函式就不是 Thread-Safe 的。

> 延伸閱讀：
> * [Lec3：共享記憶體程式設計 - Pthreads](https://hackmd.io/@Jaychao2099/PP-2025-3)
> * [Lec4：共享記憶體程式設計 - OpenMP](https://hackmd.io/@Jaychao2099/PP-2025-4)

### 模型二：分散式記憶體模型 (Distributed-Memory Model)

* **核心**：程式設計師透過多行程 (Multiprocessing) 來開發，最廣泛使用的標準是 **MPI (Message Passing Interface)**。
* **溝通方式**：
* Process 之間透過明確的 `Send` 和 `Receive` 函式來傳遞訊息。
* 除了點對點的通訊，MPI 也提供了高效的 **群體通訊 (Collective Communication)** 操作，如：
* **Broadcast**：一個 process 將資料廣播給所有其他 process。
* **Reduction**：將所有 process 的資料進行匯總運算（如加總、找最大值），並將結果送到一個 process 。

> 延伸閱讀：
> * [Lec5：分散式記憶體程式設計 - MPI](https://hackmd.io/@Jaychao2099/PP-2025-5)
> * [Lec9：分散式記憶體程式設計 - MapReduce](https://hackmd.io/@Jaychao2099/PP-2025-9)

### 模型三：混合式系統程式設計 (Programming Hybrid Systems)

現代的高效能計算系統通常是混合式的。例如，一個叢集由多個節點組成（分散式記憶體），而每個節點內部又有多個共享記憶體的核心（共享記憶體）。

在這種系統上，可以採用混合式程式設計：

* **跨節點 (Inter-node)**：使用 MPI 進行 process 間的訊息傳遞。
* **節點內 (Intra-node)**：使用 Pthreads 或 OpenMP 進行執行緒層級的平行化，以充分利用節點內的多核心資源。

---

## 總結 (Summary)

* 單一處理器為了提升效能，發展出 **指令層級平行化 (ILP)** 技術，如管線化 (Pipelining)、超純量 (Superscalar) 與亂序執行 (Out-of-Order Execution)。這些技術多半由硬體自動完成，對程式設計師隱藏。
* 需要程式設計師明確介入的 **SIMD (Single Instruction, Multiple Data)** 平行化，是透過向量處理來同時操作多筆資料的關鍵技術，也是第一次作業的核心。
* 理解 **執行緒層級平行化 (TLP)** 與結合 ILP 與 TLP 的 **同步多執行緒 (SMT / Hyper-Threading)** 技術，能了解單一核心如何能更有效地被利用。
* 記憶體系統是另一個核心議題。CPU 與記憶體之間存在速度鴻溝 (Memory Wall)，若能利用 **局部性原則 (Principle of Locality)** 和 **記憶體階層 (Memory Hierarchy)**，特別是快取 (Cache)，此問題可被緩解。
* 現代平行計算機的主流架構：
1. **共享記憶體架構 (Shared-Memory)**：
* UMA 與 NUMA。
* 多核心環境下衍生的兩大關鍵問題：
* 由硬體解決的 **快取一致性 (Cache Coherence)**。
* 程式設計師必須面對的、關乎不同記憶體操作順序的 **記憶體一致性模型 (Memory Consistency Model)**。
2. **分散式記憶體架構 (Distributed-Memory)**：以獨立節點和私有記憶體為基礎，其通訊必須透過 **訊息傳遞 (Message Passing)** 來明確執行。

總體而言，本課從硬體演進的脈絡，解釋了為何平行程式設計在今日不可或缺，並為後續將探討的共享記憶體程式設計模型 (如 Pthreads) 與分散式記憶體程式設計模型 (如 MPI) 鋪平了道路。

---

## 參考資料 (References)

* [UC Berkeley (UCB) 的平行程式設計短期課程](http://parlab.eecs.berkeley.edu/2012bootcamp)
* [卡內基梅隆大學 (Carnegie Mellon University) 的公開課程：平行計算機架構與程式設計 (CS 418)](http://www.cs.cmu.edu/afs/cs/academic/class/15418-s11/public/lectures/)
* [勞倫斯利佛摩國家實驗室 (Lawrence Livermore National Laboratory) 的平行計算簡介](https://computing.llnl.gov/tutorials/parallel_comp/)