in C Programming ~ 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
comments powered by Disqus