平行程式 6C~6D Communication Routines and Parallel Function Code

教材:10710周志遠教授平行程式 https://www.youtube.com/playlist?list=PLS0SUwlYe8cxqw70UHOE5n4Lm-mXFXbZT 20250825 筆記內容可能有錯僅供參考 6C~6D Communication Routines and Parallel Function Code 今日大綱 MPI-IO 與共享記憶體平行 I/O 的重要性與挑戰 MPI-IO 的解決方案 MPI-IO 讀寫操作的類型共享記憶體程式設計 Process 與 Thread 的差異為什麼單機平行程式偏好 Threads Pthreads 是什麼 ### **MPI-IO 與共享記憶體** ``` Examples: Divide MPI tasks into two group int rank, numtasks; MPI_Group orig_group, new_group; MPI_Comm new_comm; MPI_Init(); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &numtasks); /* Extract the original group handle */ MPI_Comm_group(MPI_COMM_WORLD, &orig_group); /* Divide tasks into two distinct groups based upon rank */ int rank1[4] = {0,1,2,3}, rank2[4] = {5,6,7,8}; if (rank < numtasks/2) MPI_Group_incl(orig_group, numtasks/2, rank1, &new_group); else MPI_Group_incl(orig_group, numtasks/2, rank2, &new_group); /* Create new communicator & Broadcast within the new group */ MPI_Comm_create(MPI_COMM_WORLD, new_group, &new_comm); MPI_Barrier(new_comm); ``` #### **MPI 群組與變數理解** - **群組建立的困惑**: 在MPI中，大家可能會對`new group`的建立感到困惑。 - `rank1` (包含0,1,2,3) 和 `rank2` (包含5,6,7,8) 在執行 `defil` 時的行為是**不一致的**。 - 這兩個函數碼執行後會**建立兩個不同的新群組**。 - 由於這是**集體操作 (collective code)**，原群組中的所有行程 (processes) 都必須呼叫此函數碼。 - 雖然所有行程都呼叫同一函數，但其結果可以同時建立兩個群組。 - 每個 MPI 測試取得的 `new group` 取決於行程本身。前方的行程獲得的是第一個群組的項目，後方的行程獲得的是第二個群組的。 - 對於未出現在這些群組中的行程（例如數字4），其 `new group` 是**沒有意義的**，因為它根本不屬於任何群組。 - **變數的獨立性**: 在編寫 MPI 程式時，即使變數名稱相同，但在計算過程中，每個行程取得的值以及 API 回傳的值都**可能不同**。 - 這是因為它們各自擁有**不同的記憶體空間 (memory space)**。 - 雖然使用相同的變數名稱可以讓程式碼更簡潔，但必須**注意避免錯誤覆寫**，並理解這些看似相同的變數實際上具有不同的值。 #### **平行 I/O 的重要性與挑戰** - **I/O 在平行計算中的關鍵性**: I/O 是非常重要的部分，尤其與行程搭配時更是如此。 - **速度瓶頸**: 處理器速度、記憶體速度以及磁碟存取速度之間存在**巨大的差異**。 - 如果只專注於處理而忽視檔案存取，程式很多時候會被卡住。 - **計算與儲存的分離**: 在傳統高效能計算系統中，計算資源（如超級電腦）和儲存資源（如分散式檔案系統）甚至是由**兩個不同的系統**提供。 - 分散式檔案系統是一個獨立的電腦群組和軟體，專門為前端的超級電腦提供資料。 - **平行檔案系統 (Parallel File System, PFS)**: - PFS 擁有**大量的儲存節點 (storage nodes)**。 - 每個儲存節點都有**獨立的網路連結通道**連接到計算節點 (compute nodes)。 - 這使得計算節點和儲存節點可以**一對一配對**進行資料傳輸。 - 更多的平行行程、更多的儲存節點和計算節點，將會帶來**更大的聚合網路頻寬 (aggregate networking)**，從而**加快讀取速度**。這就是所謂的 **平行 I/O (parallel IO)**。 #### **未使用 MPI-IO 的問題** - **直覺式 `fopen`/`fread` 的限制**: 若不透過 `MPI-IO` 函式庫，各行程會直覺地使用 `fopen` 和 `fread` 進行循序 I/O 操作。 - **檔案系統視角**: 對於檔案系統而言，它會看到**許多獨立的行程同時嘗試開啟同一個檔案**。 - **只讀操作 (Read-only)**: 如果只是讀取，通常檔案系統會允許。但重複開啟仍會因**鎖定問題 (locking issues)** 而變慢。 - **寫入權限 (Write permission)**: 如果目的是寫入，一般檔案系統**不允許**多個行程同時寫入，因為這會導致**資料一致性問題 (data consistency problem)**。直接使用 `fopen` 帶寫入權限會導致錯誤。 - **簡單解決方案：分割檔案**: - 將一個大檔案（例如10GB）分割成許多小檔案（例如10個1GB的檔案）。 - 每個行程可以獨立存取一個小檔案，只要不同時讀取同一個檔案即可。 - **缺點**: - 若檔案極大或行程數量多，會產生**數量龐大的小檔案**（例如1,000或10,000個）。 - 這對檔案系統造成巨大的壓力，因為需要**額外的管理成本 (management cost)**。 - 對使用者而言也很困擾，因為難以管理這麼多檔案。 - 若行程數量改變，檔案ID的對應關係也需重新考慮，管理起來很麻煩。 #### **MPI-IO 的解決方案** - **MPI-IO 的核心**: `MPI-IO` 函式庫正是為了解決上述問題。 - **`MPI_File_open` 的機制**: - 行程呼叫 `MPI_File_open` (而非直接 `fopen`)。 - `MPI_File_open` 是一個 **集體操作 (collective code)** 的 API。 - 它會收集所有行程的資訊，然後向下產生**單一的 `file open` 指令**給底層檔案系統。 - 因此，檔案系統只會看到一個 `fopen` 操作。 - MPI 函式庫會管理檔案的令牌 (token)，並協調所有行程的存取，決定存取方式和順序。 - `MPI_File_open` **必須是集體操作**。 - **功能與效益**: MPI-IO 的 APIs 協助統一執行檔案的開啟、關閉、讀取和寫入操作。 - 透過 MPI-IO，多個 MPI 行程可以**同時存取單一檔案**而不會產生問題。 - 這能有效**改善效能**。 #### **MPI-IO 讀寫操作的類型** - **讀寫操作的細分**: 不論是讀取 (`read`) 或寫入 (`write`)，都可以分為兩種： - **集體 I/O (Collective IO)** - **獨立 I/O (Independent IO)** 1. **集體 I/O (Collective IO)**: - **所有行程必須同時呼叫**讀取或寫入操作。 - MPI 函式庫內部會維護一個 **internal IO buffer**。 - 所有行程**共用**這個 buffer 來傳輸資料 (先寫入 buffer ，或從 buffer 讀取後再複製到使用者程式)。 - **優點**: - 將許多由個別行程發出的小型、可能不連續但邏輯上相連的 I/O 請求，**聚合 (aggregate) 成一個大型的 I/O 請求**。 - 這對於檔案系統而言，變成了一個更大的 I/O 大小，**效率會非常好**。 - 特別適合於處理小量 I/O 請求。 2. **獨立 I/O (Independent IO)**: - **沒有內部 buffer**。 - 每個行程直接呼叫自己的讀取或寫入操作。 - **不是集體操作 (not collective)**。行程不需同時呼叫，一個行程讀取或寫入後即可返回，不會被卡住。 - **優點**: - 適合處理**大量 I/O (large IO)** 請求。 - 若單個行程一次讀寫的資料量已經很大（例如數MB或GB），則不需要與其他行程混合處理。 - 直接使用獨立 I/O 的效能會比集體 I/O 更好，因為集體 I/O 多了一次記憶體複製 (memory copy) 的開銷，且需要等待其他行程。 - **寫入一致性問題 (Write consistency)**: - 在獨立 I/O 中，程式設計師必須在應用層面**自行確保**各行程不會同時寫入相同位置。 - 這可以透過計算索引或使用同步機制（例如 barrier）來避免。 - 如果沒有處理好且寫入位置相同，函式庫層會對寫入進行排序，**後寫的資料會覆蓋 (overwrite) 先寫的結果**。 - 獨立 I/O 不會有鎖定問題，但資料一致性由使用者程式負責。 - **MPI-IO 的其他函數**: 除了讀寫，還有 `MPI_File_close` 和 `MPI_File_sync` (將資料刷新到儲存系統) 等函數，這些都必須透過 MPI 函式庫來與檔案系統互動。 - **實作考量 (作業)**: - 在僅有本機檔案系統而非平行檔案系統（如 Lustre）的環境下，集體 I/O 和獨立 I/O 的效能差異可能**不明顯**。因為最終所有 I/O 都會集中在同一處形成瓶頸。 - 但在真實的高效能計算環境中，若有平行檔案系統，MPI-IO 對效能的影響極大，且集體/獨立 I/O 的選擇需根據**寫入模式 (write pattern)** 進行調優。 #### **Even-Odd Sort (作業一)** - **演算法概述**: - 一個簡單的排序演算法，基於迭代。 - 在不同迭代中，會與左右鄰居進行**交換**。 - `Even-Odd` 指的是在奇數迭代和偶數迭代中，交換的對象不同（例如，一輪與左鄰居交換，下一輪與右鄰居交換）。 - 透過比較和交換，將較大的數字推向左邊，較小的數字推向右邊，最終使整個陣列排序完成。 - **基本版**: - 必須**完全遵循演算法的計算過程**，即每次只允許**交換一個元素**。 - 即使是在同一機器內部或跨機器邊界，排序操作也必須依此演算法進行。 - 此版本**不追求效能優化**，只要能正確運作即可。 - **主要挑戰**: 處理**跨機器邊界 (machine boundary)** 的資料交換，需要使用 `MPI_Send` 和 `MPI_Receive`。使用**blocking S/R** 可能會節省時間。 - **進階版**: - 只在**通訊模式 (communication pattern) 層面**進行限制。 - 例如，`rank0` 只能發送訊息給 `rank1`；`rank1` 可以發送給 `rank0` 或 `rank2`。通訊模式需遵循 `Even-Odd` 概念，但針對行程 ID 或機器 ID。 - **不限制每個行程內部對數字的處理方式** (計算方式)。每個行程可以自由處理其子陣列的排序。 - **通訊彈性**: 行程之間傳輸資料時，可以傳輸**所有元素、一半或任意數量**。 - 由於計算方式沒有嚴格限制，此版本允許**多種優化方式**。 - **演算法特性**: - **循序版 Even-Odd Sort**: 複雜度很高，效率不高，因為每次迭代內部都有許多小的交換。 - **平行版 Even-Odd Sort**: 在平行化後，所有行程可以在同一個迭代中同時向左右鄰居發送或接收資料。其計算速度可以**非常快 (umlinear time)**，是一種不錯的平行排序方法。 - **實作考量**: - **邊界檢查 (Boundary Check)**: 需特別處理邊界情況，例如最左邊的行程不能再向左發送。 - **資料分割 (Data Partitioning)**: 每個行程處理的數字數量可能不同，理想情況是**越平均越好**，以平衡計算量、I/O 量和網路流量。若無法完全平均，也需考慮邊界情況。 - 進階版的優化將圍繞這些考量進行。 #### **共享記憶體程式設計** - **平行程式設計的兩大模型**: - **訊息傳遞 (Message Passing)**，例如 `MPI`。 - **共享記憶體 (Shared Memory)**，例如 `Pthreads` 和 `OpenMP`。 - **共享記憶體程式的特性**: - **API 數量少**: 非常底層，主要用於建立、刪除、合併執行緒 (threads)。 - **通訊方式**: 無需專門的 API，因為執行緒直接存取共享記憶體中的資料。資料交換和資訊共享非常容易。 - **主要挑戰：同步化 (Synchronization)**: - 所有執行緒可以隨意修改共享記憶體中的值，且不必通知其他執行緒。 - 必須添加程式碼（如 **locks** 或 **barriers**）來確保修改的順序和時間點沒有衝突。 - 若同步控制不當，可能導致 **deadlock**，即執行緒互相等待，最終所有執行緒都無法動彈。 - **Deadlock 原因對比**: 共享記憶體中的 deadlock 是由於互相等待，而訊息傳遞中的 deadlock 通常是由於集體操作中某個行程卡住等待其他行程，更難預測和偵錯。 - **快取一致性 (Cache Coherency)**: - 執行緒可能運行在不同的核心 (cores) 上，每個核心有獨立的快取。 - 需要確保不同核心的快取中的值是一致的 (cache copy)。 - 這個問題通常由 **CPU 處理器** 自動解決，程式設計師無需處理。 - **共享記憶體的常見實作**: - **Pthreads (POSIX Threads)**: 一種執行緒函式庫 (thread library)。 - **OpenMP**: 透過編譯器指令 (compiler directive) 協助產生平行程式碼。 - **Unix 行程 (Unix processes)**: 也可以透過作業系統在行程之間建立共享記憶體進行通訊，但較不常見。 #### **行程 (Process) 與執行緒 (Thread) 的差異** - **行程 (Process)**: - 在執行時擁有**獨立的記憶體內容**，例如： - **堆疊 (stack)** 儲存區域變數 (local variables)。 - **檔案描述符 (file descriptors)** 儲存資源。 - **資料區 (data memory)** 儲存全域變數 (global variables)。 - 每個行程擁有其**獨立的這些內容**。 - 通常一個行程等同於一個執行緒 (multi-threaded process 中的主執行緒)。 - **執行緒 (Thread)**: - 因應多核心 CPU (multi-core CPU) 和平行計算概念的發展而生。 - 一個行程可以**建立多個執行緒**。 - **關鍵差異**: 同一個行程內的不同執行緒，**部分記憶體內容是共享的，部分是不共享的**。 - **共享部分**: 是執行緒之間可以溝通的原因。主要共享的是**全域記憶體 (global memory)**，即**全域變數 (global variables)**。 - **非共享部分**: 使得執行緒可以獨立執行各自的程式碼 (例如堆疊中的區域變數)。程式碼雖然相同，但它們執行的指令位置可以不同，從而產生不同的行為。 - **資源共享**: 大部分資源（例如透過一個執行緒開啟的檔案，其檔案句柄 (file handle) 可以傳給任何其他執行緒使用）是**共享的**。 - **作業系統實作**: 在實作上，許多作業系統（如 Linux）對行程和執行緒的區分不明顯，主要透過建立時的旗標 (flag) 來決定哪些記憶體內容是共享的。 - **優點**: 透過執行緒，可以在一個行程內直接利用多核心 CPU，並透過共享記憶體空間進行程式編寫。 #### **為什麼單機平行程式偏好執行緒 (Threads)** - **建立速度 (Creation Speed)**: - 建立一個執行緒 (例如 `pthread_create`) 比建立一個行程 (例如 `fork` 系統呼叫) 要快得多。 - 行程比較肥，包含更多記憶體內容，因此建立速度慢約 **15 到 50 倍**。 - 在單機上若只是為了共享記憶體進行通訊，建立執行緒會快很多。 - **通訊速度 (Communication Speed)**: - 在同一台機器內部，執行緒透過直接存取共享記憶體的方式讀取資料，速度比 MPI 透過記憶體複製 (`MPI_Send`/`MPI_Receive`) 的方式**快 2 到 15 倍**。 - 即使 MPI 函式庫在單機環境下進行了優化，它至少仍需要進行一次記憶體複製操作，這需要時間。 - **結論**: 如果程式只在單一機器上運行，大多數人會選擇使用執行緒，因為其效率更高。但 MPI 程式仍可在單機上運行。 #### **混合平行程式設計 (Hybrid Parallel Programming)** - **組合模式**: 結合了共享記憶體 (執行緒) 和訊息傳遞 (MPI) 這兩種平行計算方式。 - **應用場景**: 在單一機器內部利用執行緒進行共享記憶體平行化，而在跨機器時則使用 MPI 進行通訊。 - 這是目前**最常見的平行程式設計方式**。 #### **Pthreads (POSIX Threads) 是什麼** - **Pthreads 的定義**: - `P` 代表 `POSIX` (Portable Operating System Interface)。 - Pthreads 是 `POSIX` 系統 API 中定義的**執行緒介面 (thread interface)**。它是一個函式庫，是 `POSIX` 介面的一部分。 - **`pthread_create` 函數**: 用於建立執行緒的主要 API。 - **執行緒的行為**: 一個被建立的執行緒會被指派一個**函數指標 (function pointer)**，它唯一的任務就是**執行那個函數碼**。 - 主執行緒 (main thread) 和被建立的執行緒 (created thread) 可以同時被作業系統排程執行，從而實現平行加速。 - **協作方式**: 執行緒透過**共享全域變數 (global variables)** 進行溝通。執行緒完成函數執行後，也可以透過**return value** 傳遞資訊。 - **`pthread_create` 的參數**: 1. **`thread` (執行緒 ID)**: 一個指向 `pthread_t` 變數的指標，用於儲存新執行緒的 ID 。主執行緒可以透過此令牌與新執行緒溝通（例如使用 `pthread_join` 等待其結束並取得返回值）。 2. **`attr` (屬性)**: 指向 `pthread_attr_t` 結構的指標，用於設定執行緒的配置參數。通常設為 `NULL` 使用預設值。 - 可配置屬性，例如指定執行緒的記憶體配置應該與執行該執行緒的 CPU 晶片在同一位置，以加速存取。 3. **`start_routine` (起始常式/函數指標)**: 指向新執行緒將要執行的函數。 4. **`arg` (參數)**: 一個 `void*` 型別的指標，用於向 `start_routine` 傳遞參數。 - 若要傳遞多個參數，可以將它們**封裝在一個 struct 中**，然後傳遞該結構的指標。 - 在執行緒的函數內部，需要對此指標進行**類型轉換 (cast)** 並解參考 (dereference) 來取出參數值。這是一個較為底層的操作，若操作不當可能導致資料錯誤。