Sign in Subscribe
C

序：平行化程式設計（多核心編程）

admin

• 9 min read

平行化程式設計會越來越重要的這件事情，我想也不必我多說（因為從很早就開始被提倡了），早在幾年前，大家就注意到單核心高頻率的 CPU 是不可行的，為什麼呢？

  1. Power：當 CPU 的時脈頻率一直提高，所耗費的功率也會呈指數上升，為了省電，只好放棄了繼續提高時脈的想法。
  2. ILP (Instruction-Level Parallelism)：不是每道指令都可以拿來管線化的，所以時脈再高也無用武之地。
  3. Memory Wall：當記憶體頻寬跟不上 CPU 處理速度時，時脈再高的 CPU 也只是增加閒置時間。

因此，就演變成現在大家所熟悉的多核心處理器，隨著硬體的進步，軟體當然也要配合才可以發揮最大的效能。這就是此篇文章的目的，從抽象的角度先跟大家分享平行程式設計所應該注意的，有什麼工具、函式庫可以用？接著，會開啟一系列的文章來討論相關的議題。

回到主題，在寫平行化程式的時候，基本上我們應該要注意幾點：

  1. Scalability：寫程式的時候，你絕對不可以因為這只跑在你的雙核心電腦上，就只用兩個執行緒（舉例）。你的程式效能應該要能隨著處理器數量的增加而增加，所以千萬不可以把程式的架構寫死。
  2. Correctness：請先要求自己，用單一執行緒來執行也會正確，不要只顧著平行化，結果程式在單一處理器上跑就會產生錯誤。接著，請避免 Race Condition 以及 Dead Lock。
  3. Maintainability：類似第一點，保持程式架構的彈性，而這部份可以透過高度抽象的執行緒函式庫來幫忙（接著會介紹），也就是儘量不要直接用 pthread 來寫，除非是在不得已的情況下。

接著，以下是前輩們從錯誤中學習到的經驗：

1. Think parallelism first

首先考慮程式中的平行性。不要先考慮如何以傳統方法實現你的程式，然後再試著把平行處理硬塞進去。
而這裡所提到的「Parallelism」分為兩種：

  • Data parallelism
    資料平行處理非常簡單。它是指你有大量資料需要處理 (e.g., 圖像中的許多像素)，把這些資料進行分解並交給多個處理器進行處理，這就是一種資料平行處理的方法。許多年來，這一直是超級電腦最擅長的領域。人們對這類問題有著非常清楚的瞭解，過去對資料平行處理的重視程度也一直超過任務平行處理。
  • Task parallelism

任務平行處理則是指你有多個任務需要完成。例如：你有一個很大的資料集，你想知道該資料集的最小值、最大值和平均值，你可以讓不同的處理器針對同一個資料集分別計算不同的答案。因此，任務平行處理是一種不同的看待問題方式，它不是通過資料分解讓不同的處理器同時做同一項工作，而是對任務進行分解。而整個程式可能是 Task A -> Task B -> … 循序執行。

2. Think about task, not thread (processor)

最好的平行程式不是先問處理器的數量，然後圍繞這個數量來撰寫所有演算法。雖然較低的階層上可能存在這種情況，但程式的高層部分應該製造任務——大量任務，然後讓一些底層結構把這些任務和處理器的數量聯繫起來。顯然，與一個只能製造兩個任務的程式相比，一個能製造數千個平行任務的程式的擴展性要好得多。

3. Tools (compiler, library, debug tools)

檢查自己正在使用的工具。檢查編譯器、程式庫、除錯工具；然後問問自己：這些工具在設計時是否考慮了平行性因素？如果答案是否定的，就找找看有沒有其他工具可以使用，同時非常認真的思考一下，以免在平行處理程式設計時忽略了適當的工具，從而大大增加工作難度。

4. Sequential debugging: make sure your program can run sequentially

請確保它能以單執行緒運行。單執行緒運行時的效率並不重要，重要的是，如果你能讓程式以單執行緒運行，你就能在這一模式下完成許多除錯工作，因為你可以像除錯順序程式一樣排除程式中的常見錯誤，在此過程中不必去處理有關平行性的特殊問題。

人們很容易寫出只能以平方式運行的程式。應該避免這種不好的習慣。一般來說，撰寫一個能夠以單一執行緒運行的程式一點也不困難，而這能夠大大降低除錯的難度。

5. Limit use of lock: Inefficient, Dead lock

在程式中儘量少用 Lock，首先是因為效率低——它們限制了程式的可擴展性。再來就是，在一個不斷變化而且需要呼叫函式庫的程式中，鎖和鎖之間常常相互干擾並造成死結，進而產生各種各樣的問題。

6. Memory allocation: bottleneck

事實證明，在程式的平行化過程中，如果你繼續使用以前使用的記憶體分配技術，則記憶體分配將變成一個很常見的程式瓶頸。與一個可擴展的記憶體分配程式相比，使用多個記憶體池的效率要高得多。因為在分配的過程，你也應該要考慮到平行化的問題。

7. Amdahl’s law

就今天的程式和資料集而言，對速度的提升不要期望太高。應該把可擴展性作為目標。你可以在現有處理器上獲得一定程度的性能提升，但一定要好好想想，隨著工作量的增加，你如何實現擴展。將來，你的程式需要處理更多資料，或者完成更多工。因此，應隨時把可擴展性放在心上。

效能的提升有限，多核心處理器無用武之地？

如果只從表面來看Amdahl定律現在如何提高程式的運行速度，你會發現，多核心處理器和平行處理技術並非那麼吸引人。（因為按照 Amdahl’s Law 來看，效能最高也就是 1/(1-P)）這究竟是怎麼回事？我們已經造出了有數千個處理器的超級電腦，顯然，僅憑Amdahl定律並不能解釋這一現象。

而能夠解釋的定律由 Gene Amdahl 在 1967 年發現。

令人奇怪的是，很久之後，直到 1988 年，Gustafson 才就Amdahl定律提出了自己的意見。他對此抱有完全不同的看法，他認為，電腦所做的工作每年都在發生變化。隨著電腦運算能力的增強，我們交給它的工作量也越來越大，讓它處理的資料越來越多。直至今天，這一趨勢仍未改變。

如果我們換個角度來看，比如說，程式的執行需要 500 個單位時間，我們就把並行部分的工作量增加一倍，在相同時間內，我們將完成 200 個單位的工作。 執行這個程式仍然需要 500 個單位時間，但我們完成了 700 個單位時間的工作，也就是說，只需要 2 個處理器，就能把速度提高 40％。如果我們再增加兩個處理器，每個處理器完成同樣的工作量，我們就能在同樣時間內完成 1100 個單位時間的工作，也就是說，速度提高了 2.2 倍。

Gustafson 的基本觀點是，如果我們不斷增加需要完成的工作量——這正是電腦發展過程中的實際情況，那麼串列部分對我們的影響將逐漸減弱，運行速度將隨著處理器數量的增加而迅速提升。也許我們對平行處理技術的使用和速度的提升還不夠盡如人意——並非每個處理器都能用以提高速度。如果我們有 10 個處理器，我們無法把速度提高 10 倍，但我們能使速度呈線性提升。如果我們把 10 個處理器增加到 20 個，則速度大概能提高一倍。

如果你聽到有人以Amdahl定律為由稱平行處理技術無用，你可以引用 Gustafson 的結論來回應，並說明具體的方法。這就是超級電腦能夠成功運用並行技術的關鍵所在——我們不斷增加資料集，因為有了多核心處理器，這一趨勢會不斷延續。

Abstraction to use for parallelism

前面提到，若不得以，千萬不要直接使用 pthread 來編程，建議的優先順序如下（由高至低）：

  1. Native Library：如果你使用的 Framework 本身就有 API 可以呼叫的話，就不要自己寫，因為這些函式通常都會綁你處理好平行化部分，例如：Obj-C Framework 中的 Core Animation
  2. OpenMP
  3. Threading Building Blocks
  4. Message Passing Interface