設(shè)計(jì)并行算法的思路(1)

1. 模型抽象

一般來(lái)說(shuō)如果一個(gè)問(wèn)題可以被抽象為一個(gè) DAG(有向無(wú)環(huán)圖)那么這個(gè)問(wèn)題都可以用來(lái)并行計(jì)算。常見(jiàn)問(wèn)題可以抽象下面兩種模型。

1） for 循環(huán)的展開。

for(int i = 0 ; i < N ; i++)
  work(i);

這種問(wèn)題可以分解為 N 個(gè)問(wèn)讓 p 個(gè) cpu 同時(shí)計(jì)算。

2）divide and conquer, 分治算法。

int work(int start, int end){
  if(end -  start  < N){
    //do some thing
  }
  work(start, (star+end) / 2 );
  work((star+end) / 2+1, end );
}

通過(guò)divide 的方式將問(wèn)題劃歸為一列不相關(guān)的子問(wèn)題，這些子問(wèn)題可以同時(shí)被順序解決。這樣也提高了工作效率。常見(jiàn)的例子為，快速排序和歸并排序。

2. 問(wèn)題分析

對(duì)于樣的模型，我們?nèi)绾螌?duì)它們進(jìn)行量化分析呢？在這里需要定義兩個(gè)指標(biāo) work 與 span。

Work 是在順序執(zhí)行的情況下的總計(jì)算復(fù)雜度。也就是我們常說(shuō)的計(jì)算復(fù)雜度。

Depth(span) 是指每個(gè)處理器被分配的任務(wù)。通常情況下是一個(gè) DAG 圖中最長(zhǎng)的路徑(如如圖中的黃色的路徑)。

image

幾條定律

在分析時(shí)間復(fù)雜度的時(shí)候，我們暫時(shí)拋開內(nèi)存和通信上面的開銷。

1 speed up

S_{p} =\frac{W}{T_{p}}

2 時(shí)間復(fù)雜度的下界

T_{p} \geq \frac{W}{p}, \ \ T_{p} \geq D \rarr T_{p} \geq \max\{ \frac{W}{p}, D \} 其中 p 是處理器的數(shù)量，D是上面提到的 span

3 時(shí)間復(fù)雜度的上界
image

為了證明上界，我們講將整個(gè) DGA 圖轉(zhuǎn)換為上圖的的模式?？梢苑指顬橐粋€(gè)個(gè)的 phase（圖中的黃色分割線），中間的藍(lán)色點(diǎn)就是 critical path，也就是我們之前講的 D 。這個(gè)新的圖有如下性質(zhì)：

  1. 每一個(gè)critical 路徑上的一個(gè)節(jié)點(diǎn)就是一個(gè) phase。
  2. 同一層上左右兩邊的非關(guān)鍵路徑上的node代表一組task，他們之間沒(méi)有相互依賴。
  3. DAG 圖中的每一個(gè)點(diǎn)都會(huì)出現(xiàn)在一個(gè) phase中。

W_{i} 代表每一個(gè)phase里面的work數(shù)目。 T_{i} = \lceil \frac{W_{i}}{p}\rceil 。 T_{D} = \sum ^{D}_{i=1}\ \lceil \frac{W_{i}}{p}\rceil =T_{D} = \sum ^{D}_{i=1}\ \lfloor \frac{W_{i} - 1}{p}\rfloor + 1

這里有由 ceilling 的轉(zhuǎn)化公式 \lceil \frac{a}\rceil = \lfloor \frac{a-1}\rfloor + 1 轉(zhuǎn)化而得。

\sum ^{D}_{i=1}\ \lfloor \frac{W_{i} - 1}{p}\rfloor + 1 \leq \sum ^{D}_{i=1}\ \frac{W_{i} - 1}{p} + 1 = \frac{W-D}{p} + D

其實(shí)直觀的理解這個(gè)就是阿達(dá)姆法則 \frac{W-D}{p} 是可并行化的部分而 D 是不可并行化的。

所以增速 speed \geq \frac{W_{1}}{\frac{W-D}{p} + D } = \frac{p}{\frac{W-D + pD}{W_{1}}} \

= \frac{p}{\frac{W}{W_{1}}+\frac{p-1}{W_{1}/D}}

  1. if W= W_1 （work optimality）串行與并行的work是一樣的。

3. 設(shè)計(jì)并行算法

那么為了設(shè)計(jì)并行算法要實(shí)現(xiàn)的目標(biāo)是 Work 與 span 都要小。

Work efficiency: A parallel algorithm is work efficient if it performs asymptotically the same work as the best known sequential algorithm for that problem.

需要遵循兩條原則

  1. work optimality: w = w1 = O(n) if possible
  2. low span, D(n) = O(log^K{n})

對(duì)于 divide and conquer 的問(wèn)題的理論上最優(yōu)是

T(n) = 2T(\frac{n}{2}) + O(1) = O(n)

W(n) = 2W(\frac{n}{2}) + O(1) = O(n)

D(n) = D(\frac{n}{2}) + O(1) = O(logn)

對(duì)于 for 循環(huán)

W_{p}(n) = O(n) D(n) = O(1)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容