# 平行程式 Lec1：淺談並行與分散式程式設計
---
## 什麼是平行計算 (The What and Why of Parallel Computing)
在深入探討平行計算之前，我們需要先理解其對立面 —— 傳統的循序計算模式。
### 從循序計算 (Sequential Computing) 談起
傳統的電腦架構，如馮紐曼架構 (von Neumann architecture)，其核心設計是透過一個程式計數器 (Program Counter, PC) 來依序執行指令。這意味著程式碼被視為一連串的指令，一次只執行一道，形成一個單一的控制流 (single thread of control)。
<center><img src="https://hackmd.io/_uploads/H1NOhgVoel.png" alt="image" width="50%" /></center>
**循序計算的特點：**
1. **單一執行緒**：程式在任何時刻都只有一條執行路徑。即使遇到 `if-else` 這樣的條件分支，也只會根據條件選擇其中一條路徑執行。
2. **逐一執行**：問題被分解成一系列離散的指令，這些指令按照程式碼的順序一個接一個地執行。
3. **單一 CPU 核心利用**：傳統上，軟體是為單一 CPU 核心設計的，即使在多核心處理器上運行，這類程式也只會使用到其中一個核心。
### 平行計算的定義
簡單來說，Parallel Computing (平行計算) 是指 **同時使用多個計算資源來解決一個計算問題**。相較於循序計算一次處理一個指令，平行計算透過將問題分解，並將這些子問題分配給多個處理器，來達成同時執行的目的，進而大幅縮短解決問題所需的時間。
### 釐清相似術語：Concurrent, Parallel, Distributed
在討論平行計算時，常會遇到幾個容易混淆的術語。雖然它們沒有絕對的官方定義，但業界普遍有以下共識：
* **Concurrent Computing (並行計算)**：指一個程式中有多個任務 (tasks) 在 **同一時間段內處於「進行中」(in progress) 的狀態**。這不代表它們「同時」在執行。例如，在單核心 CPU 上，作業系統可以快速地在多個 threads 之間切換，讓每個 threads 都執行一部分，給人一種它們都在運行的錯覺。它們是交錯執行 (interleaved)，而非真正平行的。
* **Parallel Computing (平行計算)**：指一個程式中有多個任務 **緊密協作 (cooperate closely)，並真正地「同時」執行** 以解決一個問題。這意味著底層必須有足夠的實體計算資源 (例如多個 CPU 核心)，讓每個任務都能分配到一個核心來獨立運行。
* **Distributed Computing (分散式計算)**：指一個程式需要與 **位於不同電腦上的其他程式** 協同合作來解決一個問題。這些程式運行在由網路連接的多台獨立電腦上，共同完成一個更大的目標，例如大型科學計算或雲端服務。
---
## 為何要使用平行計算？
推動平行計算發展的動力主要來自三個方面：**節省成本**、**解決更複雜的問題**，以及 **應對硬體架構的演進**。
### 1. 節省時間與金錢 (Save time and/or money)
這是最直接的動機。透過投入更多的計算資源 (更多的 CPU 核心)，理論上可以顯著縮短任務的完成時間。時間就是金錢，執行速度的提升直接轉化為成本的節省。例如，在密碼學領域，使用平行計算暴力破解 56-bit DES 金鑰的時間，從 1998 年的 56 小時 (成本 $250,000) 縮短到 2006 年的 6.4 小時 (成本 $10,000)。
### 2. 解決更大規模的問題 (Solve larger problems)
許多現代科學與工程問題的規模和複雜度，已經遠遠超出單一電腦所能負荷的極限，特別是在記憶體容量方面。
* **巨量資料 (Big Data)**：當資料量大到一台機器的記憶體甚至硬碟都無法容納時，就必須使用多台機器進行分散式處理。
* **複雜模擬與分析**：氣候模擬、藥物開發、能源研究、基因序列分析等領域，都需要龐大的計算能力，單機已無法在合理時間內完成。例如，AMD 的 [COVID-19 HPC Fund](https://www.amd.com/en/corporate/amd-covid-19-hpc-fund) 便利用高效能計算資源，加速了對 COVID-19 的藥物與疫苗研發。
### 3. 硬體架構的趨勢 (Architectures demand it!)
**"The free lunch is over."** 這句話精準地描述了硬體發展的轉捩點。
在 2002 年以前，開發者享受著「免費的午餐」：他們只需要撰寫循序執行的程式，然後等待下一代 CPU 的問世。由於摩爾定律 (Moore's Law) 的推動，CPU 的時脈速度 (Clock Speed) 不斷提升，使得舊程式在新硬體上能自動變快，無需任何修改。
然而，這個趨勢在 2000 年初遇到了物理瓶頸：
* **時脈速度的極限 (Wire Delay)**：當晶片製程進入奈米等級，電晶體間的導線延遲 (與電阻和電容的乘積 R\*C 成正比) 成為瓶頸，使得時脈速度難以再大幅提升。
* **功耗與散熱問題 (Power Consumption)**：更高的時脈速度意味著更高的功耗和廢熱。處理器的功率密度 (Power Density) 急遽上升，散熱成為了巨大的挑戰，若無法有效散熱，晶片將無法穩定運作。
> 約在 2002-2004 年後，處理器效能的成長曲線趨於平緩，時脈速度的提升遇到瓶頸。
> 為突破瓶頸，業界轉向在單一晶片上整合多個處理核心 (Multi-core)，核心數量的成長取代了時脈速度的成長。
這個轉變意味著，單純增加處理器核心數並不會讓傳統的循序程式變快。為了充分利用現代多核心處理器的強大能力，開發者 **必須** 撰寫平行程式。
---
## 為何與如何進行平行程式設計 (The Why and How of Parallel Programming)
### 為何需要手動撰寫平行程式？
既然硬體趨勢是多核心，為何不能開發一個聰明的編譯器，自動將循序程式轉換為平行程式呢？數十年來，研究人員在此方向上投入了大量努力，但成效非常有限。
主要困難在於 **相依性分析 (Dependency Analysis)**。編譯器很難在所有情況下都 100% 準確地判斷程式中的哪些部分是真正獨立、可以安全地平行執行的。尤其在 C/C++ 這類有指標 (pointer) 的語言中，不同的指標可能指向同一塊記憶體 (aliasing)，使得靜態分析變得極其困難。為了保證程式的正確性，編譯器只能採取保守策略，只要無法確定獨立性，就不進行平行化。
因此，將平行化的責任交給了最了解程式邏輯的開發者。開發者需要明確地告訴系統：哪些任務可以同時執行，以及它們之間需要如何溝通與協調。
### 平行化的基本思路：一個加總範例
假設我們需要計算 n 個數值的總和，每個數值都由一個獨立的函式 `Compute_next_value()` 產生。
**循序程式碼：**
```c=
// 循序計算 n 個數值的總和
sum = 0;
for (i = 0; i < n; i++) {
x = Compute_next_value(...);
sum += x;
}
```
#### 平行化步驟：
1. **分割 (Partitioning)**：假設我們有 `p` 個核心 (`p` 遠小於 `n`)。我們可以將 `n` 個計算任務大致平均分配給 `p` 個核心。每個核心計算約 `n/p` 個數值，並將它們加總到一個**私有 (private)** 的局部總和變數 `my_sum` 中。
2. **彙總 (Aggregation)**：當所有核心都完成了它們的局部計算後，需要將這些 `my_sum` 彙總起來得到最終的總和。
* **樸素方法**：所有核心將它們的 `my_sum` 發送給一個指定的「主核心」(master core)，由主核心循序地將它們相加。當核心數 `p` 很大時，主核心會成為效能瓶頸。
* **更佳方法 (樹狀彙總)**：核心兩兩配對相加，然後將結果再兩兩配對相加，以此類推，形成一個樹狀的計算結構。這種方式可以平行地進行多個加法運算，大大提高了彙總階段的效率。
<center><img src="https://hackmd.io/_uploads/B1S9Jb4sle.png" alt="image" width="70%" /></center>
> 上圖顯示，8 個核心的局部總和可以透過 3 個時間步驟的平行加法完成，而非 7 個時間步驟的循序加法。
這個例子突顯了手動設計平行演算法的重要性，因為一個聰明的彙總策略 (樹狀彙總) 是自動化工具很難「發現」的。
### 任務平行 (Task Parallelism) vs. 資料平行 (Data Parallelism)
撰寫平行程式主要有兩種策略：
* **Task Parallelism (任務平行)**：將問題中 **不同的任務** 分配給不同的核心。每個核心做的事情可能完全不同。
* **比喻**：兩位助教批改一份考卷，一位助教批改第 1-5 題，另一位批改第 6-10 題。他們處理的是同一份資料 (考卷)，但執行的任務不同。
* **Data Parallelism (資料平行)**：將問題中的 **資料** 進行分割，讓每個核心對其分配到的資料執行 **大致相同的操作**。
* **比喻**：兩位助教批改 100 份考卷，一位助教批改前 50 份，另一位批改後 50 份。他們執行的任務完全相同 (批改整份考卷)，但處理的資料不同。
本課程將主要聚焦於 Data Parallelism，因為它在科學計算和巨量資料處理中極為常見，且其平行性通常存在於迴圈 (loops) 之中，是效能優化的關鍵所在。
### 平行程式設計的核心挑戰：協調 (Coordination)
一旦將任務分散到多個核心，就必須對它們的行為進行協調。協調主要涉及以下三個方面：
1. **通訊 (Communication)**：核心之間交換資料的過程。例如，在加總範例中，各核心需要將其 `my_sum` 傳遞給其他核心。
2. **負載平衡 (Load Balancing)**：確保分配給每個核心的工作量大致相等，避免出現某些核心早已完成工作，卻在空等其他忙碌核心的情況。
3. **同步 (Synchronization)**：確保程式中的某些事件以正確的順序發生。例如，在進行樹狀彙總前，必須等待所有核心都完成它們的局部加總計算。
---
## 平行程式設計模型 (Parallel Programming Models)
Programming Model (程式設計模型) 是一套語言和函式庫的集合，它為開發者提供了一個抽象的機器視圖，讓我們可以專注於平行演算法的設計，而不用處理底層硬體的複雜細節。
### 共享記憶體模型 (Shared-Memory Model)
在共享記憶體模型中，所有執行緒 (threads) 共享同一個全域位址空間 (global address space)。
* **架構**：程式由多個 threads 組成，這些 threads 可以存取共享的變數 (例如全域變數或在堆 heap 上分配的物件)，同時也擁有自己的私有變數 (例如函式內的區域變數，存放在各自的堆疊 stack 中)。
* **通訊**：通訊是 **隱性 (implicit)** 的。一個 threads 只需將資料寫入共享變數，另一個 threads 便可直接讀取，從而完成資料交換。
* **共享變數**：在函式區域以外宣告的變數、heap、`static` 的 local variable。
* **挑戰**：最大的挑戰是 **競爭條件 (Race Condition)**。當兩個或多個 threads 同時存取同一個共享變數，且至少其中一個是寫入操作時，若沒有適當的同步機制，最終的結果將取決於 threads 執行的相對順序，可能導致程式出錯。
* **解決方案**：使用同步原語 (synchronization primitives)，如 **鎖 (Locks)**。在存取共享資源前，threads 必須先取得鎖；存取完畢後，再釋放鎖。鎖確保了在任何時刻，只有一個執行緒能進入被保護的程式碼區段 (稱為 **Critical Section**)，從而避免了 Race Condition。
```c=
// 使用 lock 保護共享變數 s 的更新
local_s1 = 0;
for (i = 0; i < n/2; i++) {
local_s1 = local_s1 + f(A[i]); // 在私有變數上計算
}
lock(lk); // 取得鎖
s = s + local_s1; // 進入 Critical Section，安全地更新共享變數
unlock(lk); // 釋放鎖
```
* **代表技術**：
* **Pthreads (POSIX Threads)**：一個較低階的 C 語言函式庫標準，開發者需要手動管理 threads 的建立、同步與資料共享，其本質為 System calls。
```c=
void* SayHello(void *foo) {
printf( "Hello, world!\n" );
return NULL;
}
int main() {
pthread_t threads[16];
int tn;
for(tn=0; tn<16; tn++) {
pthread_create(&threads[tn], NULL, SayHello, NULL);
}
for(tn=0; tn<16 ; tn++) {
pthread_join(threads[tn], NULL);
}
return 0;
}
```
* **OpenMP (Open Multi-Processing)**：一個較高階的模型，主要透過編譯器指導 (compiler directives) 來實現平行化。開發者只需在循序程式碼的特定區塊（如迴圈）前加上 **`#pragma omp parallel`** 等指令，編譯器就會自動生成對應的多 threads 程式碼。
```c=
#include “omp.h”
void main() {
// thread 數量預設為 core 數量
#pragma omp parallel
{
int ID = omp_get_thread_num();
printf(“ hello(%d) ”, ID);
printf(“ world(%d) \n”, ID);
}
}
```
### 分散式記憶體模型 (Distributed-Memory Model)
在分散式記憶體模型中，每個行程 (process) 都有自己獨立的記憶體空間，無法直接存取其他行程的記憶體。
* **架構**：程式由多個獨立的行程組成，它們可以在同一台機器的不同核心上，或在不同機器的核心上運行。
* **通訊**：通訊是 **顯性 (explicit)** 的。行程之間必須透過 **訊息傳遞 (Message Passing)** 來交換資料，例如一個行程呼叫 `send()` 函式，另一個行程呼叫 `receive()` 函式。
* **挑戰**：主要的挑戰是避免 **死結 (Deadlock)**。例如，如果兩個行程都執行 `send()` 等待對方 `receive()`，但它們的 `receive()` 操作又都寫在 `send()` 之後，那麼兩個行程就會永遠地互相等待，導致程式卡死。
* **解決方案**：
1. 調整 `send`/`receive` 的配對順序 (例如，行程 1 先 `send` 後 `receive`，行程 2 則先 `receive` 後 `send`)。
2. 使用 **非阻塞 (non-blocking)** 的通訊函式。
* **代表技術**：
* **MPI (Message Passing Interface)**：一個訊息傳遞的標準，定義了一系列函式庫的介面，是高效能計算 (HPC) 領域的事實標準 (de facto standard)。
```c=
for (i = 1; i < numprocs; i++) {
sprintf(buff, "Hello %d! ", i);
MPI_Send(buff, BUFSIZE, MPI_CHAR, i, TAG, MPI_COMM_WORLD);
}
for (i = 1; i < numprocs; i++) {
MPI_Recv(buff, BUFSIZE, MPI_CHAR, i, TAG, MPI_COMM_WORLD, &stat);
printf("%d: %s\n", myid, buff);
}
```
### 共享 vs. 分散式模型比較
| 特性 | 共享記憶體模型 (Shared Memory) | 分散式記憶體模型 (Message Passing) |
| :--- | :--- | :--- |
| **優點** | 隱性通訊，寫作較直觀；利用快取 (cache) 可達成低延遲通訊。 | 顯性通訊，不易出錯；資料佈局可控性高；可擴展到大規模叢集。 |
| **缺點** | 需處理 Race Condition；Cache 一致性問題可能導致效能下降；硬體擴展成本高。 | 顯性通訊，寫作較複雜；通訊延遲較高；可能發生 Deadlock。 |
### 資料平行模型 (Data-Parallel Model)
這是一種更抽象的模型，專注於對整個資料集合（如陣列、矩陣）套用平行操作。
* **架構**：程式仍是單一控制流，但其中包含了能在資料集合上平行執行的特殊運算子。例如 `C = A + B` 可能代表將陣列 `A` 和 `B` 的對應元素平行相加，結果存入陣列 `C`。
* **通訊與同步**：通訊和同步都隱含在平行運算子中，對開發者透明。
* **代表技術**：
* **GPU (Graphics Processing Unit) 程式設計 (CUDA, OpenCL)**：
* GPU 是一種為高吞吐量 (Throughput) 優化的處理器，擁有數千個小型核心，非常適合執行大規模的資料平行任務。
* 開發者需要撰寫一個稱為 **Kernel 函式**，這個函式會被 GPU 上的成千上萬個 threads 同時執行，每個 threads 處理一小部分資料。
* 資料需要在主機 (CPU) 記憶體和設備 (GPU) 記憶體之間 **明確地進行複製**。
`Sequential version`
```c=
int main() {
int A[ ] = {…};
int B[ ] = {…};
for (i = 0; i < N; i++) {
C[i] = A[i] + B[i];
}
}
```
`Parallel version`
```c=
__global__ void vecAdd(int A[ ], int B[ ], int C[ ]) {
int i = threadIdx.x;
C[i] = A[i] + B[i];
}
int main() {
int hA[ ] = {…};
int hB[ ] = {…};
cudaMemcpy(dA, hA, sizeof(hA), HostToDevice);
cudaMemcpy(dB, hB, sizeof(hB), HostToDevice);
vecAdd<<<1, N>>>(dA, dB, dC);
cudaMemcpy(dC, hC, sizeof(hC), DeviceToHost);
}
```
* **MapReduce**：
* 由 Google 提出 (未開源)，用於在大型電腦叢集上處理巨量資料集的程式設計模型。
* 開發者只需定義兩個函式：`Map` 函式和 `Reduce` 函式。
* `Map`：對輸入資料進行 **轉換和篩選**，提取出中間的 **鍵值對 (key-value pairs)**。
* `Reduce`：將具有相同鍵 (key) 的中間值 (values) 彙總起來，產生最終結果。
* 底層的資料分割、任務調度、節點間通訊等複雜工作都由框架自動處理。
<center><img src="https://hackmd.io/_uploads/BJLgyG4seg.png" alt="image" width="70%" /></center>
* Hadoop 為依據 Google 釋出之論文所建構出的開源專案，主要由 Java 撰寫。
---
## 效能評估 (Performance Evaluation)
寫完平行程式後，我們需要客觀的指標來評估其效能好壞。
### 加速比 (Speedup)
加速比是最直觀的指標，衡量平行程式相比於**最佳的循序程式**快了多少倍。
$$
S_p = \frac{T_{serial}}{T_{parallel}}
$$
其中 $S_p$ 是使用 $p$ 個處理器時的加速比，$T_{serial}$ 是循序執行時間，$T_{parallel}$ 是平行執行時間。
<center><img src="https://hackmd.io/_uploads/SkrHlf4oxe.png" alt="image" width="60%" /></center>
理想情況下，使用 $p$ 個核心能獲得 $p$ 倍的加速，稱為 **線性加速比 (Linear Speedup)**。但由於平行化會引入額外的開銷 (如通訊、同步、執行緒建立)，現實中很難達到。
### 效率 (Efficiency)
效率衡量了計算資源被有效利用的程度，是 **加速比** 與 **處理器數量** 的比值。
$$
E_p = \frac{S_p}{p} = \frac{T_{serial}}{p \cdot T_{parallel}}
$$
效率的理想值為 1 (或 100%)，代表所有處理器都被完美利用。通常，隨著處理器數量的增加，額外開銷的比重會上升，導致效率下降。
<center><img src="https://hackmd.io/_uploads/B1owlz4ilg.png" alt="image" width="60%" /></center>
### 可擴展性 (Scalability)
可擴展性描述了一個平行程式在增加處理器數量時，其效能提升的能力。
* **強擴展性 (Strongly Scalable)**：在 **固定問題大小** 的情況下，增加處理器數量，程式仍然能保持高效率（或獲得顯著的加速比）。這通常很難達成，因為問題大小固定時，每個處理器分配到的工作量會變少，使得平行開銷的佔比增加。
* **弱擴展性 (Weakly Scalable)**：在增加處理器數量的 **同時，也按比例增加問題大小**，程式能夠維持固定的效率。**這在許多科學計算應用中是常見且重要的特性**。
### 阿姆達爾定律 (Amdahl's Law)
Amdahl's Law 指出，對於一個 **固定大小** 的問題，其平行加速比的上限，受限於程式中 **必須循序執行部分** 的比例。
> **"Every parallel program contains at least one serial program"**
假設程式中循序部分的比例為 `s` (例如 $s = 0.1$ 代表 10% 的程式碼無法平行化)，可平行化部分的比例為 $p = 1-s$。那麼，在使用 $N$ 個處理器時，理論上的最大加速比為：
$$
\text{Speedup} \le \frac{1}{s + \frac{p}{N}} = \frac{1}{(1-p) + \frac{p}{N}}
$$
當處理器數量 $N$ 趨近於無窮大時，加速比的極限為：
$$
\lim_{N\to\infty} \text{Speedup} = \frac{1}{s}
$$
<center><img src="https://hackmd.io/_uploads/SkPg-fEieg.png" alt="image" width="60%" /></center>
這意味著，如果你的程式有 10% 無法平行化，那麼無論你使用多少個處理器，最大加速比也無法超過 10 倍。這凸顯了 **優化循序部分** 和 **提高平行化比例** 的重要性。
且這只是理想情況，實際上平行化處理必有其 overhead，導致 core 數量增加到一定程度時，speedup 反而會被大量的平行化成本抵銷。
### 古斯塔夫森定律 (Gustafson's Law)
Gustafson's Law 提供了另一個視角。它假設的不是固定問題大小，而是 **固定的平行執行時間**。這更符合現實中人們使用更強大的電腦來解決更大問題的情境。
$$
\text{Speedup} \le \frac{s + Np}{s + p} = s + Np = (1 - p) + Np = 1 + (N - 1)p
$$
該定律指出，如果問題的可平行化部分大小可以隨著處理器數量增加而增加，那麼加速比幾乎可以與處理器數量成線性增長。這解釋了為何在弱擴展性的場景下，即使循序部分的比例存在，我們仍然可以透過增加問題規模來獲得非常高的加速比。
---
## 總結 (Summary)
* 硬體從單核心走向多核心的趨勢，使得平行程式設計成為提升軟體效能的必經之路。
* 撰寫平行程式的核心是將工作進行有效分割，並妥善處理核心之間的 **通訊、負載平衡與同步**。
* 不同的 **程式設計模型**（共享記憶體、分散式記憶體、資料平行）為開發者提供了不同的抽象層次和工具集，適用於不同的硬體架構和問題類型。
* 評估平行程式效能時，除了看重 **加速比**，還需考慮 **效率** 和 **可擴展性**，並理解 **Amdahl's Law** 所揭示的理論極限。
---
## 參考資料 (References)
* [An Introduction to Parallel Programming, by Peter Pacheco](https://www.amazon.com/Introduction-Parallel-Programming-Peter-Pacheco/dp/0123742609)
* [Introduction to Parallel Computing, by Blaise Barney, Lawrence Livermore National Laboratory](https://computing.llnl.gov/tutorials/parallel_comp/)
* [MIT Course 6.189, "Multi-core Programming Primer"](https://ocw.mit.edu/courses/6-189-multicore-programming-primer-january-iap-2007/)
* [UCB Course CS267, "Applications of Parallel Computers"](https://sites.google.com/lbl.gov/cs267-spr2024/home)
Sign in with Wallet
Connect another wallet