第三章并行算法2016

并行算法概述

著名計(jì)算機(jī)科學(xué)家沃思(NikiklausWirth)：

算法

+數(shù)據(jù)結(jié)構(gòu)=程序(1)數(shù)據(jù)結(jié)構(gòu)(datastructure)對(duì)數(shù)據(jù)的描述。在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類(lèi)型和數(shù)據(jù)的組織形式(2)算法(algorithm)對(duì)操作的描述。即要求計(jì)算機(jī)進(jìn)行操作的步驟Content3并行計(jì)算模型（ParallelComputingModel）設(shè)計(jì)并行算法基本方法VonNeumannModel4指令處理（InstructionProcessing）5譯指Decodeinstruction計(jì)算地址Evaluateaddress取操作數(shù)Fetchoperandsfrommemory執(zhí)行操作Executeoperation存儲(chǔ)結(jié)果Storeresult從內(nèi)存取指令并行計(jì)算模型

ParallelComputingModel6計(jì)算模型橋接軟件和硬件為算法設(shè)計(jì)提供抽象體系結(jié)構(gòu)Ex)PRAM,BSP,LogP并行程序設(shè)計(jì)模型

ParallelProgrammingModel7程序員使用什么來(lái)編碼?確定通信（communication）和同步（synchronization）暴露給程序員的通信原語(yǔ)（Communicationprimitives）實(shí)現(xiàn)編程模型

Ex)Uniprocessor,Multiprogramming,Dataparallel,message-passing,shared-address-spaceAspectsofParallelProcessing8AlgorithmdeveloperApplicationdeveloperInterconnectionNetworkMemoryPPPPMemoryPPPPMemoryPPPPMemoryPPPPMultiprocessorsMultiprocessorsMultiprocessorsMultiprocessorsParallelcomputingmodelParallelprogrammingmodelSystemprogrammerArchitecturedesigner3421MiddlewareParallelComputingModels–并行隨機(jī)存取機(jī)（ParallelRandonAccessMachine）9特性：ProcessorsPi

(0ip-1)每一處理器可配有局部?jī)?nèi)存一全局共享內(nèi)存

所有處理器都可以訪問(wèn)PRAM示意圖10P1P2P3PpSharedMemoryCLKPprocessorsconnectedtoasinglesharedmemoryEachprocessorhasauniqueindex.SingleprogramexecutedinMIMDmode并行隨機(jī)存取機(jī)ParallelRandonAccessMachine11操作類(lèi)型：

同步處理器執(zhí)行時(shí)會(huì)加鎖

F每一步，處理器或工作或待機(jī)

F適用于SIMD和MIMD體系結(jié)構(gòu)異步處理器有局部時(shí)鐘，用于同步處理器

F適用于MIMD體系結(jié)構(gòu)ProblemswithPRAM12是對(duì)現(xiàn)實(shí)世界并行系統(tǒng)的一種簡(jiǎn)化描述未考慮多種開(kāi)銷(xiāo)延遲，帶寬，遠(yuǎn)程內(nèi)存訪問(wèn)，內(nèi)存訪問(wèn)沖突，同步開(kāi)銷(xiāo),etc在PRAM上理論分析性能分析好的算法，實(shí)際性能可能差并行隨機(jī)存取機(jī)ParallelRandonAccessMachine13Read/Write沖突

EREW:Exclusive-Read,Exclusive-Write對(duì)一變量無(wú)并發(fā)操作

(readorwrite)CREW:Concurrent–Read,Exclusive–Write允許并發(fā)讀同一變量互斥寫(xiě)ERCW:ExclusiveRead–ConcurrentWriteCRCW:Concurrent–Read,Concurrent–Write并行隨機(jī)存取機(jī)ParallelRandonAccessMachine14基本Input/Output操作全局內(nèi)存globalread(X,x)globalwrite(Y,y)局部?jī)?nèi)存read(X,x)write(Y,y)例子:在PRAM模型上求和15

對(duì)有n=2k個(gè)數(shù)的數(shù)組A求和 APRAMmachinewithnprocessor

計(jì)算S=A(1)+A(2)+….+A(n)構(gòu)建二叉樹(shù)，計(jì)算和例子:在PRAM模型上求和16

B(1)=A(1)B(2)=A(2)B(1)=A(1)B(2)=A(2)B(1)=A(1)B(2)=A(2)B(1)=A(1)B(2)=A(2)P1P2P3P4P5P6P7P8B(1)B(2)B(3)B(4)P1P2P3P4B(1)B(2)P1P2B(1)S=B(1)P1P1Level>1,PicomputeB(i)=B(2i-1)+B(2i)Level1,PiB(i)=A(i)例子:在PRAM模型上求和17AlgorithmprocessorPi(i=0,1,…n-1)Input A:arrayofn=2kelementsinglobalmemoryOutput S:S=A(1)+A(2)+…..A(n)LocalvariablesPi n: i:processorPiidentityBegin 1.globalread(A(i),a) 2.globalwrite(a,B(i)) 3.forh=1tologn

do if(i≤n/2h)thenbegin globalread(B(2i-1),x) globalread(B(2i),y) z=x+y globalwrite(z,B(i)) end 4.ifi=1thenglobalwrite(z,S)End其它分布式模型18DistributedMemoryModel無(wú)全局內(nèi)存每一處理器有局部?jī)?nèi)存PostalModel當(dāng)訪問(wèn)非局部?jī)?nèi)存時(shí)，處理器發(fā)送請(qǐng)求處理器不會(huì)停止，它會(huì)繼續(xù)工作直到數(shù)據(jù)到達(dá)NetworkModels19關(guān)注通信網(wǎng)絡(luò)拓?fù)涞挠绊懺缙诓⑿杏?jì)算關(guān)注點(diǎn)分布式內(nèi)存模型遠(yuǎn)程內(nèi)存訪問(wèn)的代價(jià)與拓?fù)浜驮L問(wèn)模式相關(guān)提供有效的

數(shù)據(jù)映射通信路由LogP20受并行計(jì)算機(jī)設(shè)計(jì)的影響分布式內(nèi)存多處理器模型處理器通信通過(guò)點(diǎn)對(duì)點(diǎn)的消息通信實(shí)現(xiàn)目標(biāo)是分析并行計(jì)算機(jī)的性能瓶頸制定通信網(wǎng)絡(luò)的性能特點(diǎn)

為數(shù)據(jù)放置提供幫助顯示了平衡通信的重要性模型參數(shù)ModelParameters21延遲Latency(L)從源到目的端發(fā)送消息的延遲Hop（跳）

count和Hopdelay通信開(kāi)銷(xiāo)CommunicationOverhead(o)處理器在發(fā)送或接收一條消息時(shí)的時(shí)間開(kāi)銷(xiāo)通信帶寬Communicationbandwidth(g)消息之間的最小時(shí)間間隔處理器數(shù)量Processorcount(P)處理器個(gè)數(shù)LogPModel22發(fā)送方sender接收方receiveroLgotBulkSynchronousParallel23BulkSynchronousParallel(BSP)P個(gè)配有局部?jī)?nèi)存的處理器路由器周期性全局同步考慮因素帶寬限制延遲同步開(kāi)銷(xiāo)未考慮因素

通信開(kāi)銷(xiāo)處理器拓?fù)銪SPComputer24分布式內(nèi)存體系結(jié)構(gòu)3種部件節(jié)點(diǎn)處理器局部?jī)?nèi)存路由器

(CommunicationNetwork)點(diǎn)對(duì)點(diǎn)（Point-to-point）,消息傳遞（

messagepassing）或者共享變量(sharedvariable)路障全部或部分IllustrationofBSP25CommunicationNetwork(g)PMPMPMNode(w)NodeNodeBarrier(l)w

每一超步（superstep）最大計(jì)算時(shí)間計(jì)算最多消耗w個(gè)時(shí)鐘周期.g

當(dāng)所有處理器都參與通信時(shí)，發(fā)送一消息單元所需要的時(shí)鐘周期，即網(wǎng)絡(luò)帶寬h：每一超步最大接收和發(fā)送消息的數(shù)量通信操作需要gh

時(shí)鐘周期l：路障（Barrier）同步需要l

時(shí)鐘周期BSP程序26每一BSP計(jì)算由S個(gè)超步構(gòu)成一超步包括一系列步驟和一個(gè)路障Superstep任何遠(yuǎn)程內(nèi)存訪問(wèn)需要路障–松散同步BSP程序27Superstep1Superstep2BarrierP1P2P3P4ComputationCommunicationExample:PregelPregelisaframeworkdevelopedbyGoogle:SIGMOD2010高擴(kuò)展容錯(cuò)靈活實(shí)現(xiàn)圖算法BulkSynchronousParallelModel29DataDataDataDataDataDataDataDataDataDataDataDataDataDataCPU1CPU2CPU3CPU1CPU2CPU3DataDataDataDataDataDataDataCPU1CPU2CPU3IterationsBarrierBarrierDataDataDataDataDataDataDataBarrier圖30GraphEntitiesandSupersteps31計(jì)算由頂點(diǎn)、邊和一系列迭代（即超步）構(gòu)成每一頂點(diǎn)賦有值。每一邊包含與源點(diǎn)、邊值和目的頂點(diǎn)每一超步：用戶定義的函數(shù)F

處理每一頂點(diǎn)VF

在超步S–1讀發(fā)送給V的消息，發(fā)送消息給其它頂點(diǎn)。這些消息將在S+1超步收到F

更改頂點(diǎn)V

和出邊的狀態(tài)F可以改變圖的拓?fù)渌惴ńK止AlgorithmTermination32根據(jù)各頂點(diǎn)投票決定算法是否終止superstep0，每一頂點(diǎn)活躍所有活躍頂點(diǎn)參與任意給定超步中的計(jì)算當(dāng)頂點(diǎn)投票終止時(shí)，頂點(diǎn)進(jìn)入非活躍狀態(tài)如果頂點(diǎn)收到外部消息，頂點(diǎn)可以進(jìn)入活躍狀態(tài)當(dāng)所有節(jié)點(diǎn)都同時(shí)變?yōu)榉腔钴S狀態(tài)時(shí)，程序終止ActiveInactiveVotetoHaltMessageReceivedVertexStateMachineThePregelAPIinC++33APregelprogramiswrittenbysubclassingthevertexclass:template<typenameVertexValue,typenameEdgeValue,typenameMessageValue>classVertex{public:virtual

voidCompute(MessageIterator*msgs)=0;conststring&vertex_id()const;int64superstep()const;constVertexValue&GetValue();VertexValue*MutableValue();OutEdgeIteratorGetOutEdgeIterator();voidSendMessageTo(conststring&dest_vertex,constMessageValue&message);voidVoteToHalt();};OverridethecomputefunctiontodefinethecomputationateachsuperstepTopassmessagestootherverticesTodefinethetypesforvertices,edgesandmessagesTogetthevalueofthecurrentvertexTomodifythevalueofthevertexPregelCodeforFindingtheMaxValue34ClassMaxFindVertex :publicVertex<double,void,double>{ public: virtualvoidCompute(MessageIterator*msgs){ intcurrMax=GetValue(); SendMessageToAllNeighbors(currMax); for(;!msgs->Done();msgs->Next()){ if(msgs->Value()>currMax) currMax=msgs->Value(); } if(currMax>GetValue()) *MutableValue()=currMax; elseVoteToHalt(); }};FindingtheMaxValueinaGraph

3536213621626666266666666節(jié)點(diǎn)內(nèi)數(shù)值是節(jié)點(diǎn)值藍(lán)色箭頭是消息藍(lán)色節(jié)點(diǎn)投票終止6模型總結(jié)36Nosinglemodelisacceptable!Betweenmodels,subsetofcharacteristicsarefocusedinmajorityofmodels計(jì)算并行（ComputationalParallelism）通信延遲（CommunicationLatency）通信開(kāi)銷(xiāo)（CommunicationOverhead）通信帶寬（CommunicationBandwidth）執(zhí)行同步（ExecutionSynchronization）內(nèi)存層次（MemoryHierarchy）網(wǎng)絡(luò)拓?fù)洌∟etworkTopology）計(jì)算并行（ComputationalParallelism）37處理器數(shù)量靜態(tài)versus動(dòng)態(tài)并行處理器數(shù)目固定？容錯(cuò)網(wǎng)絡(luò)允許節(jié)點(diǎn)失效許多并行系統(tǒng)通過(guò)增加節(jié)點(diǎn)數(shù)目允許增量更新延遲Latency38固定長(zhǎng)度的消息vs.變長(zhǎng)消息?網(wǎng)絡(luò)拓?fù)?通信開(kāi)銷(xiāo)?基于競(jìng)爭(zhēng)的延遲?內(nèi)存層次?帶寬39有限資源WithlowlatencyTendencyforbandwidthabusebyfloodingnetwork同步Synchronization40通過(guò)消息傳遞實(shí)現(xiàn)同步Synchronizationasacommunicationcost統(tǒng)一模型?41困難并行機(jī)復(fù)雜始終在演變之中來(lái)自不同領(lǐng)域的不同用戶從不同用戶的需求中抽象出一組共同特性同樣需要在描述和指定上取得平衡Content42并行計(jì)算模型ParallelComputingModel并行算法的基本方法Concepts分解（Decomposition）任務(wù)（Task）映射（Mapping）算法模型（AlgorithmModel）分解、任務(wù)及依賴(lài)圖43設(shè)計(jì)并行算法的第一步是將問(wèn)題分解成可并發(fā)執(zhí)行的任務(wù)分解可用任務(wù)依賴(lài)圖(taskdependencygraph)

表示。圖中節(jié)點(diǎn)代表任務(wù)，邊代表任務(wù)依賴(lài)Example:MultiplyingaDenseMatrixwithaVector44計(jì)算輸出向量y的每一元素可獨(dú)立進(jìn)行。因此，矩陣與向量之積可分解為n個(gè)任務(wù)Example:DatabaseQueryProcessing在如下數(shù)據(jù)庫(kù)上執(zhí)行查詢(xún):MODEL=``CIVIC''ANDYEAR=2001AND (COLOR=``GREEN''ORCOLOR=``WHITE)

ID#ModelYearColorDealerPrice4523Civic2002BlueMN$18,0003476Corolla1999WhiteIL$15,0007623Camry2001GreenNY$21,0009834Prius2001GreenCA$18,0006734Civic2001WhiteOR$17,0005342Altima2001GreenFL$19,0003845Maxima2001BlueNY$22,0008354Accord2000GreenVT$18,0004395Civic2001RedCA$17,0007352Civic2002RedWA$18,00045Example:DatabaseQueryProcessing執(zhí)行查詢(xún)可分成任務(wù)。每一任務(wù)可看作產(chǎn)生滿足某一條件的中間結(jié)果46邊表示一個(gè)任務(wù)的輸出是另一個(gè)任務(wù)的輸入Example:DatabaseQueryProcessing同一問(wèn)題可采用其它方式分解。不同的分解可能存在重大的性能差異47任務(wù)粒度分解的任務(wù)數(shù)量越多，粒度越小。否則粒度越大48并行度DegreeofConcurrency49能并行執(zhí)行的任務(wù)數(shù)稱(chēng)為一分解的degreeofconcurrency

maximumdegreeofconcurrency

averagedegreeofconcurrency

當(dāng)任務(wù)粒度小時(shí)，并行度大。任務(wù)交互圖TaskInteractionGraphs50任務(wù)之間通常需要交換數(shù)據(jù)

表達(dá)任務(wù)之間交換關(guān)系的圖稱(chēng)為taskinteractiongraph.taskinteractiongraphs

表達(dá)數(shù)據(jù)依賴(lài)；taskdependencygraphs表達(dá)controldependencies.TaskInteractionGraphs:AnExample

稀疏矩陣A乘以向量

b.51計(jì)算結(jié)果向量的每一元素可視之為獨(dú)立任務(wù)

由于內(nèi)存優(yōu)化，可以將b

根據(jù)任務(wù)劃分，可以發(fā)現(xiàn)任務(wù)交互圖和矩陣A的圖一樣進(jìn)程和映射（ProcessesandMapping）

52任務(wù)的數(shù)量超過(guò)處理單元的數(shù)量，因此必須將任務(wù)映射到進(jìn)程恰當(dāng)?shù)娜蝿?wù)映射對(duì)并行算法的性能非常重要

映射由任務(wù)依賴(lài)圖和任務(wù)交互圖決定

任務(wù)依賴(lài)圖確保任務(wù)在任何時(shí)間點(diǎn)均勻分布到所有進(jìn)程

(minimumidlingandoptimalloadbalance).任務(wù)交互圖用于確保進(jìn)程與其它進(jìn)程之間的交互最少

(minimumcommunication).

ProcessesandMapping:Example

將數(shù)據(jù)庫(kù)查詢(xún)?nèi)蝿?wù)映射到進(jìn)程.根據(jù)同一層沒(méi)有依賴(lài)關(guān)系，同一層任務(wù)可分配給不同進(jìn)程53分解技術(shù)DecompositionTechniques54?遞歸分解（recursivedecomposition）

?

數(shù)據(jù)分解（datadecomposition）

?

探索分解（exploratorydecomposition）

?

猜測(cè)分解（speculativedecomposition）

遞歸分解（RecursiveDecomposition）

55適合可用分治法解決的問(wèn)題.給定問(wèn)題首先分解為一系列子問(wèn)題

這些子問(wèn)題進(jìn)一步遞歸分解，直到所需要的任務(wù)粒度RecursiveDecomposition:Example經(jīng)典的例子是快速排序Inthisexample,oncethelisthasbeenpartitionedaroundthepivot,eachsub-listcanbeprocessedconcurrently.Thiscanberepeatedrecursively.56RecursiveDecomposition:Example57

考慮在序列里循環(huán)找最小值:

1.procedure

SERIAL_MIN(A,n) 2.begin 3.min=A[0]; 4.for

i

:=1to

n?1do 5. if

(A[i]<min)min:=A[i]; 6.endfor; 7.return

min; 8.end

SERIAL_MINRecursiveDecomposition:Example58

Wecanrewritetheloopasfollows:

1.procedureRECURSIVE_MIN(A,n)

2.begin

3.if(n=

1)then

4. min:=A[0];

5.else

6. lmin:=RECURSIVE_MIN(A,n/2);

7. rmin:=RECURSIVE_MIN(&(A[n/2]),n-n/2

);

8. if(lmin<rmin)then

9. min:=lmin;

10. else

11. min:=rmin;

12. endelse;

13.endelse;

14.return

min;

15.endRECURSIVE_MIN

RecursiveDecomposition:Example

以上代碼可用如下求最小數(shù)例子說(shuō)明.求{4,9,1,7,8,11,2,12}的最小數(shù).任務(wù)依賴(lài)圖如下:59數(shù)據(jù)分解（DataDecomposition）60劃分?jǐn)?shù)據(jù)，將數(shù)據(jù)分配給不同任務(wù)

輸入數(shù)據(jù)劃分中間數(shù)據(jù)劃分輸出劃分輸出數(shù)據(jù)的每一元素可以獨(dú)立計(jì)算出輸出分解例子

nxn

矩陣A和B相乘得到矩陣C.輸出矩陣C的計(jì)算

可以分為如下四個(gè)任務(wù):61Task1:

Task2:Task3:Task4:

輸出分解例子以前面的矩陣相乘例子為例，還可以派生如下兩種劃分:DecompositionIDecompositionIITask1:C1,1

=

A1,1B1,1

Task2:C1,1

=

C1,1

+

A1,2B2,1

Task3:C1,2

=

A1,1B1,2

Task4:C1,2

=

C1,2

+

A1,2B2,2

Task5:C2,1

=

A2,1B1,1

Task6:C2,1

=

C2,1

+

A2,2B2,1

Task7:C2,2

=

A2,1B1,2

Task8:C2,2

=

C2,2

+

A2,2B2,2

Task1:C1,1

=

A1,1B1,1

Task2:C1,1

=

C1,1

+

A1,2B2,1

Task3:C1,2

=

A1,2B2,2

Task4:C1,2

=

C1,2

+

A1,1B1,2

Task5:C2,1

=

A2,2B2,1

Task6:C2,1

=

C2,1

+

A2,1B1,1

Task7:C2,2

=

A2,1B1,2

Task8:C2,2

=

C2,2

+

A2,2B2,2

62InputDataPartitioning63如果輸出事先未知，這時(shí)可以考慮輸入劃分每一任務(wù)處理一部分輸入數(shù)據(jù)，形成局部結(jié)果。合并局部結(jié)果形成最終結(jié)果InputDataPartitioning:Example

統(tǒng)計(jì)事務(wù)數(shù)量的例子可采用輸入數(shù)據(jù)劃分。64劃分輸入和輸出數(shù)據(jù)

也可以將輸入劃分和輸出劃分相結(jié)合以便得到更高的并行度.對(duì)于統(tǒng)計(jì)事務(wù)的例子，事務(wù)集(input)和事務(wù)統(tǒng)計(jì)數(shù)量

(output)可同時(shí)劃分如下:65中間數(shù)據(jù)劃分（IntermediateDataPartitioning）66計(jì)算通?？梢暈橐幌盗袕妮斎氲捷敵龅淖儞Q.因此，可考慮將中間結(jié)果進(jìn)行分解IntermediateDataPartitioning:Example

考慮密集矩陣相乘：67IntermediateDataPartitioning:Example

中間結(jié)果產(chǎn)生8+4tasks:StageI68StageIITask01:D1,1,1=A1,1B1,1Task02:D2,1,1=A1,2B2,1Task03:D1,1,2=A1,1B1,2Task04:D2,1,2=A1,2B2,2Task05:D1,2,1=A2,1B1,1Task06:D2,2,1=A2,2B2,1Task07:D1,2,2=A2,1B1,2Task08:D2,2,2=A2,2B2,2Task09:C1,1=D1,1,1+D2,1,1Task10:C1,2

=D1,1,2+D2,1,2Task11:C2,1=D1,2,1+D2,2,1Task12:C2,,2=D1,2,2+D2,2,2IntermediateDataPartitioning:Example

Thetaskdependencygraphforthedecomposition(showninpreviousfoil)into12tasksisasfollows:69探索分解（ExploratoryDecomposition）

70在許多場(chǎng)合，隨著執(zhí)行的逐步推進(jìn)而進(jìn)行劃分.這些應(yīng)用通常涉及搜索解答的狀態(tài)空間適合應(yīng)用包括：組合優(yōu)化，定理證明，游戲，

etc.ExploratoryDecomposition:Example

15puzzle(atilepuzzle).

71ExploratoryDecomposition:Example產(chǎn)生當(dāng)前狀態(tài)的后繼狀態(tài)，將搜索每一狀態(tài)視為一獨(dú)立任務(wù)72SpeculativeDecomposition73在某些應(yīng)用，任務(wù)之間依賴(lài)事先未知

兩種方法:保守方法（conservativeapproaches）：當(dāng)確認(rèn)沒(méi)有依賴(lài)時(shí)，可以識(shí)別獨(dú)立任務(wù),樂(lè)觀方法（optimisticapproaches）即使可能是錯(cuò)誤的，仍然調(diào)度任務(wù)

保守方法可能產(chǎn)生較少的并發(fā)；樂(lè)觀方法可能需要回滾SpeculativeDecomposition:Example

模擬網(wǎng)絡(luò)的例子（例如生產(chǎn)線和計(jì)算機(jī)網(wǎng)絡(luò)）.任務(wù)是模擬不同輸入和節(jié)點(diǎn)參數(shù)（如延遲）下網(wǎng)絡(luò)的行為74混合分解（HybridDecompositions）

75在quicksort,遞歸分解限制了并發(fā)。這時(shí)可用數(shù)據(jù)分解和遞歸分解

對(duì)于找最小數(shù)，可用數(shù)據(jù)分解和遞歸分解任務(wù)特性

76任務(wù)特征影響并行算法的選擇及其性能

任務(wù)生成

任務(wù)粒度

與任務(wù)相關(guān)的數(shù)據(jù)規(guī)模TaskGeneration77靜態(tài)任務(wù)生成

例如：矩陣運(yùn)算，圖算法，圖像處理應(yīng)用以及其它結(jié)構(gòu)化問(wèn)題.任務(wù)分解通常用數(shù)據(jù)分解和遞歸分解.動(dòng)態(tài)任務(wù)生成

一個(gè)例子是15謎–每一15謎棋局由前一棋局產(chǎn)生.應(yīng)用通常用探索和猜測(cè)法分解.TaskSizes78任務(wù)粒度可以是統(tǒng)一，也可以是非一致

例如：組合優(yōu)化問(wèn)題里很難估計(jì)狀態(tài)空間的大小SizeofDataAssociatedwithTasks79Thesizeofdataassociatedwithataskmaybesmallorlargewhenviewedinthecontextofthesizeofthetask.Asmallcontextofataskimpliesthatanalgorithmcaneasilycommunicatethistasktootherprocessesdynamically(e.g.,the15puzzle).Alargecontexttiesthetasktoaprocess,oralternately,analgorithmmayattempttoreconstructthecontextatanotherprocessesasopposedtocommunicatingthecontextofthetask.CharacteristicsofTaskInteractions80Tasksmaycommunicatewitheachotherinvariousways.Theassociateddichotomyis:Staticinteractions:Thetasksandtheirinteractionsareknowna-priori.Thesearerelativelysimplertocodeintoprograms.Dynamicinteractions:Thetimingorinteractingtaskscannotbedetermineda-priori.Theseinteractionsarehardertocode,especially,asweshallsee,usingmessagepassingAPIs.CharacteristicsofTaskInteractions81規(guī)則交互（Regularinteractions）:交互有明確的模式.模式可以用于有效的實(shí)現(xiàn).不規(guī)則交互（Irregularinteractions）:交互缺乏模式.CharacteristicsofTaskInteractions:Example82

規(guī)則靜態(tài)交互例子如圖像抖動(dòng):CharacteristicsofTaskInteractions:Example83

稀疏矩陣相乘是靜態(tài)不規(guī)則交互例子CharacteristicsofTaskInteractions84交互可以是只讀或讀寫(xiě).只讀任務(wù)只需從相關(guān)任務(wù)中讀數(shù)據(jù).讀寫(xiě)任務(wù)從相關(guān)任務(wù)中讀和寫(xiě)數(shù)據(jù).Mapping85負(fù)載平衡映射

StaticandDynamicMapping減小交互開(kāi)銷(xiāo)的映射

MaximizingDataLocalityMinimizingContentionandHot-SpotsOverlappingCommunicationandComputationsReplicationvs.CommunicationGroupCommunicationsvs.Point-to-PointCommunication并行算法設(shè)計(jì)模型

Data-Parallel,Work-Pool,TaskGraph,Master-Slave,Pipeline,andHybridModelsMappingTechniques86映射必須減小開(kāi)銷(xiāo).主要開(kāi)銷(xiāo)包括：communication

和

idling.Minimizingtheseoverheadsoftenrepresentscontradictingobjectives.例如：Assigning

allworktooneprocessortriviallyminimizescommunicationattheexpenseofsignificantidling.MappingTechniquesforMinimumIdling87

映射需同時(shí)減小idling和負(fù)載不均衡.均衡負(fù)載不一定減小

idling.MappingTechniquesforMinimumIdling88

映射技術(shù)可以是靜態(tài)或動(dòng)態(tài).StaticMapping任務(wù)事先映射到進(jìn)程Forthistowork,wemusthaveagoodestimateofthesizeofeachtask.Eveninthesecases,theproblemmaybeNPcomplete.DynamicMapping運(yùn)行期間，任務(wù)映射到進(jìn)程Thismaybebecausethetasksaregeneratedatruntime,orthattheirsizesarenotknown.

SchemesforStaticMapping89MappingsbasedondatapartitioningMappingsbasedontaskgraphpartitioningHybridmappingsMappingsBasedonDataPartitioning901-Dblockdistributionschemes.BlockArrayDistributionSchemes

Blockdistributionschemescanbegeneralizedtohigherdimensionsaswell.91BlockArrayDistributionSchemes:Examples92對(duì)于矩陣A

和B相乘，可用塊分解法劃分輸出矩陣C.對(duì)于負(fù)載平衡，每一任務(wù)處理同樣數(shù)量的C中元素

(NotethateachelementofCcorrespondstoasingledotproduct.)CyclicandBlockCyclicDistributions93Iftheamountofcomputationassociatedwithdataitemsvaries,ablockdecompositionmayleadtosignificantloadimbalances.AsimpleexampleofthisisinLUdecomposition(orGaussianElimination)ofdensematrices.LUFactorizationofaDenseMatrix1:2:3:4:5:6:7:8:9:10:11:12:13:14:94

AdecompositionofLUfactorizationinto14tasks-noticethesignificantloadimbalance.BlockCyclicDistributions95Variationoftheblockdistributionschemethatcanbeusedtoalleviatetheload-imbalanceandidlingproblems.Partitionanarrayintomanymoreblocksthanthenumberofavailableprocesses.Blocksareassignedtoprocessesinaround-robinmannersothateachprocessgetsseveralnon-adjacentblocks.GraphPartitioningbasedDataDecomposition96Incaseofsparsematrices,blockdecompositionsaremorecomplex.Considertheproblemofmultiplyingasparsematrixwithavector.Thegraphofthematrixisausefulindicatorofthework(numberofnodes)andcommunication(thedegreeofeachnode).Inthiscase,wewouldliketopartitionthegraphsoastoassignequalnumberofnodestoeachprocess,whileminimizingedgecountofthegraphpartition.PartitioningtheGraphofLakeSuperior97RandomPartitioningPartitioningforminimumedge-cut.MappingsBasedonTaskPartitioning98Partitioningagiventask-dependencygraphacrossprocesses.Determininganoptimalmappingforageneraltask-dependencygraphisanNP-completeproblem.TaskPartitioning:MappingaBinaryTreeDependencyGraph99

Exampleillustratesthedependencygraphofoneviewofquick-sortandhowitcanbeassignedtoprocessesinacube.HierarchicalMappings100Sometimesasinglemappingtechniqueisinadequate.Forexample,thetaskmappingofthebinarytree(quicksort)cannotusealargenumberofprocessors.Forthisreason,taskmappingcanbeusedatthetoplevelanddatapartitioningwithineachlevel.101

Anexampleoftaskpartitioningattoplevelwithdatapartitioningatthelowerlevel.SchemesforDynamicMapping102Dynamicmappingissometimesalsoreferredtoasdynamicloadbalancing,sinceloadbalancingistheprimarymotivationfordynamicmapping.Dynamicmappingschemescanbecentralizedordistributed.CentralizedDynamicMapping103Proc