并行程序設(shè)計(jì) 中文課件 03 并行程序設(shè)計(jì)基礎(chǔ)

ParallelProgrammingInstructor:ZhangWeizhe(張偉哲)ComputerNetworkandInformationSecurityTechniqueResearchCenter,SchoolofComputerScienceandTechnology,HarbinInstituteofTechnologyFundamentalprinciplesofparallelprogramdesign3Outline1.PCAMdesignprinciple2.ParallelProcessingEvaluation并行處理評價(jià)3.

ParallelProgrammingModel并行編程模型4.Summary并行算法的一般設(shè)計(jì)方法串行算法的直接并行化從問題描述開始設(shè)計(jì)并行算法借用已有算法求解新問題串行算法的直接并行化方法描述發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造為并行算法。評注由串行算法直接并行化的方法是并行算法設(shè)計(jì)的最常用方法之一；不是所有的串行算法都可以直接并行化的；一個(gè)好的串行算法并不能并行化為一個(gè)好的并行算法；許多數(shù)值串行算法可以并行化為有效的數(shù)值并行算法。從問題描述開始設(shè)計(jì)并行算法方法描述從問題本身描述出發(fā)，不考慮相應(yīng)的串行算法，設(shè)計(jì)一個(gè)全新的并行算法。評注挖掘問題的固有特性與并行的關(guān)系；設(shè)計(jì)全新的并行算法是一個(gè)挑戰(zhàn)性和創(chuàng)造性的工作；借用已有算法求解新問題方法描述找出求解問題和某個(gè)已解決問題之間的聯(lián)系；改造或利用已知算法應(yīng)用到求解問題上。評注這是一項(xiàng)創(chuàng)造性的工作；使用矩陣乘法算法求解所有點(diǎn)對間最短路徑是一個(gè)很好的范例。PCAM設(shè)計(jì)方法學(xué)劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)小結(jié)

PCAM設(shè)計(jì)方法學(xué)設(shè)計(jì)并行算法的四個(gè)階段劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)劃分：分解成小的任務(wù)，開拓并發(fā)性；通訊：確定諸任務(wù)間的數(shù)據(jù)交換，監(jiān)測劃分的合理性；組合：依據(jù)任務(wù)的局部性，組合成更大的任務(wù)；映射：將每個(gè)任務(wù)分配到處理器上，提高算法的性能。PCAM設(shè)計(jì)過程PCAM設(shè)計(jì)方法學(xué)劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)小結(jié)

劃分方法描述充分開拓算法的并發(fā)性和可擴(kuò)放性；先進(jìn)行數(shù)據(jù)分解(稱域分解)，再進(jìn)行計(jì)算功能的分解(稱功能分解)；使數(shù)據(jù)集和計(jì)算集互不相交；劃分階段忽略處理器數(shù)目和目標(biāo)機(jī)器的體系結(jié)構(gòu)；能分為兩類劃分：域分解(domaindecomposition)功能分解(functionaldecomposition)域分解劃分的對象是數(shù)據(jù)，可以是算法的輸入數(shù)據(jù)、中間處理數(shù)據(jù)和輸出數(shù)據(jù)；將數(shù)據(jù)分解成大致相等的小數(shù)據(jù)片；劃分時(shí)考慮數(shù)據(jù)上的相應(yīng)操作；如果一個(gè)任務(wù)需要別的任務(wù)中的數(shù)據(jù)，則會產(chǎn)生任務(wù)間的通訊；域分解示例：三維網(wǎng)格的域分解，各格點(diǎn)上計(jì)算都是重復(fù)的。下圖是三種分解方法：15域分解非規(guī)則域分解功能分解劃分的對象是計(jì)算，將計(jì)算劃分為不同的任務(wù)，其出發(fā)點(diǎn)不同于域分解；劃分后，研究不同任務(wù)所需的數(shù)據(jù)。如果這些數(shù)據(jù)不相交的，則劃分是成功的；如果數(shù)據(jù)有相當(dāng)?shù)闹丿B，意味著要重新進(jìn)行域分解和功能分解；功能分解是一種更深層次的分解。功能分解示例1：搜索樹示例2：氣候模型劃分判據(jù)劃分是否具有靈活性？劃分是否避免了冗余計(jì)算和存儲？劃分任務(wù)尺寸是否大致相當(dāng)？任務(wù)數(shù)與問題尺寸是否成比例？功能分解是一種更深層次的分解，是否合理？PCAM設(shè)計(jì)方法學(xué)劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)小結(jié)

通訊方法描述通訊是PCAM設(shè)計(jì)過程的重要階段；劃分產(chǎn)生的諸任務(wù)，一般不能完全獨(dú)立執(zhí)行，需要在任務(wù)間進(jìn)行數(shù)據(jù)交流；從而產(chǎn)生了通訊；功能分解確定了諸任務(wù)之間的數(shù)據(jù)流；諸任務(wù)是并發(fā)執(zhí)行的，通訊則限制了這種并發(fā)性；四種通訊模式局部/全局通訊結(jié)構(gòu)化/非結(jié)構(gòu)化通訊靜態(tài)/動態(tài)通訊同步/異步通訊局部通訊通訊限制在一個(gè)鄰域內(nèi)全局通訊通訊非局部的例如：AlltoAllMaster-Worker53721結(jié)構(gòu)化通訊每個(gè)任務(wù)的通訊模式是相同的；下面是否存在一個(gè)相同通訊模式？25無結(jié)構(gòu)化通訊unstructuredcommunicationnetworksmaybearbitrarygraphs.非結(jié)構(gòu)化通信網(wǎng)絡(luò)可能是任意的圖形。26靜態(tài)/動態(tài)staticcommunication,theidentityofcommunicationpartnersdoesnotchangeovertime;靜態(tài)通信，通信伙伴的身份不會隨著時(shí)間而改變;theidentityofcommunication

partnersindynamiccommunicationstructuresmaybedeterminedbydatacomputedatruntimeandmaybehighlyvariable.動態(tài)通信結(jié)構(gòu)中的通信伙伴的身份可能是由運(yùn)行時(shí)計(jì)算的數(shù)據(jù)確定的，并且可能是高度可變的。27同步/異步Insynchronouscommunication,producersandconsumersexecuteinacoordinatedfashion,withproducer/consumerpairscooperatingin

datatransferoperations;在同步通信中，生產(chǎn)者和消費(fèi)者以一種協(xié)調(diào)的方式執(zhí)行，在數(shù)據(jù)傳輸操作中合作生產(chǎn)/消費(fèi)者對;

incontrast,asynchronouscommunicationmayrequirethataconsumerobtaindatawithoutthecooperationoftheproducer相反，異步通信可能要求消費(fèi)者在沒有生產(chǎn)者合作的情況下獲取數(shù)據(jù)。通訊判據(jù)所有任務(wù)是否執(zhí)行大致相當(dāng)?shù)耐ㄓ?是否盡可能的局部通訊？通訊操作是否能并行執(zhí)行?同步任務(wù)的計(jì)算能否并行執(zhí)行？PCAM設(shè)計(jì)方法學(xué)劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)小結(jié)

方法描述組合是由抽象到具體的過程，是將組合的任務(wù)能在一類并行機(jī)上有效的執(zhí)行；合并小尺寸任務(wù)，減少任務(wù)數(shù)。如果任務(wù)數(shù)恰好等于處理器數(shù)，則也完成了映射過程；通過增加任務(wù)的粒度和重復(fù)計(jì)算，可以減少通訊成本；保持映射和擴(kuò)展的靈活性，降低軟件工程成本；31Examplesofagglomeration表面-容積效應(yīng)通訊量與任務(wù)子集的表面成正比，計(jì)算量與任務(wù)子集的體積成正比；增加重復(fù)計(jì)算有可能減少通訊量；重復(fù)計(jì)算重復(fù)計(jì)算減少通訊量，但增加了計(jì)算量，應(yīng)保持恰當(dāng)?shù)钠胶?；重?fù)計(jì)算的目標(biāo)應(yīng)減少算法的總運(yùn)算時(shí)間；重復(fù)計(jì)算示例：二叉樹上N個(gè)處理器求N個(gè)數(shù)的全和，要求每個(gè)處理器均保持全和。 二叉樹上求和，共需2logN步重復(fù)計(jì)算示例：二叉樹上N個(gè)處理器求N個(gè)數(shù)的全和，要求每個(gè)處理器均保持全和。

蝶式結(jié)構(gòu)求和，使用了重復(fù)計(jì)算，共需logN步組合判據(jù)增加粒度是否減少了通訊成本？重復(fù)計(jì)算是否已權(quán)衡了其得益？是否保持了靈活性和可擴(kuò)放性？組合的任務(wù)數(shù)是否與問題尺寸成比例?是否保持了類似的計(jì)算和通訊？有沒有減少并行執(zhí)行的機(jī)會？PCAM設(shè)計(jì)方法學(xué)劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)小結(jié)

方法描述每個(gè)任務(wù)要映射到具體的處理器，定位到運(yùn)行機(jī)器上；任務(wù)數(shù)大于處理器數(shù)時(shí)，存在負(fù)載平衡和任務(wù)調(diào)度問題；映射的目標(biāo)：減少算法的執(zhí)行時(shí)間并發(fā)的任務(wù)

不同的處理器任務(wù)之間存在高通訊的

同一處理器映射實(shí)際是一種權(quán)衡，屬于NP完全問題負(fù)載平衡算法靜態(tài)的：事先確定；概率的：隨機(jī)確定；動態(tài)的：執(zhí)行期間動態(tài)負(fù)載；基于域分解的：遞歸對剖局部算法概率方法循環(huán)映射任務(wù)調(diào)度算法任務(wù)放在集中的或分散的任務(wù)池中，使用任務(wù)調(diào)度算法將池中的任務(wù)分配給特定的處理器。下面是兩種常用調(diào)度模式：經(jīng)理/雇員模式非集中模式映射判據(jù)采用集中式負(fù)載平衡方案，是否存在通訊瓶頸？采用動態(tài)負(fù)載平衡方案，調(diào)度策略的成本如何？PCAM設(shè)計(jì)方法學(xué)劃分(Partitioning)通訊(Communication)組合(Agglomeration)映射(Mapping)小結(jié)

小結(jié)劃分域分解和功能分解通訊任務(wù)間的數(shù)據(jù)交換組合任務(wù)的合并使得算法更有效映射將任務(wù)分配到處理器，并保持負(fù)載平衡4444Foster’sMethod*inAction

4545HeatTransferProblem

JacobiMethod2DimensionalGridModelingasteelplate二維網(wǎng)格建模了一塊鋼板Asimulatedheatsourceisappliedtoonethe“top”boundary一個(gè)模擬熱源被應(yīng)用到一個(gè)“頂部”邊界上。Simulationisrunoveranumberoftime-steps模擬在許多時(shí)間步驟中運(yùn)行Foreachtimestep,newvaluesforeachelementofthegridarecalculateduntilthevaluesconverge.(JacobiMethod)對于每一次的步驟，計(jì)算網(wǎng)格中每個(gè)元素的新值，直到值收斂。(雅可比方法)Valuesforeachelementarebasedonthevaluesofitsneighborabove,below,left&right每個(gè)元素的值都基于其鄰居的值HeatSourceAppliede[i][j]e[i][j+1]e[i][j-1]e[i-1][j]e[i+1][j]4646HeatTransferProblem

SerialCSolution1of4#include<stdio.h>#include<math.h>#defineEPSILON0.00001#defineN100#definetime_steps100intmain(intargc,char*argv[]){inti,j;intstep;doubletime;doubleeps,enew;doubletime_max=3.0;doublealpha=0.06;doubledx=1.0/N;doubledy=1.0/time_steps;doubledt=time_max/time_steps;doubledxinv=1.0/dx;doubledyinv=1.0/dy;doubledtinv=1.0/dt;doubledivinv=1.0/(dtinv+2*alpha*(dxinv*dxinv+dyinv*dyinv));doublet[N][N];doubletold[N][N];doubleminval,maxval;longclock(),cputime;charfname[40];FILE*out;4747HeatTransferProblem

SerialCSolution2of4//initializeinteriorvaluesfor(i=1;i<(N-1);i++)for(j=1;j<(N-1);j++)told[i][j]=0.0;//setinitialboundaryconditionsfor(i=0;i<N;i++){told[i][0]=0.0;//lefttold[i][N-1]=0.0;//right}for(j=0;j<N;j++)told[N-1][j]=0.0;//bottom//foralltimestepsfor(step=1;step<=time_steps;step++){time=step*(time_max/time_steps);//resettopboundaryconditioneachtimestepfor(j=0;j<N;j++)told[0][j]=2.0*sin(time);//top

4848HeatTransferProblem

SerialCSolution3of4

do{eps=0.0;for(i=1;i<(N-1);i++)for(j=1;j<(N-1);j++)t[i][j]=((told[i][j+1]+told[i][j-1])*alpha*dyinv*dyinv+(told[i+1][j]+told[i-1][j])*alpha*dxinv*dxinv+(told[i][j]*dtinv))*divinv;for(i=1;i<(N-1);i++){for(j=1;j<(N-1);j++){enew=fabs(t[i][j]-told[i][j]);if(enew>eps){eps=enew;}}}for(i=0;i<N;i++)for(j=0;j<N;j++)told[i][j]=t[i][j];}while(eps>EPSILON);4949HeatTransferProblem

SerialCSolution4of4

//Dumprasterdatetoafileminval=0.0;maxval=0.0;for(i=0;i<N;i++){for(j=0;j<N;j++){if(t[i][j]<minval){minval=t[i][j];}if(t[i][j]>maxval){maxval=t[i][j];}}}

sprintf(fname,"Output\\heat%03d.raw",step);out=fopen(fname,"w+b");for(i=0;i<N;i++)for(j=0;j<N;j++)fprintf(out,"%c",(int)(((t[i][j]-minval)*255.0)/(maxval-minval)));fclose(out);printf("Timestep:%d\r",step);

}//foralltimestepscputime=clock();printf("%dtimestepsin%.2fseconds\n",step-1,cputime/1.0e+3);}5050Step1:PartitioningThePrimitivetaskwouldbeComputingeachelementintheGrid原始任務(wù)是計(jì)算網(wǎng)格中的每個(gè)元素Goals:OrderofmagnitudemorePrimitivetasksthanProcessors比處理器更原始的任務(wù)Minimizeredundantcomputationsanddata最小化冗余計(jì)算和數(shù)據(jù)Primitivetasksareapproximatelythesamesize原始任務(wù)的大小大致相同ThenumberofPrimitivetasksincreaseasproblemsizeincreases隨著問題大小的增加，原始任務(wù)的數(shù)量會增加5151Step2:CommunicationEachPrimitivetaskneedsaninputchannelto4neighbors每個(gè)原始任務(wù)需要一個(gè)輸入通道到4個(gè)鄰居EachPrimitivetaskneedsanoutputchannelto4neighbors每個(gè)原始任務(wù)都需要一個(gè)輸出通道到4個(gè)鄰居Goals:CommunicationisbalancedamongallTasks溝通在所有任務(wù)中都是平衡的EachTaskCommunicateswithaminimalnumberofneighbors每個(gè)任務(wù)都與少量的鄰居進(jìn)行通信TaskscanPerformCommunicationsconcurrently任務(wù)可以同時(shí)執(zhí)行通信TaskscanPerformComputationsconcurrently任務(wù)可以同時(shí)執(zhí)行計(jì)算5252Step3:Agglomeration5353Step4:MappingProcessor0Processor1ProcessornGhostcellsGhostcells54CaseStudy:AtmosphereModel55Outline1.PCAMdesignprinciple2.ParallelProcessingEvaluation

3.

ParallelProgrammingModel

4.Summary56ParallelProcessingEvaluation

Severalwaystoevaluatetheparallelprocessingperformance:評估并行處理性能的幾種方法:●Scale-up放大●Speedup加速●Efficiency效率●Overallsolutiontime整體解決時(shí)間●Price/performance價(jià)格/性能

57ParallelProcessingEvaluation.2Scale-up

Scale-upisenhancedthroughput,referstotheabilityofasystemntimeslargertoperformanntimeslargerjob,inthesametimeperiodastheoriginalsystem.Withaddedhardware,aformulaforscale-upholdsthetimeconstant,andmeasurestheincreasedsizeofthejobwhichcanbedone.放大是增強(qiáng)的吞吐量，指的是在與原始系統(tǒng)相同的時(shí)間段內(nèi)，n倍于更大的系統(tǒng)執(zhí)行n倍大的作業(yè)的能力。通過添加硬件，一個(gè)用于放大的公式保持時(shí)間常數(shù)，并且可以測量可以完成的工作的增加的大小。58ParallelProcessingEvaluation.3

SequentialSystem:HardwareTime100%TaskParallelSystem:HardwareHardwareTimeTime200%TaskFigure5Scale-up59ParallelProcessingEvaluation.4Scale-upmeasurementformula:

Scale-up=Transactionvolumeofmultiprocessors多處理器的事務(wù)量Transactionvolumeofuniprocessor單處理器的事務(wù)量60ParallelProcessingEvaluation.5Forexample,iftheuniprocessorsystemcanprocess100transactionsinagivenamountoftime,andtheparallelsystemcanprocess200transactionsinthisamountoftime,thenthevalueofscale-upwouldbeequalto200/100=2.Value2indicatestheidealoflinearscale-up:whentwiceasmuch,hardwarecanprocesstwicethedatavolumeinthesameamountoftime.

61ParallelProcessingEvaluation.6Speedup

Speedup,theimprovedresponsetime,definedasthetimeittakesaprogramtoexecuteinsequential(withoneprocessor)dividedbythetimeittakestoexecuteinparallel(withmanyprocessors).Itcanbeachievedbytwoways:breakingupalargetaskintomanysmallfragmentsandreducingwaittime.加速，提升的響應(yīng)時(shí)間，定義為程序按順序（使用一個(gè)處理器）執(zhí)行的時(shí)間除以并行執(zhí)行所需的時(shí)間（與許多處理器）之間的時(shí)間。它可以通過兩種方式實(shí)現(xiàn)：將大型任務(wù)分解成許多小碎片，并減少等待時(shí)間。62ParallelProcessingEvaluation.7

SequentialSystem:HardwareTime100%TaskParallelSystem:Hardware

HardwareTimeTime50%Task50%TaskFigure6Speedup63ParallelProcessingEvaluation.8Speedupmeasurementformula:

Elapsedtimeofauniprocessor單處理器的經(jīng)過時(shí)間Speedup=多處理器的經(jīng)過時(shí)間

Elapsedtimeofthemultiprocessors64ParallelProcessingEvaluation.9Forexample,iftheuniprocessortook40secondstoperformatask,andtwoparallelsystemstook20seconds,thenthevalueofspeedup=40/20=2.Value2indicatestheidealoflinearspeedup:whentwiceasmuch,hardwarecanperformthesametaskinhalfthetime.65ParallelProcessingEvaluation.10Figure.Linearandactualspeedup66ParallelProcessingEvaluation.11

Amdahl’sLawAmdahl'sLawisalawgoverningthespeedupofusingparallelprocessorsonaproblem,versususingonlyonesequentialprocessor.Amdahl’slawattemptstogiveamaximumboundforspeedupfromthenatureofthealgorithm:

Amdahl定律是一個(gè)規(guī)則，在一定的計(jì)算負(fù)載下，為達(dá)到實(shí)時(shí)性可利用增加處理器數(shù)來提高計(jì)算速度。Amdahl定律試圖從算法的性質(zhì)中給出加速的最大限制：Amdahl定律出發(fā)點(diǎn)：固定不變的計(jì)算負(fù)載；固定的計(jì)算負(fù)載分布在多個(gè)處理器上的，增加處理器加快執(zhí)行速度，從而達(dá)到加速的目的。68ParallelProcessingEvaluation.12

Amdahl’sLaw

S:purelysequentialpart純串行部分P:parallelpart并行部分S+P=1(forsimplicity簡化)

Maximumspeedup=

S+P

S+Pn=

16970ParallelProcessingEvaluation.13

Gustafson’sLaw

Ifthesizeofaproblemisscaledupasthenumberofprocessorsincreases,speedupveryclosetotheidealspeedupispossible.如果問題的大小隨著處理器數(shù)量的增加而增加，加速非常接近理想的加速是可能的。Thatis,aproblemsizeisvirtuallyneverindependentofthenumberofprocessors.也就是說，問題大小實(shí)際上從不與處理器數(shù)量無關(guān)。

71ParallelProcessingEvaluation.14

Gustafson’sLaw

Maximumspeedup

=S+(P*n)

S+P=n+(1-n)*SGustafson定律出發(fā)點(diǎn)：對于很多大型計(jì)算，精度要求很高，即在此類應(yīng)用中精度是個(gè)關(guān)鍵因素，而計(jì)算時(shí)間是固定不變的。此時(shí)為了提高精度，必須加大計(jì)算量，相應(yīng)地亦必須增多處理器數(shù)才能維持時(shí)間不變；除非學(xué)術(shù)研究，在實(shí)際應(yīng)用中沒有必要固定工作負(fù)載而計(jì)算程序運(yùn)行在不同數(shù)目的處理器上，增多處理器必須相應(yīng)地增大問題規(guī)模才有實(shí)際意義。73ParallelProcessingEvaluation.15

Examplespeedup:Amdahl&Gustafson74ParallelProcessingEvaluation.16Efficiency

Therelativeefficiencycanbeausefulmeasureastowhatpercentageofaprocessor’stimeisbeingspentinusefulcomputation.相對效率可能是一個(gè)有用的措施，即在有用的計(jì)算中花費(fèi)的處理器時(shí)間的百分比是多少。

Efficiency=Speedup*100Numberofprocessors75ParallelProcessingEvaluation.17

FigureOptimumefficiency&actualefficiency76Outline1.PCAMdesignprinciple2.ParallelProcessingEvaluation3.ParallelProgrammingModel4.Summary77ParallelProgrammingModelsSharedMemoryModel共享內(nèi)存模型DSMThreads/OpenMP(enabledforclusters)Javathreads(HKUJESSICA,IBMcJVM)MessagePassingModel消息傳遞模型PVMMPIHybridModel混合模型Mixingsharedanddistributedmemorymodel混合共享和分布式內(nèi)存模型UsingOpenMPandMPItogetherObjectandServiceOrientedModels面向?qū)ο蠛兔嫦蚍?wù)的模型Wideareadistributedcomputingtechnologies廣域分布式計(jì)算技術(shù)OO:CORBA,DCOM,etc.Services:WebServices-basedservicecomposition基于Web服務(wù)的服務(wù)組合78Code-GranularityCodeItemLargegrain(tasklevel)ProgramMediumgrain(controllevel)Function(thread)Finegrain(datalevel)Loop(Compiler)Veryfinegrain(multipleissue)WithhardwareTaski-lTask

iTaski+1func1(){}func2(){}func3(){}a(0)=..b(0)=..a(1)=..b(1)=..a(2)=..b(2)=..+xLoadPVM/MPIThreadsCompilersCPULevelsofParallelism79并行層次與代碼粒度80ResponsibleforParallelizationGrainSizeCodeItemParallelisedbyVeryFineInstructionProcessorFineLoop/InstructionblockCompilerMedium(Standardonepage)FunctionProgrammerLargeProgram/Separateheavy-weightprocessProgrammer81并行層次粒度（指令數(shù)）并行實(shí)施編程支持甚細(xì)粒度指令級并行幾十條，如多指令發(fā)射、內(nèi)存交叉存取硬件處理器細(xì)粒度數(shù)據(jù)級并行幾百條，如循環(huán)指令塊編譯器共享變量中粒度控制級并行幾千條，如過程、函數(shù)程序員（編譯器）共享變量、消息傳遞粗粒度任務(wù)級并行數(shù)萬條，如獨(dú)立的作業(yè)任務(wù)操作系統(tǒng)消息傳遞82ParallelisationParadigmsTask-Farming/Master-Worker農(nóng)場任務(wù)/主人-工人Single-ProgramMultiple-Data(SPMD)單程序多數(shù)據(jù)（SPMD）Pipelining流水線DivideandConquer分而治之Speculation預(yù)測ParametricComputationModel參數(shù)計(jì)算模型Nimrod-G-forcomputationalintensiveparametericapplications.用于計(jì)算密集型參數(shù)應(yīng)用。GridbusBroker–fordistributeddataintensiveparametericapplications.用于分布式數(shù)據(jù)密集型參數(shù)應(yīng)用程序。83MasterWorker/SlaveModelMasterdecomposestheproblemintosmalltasks,distributestoworkersandgatherspartialresultstoproducethefinalresult.主人將問題分解為小任務(wù)，分配給工作人員并收集部分結(jié)果以產(chǎn)生最終結(jié)果。Mapping/LoadBalancing映射/負(fù)載平衡Static靜態(tài)的Dynamic動態(tài)WhennumberoftasksarelargerthanthenumberofCPUs/theyareknowatruntime/CPUsareheterogeneous.當(dāng)任務(wù)數(shù)量大于CPU/他們在運(yùn)行時(shí)知道的數(shù)量/CPU是異構(gòu)的。Static84Single-ProgramMultiple-DataMostcommonlyusedmodel.最常用的模型。Eachprocessexecutesthesamepieceofcode,butondifferentpartsofthedata.—splittingthedataamongtheavailableprocessors.每個(gè)進(jìn)程執(zhí)行相同的代碼片段，但是在數(shù)據(jù)的不同部分上執(zhí)行-在可用處理器之間分割數(shù)據(jù)。Differentnames:geometric/domaindecomposition,dataparallelism.幾何/域分解，數(shù)據(jù)并行。85DataPipeliningSuitableforfinegrainedparallelism.適用于細(xì)粒度平行度。Alsosuitableforapplicationinvolvingmultiplestagesofexecution,butneedtooperateonlargenumberofdatasets.也適用于涉及多個(gè)執(zhí)行階段的應(yīng)用，但需要對大量的數(shù)據(jù)集進(jìn)行操作。86DivideandConquerAproblemisdividedintotwoormoresubproblems,ande