平行程式設計的簡單範例

前言 & 概述

了解平行程式設計 (Parallel Programming) 的基本概念後，本篇文章，將透過簡單的程式碼範例，更深入的理解平行程式的運作原理。最後，我們也會提到撰寫平行程式的「兩個方向」與「三個元素」。

為什麼「必須」平行程式設計

前一篇文章，我們已經提到「為什麼需要平行程式設計」的三個原因。在這裡，我們先探討「為什麼『必須』平行程式設計」。

如上圖所示，四條線由上而下分別表示 Transistor 數量、Clock Speed、Power 與 ILP。根據 Moore’s Law 我們可以發現電晶體的數量呈現逐年成長 (綠線)；然而，單個 CPU 的 Clock Speed (深藍線) 卻已經趨緩下來；ILP (紫色線) 也是呈現趨緩的現象。

ILP 的全名為 Instruction-Level Parallelism，指的是即使只有 Single Core 的情況下，仍然可以透過 Compiler 與 CPU Architecture 達到指令層級的平行化運作，來加速程式的執行。

由於單個 Core 的 Clock Speed 與 ILP 皆以達到極限，也就是說我們難以再仰賴單個 Core 來提升程式的效能，因此必須在軟體本身著手，透過平行化的程式設計，使得程式可以善加利用多個 Core 的資源。

平行程式的簡單範例

假設我們有一個 Array，Array 中有 n 個元素，每一個元素彼此之間沒有相依性，我們希望對每一個元素進行一些運算後，將結果加總起來。我們可以透過上圖的程式，完成這項任務。

因為 Array 中的每一個元素彼此沒有相依性，因此我們可以透過 Parallel Programming 的技巧，將 Array 中的所有元素平均分配給所有的 Core。

舉例來說，假設我們的電腦上目前有 p 個 Core，且 Array 中有 n 個元素。那麼可以平均的分給每一個 Core n/p 個元素。如此一來，原本只有一個 Core 負責 n 個元素，現在由多個 Core 平均分擔，加速程式的執行。

我們以真實數字進行更具體的說明！如上圖所示，假設 Array 中有 24 個數字，且電腦上有 8 個 Core，我們平均分配 3 個數字給每一個 Core。

每一個 Core 都會算出自己的結果，存於 “my_sum” 變數當中。最後，再由一個 Master Core 負責將所有的 Core 的結果加總起來。透過 Parallel Programming，原來只由 Master Core 負責 24 個數字的運算，現在由 8 個 Core 同時處理自己的部分，再由 Master Core 把大家的結果集合在一起。

平行化 Reduction 的過程

在上述的例子中，我們知道最後是由 Master Core 統一將所有 Core 的結果加總在一起。因此，Master Core 必須將 8 個數字加總在一起形成 1 個數字。由原來的「很多元素」經過運算後變成「很少元素」的過程稱為 Reduction。Reduction 通常可以再進行平行化處理。

舉例來說，我們可以利用 Core 0 加總 Core 1、Core 2 加總 Core 3、Core 4 加總 Core 5、Core 6 加總 Core 7。如此一來，在時間點 A 時，同時就有 4 個 Addition 發生。將 Reduction 過程以 Parallel Programming 改寫後，原來由 Master Core (Core 0) 進行 7 個 Addition，現在只需要進行 3 個 Addition。

平行化程式設計的兩個方向

針對原有單線程的程式進行平行化處理時，有兩個方向可以進行：Task-Parallelism 與 Data-Parallelism。

• Task-Parallelism
  將原來的問題拆分成多個不同的 Task，每一個 Core 都會處理自己的 Task。舉例來說，假設餐廳有 3 個師傅要做 300 個蛋糕。由每一個師傅負責每一個蛋糕的某些步驟，因此每一個師傅所做的事情都會不同。
• Data-Parallelism
  將原來的問題中涉及資料處理的部分，分配給每一個 Core 處理部分資料。以上述蛋糕師傅的例子，每一個師傅即是負責 100 個蛋糕。因此，每一個師傅所做的事情會相同。

平行化程式設計的三個元素

針對原有的單線程程式進行平行化處理時，有三個元素需要考慮：Communication、Load Balancing 與 Synchronization。

• Communication
  平行化程式中經常會用到多個 Core，這些 Core 彼此應該如何傳遞訊息。
• Load Balancing
  如何讓每一個 Core 都能平均分擔一些任務。在上面的例子中，我們將所有的資料量平均分給每一個 Core。然而，有些清況不同類型資料所需的處理時間也不同，若依照數量進行分配，可能導致某些 Core 還在執行，某些 Core 已經閒置下來。
• Synchronization
  有些情況，我們希望某些 Core 要等待其他 Core 執行完後才繼續執行。

上述 3 點中，Communication 與Synchronization 是為了確保 Parallel Program 與原來的 Serial Program 執行的結果相同；Load Balancing 則是為了最佳化 Parallel Program 的效能。

結語

本文中，我們了解到「為什麼『必須』平行程式設計」也透過簡單的範例程式，了解平行化的概念。最後，我們也提到撰寫平行化程式的 2 個方向：

• Task-Parallelism
• Data-Parallelism

以及平行化程式中必須注意的 3 個元素：

• Communication
• Load Balancing
• Synchronization

下一篇文章，將會介紹進行平行程式設計時，常見的 3 種 Parallel Programming Model。