天天看點

MPI程式的任務分解方法

用mpi編寫并行程式時,任務分解是很重要的一部分,如何把t個任務(t塊資料,t行矩陣等)分給p個程序,實作負載均衡,是需要好好考量的問題。分解任務時需要解決兩個問題:

1.給出一個程序p,如何得知要處理的任務是哪些

2.給出一個任務t,如何得知它是由哪個程序處理的

(這裡的p和t都是從0開始計數。)

一個好的任務配置設定,應該能夠保證這兩種計算都能高效完成。下面讨論三種配置設定方式。這裡隻讨論t>p的情況,t<=p時的分解方式是顯而易見的。

一,交叉分解

對于程序p,它所處裡的任務号為t=p+kp,其中k要保證p+kp<=t。

對于任務t,處理它的程序為p=t%p

二,按塊分解

按塊分解的方法是給每個程序p配置設定連續的任務,每個程序配置設定到連續的┌t/p┐或者└t/p

┘個任務。有兩種分法。

方法一:

令r=t%p,給前r個程序配置設定┌t/p┐個任務,後p-r個程序配置設定個└t/p

┘任務。

則對于程序p,它所處裡的第一個任務号為p└t/p

┘+min(p, r),它處理的最後一個任務号為下一個程序處理的第一個任務的前一個,也即是(p+1)└t/p

┘+min(p+1, r)-1

對于任務t,處理它的程序為p=max(└t/(└

t/p┘+1)┘,└(t-r)/└ t/p┘┘),看起來的确有點麻煩,計算起來也比較費勁,是以就引出了另一種按塊劃分的方法。

方法二:

這種劃分方法并不是把較大的塊分給前面的程序,而是将這些塊“随機”的分給程序。

則對于程序p,它所處裡的第一個任務号為└pt/p┘,它處理的最後一個任務号為下一個程序處理的第一個任務的前一個,也即是└(p+1)t/p┘-1

對于任務t,處理它的程序為p=└(p(t+1)-1)/t┘

對于t=14,p=4的情況,下圖可以看出兩種分塊方式的差别:

MPI程式的任務分解方法

參考書籍:《mpi與openmp并行程式設計(c語言版)》