計算劃分和任務(wù)分配

計算劃分與任務(wù)調(diào)度并行程序的計算劃分算區(qū)(parallelregion)。在并行計算區(qū)內(nèi)，任意兩個任務(wù)間不存在W-R、R-W、非規(guī)約的W-W，因此可以在不同處理器上同時執(zhí)行。若一個并行計算區(qū)內(nèi)的兩個任務(wù)間存在規(guī)約操作導(dǎo)致的W-W，則要求每個任務(wù)在執(zhí)行規(guī)約操作時要與其它任務(wù)同步，確保時 時并行計算區(qū)存在W-R、R-W、或者W-W，否則該任務(wù)應(yīng)并入前一個并行計算區(qū)、甚至與前一個并行計算區(qū)的某個任務(wù)合并。存在讀/寫的任務(wù)分別由不同處理器執(zhí)行時，處理器間就需要進行數(shù)據(jù)交換和進度同步。相鄰兩個并行計算區(qū)的讀/寫越頻繁，它們的在執(zhí)行region(K)時，將(Ｋ)中的元素均勻分配給各PRAM處理器，依次檢測它們與K整運算均勻分配給了各個PRAM處理器，因此有利于計算資源間的負載均衡。但是當(dāng)KxP(N)的計算劃分為若干個超:計算{x:51<x<2209}中的素數(shù)，求出P(2209)；……；直至求出P(N)為止。在每個超級BSP處理器分別執(zhí)行一個任務(wù)，在通信階段將所找到的素數(shù)合并到一上，難以平衡各個BSP處理器間的負載。設(shè)計并行程序的計算劃分方案時，要充分挖掘計算任務(wù)的并行度(paralleldegree)，即在一量一個計算劃分方案：負載均衡(loadbalance)和任務(wù)粒度(granularity)。負載均衡用來衡量信量之比相對小時，則將任務(wù)劃分稱為細粒度的(fine-grained)，反之則稱為粗粒度的粒度太小可能會導(dǎo)致饑餓現(xiàn)象(starvationphenomenon)。饑餓現(xiàn)象:并行程序在執(zhí)行某個并行計算區(qū)的過程中，當(dāng)有任務(wù)尚未分配給處理器時，態(tài)。饑餓現(xiàn)象通常是由于任務(wù)粒度太小，計算劃分效率不高、或者任務(wù)執(zhí)行的規(guī)約操作并行程序的任務(wù)分配寬度優(yōu)先搜索(BFS：breadth-firstBFSG=<V,E>r到其他各點的最短距離。該問題實際是要從r出Gr為根的樹BFS_tree(r)v在該樹上的深度即為rv的最短距frontier(max_d)BFS_tree(r)0、1、……、max_d的節(jié)點的集合，BFS算法將依次生成frontier(0)、frontier(1)、……、frontier(max_d)，其中frontier(0)為集合{r}、max_d為BFS_tree(r的最大深度。生成frontier(d)(d0vfrontier(d和v,uE，若

????????????????(??)ufrontier(d+1)。下圖(a)BFS由fronr()(d0ronr(+1d節(jié)點。將節(jié)點vfroner(d)的擴展作為一個任務(wù)，記為ak(v)。顯然，任務(wù)ak(v1)和ak(v2)對fone(d+)W-Wv1frone(d)v2ronr()v1v2而且，若v1,uE、v2,u、v12、v1froned)、v2fronerd)且ufrne(d+)，則任務(wù)ak(v1)和ak(v2)對bf_ree]的也存在W-W。此時，ak(v1)和ak(v2)的執(zhí)bseuor+rndd)一個并行計算區(qū)，fn(1)中的每個節(jié)點代表該并行計算區(qū)中的一個任務(wù)。下圖()是以并行計算實現(xiàn)SS(fs_eeu,-1,v)和AA(k2,1)AS(fs_e+u,,v)在fs_reu-1asevre，A(k,1k2k2+1_)GE和搜索的起點r。在樹BFS_tree(r)for(k=0;k<nv;++k)bfs_tree[k]=-1;vlist[0]=r;bfs_tree[r]=r;k1=0;k2=while(k1!={oldk2=for(k=k1;k<oldk2;{v=foreachedgev,uEif(bfs_tree[u]!=-1)continue;bfs_tree[u]=v;vlist[k2++]=}}k1=}輸出：bfs_tree[]，bfs_tree[v]v在BFS_tree(r)上的父節(jié)點for(k=0;k<nv;++k)bfs_tree[k]=-1;vlist[0]=r;bfs_tree[r]=r;k1=0;k2=while(k1!={oldk2=#pragmaompparallelprivate(v,k3,u)for(k=k1;k<oldk2;++k){v=foreachedgev,uE{if(CAS(bfs_tree+u,-1,v){k3=FAA(&k2,vlist[k3]=}} BFSbfs_tree[]具有不確定性，bfs_tree[]所BFS_tree(r)BFS_tree(r)上邊不及各節(jié)點在數(shù)上的深度都是一致的，即各點到r的距離是確定的。多體問題(N- T時刻兩個粒子之間的作用力、??和??分別是這兩個粒子的質(zhì)量、(??(??,??(??),??(?? (??(??)??(??)??(??))TiT時刻的受力??(??) (2)，由此使用(3)、(4)可計算其在T+1時刻的狀態(tài)，包括空間位置坐標(??(??+1)??(??+1)??(??+1))和運動速度???(??+1)T ??(??)=?????????? (??)?? ???????? = ??,??)= ??????,?? ??,?? (??(??))2 = + = + ??(??+1)=??(??)+ = + = + ??(??)???(??) = + (??

??,??)= + ( ? ??=0,??≠?? ??(??)???(??) = + (??

??,??)= + ( ? ??=0,??≠?? ??(??)???(??) = + (???? ??,??)= + ( ?

??=0,??≠?? ???(??+1)=???(??)+??(??)(??(??)? ???(??+1)=???(??)+??(??)(??(??)? = + ? = + ? = + ? = + ? ???(??+1)=???(??)+??(??)(??(??)? ???(??+1)=???(??)+??(??)(??(??)? 其中??(??) 2√ (??) (??) (??)2((?????????)+(?????????)+(?????????)N-body問題的主要開銷是根據(jù)(2)計算各個粒子的受力。盡管每個粒子都可以分別根據(jù)(2)計算在T時刻受到的作用力，但是粒子i和粒子j之間的作用力是相互的，即??(??)=??(??)。因此，先計算出每個粒子對之間的作用力，然后再通過規(guī)約計算得出每個粒子 (表示算。N顆粒子的問題中，每個時間步上要執(zhí)行N(N-1)/2次(5)表示的規(guī)約計算，這些計算構(gòu)成并行程序的一個并行計算區(qū)。若將這N顆粒分為K份，則可以將這些計算分為算區(qū)和任務(wù)劃分可以用下圖表示，共有28規(guī)約計算的元素，整個并行計算區(qū)中的計10個任務(wù)。這些任務(wù)可以分為兩類，處于對角線上的任務(wù)和非對角線的任務(wù)，NK；而對角線上任務(wù)的運算量r(0,r(0,r(0,r(0,r(0,r(0,r(0,r(1,r(1,r(1,r(1,r(1,r(1,r(2,r(2,r(2,r(2,r(2,r(3,r(3,r(3,r(3,r(4,r(4,r(4,r(5,r(5,r(6,(data-parallelpattern)、分治并行(divide-conquerpattern)、流水并行(pipelinepattern)。這三種同，部分或者全部元素可以按照任意順序進行處理。例如前面的BFS搜索就是一個數(shù)據(jù)并行的問題，其中所處理的數(shù)據(jù)集合用一個圖表示，frontier(d)(d0)中的各點可以按照任意順 行模式的計算劃分和分配。這一任務(wù)分配方式以并行程序的數(shù)據(jù)劃分(datadistribution)為基沒有。并行程序在對數(shù)組進行數(shù)據(jù)劃分時有“塊劃分(block)”和“循環(huán)劃分(cyclic)”結(jié)構(gòu)，除了一個全局空間外，各個處理器通常都有自己的本地高速空間，例如SMP、multi-core和GPU均采用多級結(jié)構(gòu)。數(shù)據(jù)并行計算中相鄰迭代常常下標相性，有利于在執(zhí)行子任務(wù)時開發(fā)處理器的本地高速空間的能力。特別是在基于cache機制的訪存系統(tǒng)中，可以明顯降低cache失效率、提高效率。N-Body問題中，兩個粒子對之間的計算通常用一個二重循環(huán)表示，其中內(nèi)層示例1：基于靜態(tài)數(shù)據(jù)劃分的數(shù)據(jù)并行模式。例如述的N-body求解時，可以采用靜態(tài)方式進行數(shù)據(jù)劃分，即并行程序一開始就將N顆粒分為K份i(0i<K)，其中K是處理器的數(shù)量。任務(wù)taskij(0i<j<K)結(jié)構(gòu)，除了一個全局空間外，各個處理器通常都有自己的本地高速空間，例如SMP、multi-core和GPU均采用多級結(jié)構(gòu)。數(shù)據(jù)并行計算中相鄰迭代常常下標相性，有利于在執(zhí)行子任務(wù)時開發(fā)處理器的本地高速空間的能力。特別是在基于cache機制的訪存系統(tǒng)中，可以明顯降低cache失效率、提高效率。針對數(shù)據(jù)并行 “動態(tài)循環(huán)分片(dynamictiling)”方法。在數(shù)據(jù)并行循環(huán)的執(zhí)行過，每當(dāng)某個計性能瓶頸。例如在有8顆處理器的并行系統(tǒng)上計算兩個向量A和B的點積DP(A,B)=∑(????×????)4算步，就能夠求出整個向量的點積結(jié)果DP(A,B)。8顆處理器上采用分治并行計算向量A和B-rdcnur些)11”的模式和“”1”的模式下，每個生產(chǎn)者子任務(wù)結(jié)果需要一個消費者子任務(wù)做進一步的處1N)ii1及(并發(fā)計算(concurrent當(dāng)兩個任務(wù)不存在的數(shù)據(jù)(包括W-R、R-W、W-W)時，則稱它們是無關(guān)的。無關(guān)任務(wù)間不存在同步需求，它們的控制線程(threadofcontrol)互相獨(a)中，task1task2，兩種情形下會以這種計算形式執(zhí)行無關(guān)的任務(wù)：計算系統(tǒng)task1task2task1task2提供所需要的task1task2提供所需要的資源。圖(c)task1task2的請求，task2task1存在資源競爭，它們將采用分時策略占用競爭的資源，task1執(zhí)行時則將task2掛起、反之task2執(zhí)行時則將task1掛起。Task1 Task1 Task1(c)串行執(zhí) (b)并行執(zhí)

(a)?????????????????(??計算系統(tǒng)中處理器的數(shù)量、??是該時間間隔內(nèi)完成的任務(wù)數(shù)、??????????????????(0????)是所完成處理器時間消耗量。單個任務(wù)的處理器時間消耗量可以用?????表示，其中??是該任它們可以是無關(guān)的、也可能存在規(guī)約操作導(dǎo)致的W-W。計算(HTC:high-throughputcomputing)領(lǐng)域、任務(wù)群計算(MTC:many-taskcomputing)領(lǐng)域、和實時計算(RTC:real-timecomputing)領(lǐng)域的問題求解。2.4. 高性能計算算資源，由這些資源協(xié)助完成應(yīng)用問題的數(shù)據(jù)處理。一個高性能計算系統(tǒng)(high-performancecomputingsystem)由應(yīng)用軟件、系統(tǒng)軟件和硬件設(shè)備組成。它在問題求解時采用承擔(dān)的運算量并最終減少應(yīng)用問題的數(shù)據(jù)處理時間消耗。HPC中，單個任務(wù)的運行時間一2.4. 高通量計算本、機器運行和制冷的電力能源成本以及設(shè)備的場地成本等。HTC通過在不同的用戶之間運行和成本，最終降低單個任務(wù)的計算成本。HTC中，任務(wù)通常指的是某個程序的運天、甚至月。各任務(wù)分別由不同的用戶提交、互相獨立，每個任務(wù)都可以獨立調(diào)度和執(zhí)行。與HPC相比，HTC中任務(wù)的數(shù)量較少，但單個任務(wù)的資源消耗量大、運行周期長，而且HTC系統(tǒng)中任務(wù)的數(shù)量在系統(tǒng)運行過動態(tài)增長。HTCHTC

PBS、Condor所解決的問題是對網(wǎng)絡(luò)計算系統(tǒng)中的資源進行統(tǒng)一管理和分配，并提供統(tǒng)一的接口供不同的用戶透明、共享這些資源，如上圖所示。HTC系HTC系統(tǒng)的計算節(jié)點是并行計算機時，也可以在該節(jié)點上并行執(zhí)行多個任務(wù)。處理器數(shù)量以及其他軟件和硬件要求、程序的輸入和輸出數(shù)據(jù)文件等。HTC系統(tǒng)收到一個任務(wù)完成后，HTC系統(tǒng)將收回該任務(wù)占用的資源；同時檢查等待隊列，從中選擇一個資源需求能夠得到滿足的任務(wù)并啟動該任務(wù)的執(zhí)行。HTC調(diào)度器總是在滿足各個任務(wù)的資并行執(zhí)行技術(shù)縮短各個任務(wù)的完工時間。HTC的主要目標是在一個相當(dāng)長的時間內(nèi)利用已2.4. 任務(wù)群計算HPCHTCHPC一樣，MTC中任務(wù)的數(shù)量非常多，可HTC一樣，MTC中的任務(wù)都是可以獨立調(diào)度的，每個任務(wù)都以文件作為輸入和輸出、分別請求運行某個可執(zhí)行程序。但是，MTC與HPC、HTC又都有所不同，它的任務(wù)通常比HPCHTC的任務(wù)簡單，單個任務(wù)的資源需求一般可以在單臺計算機上得到滿足，任務(wù)的運行周期一般以秒、分、或者小時記。在MTC中，通常在于并行的不同之處在于，MTC