iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 8
0
自我挑戰組

當傳統演算法遇到新的計算模型系列 第 8

Day 8: 平行計算模型(一)Parallel Computation Model, Part 1 -- 加總問題

共享記憶體

在這篇文章當中,我們探討的平行計算模型是,所有的處理器都有共享記憶體。看到這個詞應該很多朋友第一時間腦中都會蹦出一個詞彙叫做 共享經濟,想必相當划算 Race Condition(中文翻譯好像叫做競態條件,這什麼趣味名詞...)。不過就讓我們暫時假設可以好好地不用擔心 Race Condition 吧 ( ̄▽ ̄#)﹏﹏

順便講講

這次我們要討論的是一個叫做 CREW PRAM 的平行計算模型。按照字面上的意思解讀,就是可以讓不同執行緒同時讀取同一個位址的記憶體、但是不能同時寫入、然後所有執行緒共享記憶體這樣。

平行演算法分析

要怎麼衡量一個平行演算法的工作效率呢?由於各家平行計算的系統架構都不同。我們來考慮一個最抽象化的模型吧!

☯ 總工作量 Work (W)

顧名思義,總工作量的定義就是所有處理器花在這支程式上的時間總和(不包含待命時間)。如果把待命時間也考慮進去的話,它叫做總花費 Cost。

☯ 工作深度 Depth (D)

顧名思義,工作深度就是根據計算的相依性,找出相依性最長的那件工作。以圖論的角度而言,如果我們把所有運算步驟的相依性繪製成一個有向無環圖,那麼工作的深度就是這個圖上的最長路徑長度。在某些模型中,這個數值又被稱呼為 Span(跨度)。

有了這些概念後,Brent 得出了以下結論:對於一個深度是 D、總工作量是 W 且擁有 P 個處理器的平行演算法來說,執行時間不超過 https://chart.googleapis.com/chart?cht=tx&chl=O(W%2FP%2BD)

什麼樣子的演算法適合(被改造成)平行化?

可以想見,如果一個演算法內部的演算流程不太具有相依性,那麼就有機會改造成平行演算法。讓我們來舉個例子吧~比方說我們想要計算 https://chart.googleapis.com/chart?cht=tx&chl=n 個東西的總和。如果單純地寫一個 for 迴圈:

for (int i = 0; i < n; i++)
    sum += a[i];

那麼程式執行時必須要先把 a[0] 加到 sum、再把 a[1] 加到 sum、以此類推。不管怎麼加 sum 都必須要被更動到 https://chart.googleapis.com/chart?cht=tx&chl=n 次。這樣會造成相當大的深度。(題外話:大家可以想想看為什麼我們看到上面這段 code 的時候,不能隨意更動它變成平行的演算法?)如果這些資料本身被加起來的過程沒有相依性,我們就不應該寫出這樣的程式碼,因為這樣的程式碼會不利於平行化。

但如果我們就只是單純地想要計算 https://chart.googleapis.com/chart?cht=tx&chl=n 個數字的總和,誰先加誰後加沒什麼關係,我們可以把輸入拆成很多部份,讓 https://chart.googleapis.com/chart?cht=tx&chl=P 個處理器分別加總 https://chart.googleapis.com/chart?cht=tx&chl=n%2FP 個數字,最後再依序把他們加到某個記憶體的位址上。這樣一來,工作深度便成了 https://chart.googleapis.com/chart?cht=tx&chl=O(P%20%2B%20n%2FP),當 https://chart.googleapis.com/chart?cht=tx&chl=P%3D%5Csqrt{n} 的時候會達到最小深度 https://chart.googleapis.com/chart?cht=tx&chl=O(%5Csqrt{n}),比原本的深度 https://chart.googleapis.com/chart?cht=tx&chl=O(n) 來得好呢。

同樣的想法可以繼續延伸下去,我們可以把它想成一棵加法樹,每一個節點代表一個子集合的加總問題。如果我們每次都把一個集合拆成 https://chart.googleapis.com/chart?cht=tx&chl=k 個更小的子集合,分別加完以後再把他們加起來。工作深度就會是 https://chart.googleapis.com/chart?cht=tx&chl=O(k%2B%5Clog_k%20n)(證明略,大家可以想想為什麼是 https://chart.googleapis.com/chart?cht=tx&chl=O(k%2B%5Clog_k%20n) 而非 https://chart.googleapis.com/chart?cht=tx&chl=O(k%2B%5Clog_k%20n))因此,如果我們讓 https://chart.googleapis.com/chart?cht=tx&chl=k%20%3D%20%5Clog%20n%2F%20%5Clog%5Clog%20n,那麼該演算法的工作深度就會是 https://chart.googleapis.com/chart?cht=tx&chl=O(%5Clog%20n%2F%20%5Clog%5Clog%20n),很棒吧!

今天先討論到這邊,我們明天繼續改造更多演算法~

參考資料

  1. https://www.cs.cmu.edu/~guyb/papers/BM04.pdf

上一篇
Day 7: 外部存取模型 External Memory Model
下一篇
Day 9: 平行計算模型(二) Parallel Computation Model, Part 2 -- 搜索問題
系列文
當傳統演算法遇到新的計算模型21

尚未有邦友留言

立即登入留言