平行處理(Parallel processing, PP)
為什麼要採用平行計算有以下原因:
PP可以加快計算速度,即在更短的時間內解決相同的問題或在相同的時間內解決更多更複雜的問題,特別是對一些的巨量計算問題,不使用平行計算是根本無法解決。
節省投入,平行計算可以以較低的投入完成串列計算才能夠完成的任務。
物理極限的約束,只有通過並行才能夠不斷提高速度。
現在多核心的電腦很普遍,多個CPU代表電腦擁有同時處理多項工作的能力,我們可以將單一工作分解,成為數個可獨立執行的部份來平行處理,這就是程式平行化的概念,開發者可以透過這方面的知識,讓程式能夠在更短的時間執行完畢。
以下是程式能平行化的條件:
程式中只有彼此不相關,以及可以獨立執行的部分才能被平行化。
- 第一點是說如果兩個任務是彼此相關的,例如任務B需要任務A的計算結果,那麼即使想將這兩個任務平行處理,B也必須等到A完成後才能運作,這樣只能序列執行而無法進行平行化。
程式碼必須經過適當的修改才能被平行化。
- 第二點指的是必須對程式碼中需要平行執行的部分設計,像是如何將任務切割、建立執行緒去執行被分割的任務、或在不同執行程序間交換訊息等。不同的平行化 API有不同的做法,有的API提供若干函式來處理這些工作,開發者必須在要平行化的程式區段中,調用這些API函式以達成平行執行的目的,而有些API則是以程式敘述或註解形式,放在程式碼要平行化的區段,然後透過這些敘述,告訴編譯器在編譯階段將該區段設定為平行執行。
平行化方式和實際執行程式的平臺架構有關。
第三點指的是平行處理方式是依執行程式的平臺架構而定,目前常見的有共享記憶體架構(shared memory)、分散記憶體架構(distributed memory)、與異質裝置架構(heterogeneous device)三種。
共享記憶體架構是最常見的平行執行架構,所有配備多核心CPU的電腦都算,以多執行緒(multi-thread)型式為主流,一般使用的API為Pthreads與OpenMP;
- 分散記憶體架構則應用在叢集電腦上,其平行程式是屬於多程序(multi-process)型式,程序之間的訊息是透過網路來傳遞,常用的平行化API為MPI(Message Passing Interface);
- 異質裝置結構指的是用和CPU不同的計算裝置,像是使用顯示卡做計算的GPGPU運算即是屬於此類,較出名的API有CUDA、OpenCL等。
程式平行化的副作用
有時候經過平行化的程式反而比原本序列程式來得慢,因為在平行執行時會比其在序列執行時,多出一些像是分配任務、交換資訊之類的額外工作,如果這些額外工作的花費時間,比平行執行所獲得的效益還大的話,平行化反而會拖慢完成的時間。因此通常只對要花費較多時間的任務進行平行化,且會建立比較的基準,通常比較的基準就是該程式的序列執行版本,當我們將程式平行化後會跟基準做比較,看平行執行是否划得來。
程式平行化的考量
能獲得多少加速的效益:一個程式是否該被平行化,要考慮到它可被平行化的部份佔整體的時間比例,假如一個程式只有10%部分可以被平行化,即使是最理想狀況,把這10%的部分縮減到近於0,也只縮減1/10的時間,如果這個程式的執行時間本來就不長,那加速更顯得沒有必要。
要花多少時間修改程式:我們都希望修改程式的時間越短、困難度越低越好,除了取決於開發者的經驗外,也跟採用的API有很大的關係,通常越低階的API,像Pthreads、MPI等可以提供比較好的平行效能,但是困難度較高,而高階的API,像OpenMP等的性能取決於編譯器好壞,但具有簡單易學及快速修改程式的優點。
參考文獻
1 | Barry, Wilkinson, Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, 2/E, Pearson Education India, 2006. |
2 | Hager, Georg and Wellein, Gerhard, Introduction to high performance computing for scientists and engineers, CRC Press, 2010. |
3 | Barney, Blaise and others, Introduction to parallel computing, 2010. |