An Introduction to Parallel Programming（平行程式設計導論）

引用

Pacheco, P. S., & Malensek, M. (2021). An Introduction to Parallel Programming (2nd ed.). Morgan Kaufmann (Elsevier).

章節概要

第二版約496頁，共8章。第一版的三種程式設計介面（用於分散式記憶體的MPI，以及用於共享記憶體的Pthreads和OpenMP）之外，新增一章談以CUDA進行GPU程式設計。作者把本書定位為初階入門書，對象是能在傳統單處理器系統上寫程式、但幾乎沒有多處理器程式設計經驗的學生和專業人士。出版社強調本書採教學式寫法，從小程式開始，逐步進展到較難的例子，練習要求學生編譯、執行並修改範例程式。作者提供下載的原始碼附有一份索引，把每個程式對應到討論它的小節，從中可以看出各章都是圍繞少數幾個在全書反覆出現的問題來組織的。

第1章：Why Parallel Computing（為什麼需要平行運算）

開頭一章正如標題所說，說明為什麼需要平行運算，之後全書才轉入硬體、軟體和各個程式設計介面。

第2章：Parallel Hardware and Parallel Software（平行硬體與平行軟體）

平行硬體與軟體的背景知識。勘誤表顯示，硬體部分包含快取一致性（2.3.5節），並附有作者的說明：由於匯流排無法擴展，窺探式一致性如今已很少使用。程式碼索引顯示，2.7.1節有一個循序版的直方圖程式，它是本章開發平行程式的範例。

第3章：Distributed Memory Programming with MPI（以MPI進行分散式記憶體程式設計）

從一個讓每個行程輸出問候語的程式開始，接著分幾個版本平行化梯形積分法，從點對點訊息逐步進展到歸約、廣播等集體操作。後面各節討論以scatter和gather分配向量、矩陣向量乘法、衍生資料型別、計時與效能評估，以及平行奇偶交換排序。

第4章：Shared-Memory Programming with Pthreads（以Pthreads進行共享記憶體程式設計）

以問候程式和矩陣向量乘法引入執行緒，再藉估算π的程式揭露競爭條件，並比較保護臨界區段的幾種方法：忙碌等待、互斥鎖和號誌。進一步的主題包括以三種方式實作的屏障、應用於共享鏈結串列的讀寫鎖，以及執行緒安全——透過用一個非執行緒安全的函式庫函式切分文字來說明。

第5章：Shared-Memory Programming with OpenMP（以OpenMP進行共享記憶體程式設計）

以臨界區段、reduction子句和parallel for迴圈重新處理梯形積分法；展示一個無法直接平行化的迴圈（費氏數列）；並討論變數範圍、奇偶排序、迴圈排程、利用critical、atomic和鎖在執行緒間傳遞訊息、矩陣向量乘法、OpenMP任務，以及執行緒安全。

第6章：GPU Programming with CUDA（以CUDA進行GPU程式設計）

本版新增。從以一個執行緒區塊啟動的核心函式開始，接著是向量加法、從裝置傳回結果，以及三個逐步改良的CUDA版梯形積分法（根據勘誤表，6.11節討論warp洗牌函式），最後實作雙調排序，先在單一執行緒區塊內，再跨越多個區塊。

第7章：Parallel Program Development（平行程式開發）

兩個規模較大的個案研究，每個都以書中所有介面求解。n體問題求解器分基本版和簡化版，分別以OpenMP、Pthreads、MPI和CUDA平行化；接著開發樣本排序的循序版，以及OpenMP、Pthreads、MPI和CUDA版本，其中MPI版本採用不同的通訊模式。

第8章：Where to Go from Here（下一步往哪裡走）

最後一章正如標題所示，為進一步學習指引方向。

核心概念

第1–2章：基礎

• 共享記憶體與分散式記憶體：平行系統的兩大類，決定行程是透過記憶體還是透過訊息溝通。
• 快取一致性：讓共享資料在不同核心快取中的副本保持一致。
• 平行軟體：寫成以多個合作的行程或執行緒方式執行的程式。

第3章：MPI

• 點對點通訊與集體通訊：在兩個行程之間傳送訊息，或在所有行程之間同時通訊（reduce、broadcast、scatter、gather）。
• 資料分配：把向量和矩陣以區塊方式分給各行程。
• 衍生資料型別：描述不連續的資料，使其能以一則訊息傳送。
• 效能評估：為平行程式計時並判斷其擴展性，這是3.6節的主題。

第4–5章：Pthreads與OpenMP

• 競爭條件與臨界區段：多個執行緒同時更新共享資料時產生的錯誤，以及必須加以保護的程式區域。
• 互斥鎖、號誌、屏障、條件變數與讀寫鎖：Pthreads的同步工具。
• 指引與子句：OpenMP平行化迴圈與程式區域的方式，包括歸約與排程。
• 執行緒安全：函式在被多個執行緒同時呼叫時能否正確運作。

第6–7章：GPU與較大的程式

• 核心函式、執行緒與區塊：CUDA在GPU上執行大量以區塊組織的輕量執行緒的模型。
• warp層級操作：warp洗牌等函式，讓同一warp中的執行緒能有效率地交換數值。
• n體模擬與樣本排序：用來在實際問題上比較全部四種介面的個案研究。

評析

優點

• 所有介面處理同樣的問題。 梯形積分法出現在MPI、OpenMP和CUDA中；矩陣向量乘法和奇偶交換排序反覆出現；第7章以全部四種介面求解n體問題和樣本排序。學生可以直接比較各種程式設計模型，而不必面對互不相關的例子逐一學習。
• 從有缺陷的程式中學習。 程式碼索引顯示出一種刻意的安排：先給出有錯誤或過於簡單的版本（容易發生競爭的π估算、錯誤的費氏數列迴圈、非執行緒安全的文字切分），再加以修正，讓學生明白同步工具為何存在。
• 實用且可執行。 作者提供全部原始碼，並在網站上維護勘誤表；出版社也為教師列出講義投影片、習題解答和圖庫。練習要求學生編譯、執行並修改程式。
• 跟上GPU的發展。 新增的CUDA一章以及第7章中的CUDA版本，把加速器帶進一本原本只談CPU和叢集的教材。

局限

• 以C語言和API為中心。 所有程式都以C撰寫，本書教授的是四種特定介面。它不涉及更高階的框架，也不談超出範例所需範圍的平行演算法理論。
• GPU部分只談CUDA。 使用其他加速器或可攜式GPU框架的讀者需要另找資料。出版社也提到異質程式設計，但目錄中沒有專門討論它的章節，因此讀者不應期待對這個主題有深入的論述。
• 不是分散式系統教材。 本書談的是如何在多個處理器上讓一項計算跑得更快；容錯、一致性和複製這些本課程其他部分的核心內容，都不在其範圍內。
• 部分硬體內容容易過時。 作者自己的勘誤表指出，第2章關於窺探式一致性的描述，反映的是一種如今已很少使用的技術。

在課程中的定位

在分散式系統課程中，本書負責平行運算這一面：如何撰寫程式，利用多個核心、多個節點或GPU讓一項計算跑得更快。其他幾本書回答的是另一個問題：如何打造在不可靠的機器和網路上仍能持續運作的服務。羅伯托·維蒂洛的 Understanding Distributed Systems 是寫給開發者的簡明入門，談網路化服務中的通訊、協調、擴展與韌性；庫魯里斯等人的 Distributed Systems: Concepts and Design，以及范史廷和塔能鮑姆的 Distributed Systems，是從原理出發的教科書，探討架構、命名、協調、一致性、複製與容錯。

克萊普曼和里科米尼的 Designing Data-Intensive Applications 探討正式環境資料系統中的複製、分割與串流處理；卡尚、蓋拉維和羅德里格斯的 Introduction to Reliable and Secure Distributed Programming 是談容錯抽象與共識的研究所教科書。帕切可和馬倫塞克書中談MPI的第3章是最接近的橋樑：行程間的訊息傳遞是兩者的共同基礎，但本書的目標是速度，而非容忍故障。當課程包含平行程式設計時，或作為分散式系統教材的實務補充時，可以閱讀本書。

如何使用本書

本書適合修第一門平行運算或高效能運算課程的大學生、需要為自己的程式加速的理工科學生，以及沒有平行經驗的程式設計師。由於所有範例都以C撰寫，讀者需要熟悉C語言程式設計，包括指標和陣列。

• 核心： 先讀第1–2章掌握術語和設計方法，再至少深入學習一種介面。許多課程選讀第3章（MPI）和第5章（OpenMP）；第4章（Pthreads）最清楚地展示底層的同步機制。
• GPU選項： 第6章；若課程以GPU為重點，可以緊接在第2章之後閱讀。
• 綜合： 學完所選介面之後讀第7章；用這些介面跟著做n體問題和樣本排序的解法，並比較其效能。
• 收尾： 第8章指出進一步學習的方向。

從作者網站下載原始碼，邊讀邊執行每個範例，並以不同數量的行程或執行緒計時，效能評估就此變得具體。依賴GPU程式碼清單之前，先查看勘誤表。效能表現無法在單一核心上學會，若有條件，請使用真正的多核心機器，以及小型叢集或GPU。