【圖文】第十六章 并行算法

1、 16.7 MIMD-SM上的異步并行求和算法 上的異步并行求和算法 假設(shè)共享存儲器多處理機系統(tǒng)有P個處理器，其編號為 ， 假設(shè)共享存儲器多處理機系統(tǒng)有 個處理器，其編號為P1， 個處理器 P2，Pp-1,由一個全局變量 由一個全局變量total-sum存儲數(shù)據(jù)的總和， 存儲數(shù)據(jù)的總和， ， ， 由一個全局變量 存儲數(shù)據(jù)的總和 每個處理器Pi分配一個并發(fā)進程都有各自的局部變量 分配一個并發(fā)進程都有各自的局部變量local每個處理器 分配一個并發(fā)進程都有各自的局部變量 sum，該局部變量是用來存儲部分?jǐn)?shù)據(jù)的子和，然后將所求 ，該局部變量是用來存儲部分?jǐn)?shù)據(jù)的子和， 得的local-sum加到全局變

2、量 加到全局變量total-sum中。 得的 加到全局變量 中 很明顯可以看出此算法存在存儲沖突。 很明顯可以看出此算法存在存儲沖突。假如說當(dāng)一個進程把 所求得的部分?jǐn)?shù)據(jù)子和local-sum加到全局變量 加到全局變量total-sum中 所求得的部分?jǐn)?shù)據(jù)子和 加到全局變量 中 時有另一個進程也要把部分的數(shù)據(jù)子和加進去， 時有另一個進程也要把部分的數(shù)據(jù)子和加進去，那么就會產(chǎn) 生資源沖突，這種沖突會很頻繁的發(fā)生， 生資源沖突，這種沖突會很頻繁的發(fā)生，因為全局變量總和 的相加操作需要異步進行。 的相加操作需要異步進行。 我們通常所用的解決沖突的辦法是當(dāng)要訪問全局變量時先首 先對它進行加鎖，使得其他

3、進程無法同時使用這個資源， 先對它進行加鎖，使得其他進程無法同時使用這個資源，當(dāng) 訪問結(jié)束后立即解鎖以免耽誤其他進程對其進行的操作。 訪問結(jié)束后立即解鎖以免耽誤其他進程對其進行的操作。 MIMD-SM機器上的異步并行求和其實是一個進程和 個并發(fā) 機器上的異步并行求和其實是一個進程和P個并發(fā) 機器上的異步并行求和其實是一個進程和 子進程組成，每個子進程分別求出分配給他的n/p個數(shù)據(jù)的子 子進程組成，每個子進程分別求出分配給他的 個數(shù)據(jù)的子 和。 2011-5-24 36 16.7 MIMD-SM上的異步并行求和算法 上的異步并行求和算法 算法16.5 MIMD-SM機器上的異步并行求和算法 算法

4、 機器上的異步并行求和算法 begin /開始主進程 開始主進程 total_sum=0; for i=1 to p do in parallel begin sub_sum(i,local_sum; lock(total_sum; /對全局變量 對全局變量total_sum加鎖 對全局變量 加鎖 total _sum= total _sum+local_sum; unlock(total_sum; end end procedure sub_sum(i,local_sum /并發(fā)子進程 并發(fā)子進程 begin local_sum=0； ； for j=i to n step p do loc

5、al_sum=local_sum+xj; return local_sum; end 2011-5-24 37 16.7 MIMD-SM上的異步并行求和算法 上的異步并行求和算法 上述算法在最壞情況下的運算時間， 上述算法在最壞情況下的運算時間，該運算時間有以下幾部 分組成： 分組成： （1）生成進程所需要的時間：生成 個子進程需要時間為 ）生成進程所需要的時間：生成p個子進程需要時間為 O(p; （2）局部求和所需要的時間：每個子進程都需要對 ）局部求和所需要的時間：每個子進程都需要對n/p個數(shù) 個數(shù) 據(jù)求和，所以局部求和時間為O(n/p; 據(jù)求和，所以局部求和時間為 （3）求取總和所需要的時間：因為在任何一個時間只能由一 ）求取總和所需要的時間： 個進程執(zhí)行總和的操作，相當(dāng)于p個處理器串行地對全局變量 個進程執(zhí)行總和的操作，相當(dāng)于 個處理器串行地對全局變量 total-sum進行加鎖、解鎖操作，所以需要的時間為 進行加鎖、 進行加鎖 解鎖操作，所以需要的時間為O(p; （4）進程同步所需要的時間：進程是異步并行執(zhí)行的，所以 ）進程同步所需要的時間：進程是異步并行執(zhí)行的， 在最壞情況下p個并發(fā)進程同步結(jié)束需要的時間為 個并發(fā)進程同步結(jié)束需要的時間為O(p。 在最壞情況下 個并發(fā)進程同步結(jié)束需要的時間為 。 因此上述算法在最壞情況下的運算時