教材:10710周志遠教授平行程式
https://www.youtube.com/playlist?list=PLS0SUwlYe8cxqw70UHOE5n4Lm-mXFXbZT

20250820 筆記
內容可能有錯僅供參考

第1C講 平行程式
第1D講 平行程式
第2A講 平行電腦與平行模型的分類
第2B講 平行程式模型的本質：硬體抽象層

今日大綱
什麼是平行計算？
生活中的平行計算例子
平行計算與分散式計算的差異
為什麼需要平行計算？
平行計算的演進階段
平行系統架構分類與程式模型
1.Flynn's 經典分類法
2.記憶體架構分類
3.程式模型分類

### 什麼是平行計算？

平行計算的核心概念是使用多個處理器（或計算單元）同時解決單一問題。與傳統的循序計算不同 ，平行計算的目標是透過多個處理器協同工作，來大幅縮短問題的解決時間。即使平行程式在執行時所執行的指令總數可能與循序程式相同，但由於有更多的處理器同時分擔運算，整體完成時間得以縮短。

### 生活中的平行計算例子

平行計算的理念在我們日常生活中也隨處可見：

- 麥當勞點餐：多個點餐櫃檯同時服務多個顧客。
- 國道收費站：多個收費車道同時處理車輛通行。
- 工廠流水線：多個工位同時進行產品的不同組裝步驟。

### 平行計算與分散式計算的差異

儘管都涉及多個計算單元，但平行計算和分散式計算在處理問題和目的上有所不同

- 平行計算
- 強調同步計算，通常在一個單一系統內部的多個處理器上執行，處理的是同一個程式的不同部分 。
- 常見於科學計算，例如天氣預測、F1賽車風阻模擬、飛機流體力學分析等需要大量運算的領域 。
- 目標是將一個大問題拆分成多個小問題，平行處理以加速。
- 分散式計算 ：
- 強調資源分享與資料傳遞，通常由多台獨立的電腦組成，這些電腦透過網路互相溝通與傳遞資料。
- 服務於不同的使用者或目的，可能跨越很大的地理區域 。
- 例如大型資料中心的運作，其主要需求是處理大量資料並確保服務不中斷，而非單純追求極致的計算效能。

### 為什麼需要平行計算？

平行計算的發展是為了應對現代計算的需求和挑戰，其主要原因包括：

- 節省時間與成本：
- 這是平行計算最主要的目的。透過使用更多計算資源，可以大幅縮短程式的執行時間，讓結果在有意義的時間內產生。
- 許多計算成本與時間呈正相關，縮短時間也能減少這些成本。像是深度學習模型訓練在CPU上可能需要150小時，但在GPU上僅需15小時，大大加速研究進程。
- 解決更大的問題：
- 許多現實世界的複雜問題，如氣象模擬、工程設計（賽車、飛機的空氣動力學模擬）、天文物理學中的行星模擬等，需要龐大的計算量和記憶體資源。
- 單一電腦的儲存空間和計算能力有限，難以容納所有資料或完成這些大型計算。例如，GPU雖然計算能力強，但記憶體空間相對有限。
- 透過平行計算，結合多個GPU或多台電腦協同運作，才能解決這些規模龐大的問題。
- 充分利用硬體資源：
- 當前生活中的大多數電腦，包括手機、筆記型電腦和伺服器，幾乎都內建多核心CPU或GPU等平行處理單元。
- 如果程式不能有效利用這些多核心資源，將會造成嚴重的浪費。
- 摩爾定律的挑戰與異質系統的興起：
- 早期電腦性能的提升主要依靠提高單一處理器的頻率和製程微縮。然而，從2000年代初開始，這種單一核心性能的提升遇到了散熱、功耗和頻率瓶頸等限制，即所謂的「功耗牆」或「頻率牆」問題。
- 因此，硬體發展轉向增加處理器核心數量，這使得平行計算成為必然趨勢。
- 現在的手機和電腦在購買時，人們關心的已不再是單一核心的速度，而是「幾核心」。
- 目前的計算趨勢是異質計算 ，即將CPU與GPU，甚至其他專用加速器（如FPGA、ASIC）結合，利用它們各自的優勢來達到最佳效能。CPU擅長處理通用、序列化的工作，而GPU擅長處理大量平行、同質的工作。

### 平行計算的演進階段 (趨勢)

計算的發展趨勢可分為四個主要階段，反映了平行計算的演進：

1. CPU (循序計算)：早期電腦主要依靠單一CPU核心來執行循序程式。
2. 多核心CPU (多執行緒)：隨著單核性能提升受限，一台電腦內開始整合多個CPU核心，或一個CPU內部擁有多個計算核心。這需要使用如 Pthread 或 OpenMP 等工具來實現單機多核心的平行計算。
3. 分散式系統：當單一電腦的資源不足以解決問題時，需要多台電腦協同運作。這個階段的典型範例包括 MPI 和 MapReduce 等分散式程式設計框架。
4. 異質系統 ：這是目前的主流趨勢，系統包含不同類型的處理器（如CPU與GPU）共同進行計算。GPU因其大規模平行處理能力而受到重視，用於加速特定類型（尤其是資料平行）的計算。相關的程式設計模型包括 Shader、CUDA 和 OpenCL。

### 平行系統架構分類與程式模型

為了更好地理解和設計平行系統，存在多種分類方式：

1. Flynn's 經典分類法

這是最早且最基礎的分類方式之一，於1966年提出，從**處理器（處理單元）的角度**，根據指令流 和資料流的數量關係，將電腦架構分為四種：

- 單一指令流，單一資料流 ( SISD )：
- 最簡單的架構，一次只能處理一條指令，並應用於一個資料元素。
- 對應於早期單核心處理器的電腦，程式無法被平行化，只能循序執行。
- 單一指令流，多重資料流 ( SIMD )：
- 同時執行相同的指令，但應用於不同的資料元素。
- GPU (圖形處理單元) 是最典型的SIMD架構範例，它能夠進行大規模的資料平行處理，如陣列運算。
- 現代的Intel CPU中也包含如 AVX 等向量處理單元，也屬於SIMD設計，用於加速這類計算。
- SIMD的優勢在於控制邏輯相對簡化，因此可以在單一晶片中放入大量的計算單元。
- 多重指令流，單一資料流 (MISD )：
- 多個處理器執行不同的指令，但操作**相同的資料元素**。
- 這是一種在實驗階段提出，但在實際應用中**極為罕見**的架構。
- 唯一的潛在應用可能是容錯系統 ，多個處理器執行相同計算，如果一個出錯可以參考其他結果。
- 多重指令流，多重資料流 (MIMD)：
- 多個處理器同時執行不同的指令，並操作**不同的資料元素**。
- 這是最通用、最有彈性的架構，因為處理器之間完全沒有限制，可以執行完全不同的程式。
- 現代的多核心CPU設計就屬於MIMD，每個核心可以獨立運作。
- 缺點是系統複雜度高，導致在單一晶片中難以整合大量的處理單元（相比GPU的核心數較少）。

2. 記憶體架構分類

這種分類是從記憶體如何被處理器存取和共用的角度進行，分為共享記憶體和分散式記憶體：

- 共享記憶體 ：
- 所有處理器共享同一個記憶體位址空間，任何一個處理器寫入的資料，其他處理器都能直接讀取到。
- 常見於單一計算節點的設備，例如一般的手機、筆記型電腦和伺服器。
- 共享記憶體架構又可細分為兩種：
- 統一記憶體存取 (UMA )：所有CPU到記憶體的存取速度和延遲都是一致的。這是單一系統通常希望達到的狀態，因為每個CPU扮演的角色相同，效能預期也相同，有利於軟體管理。
- 非統一記憶體存取 (NUMA )：雖然記憶體仍然是共享的，但由於硬體連接方式的差異，不同CPU存取不同記憶體區塊的速度會不同（本地存取快於遠端存取）。
- 這種架構常見於真正的超級電腦或高性能伺服器，因為CPU數量增加時，難以將所有CPU都直接連接到同一個記憶體晶片。
- 它增加了系統的複雜度，程式設計者或作業系統需要考慮資料和程式在記憶體中的分配位置，以優化效能。
- 分散式記憶體 ：
- 每個處理器擁有獨立的記憶體位址空間，彼此的記憶體不能直接共用。
- 如果一個程式需要存取另一個處理器的資料，必須透過**網路傳遞訊息來溝通。
- 這種架構允許構建非常大規模的計算系統。具體類型包括：
- 叢集 (Cluster)：由多台標準電腦透過網路連接而成，通常由單一管理員管理，軟體環境高度一致。像是課程使用的環境就是一個叢集。
- 超級電腦 ：通常是規模更大的叢集，包含數百甚至更多伺服器，極致追求計算效能，硬體和軟體通常會為此特別客製化。
- 資料中心 ：規模可能達到數千甚至數百萬台伺服器，主要圍繞資料管理，目標是存取和處理大量資料，並確保服務不中斷和資料不丟失，對單純計算效能的要求可能次之。

3. 程式模型分類

程式模型是指程式設計者編寫平行程式的方式和邏輯，它是一層抽象，簡化了直接與複雜硬體互動的過程。

- 共享記憶體程式模型(shared memory programming model) ：

- 程式設計者可以直接在共享記憶體空間中讀寫資料來進行溝通。
- 常見的例子包括：
- Pthread ：提供低階的執行緒控制，程式設計者需要手動管理執行緒的創建、同步和資料共享，提供高度的控制和優化空間，但複雜度較高。
- OpenMP ：提供高階的編譯器指令，允許程式設計者在現有循序程式碼的基礎上，透過簡單的標註來自動生成平行程式，降低了寫程式難度。
- 優點：溝通速度快，因為是直接記憶體存取。
- 缺點：
- 擴展性受限於單一電腦的記憶體容量和處理器數量。
- 容易產生資料競爭等問題，導致程式的複雜度在規模擴大時難以控制。
- 訊息傳遞程式模型 (Message passing programming model)：

- 針對分散式記憶體硬體架構設計，處理器之間透過明確的訊息發送和接收操作來交換資料和溝通。
- 最主要且常用的程式庫是 MPI ，它定義了一系列用於溝通的API，如send、receive、broadcast等。
- 優點：
- 極高的擴展性，可以在數百、數千甚至數百萬台電腦上運行，能夠解決超大規模的問題。
- 溝通方式明確，程式設計者可以精確控制資料何時被修改和傳遞。
- 缺點：
- 與傳統循序程式編寫方式不同，需要顯式地設計資料的發送和接收，增加了程式設計的複雜度。
- 由於透過網路傳輸，**溝通延遲較高**，可能導致效能不如共享記憶體模型在單機上的表現。
- 如果發送和接收操作不匹配，程式可能會卡住 。

需要注意的是，硬體架構和程式模型之間並非嚴格的一對一關係。例如：

- 您可以在共享記憶體機器 (如單台多核心電腦) 上使用MPI這樣的訊息傳遞模型來編寫程式。MPI會確保不同處理器之間透過記憶體複製的方式傳遞訊息，而非直接共享記憶體空間。
- 雖然不常見且代價高昂，但也可以在某些特殊的「大記憶體機器」 上運行共享記憶體程式模型，即使底層是分散式記憶體的設計，硬體層面透過特殊技術使其看起來像共享記憶體。

然而，通常情況下，讓程式模型與底層硬體架構相匹配會是更簡單、更有效、成本更低的選擇。

---
其他課程連結

[平行程式1C~2B Introduction parallel programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/Syxh3H7Kxe)
[平行程式3A~3D The Latest Developments and Applications Using Parallel Programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJh7QFVKle)
[平行程式4A~4B IO Parallel IO and Program Analysis](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJLMsuHFgg)
[平行程式5A~5B The Latest Developments and Applications Using Parallel Programming](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/SJh57hIFle)
[平行程式6A~6B Communication Routines and Parallel Function Code](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/r1X9kX_Fle)
[平行程式 6C~6D Communication Routines and Parallel Function Code](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/S1DPjoYFlx)
[平行程式 7A~8A Pthread:Synchronization Problem & Tools](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJu-_0tKge)
[平行程式 8B~8D Synchronization Tools & Open Multi-Processing(OpenMP)](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1ki4E2Fee)
[平行程式 9A~9B Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJTYMrpKlx)
[平行程式 10A~10B Synchronization Tools & Open Multi-Processing Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/B1cY6M1qee)
[平行程式 10C~10D Synchronization Tools & Open Multi-Processing Synchronization Construct](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BkgFaNg5gg)
[平行程式 11A~11B Parallel Work Pool and Termination / Parallel Sorting](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1hfOw-5xl)
[平行程式 12A~12B Parallel Sorting and Pipelined Computations](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/Symo-zQ9eg)
[平行程式 12C~12D Parallel Sorting and Pipelined Computations](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJYNKDVceg)
[平行程式 13A-13B Sychronous Parallelism](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HJ2UJ2Bqex)
[平行程式 14A~14B Heterogeneous Computing](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BksS4yP5eg)
[平行程式 14C~14D Heterogeneous Computing](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/BJrfTUd9xx)
[平行程式 15A~15B Parallel Programming Model on GPU](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/ByWnl-t5gg)
[平行程式 16A~16B What is Compute Unified Device Architecture(CUDA)?](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/HyYpsjcqgl)
[平行程式 17A~18A 平行運算的CUDA](https://hackmd.io/@6FOC2dvARe-Vz0kVSyajew/H1dUeBT5lg)
[平行程式 18B~19A 記憶體層級 / CUDA的優化](https://hackmd.io/@JuitingChen/HyF44e1jge)
[平行程式 19B~19D 記憶體層級 / CUDA的優化 ](https://hackmd.io/@JuitingChen/ryPEu4lieg)
[平行程式 20A~20B CUDA優化全域和區域記憶體/共享記憶體](https://hackmd.io/@JuitingChen/r1X659Zoxl)
[平行程式 21A~21B Parallel Reduction / Distributed Computing Framework](https://hackmd.io/@JuitingChen/HyiOpozjxl)
[平行程式 NTHU-PP-Chap10-Big Data-Part1 ](https://hackmd.io/@JuitingChen/Hyc-e3Golx)
[平行程式 NTHU-PP-Chap10-Big Data-Part2 ](https://hackmd.io/@JuitingChen/ryC_QTXoxl)
[平行程式 NTHU-PP-Chap11-MapReduce](https://hackmd.io/@JuitingChen/HJgBXJOsge)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part1](https://hackmd.io/@JuitingChen/ryh5hBtsge)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part2](https://hackmd.io/@JuitingChen/rJ2G7kdjxg)
[平行程式 NTHU-PP-Chap12-Distributed Training-Part3](https://hackmd.io/@JuitingChen/HkA471dilx)
[平行程式 NTHU-PP-Chap13-UCX-Part1](https://hackmd.io/@JuitingChen/rJbq103ieg)
[平行程式 NTHU-PP-Chap13-UCX-Part2](https://hackmd.io/@JuitingChen/SJpNmk_ixl)
[平行程式 NTHU-PP-Chap13-UCX-Part3](https://hackmd.io/@JuitingChen/HkIUYa13xe)