第三章并行算法2016

并行算法概述

著名計算機科學家沃思(NikiklausWirth)：

算法

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

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

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

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

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

所有處理器都可以訪問PRAM示意圖10P1P2P3PpSharedMemoryCLKPprocessorsconnectedtoasinglesharedmemoryEachprocessorhasauniqueindex.SingleprogramexecutedinMIMDmode并行隨機存取機ParallelRandonAccessMachine11操作類型：

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

F每一步，處理器或工作或待機

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

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

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

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

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

計算S=A(1)+A(2)+….+A(n)構(gòu)建二叉樹，計算和例子:在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無全局內(nèi)存每一處理器有局部內(nèi)存PostalModel當訪問非局部內(nèi)存時，處理器發(fā)送請求處理器不會停止，它會繼續(xù)工作直到數(shù)據(jù)到達NetworkModels19關(guān)注通信網(wǎng)絡拓撲的影響早期并行計算關(guān)注點分布式內(nèi)存模型遠程內(nèi)存訪問的代價與拓撲和訪問模式相關(guān)提供有效的

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

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

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

通信開銷處理器拓撲BSPComputer24分布式內(nèi)存體系結(jié)構(gòu)3種部件節(jié)點處理器局部內(nèi)存路由器

(CommunicationNetwork)點對點（Point-to-point）,消息傳遞（

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

每一超步（superstep）最大計算時間計算最多消耗w個時鐘周期.g

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

時鐘周期l：路障（Barrier）同步需要l

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

處理每一頂點VF

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

更改頂點V

和出邊的狀態(tài)F可以改變圖的拓撲算法終止AlgorithmTermination32根據(jù)各頂點投票決定算法是否終止superstep0，每一頂點活躍所有活躍頂點參與任意給定超步中的計算當頂點投票終止時，頂點進入非活躍狀態(tài)如果頂點收到外部消息，頂點可以進入活躍狀態(tài)當所有節(jié)點都同時變?yōu)榉腔钴S狀態(tài)時，程序終止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é)點內(nèi)數(shù)值是節(jié)點值藍色箭頭是消息藍色節(jié)點投票終止6模型總結(jié)36Nosinglemodelisacceptable!Betweenmodels,subsetofcharacteristicsarefocusedinmajorityofmodels計算并行（ComputationalParallelism）通信延遲（CommunicationLatency）通信開銷（CommunicationOverhead）通信帶寬（CommunicationBandwidth）執(zhí)行同步（ExecutionSynchronization）內(nèi)存層次（MemoryHierarchy）網(wǎng)絡拓撲（NetworkTopology）計算并行（ComputationalParallelism）37處理器數(shù)量靜態(tài)versus動態(tài)并行處理器數(shù)目固定？容錯網(wǎng)絡允許節(jié)點失效許多并行系統(tǒng)通過增加節(jié)點數(shù)目允許增量更新延遲Latency38固定長度的消息vs.變長消息?網(wǎng)絡拓撲?通信開銷?基于競爭的延遲?內(nèi)存層次?帶寬39有限資源WithlowlatencyTendencyforbandwidthabusebyfloodingnetwork同步Synchronization40通過消息傳遞實現(xiàn)同步Synchronizationasacommunicationcost統(tǒng)一模型?41困難并行機復雜始終在演變之中來自不同領(lǐng)域的不同用戶從不同用戶的需求中抽象出一組共同特性同樣需要在描述和指定上取得平衡Content42并行計算模型ParallelComputingModel并行算法的基本方法Concepts分解（Decomposition）任務（Task）映射（Mapping）算法模型（AlgorithmModel）分解、任務及依賴圖43設(shè)計并行算法的第一步是將問題分解成可并發(fā)執(zhí)行的任務分解可用任務依賴圖(taskdependencygraph)

表示。圖中節(jié)點代表任務，邊代表任務依賴Example:MultiplyingaDenseMatrixwithaVector44計算輸出向量y的每一元素可獨立進行。因此，矩陣與向量之積可分解為n個任務Example:DatabaseQueryProcessing在如下數(shù)據(jù)庫上執(zhí)行查詢: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í)行查詢可分成任務。每一任務可看作產(chǎn)生滿足某一條件的中間結(jié)果46邊表示一個任務的輸出是另一個任務的輸入Example:DatabaseQueryProcessing同一問題可采用其它方式分解。不同的分解可能存在重大的性能差異47任務粒度分解的任務數(shù)量越多，粒度越小。否則粒度越大48并行度DegreeofConcurrency49能并行執(zhí)行的任務數(shù)稱為一分解的degreeofconcurrency

maximumdegreeofconcurrency

averagedegreeofconcurrency

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

表達任務之間交換關(guān)系的圖稱為taskinteractiongraph.taskinteractiongraphs

表達數(shù)據(jù)依賴；taskdependencygraphs表達controldependencies.TaskInteractionGraphs:AnExample

稀疏矩陣A乘以向量

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

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

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

52任務的數(shù)量超過處理單元的數(shù)量，因此必須將任務映射到進程恰當?shù)娜蝿沼成鋵Σ⑿兴惴ǖ男阅芊浅Ｖ匾?/p>

映射由任務依賴圖和任務交互圖決定

任務依賴圖確保任務在任何時間點均勻分布到所有進程

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

(minimumcommunication).

ProcessesandMapping:Example

將數(shù)據(jù)庫查詢?nèi)蝿沼成涞竭M程.根據(jù)同一層沒有依賴關(guān)系，同一層任務可分配給不同進程53分解技術(shù)DecompositionTechniques54?遞歸分解（recursivedecomposition）

?

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

?

探索分解（exploratorydecomposition）

?

猜測分解（speculativedecomposition）

遞歸分解（RecursiveDecomposition）

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

這些子問題進一步遞歸分解，直到所需要的任務粒度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ù)例子說明.求{4,9,1,7,8,11,2,12}的最小數(shù).任務依賴圖如下:59數(shù)據(jù)分解（DataDecomposition）60劃分數(shù)據(jù)，將數(shù)據(jù)分配給不同任務

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

nxn

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

可以分為如下四個任務: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ù)據(jù)，形成局部結(jié)果。合并局部結(jié)果形成最終結(jié)果InputDataPartitioning:Example

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

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

(output)可同時劃分如下:65中間數(shù)據(jù)劃分（IntermediateDataPartitioning）66計算通?？梢暈橐幌盗袕妮斎氲捷敵龅淖儞Q.因此，可考慮將中間結(jié)果進行分解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在許多場合，隨著執(zhí)行的逐步推進而進行劃分.這些應用通常涉及搜索解答的狀態(tài)空間適合應用包括：組合優(yōu)化，定理證明，游戲，

etc.ExploratoryDecomposition:Example

15puzzle(atilepuzzle).

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

兩種方法:保守方法（conservativeapproaches）：當確認沒有依賴時，可以識別獨立任務,樂觀方法（optimisticapproaches）即使可能是錯誤的，仍然調(diào)度任務

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

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

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

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

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

任務生成

任務粒度

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

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

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

例如：組合優(yōu)化問題里很難估計狀態(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）:交互有明確的模式.模式可以用于有效的實現(xiàn).不規(guī)則交互（Irregularinteractions）:交互缺乏模式.CharacteristicsofTaskInteractions:Example82

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

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

StaticandDynamicMapping減小交互開銷的映射

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

Data-Parallel,Work-Pool,TaskGraph,Master-Slave,Pipeline,andHybridModelsMappingTechniques86映射必須減小開銷.主要開銷包括：communication

和

idling.Minimizingtheseoverheadsoftenrepresentscontradictingobjectives.例如：Assigning

allworktooneprocessortriviallyminimizescommunicationattheexpenseofsignificantidling.MappingTechniquesforMinimumIdling87

映射需同時減小idling和負載不均衡.均衡負載不一定減小

idling.MappingTechniquesforMinimumIdling88

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

SchemesforStaticMapping89MappingsbasedondatapartitioningMappingsbasedontaskgraphpartitioningHybridmappingsMappingsBasedonDataPartitioning901-Dblockdistributionschemes.BlockArrayDistributionSchemes

Blockdistributionschemescanbegeneralizedtohigherdimensionsaswell.91BlockArrayDistributionSchemes:Examples92對于矩陣A

和B相乘，可用塊分解法劃分輸出矩陣C.對于負載平衡，每一任務處理同樣數(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