第10章并行程序設(shè)計(jì)

2024/2/29程序設(shè)計(jì)語言范型

ProgrammingLanguagesParadigms第10章并行程序設(shè)計(jì)并行程序設(shè)計(jì)1內(nèi)容1.并行計(jì)算基礎(chǔ)1.1并行計(jì)算1.2硬件體系結(jié)構(gòu)1.3進(jìn)程和線程2.并行程序設(shè)計(jì)語言3.并行程序設(shè)計(jì)方法并行程序設(shè)計(jì)21.1并行計(jì)算應(yīng)用需求工程設(shè)計(jì)能源勘探醫(yī)學(xué)軍事基礎(chǔ)理論氣象預(yù)報(bào)設(shè)計(jì)自動(dòng)化并行程序設(shè)計(jì)31.1并行計(jì)算串行處理：多個(gè)任務(wù)在一個(gè)處理單元上依次執(zhí)行并行處理：多個(gè)任務(wù)在多個(gè)處理單元上同時(shí)執(zhí)行任務(wù)1任務(wù)2單處理器處理器1任務(wù)1任務(wù)2處理器2并行程序設(shè)計(jì)41.1并行計(jì)算具體方法：將被求解的問題分解為若干部分每個(gè)部分分別由不同的處理器同時(shí)進(jìn)行計(jì)算實(shí)現(xiàn)上述方法的程序稱為并行程序；具有多個(gè)處理器的、并能夠協(xié)同解決問題的計(jì)算機(jī)稱為并行計(jì)算機(jī)。并行程序設(shè)計(jì)51.1并行計(jì)算并行程序設(shè)計(jì)6內(nèi)容1.并行計(jì)算基礎(chǔ)1.1并行計(jì)算1.2硬件體系結(jié)構(gòu)1.3進(jìn)程和線程2.并行程序設(shè)計(jì)語言3.并行程序設(shè)計(jì)方法并行程序設(shè)計(jì)71.2

硬件體系結(jié)構(gòu)單指令流多數(shù)據(jù)流(SIMD)中央處理進(jìn)程指定每個(gè)處理器應(yīng)該執(zhí)行的指令，每個(gè)處理器以相同的速度執(zhí)行相同的指令并行程序設(shè)計(jì)81.2

硬件體系結(jié)構(gòu)多指令流多數(shù)據(jù)流(MIMD)目前流行的并行計(jì)算平臺(tái)進(jìn)一步分類：存儲(chǔ)器的組織方式共享存儲(chǔ)MIMD集中式共享存儲(chǔ)分布式共享存儲(chǔ)非共享存儲(chǔ)MIMD大規(guī)模并行處理機(jī)集群并行程序設(shè)計(jì)91.2

硬件體系結(jié)構(gòu)1共享存儲(chǔ)器存儲(chǔ)器統(tǒng)一編址被處理器共享使用，處理器通過讀寫共享變量相互通信。(1)集中式共享存儲(chǔ)

——對(duì)稱多處理器（SymmetricMultiProcessor）存儲(chǔ)器的結(jié)構(gòu)是集中的，處理器以相同速度訪問所有存儲(chǔ)器單元。性能限制：處理器/存儲(chǔ)器帶寬代表：IBMR50,SGIPowerChallenge,SUNEnterprise,曙光一號(hào)并行程序設(shè)計(jì)101.2

硬件體系結(jié)構(gòu)1共享存儲(chǔ)器(2)分布式共享存儲(chǔ)內(nèi)存模塊物理上局部于各個(gè)處理器內(nèi)部,但邏輯上是共享存儲(chǔ)的處理器訪問存儲(chǔ)器的速度取決于存儲(chǔ)器的位置，局部與遠(yuǎn)程內(nèi)存訪問的延遲和帶寬不一致代表:SGIOrigin2000,CrayT3D并行程序設(shè)計(jì)111.2

硬件體系結(jié)構(gòu)2分布式共享存儲(chǔ)所有的結(jié)點(diǎn)是單獨(dú)的計(jì)算系統(tǒng)，擁有自己的地址空間，存儲(chǔ)器單獨(dú)編址，數(shù)據(jù)通信通過發(fā)送消息實(shí)現(xiàn)(1)大規(guī)模并行處理機(jī)

(MassivelyParallelProcessors)采用高通信帶寬和低延遲的互聯(lián)網(wǎng)絡(luò)(專門設(shè)計(jì)和定制的)

代表:CRAYT3E(2048),ASCIRed(3072),IBMSP2,曙光1000并行程序設(shè)計(jì)121.2

硬件體系結(jié)構(gòu)2分布式存儲(chǔ)器(2)集群（Cluster）由商業(yè)計(jì)算機(jī)通過商業(yè)網(wǎng)絡(luò)連接而成為一個(gè)組織獲得并行計(jì)算能力提供了一種廉價(jià)的方式。曙光2000,3000,ASCIBlueMountain并行程序設(shè)計(jì)131.2

硬件體系結(jié)構(gòu)處理器的組織需要滿足多個(gè)處理器間的操作同步多個(gè)處理期間的相互通信并行程序設(shè)計(jì)14內(nèi)容1.并行計(jì)算基礎(chǔ)1.1并行計(jì)算1.2硬件體系結(jié)構(gòu)1.3進(jìn)程和線程2.并行程序設(shè)計(jì)語言3.并行程序設(shè)計(jì)方法并行程序設(shè)計(jì)151.3進(jìn)程和線程進(jìn)程程序在計(jì)算機(jī)上的一次執(zhí)行活動(dòng)系統(tǒng)進(jìn)行資源分配和調(diào)度運(yùn)行的一個(gè)獨(dú)立單位使多個(gè)程序并發(fā)執(zhí)行，改善資源利用率提高系統(tǒng)的吞吐量線程進(jìn)程的一個(gè)實(shí)體，是輕量級(jí)的進(jìn)程擁有很少的系統(tǒng)資源：程序計(jì)數(shù)器、寄存器和棧同一進(jìn)程的各線程共享進(jìn)程的全部資源并行程序設(shè)計(jì)16內(nèi)容1.并行計(jì)算基礎(chǔ)2.并行程序設(shè)計(jì)語言2.1沒有明顯并行機(jī)制的并行編程2.2明顯并行機(jī)制的并行編程2.3并行粒度2.4進(jìn)程的通信與同步3.并行程序設(shè)計(jì)方法并行程序設(shè)計(jì)171擴(kuò)展編譯器利用編譯器優(yōu)化程序使得目標(biāo)程序可以利用操作系統(tǒng)提供的功能運(yùn)行在多個(gè)處理器上難以得到最優(yōu)分配策略2.1沒有明顯并行機(jī)制的并行編程并行程序設(shè)計(jì)182.1沒有明顯并行機(jī)制的并行編程2擴(kuò)展已有的串行編程語言使用外部函數(shù)庫實(shí)現(xiàn)并行計(jì)算不同的操作系統(tǒng)或機(jī)器提供不同的庫函數(shù)微軟Windows線程API微軟.NET框架線程APIPOSIX線程Pthreads

是Linux操作系統(tǒng)中多線程接口的標(biāo)準(zhǔn)Pthread-win32（Windows版本）Intel的ThreadingBuildingBlocks庫用來實(shí)現(xiàn)并行語義的c++模板庫，它對(duì)c++進(jìn)行了擴(kuò)展，抽象出了線程管理機(jī)制并支持簡明的并行編程。并行程序設(shè)計(jì)19內(nèi)容1.并行計(jì)算基礎(chǔ)2.并行程序設(shè)計(jì)語言2.1沒有明顯并行機(jī)制的并行編程2.2明顯并行機(jī)制的并行編程2.3并行粒度2.4進(jìn)程的通信與同步3.并行程序設(shè)計(jì)方法并行程序設(shè)計(jì)202.2明顯并行機(jī)制的并行編程1擴(kuò)展已有的串行編程語言提供支持并行程序的關(guān)鍵字和語言高性能Fortran（HPF）語言ConcurrentCJava，在5.0版中引入了concurrency包

2人工干預(yù)處理器的分配(明顯表達(dá)并行計(jì)算)通過使用嵌入的編譯器命令建立并行說明OpenMP3使用標(biāo)準(zhǔn)的外部函數(shù)庫PVM（ParallelVirtualMachine）MPI（MessagePassingInterface）并行程序設(shè)計(jì)212.2明顯并行機(jī)制的并行編程進(jìn)程的創(chuàng)建和銷毀將當(dāng)前的進(jìn)程分為多個(gè)進(jìn)程，執(zhí)行同一段程序的拷貝不同的進(jìn)程可以按照進(jìn)程標(biāo)識(shí)執(zhí)行程序的一部分SPMD(Single

ProgramMultipleData)將一段代碼專門由一個(gè)進(jìn)程執(zhí)行每個(gè)進(jìn)程執(zhí)行不同的代碼MPMD并行程序設(shè)計(jì)222024/2/2923數(shù)據(jù)幾何劃分求【例】最大數(shù)并行程序設(shè)計(jì)232024/2/2924數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)242024/2/2925數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)252024/2/2926數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)262024/2/2927數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)272024/2/2928數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)282024/2/2929數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU

3并行程序設(shè)計(jì)292024/2/2930數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)302024/2/2931數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)312024/2/2932數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)322024/2/2933數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU2CPU3并行程序設(shè)計(jì)332024/2/2934數(shù)據(jù)幾何劃分求【例】最大數(shù)CPU0CPU1CPU

2CPU

3并行程序設(shè)計(jì)34f()s()r()q()h()g()并行程序設(shè)計(jì)35f()s()r()q()h()g()CPU0CPU2CPU

1并行程序設(shè)計(jì)36f()s()r()q()h()g()CPU0CPU2CPU1并行程序設(shè)計(jì)37f()s()r()q()h()g()CPU0CPU2CPU1并行程序設(shè)計(jì)38f()s()r()q()h()g()CPU0CPU2CPU1并行程序設(shè)計(jì)39f()s()r()q()h()g()CPU0CPU2CPU1并行程序設(shè)計(jì)40內(nèi)容1.并行計(jì)算基礎(chǔ)2.并行程序設(shè)計(jì)語言2.1沒有明顯并行機(jī)制的并行編程2.2明顯并行機(jī)制的并行編程2.3并行粒度2.4進(jìn)程的通信與同步3.并行程序設(shè)計(jì)方法并行程序設(shè)計(jì)412.3并行粒度語句級(jí)并行——小粒度一個(gè)語句成為可以并行執(zhí)行的代碼程序級(jí)并行——大粒度整個(gè)程序成為可以并行執(zhí)行的代碼過程級(jí)并行——中等粒度一個(gè)過程成為可以并行執(zhí)行的代碼并行程序設(shè)計(jì)42內(nèi)容1.并行計(jì)算基礎(chǔ)2.并行程序設(shè)計(jì)語言2.1沒有明顯并行機(jī)制的并行編程2.2明顯并行機(jī)制的并行編程2.3并行粒度2.4進(jìn)程的通信與同步3.并行程序設(shè)計(jì)方法并行程序設(shè)計(jì)43共享存儲(chǔ)結(jié)構(gòu)進(jìn)程的通信與同步多個(gè)線程可能需要同時(shí)訪問同一個(gè)數(shù)據(jù)，如果沒有正確的保護(hù)措施，對(duì)共享數(shù)據(jù)的訪問會(huì)造成數(shù)據(jù)的不一致和錯(cuò)誤。對(duì)應(yīng)低級(jí)語言代碼為：

讀x單元的內(nèi)容計(jì)算x+1將結(jié)果寫回x單元高級(jí)語言代碼為：

x++;或x=x+1;2.4進(jìn)程的通信與同步進(jìn)程1readxcomputex+1writetox進(jìn)程2readxcomputex+1writetox若兩進(jìn)程執(zhí)行每一步操作的時(shí)間關(guān)系不同，則有可能使操作的結(jié)果不相同。并行程序設(shè)計(jì)44共享存儲(chǔ)結(jié)構(gòu)進(jìn)程的通信與同步臨界區(qū)、臨界段(criticalsection)保證每次僅允許一個(gè)進(jìn)程訪問某個(gè)特定的共享資源的代碼段2.4進(jìn)程的通信與同步進(jìn)入?yún)^(qū)退出區(qū)臨界區(qū)并行程序設(shè)計(jì)45共享存儲(chǔ)結(jié)構(gòu)進(jìn)程的通信與同步在共享存儲(chǔ)結(jié)構(gòu)中的同步通常用于：確定進(jìn)程間正確的執(zhí)行次序保證各進(jìn)程對(duì)共享變量正確的讀寫次序有以下幾種常用的同步機(jī)制：鎖信號(hào)量監(jiān)控程序2.4進(jìn)程的通信與同步并行程序設(shè)計(jì)46共享存儲(chǔ)結(jié)構(gòu)進(jìn)程的通信與同步鎖機(jī)制通常用1個(gè)二進(jìn)制位變量來表示一個(gè)鎖最多只能由一個(gè)線程獲得任何線程訪問共享資源前要先獲得鎖，否則，線程將保持在該鎖的等待隊(duì)列，直到該鎖被釋放。2.4進(jìn)程的通信與同步并行程序設(shè)計(jì)47進(jìn)程1while(lock==1)do_nothing;lock=1;lock=0;臨界段進(jìn)程2while(lock==1)do_nothing;lock=1;lock=0;臨界段等待是不可分的2.4進(jìn)程的通信與同步并行程序設(shè)計(jì)48共享存儲(chǔ)結(jié)構(gòu)進(jìn)程的通信與同步信號(hào)量一個(gè)非負(fù)整數(shù)變量s，基本操作：P(s)和V(s)對(duì)信號(hào)量s執(zhí)行P操作相當(dāng)于請(qǐng)求分配一個(gè)單位資源，使s減1對(duì)信號(hào)量s執(zhí)行V操作相當(dāng)于歸還一個(gè)單位資源，使s加1二元信號(hào)量(其值0或1)與鎖的執(zhí)行效果相同2.4進(jìn)程的通信與同步并行程序設(shè)計(jì)49共享存儲(chǔ)結(jié)構(gòu)進(jìn)程的通信與同步監(jiān)視器將信號(hào)量和相關(guān)的P、V操作封裝在一起的結(jié)構(gòu)對(duì)數(shù)據(jù)的讀和寫只能由監(jiān)控程序中的過程來完成在任何時(shí)間只能由一個(gè)進(jìn)程使用監(jiān)控程序的過程2.4進(jìn)程的通信與同步x_mon:monitor

var

x_being_written:boolean;

//對(duì)共享變量的讀操作

procedureread_x

//若x正在被修改，則掛起

if(x_being_written) thenwait; readx; endread_x;

//對(duì)共享變量的寫操作

procedurewrite_x

if(x_being_written) thenwait;

x_being_written=T; writex;

x_being_written=F; signal;//叫醒掛起進(jìn)程

endwrite_x;endx_mon;并行程序設(shè)計(jì)502.4進(jìn)程的通信與同步非共享存儲(chǔ)結(jié)構(gòu)中進(jìn)程的通信與同步現(xiàn)在的消息傳遞系統(tǒng)多使用三種通信模式:同步的消息傳遞阻塞的消息傳遞和非阻塞的消息傳遞組通信機(jī)制并行程序設(shè)計(jì)51非共享存儲(chǔ)結(jié)構(gòu)中進(jìn)程的通信與同步1同步消息傳遞消息傳遞過程結(jié)束后調(diào)用才返回通常需要某種形式的同步信號(hào)。2.4進(jìn)程的通信與同步send();recv();進(jìn)程1進(jìn)程2請(qǐng)求發(fā)送，喚醒進(jìn)程2確認(rèn)開始發(fā)送進(jìn)程2掛起recv在send之前調(diào)用send();recv();進(jìn)程1進(jìn)程2請(qǐng)求發(fā)送，進(jìn)程1掛起確認(rèn)，喚醒進(jìn)程1開始消息發(fā)送過程send在recv之前調(diào)用并行程序設(shè)計(jì)52非共享存儲(chǔ)結(jié)構(gòu)中進(jìn)程的通信與同步2阻塞消息傳遞和非阻塞消息傳遞發(fā)送方只有在消息已經(jīng)發(fā)送出去之后才能返回；或接收方已經(jīng)確切的接收到消息才能返回進(jìn)程在告知系統(tǒng)發(fā)送/接收請(qǐng)求之后，便立即返回2.4進(jìn)程的通信與同步send();連續(xù)執(zhí)行recv();進(jìn)程1進(jìn)程2消息緩存并行程序設(shè)計(jì)53非共享存儲(chǔ)結(jié)構(gòu)中進(jìn)程的通信與同步3群組消息傳遞-廣播(broadcast)向所有與求解問題有關(guān)的進(jìn)程發(fā)送相同的信息數(shù)據(jù)緩存bcast();進(jìn)程1進(jìn)程2數(shù)據(jù)bcast();進(jìn)程n數(shù)據(jù)bcast();2.4進(jìn)程的通信與同步并行程序設(shè)計(jì)54非共享存儲(chǔ)結(jié)構(gòu)中進(jìn)程的通信與同步3群組消息傳遞-散播(scatter)根進(jìn)程的數(shù)據(jù)數(shù)組中的每個(gè)元素分別發(fā)送給各個(gè)進(jìn)程。數(shù)據(jù)緩存scatter();進(jìn)程1進(jìn)程2數(shù)據(jù)scatter();進(jìn)程n數(shù)據(jù)scatter();2.4進(jìn)程的通信與同步并行程序設(shè)計(jì)55非共享存儲(chǔ)結(jié)構(gòu)中進(jìn)程的通信與同步3群組消息傳遞-匯集(gather)一個(gè)進(jìn)程從一組進(jìn)程中的每一個(gè)進(jìn)程處收集一個(gè)數(shù)據(jù)有時(shí)匯集操作與一個(gè)計(jì)算操作組合在一起，對(duì)各個(gè)值進(jìn)行匯總，稱為歸約(reduce)操作．?dāng)?shù)據(jù)緩存gather();進(jìn)程1進(jìn)程2數(shù)據(jù)gather();進(jìn)程n數(shù)據(jù)gather();+2.4進(jìn)程的通信與同步并行程序設(shè)計(jì)562.2明顯并行機(jī)制的并行編程擴(kuò)展已有的串行編程語言提供支持并行程序的關(guān)鍵字和語言高性能Fortran（HPF）語言ConcurrentCJava，在5.0版中引入了concurrency包

人工干預(yù)處理器的分配(明顯表達(dá)并行計(jì)算)通過使用嵌入的編譯器命令建立并行說明OpenMP使用標(biāo)準(zhǔn)的外部函數(shù)庫PVM（ParallelVirtualMachine）MPI（MessagePassingInterface）并行程序設(shè)計(jì)57內(nèi)容1.并行計(jì)算基礎(chǔ)2.并行程序設(shè)計(jì)語言3.并行程序設(shè)計(jì)方法3.1數(shù)據(jù)并行性3.2功能并行性3.3流水線3.4負(fù)載平衡并行程序設(shè)計(jì)583.1數(shù)據(jù)并行性【例】利用數(shù)據(jù)劃分技術(shù)對(duì)數(shù)列A求和。假設(shè)有p個(gè)處理機(jī)，數(shù)列元素個(gè)數(shù)為n。A0…An/p-1An/p…A2n/p-1A2n/p…………A(p-1)n/p…An-1++++………局部和總和并行程序設(shè)計(jì)593.1數(shù)據(jù)并行性【例】數(shù)組元素累加-OpenMP

并行程序設(shè)計(jì)60并行程序設(shè)計(jì)613.1數(shù)據(jù)并行性【例】數(shù)組元素累加-MPI并行程序設(shè)計(jì)62并行程序設(shè)計(jì)63并行程序設(shè)計(jì)643.1數(shù)據(jù)并行性【例】統(tǒng)計(jì)素?cái)?shù)的個(gè)數(shù)-OpenMPint

number_of_primes=0;intprime;omp_set_num_threads(2);#pragma

ompparallelforprivate(factor,limit,prime)schedule(static,10)reduction(+;number_of_primes)

for(index=begin;index<=end;index+=2){limit=(int)sqrt((float)index)+1;prime=1;factor=3;while(prime&&(factor<=limit)){if(index%factor==0)prime=0;factor+=2;}

if(prime){#pragma

ompcritical{

number_of_primes++;}}}并行程序設(shè)計(jì)653.1數(shù)據(jù)并行性【例】統(tǒng)計(jì)素?cái)?shù)的個(gè)數(shù)-MPI#include<stdio.h>#include"mpi.h“main(int

argc,char*argv[]){

若干變量聲明；

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&id);

MPI_Comm_size(MPI_COMM_WORLD,&p);

low_value=2+BLOCK_LOW(id,p,n-1);

high_value=2+BLOCK_HIGH(id,p,n-1);size=BLOCK_SIZE(id,p,n-1);marked=(char*)malloc(size);

for(i=0;i<size;i++)marked[i]=0;

if(!id)

index=0;

prime=2;

do{if(prime*prime>low_value)

first=prime*prime-low_value;else{if(!(low_value%prime))first=0;elsefirst=prime-(low_value%prime);}并行程序設(shè)計(jì)663.1數(shù)據(jù)并行性【例】統(tǒng)計(jì)素?cái)?shù)的個(gè)數(shù)-MPIfor(i=first;i<size;i+=prime)marked[i]=1;

if(!id){

while(!marked[++index]);prime=index+2;}

MPI_Bcast(&prime,1MPI_INT,0,MPI_COMM_WORLD);}while(prime*prime<=n)count=0;

for(i=0;i<size;i++)if(!marked[i])count++;

MPI_Reduce(&count,&global_count,1,MPI_INT,MPI_SUM,0,MPI_COMM_WORLD);

MPI_Finalize();}并行程序設(shè)計(jì)673.1數(shù)據(jù)并行性分治：將一個(gè)大問題遞歸地逐步分割成若干個(gè)子問題，用簡單且相同的方法對(duì)這些子問題進(jìn)行求解。P0P2P0P4P0P6P4P0P1P2P3P4P5P6P7P0divide(s1,s1,s2);send(s2,P4);divide(s1,s1,s2);send(s2,P2);divide(s1,s1,s2);send(s2,P1);part_sum=*s1recv(&part_sum1,P1);part_sum+=part_sum1;recv(&part_sum1,P2);part_sum+=part_sum1;recv(&part_sum1,P4);part_sum+=part_sum1;并行程序設(shè)計(jì)683.1數(shù)據(jù)并行性【例】快速排序#include<stdio.h>#include<stdlib.h>#include"mpi.h“main(int

argc,char*argv[]){

int

DataSize;

int*data;

int

MyID,SumID;

inti,j,m,r;

MPI_Statusstatus;

MPI_Init(&argc,&argv);

MPI_Common_rank(MPI_COMMON_WORLD,&MyID);

MPI_Common_size(MPI_COMMON_WORLD,&SumID);并行程序設(shè)計(jì)693.1數(shù)據(jù)并行性【例】快速排序if(MyID==0){

DataSize=GetDataSize();data=(int*)malloc(DataSize*sizeof(int));

for(i=0;i<DataSize;i++)data[i]=(int)rand();}

m=log2(SumID);para_QuickSort(data,0,DataSize-1,m,0,MyID);

MPI_Finalize();}并行程序設(shè)計(jì)703.1數(shù)據(jù)并行性【例】快速排序para_QuickSort(int*data,intstart,intend,intm,intid,intMyID){inti,j,r,MyLength,int*temp;MPI_Statusstatus;

if(MyID==id){r=Partition(data,start,end);

MyLength=end-r;MPI_Send(&MyLength,1,MPI_INT,

id+exp2(m-1),MyID,MPI_COMM_WORLD);

MPI_Send(data+r+1,MyLength,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);}P0P4P0m=3并行程序設(shè)計(jì)713.1數(shù)據(jù)并行性【例】快速排序

if(MyID==id+exp2(m-1)){MPI_Recv(&MyLength,1,MPI_INT,id,id,

MPI_COMM_WORLD,&status);

temp=(int*)malloc(MyLength*sizeof(int));

MPI_Recv(temp,MyLength,MPI_INT,id,id,

MPI_COMM_WORLD,&status);}P0P4P0m=3并行程序設(shè)計(jì)723.1數(shù)據(jù)并行性【例】快速排序

para_QuickSort(data,start,r-1,m-1,id,MyID);

para_QuickSort(temp,0,MyLength-1,m-1,id+exp2(m-1),MyID);

if(MyID=id+exp2(m-1))

MPI_Send(temp,MyLength,MPI_INT,id,id+exp2(m-1),MPI_COMM_WORLD);

if(MyID=id)

MPI_Recv(data+r+1,MyLength,MPI_INT,id+exp2(m-1),id+exp2(m-1),MPI_COMM_WORLD,&status);}P0P4P0m=3m=2并行程序設(shè)計(jì)733.1數(shù)據(jù)并行性【例】快速排序para_QuickSort(int*data,intstart,intend,intm,intid,intMyID){inti,j,r,MyLength,int*temp;MPI_Statusstatus;

P0P4P0并行程序設(shè)計(jì)743.1數(shù)據(jù)并行性

if(MyID==id){r=Partition(data,start,end);

MyLength=end-r;MPI_Send(&MyLength,1,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);MPI_Send(data+r+1,MyLength,MPI_INT,id+exp2(m-1),MyID,MPI_COMM_WORLD);}

if(MyID==id+exp2(m-1)){MPI_Recv(&MyLength,1,MPI_INT,id,id,MPI_COMM_WORLD,&status);temp=(int*)malloc(MyLength*sizeof(int));

MPI_Recv(temp,MyLength,MPI_INT,id,id,MPI_COMM_WORLD,&status);}P0P4P6P4m=2para_QuickSort()并行程序設(shè)計(jì)753.1數(shù)據(jù)并行性

para_QuickSort(data,start,r-1,m-1,id,MyID);

para_QuickSort(temp,0,MyLength-1,m-1,id+exp2(m-1),MyID);

if(MyID=id+exp2(m-1))

MPI_Send(temp,MyLength,MPI_INT,id,id+exp2(m-1),MPI_COMM_WORLD);

if(MyID=id)

MPI_Recv(data+r+1,MyLength,MPI_INT,id+exp2(m-1),id+exp2(m-1),MPI_COMM_WORLD,&status);}P0P4P6P4m=2并行程序設(shè)計(jì)763.1數(shù)據(jù)并行性para_QuickSort(int*data,intstart,intend,intm,intid,intMyID){}

P0P4P6P4P4P5P6P7m=1并行程序設(shè)計(jì)773.1數(shù)據(jù)并行性para_QuickSort(int*data,intstart,intend,intm,intid,intMyID){inti,j,r,MyLength,int*temp;MPI_Statusstatus;

if(m==0){

if(MyID==0)

QuickSort(data,start,end);return;}P0P4P6P4P4P5P6P7m=0并行程序設(shè)計(jì)78內(nèi)容1.并行計(jì)算基礎(chǔ)2.并行程序設(shè)計(jì)語言3.并行程序設(shè)計(jì)方法3.1數(shù)據(jù)并行性3.2功能并行性

3.3流水線3.4負(fù)載平衡并行程序設(shè)計(jì)79并行程序設(shè)計(jì)80內(nèi)容1.并行計(jì)算基礎(chǔ)2.并行程序設(shè)計(jì)語言3.并行程序設(shè)計(jì)方法3.1數(shù)據(jù)并行性3.2功能并行性3.3流水線3.4負(fù)載平衡并行程序設(shè)計(jì)813.3流水線流水線計(jì)算是通過將任務(wù)按功能劃分成若干個(gè)級(jí)或子任務(wù)，每個(gè)級(jí)可以同時(shí)執(zhí)行，且一級(jí)的輸出是下一級(jí)的輸入。每個(gè)子任務(wù)由不同的處理部件執(zhí)行。a4a3a2…

a4

a3a2a1

a1…

a4

a3a2…

a4

a3P0P1P2P3P4…a4…并行程序設(shè)計(jì)823.3流水線流水線技術(shù)在以下計(jì)算中將會(huì)得到很好的并行效益：如果有一系列數(shù)據(jù)項(xiàng)要處理，而每個(gè)數(shù)據(jù)項(xiàng)需要多次操作；如果進(jìn)程在完成自己的全部操作之前能夠提供下一個(gè)進(jìn)程啟動(dòng)所需的信息。輸入序列d9d8d7d6d5d4d3d2d1d0P1P2P3P4P5P6P7P8P9P0并行程序設(shè)計(jì)83234567891011121314151617181920212223242526272829302345678910111213141516171819202122232425262728293023456789101112131415161718192021222324252627282930234567891011121314151617181920212223242526272829302923191713117532最終結(jié)果3.3流水線【例】篩法求素?cái)?shù)并行程序設(shè)計(jì)8423456789101112131415161718192021222324252627282930P0篩去2的倍數(shù)篩去3的倍數(shù)P1篩去5的倍數(shù)P235791113151719212325272971113171923295711131719232529【例】篩法求素?cái)?shù)并行程序設(shè)計(jì)85【例】篩法求素?cái)?shù)并行算法：因?yàn)槊總€(gè)進(jìn)程需要從上一個(gè)進(jìn)程接收的數(shù)列元素個(gè)數(shù)不確定，引入一個(gè)數(shù)列結(jié)束標(biāo)志terminator。

recv(x,Pi-1);

for(i=0;i<n;i++){

recv(number,Pi-1);if(number==terminator)break;if((number%x)!=0)send(number,Pi+1);}3.3流水線并行程序設(shè)計(jì)86【例】回代法求解上三角線性方程組an-1,0x0+an-1,1x1+

an-1,2x2+

…an-1,n-2xn-2+an-1,n-1xn-1=bn-1an-2,0x0+an-2,1x1+

an-2,2x2+

…an-2,n-2xn-2=bn-2an-3,0x0+an-3,1x1+

an-3,2x2+…=bn-3……a2,0x0+a2,1x1+

a2,2x2=b2a1,0x0+a1,1x1=b1a0,0x0=b0

3.3流水線實(shí)現(xiàn)回代法的順序方法：x0=b0/a0,0x1=(b1-a1,0x0)/a1,1x2=(b2-a2,0x0-a2,1x1)/a2,2并行程序設(shè)計(jì)87流水線并行方式流水線中第一個(gè)進(jìn)程（流水線級(jí)）計(jì)算x0，并將x0傳遞給第二個(gè)進(jìn)程；第二個(gè)進(jìn)程（流水線級(jí)）用x0計(jì)算出x1，然后將x0和x1

發(fā)給第三個(gè)進(jìn)程；第i個(gè)進(jìn)程從第i-1個(gè)進(jìn)程接收x0,x1,…,xi-1，并計(jì)算xi

，并將x0,x1,…,xi

傳遞給下一個(gè)進(jìn)程；……計(jì)算x0P0計(jì)算x1P1計(jì)算x2P2計(jì)算x3P3x0x0x1x0x1x2x0x1x2x33.3流水線bi-

ai,j

xj

0ji-1ai,ixi=并行程序設(shè)計(jì)88并行算法(1)

：進(jìn)程Pi

(0<i<n)的偽碼：for(j=0;j<i;j++){

recv(x[j],Pi-1

);send(x[j],Pi+1);}sum=0;

for(j=0;j<i;j++)sum=sum+a[i][j]*x[j];x[i]=(b[i]-sum)/a[i][i];send(x[i],Pi+1);

3.3流水線并行算法(2)進(jìn)程Pi

(0<i<n)的偽碼：sum=0;for(j=0;j<i;j++){

recv(x[j],Pi-1

);

send(x[j],Pi+1);sum=sum+a[i][j]*x[j];}x[i]=(b[i]-sum)/a[i][i];send(x[i],Pi+1);并行程序設(shè)計(jì)89內(nèi)容1.并行計(jì)算基礎(chǔ)2.并行程序設(shè)計(jì)語言3.并行程序設(shè)計(jì)方法3.1數(shù)據(jù)并行性3.2功能并行性3.3流水線3.4負(fù)載平衡并行程序設(shè)計(jì)903.4負(fù)載平衡負(fù)載平衡----在并行系統(tǒng)中，使各個(gè)節(jié)點(diǎn)盡量均衡地分配工作任務(wù)的技術(shù)，以獲得最大可能的執(zhí)行速度。終止檢測(cè)----檢測(cè)一個(gè)計(jì)算任務(wù)何時(shí)已經(jīng)結(jié)束。P1P0P2P3P4P5處理機(jī)timetime處理機(jī)P1P0P2P3P4P5并行程序設(shè)計(jì)913.4負(fù)載平衡集中式動(dòng)態(tài)負(fù)載平衡主進(jìn)程擁有要被執(zhí)行的任務(wù)集。當(dāng)從進(jìn)程完成一個(gè)任務(wù)，向主進(jìn)程請(qǐng)求另一個(gè)任務(wù)時(shí)，任務(wù)就由主進(jìn)程發(fā)給從進(jìn)程。工作池主進(jìn)程任務(wù)隊(duì)列從進(jìn)程請(qǐng)求任務(wù)(可能提交一些新任務(wù))發(fā)送任務(wù)并行程序設(shè)計(jì)923.4負(fù)載平衡【例】矩陣乘法——數(shù)據(jù)劃分策略#include<stdio.h>#include<stdlib.h>#include"mpi.h“#defineMASTER0#defineFROM_MASTER1#defineFROM_WORKER2main(int

argc,char*argv[]){

//變量定義

MPI_Init(&argc,&argv);

MPI_Common_rank(MPI_COMMON_WORLD,&taskid);

MPI_Common_size(MPI_COMMON_WORLD,&numtasks);

numworkers=numtasks-1;并行程序設(shè)計(jì)933.4負(fù)載平衡【例】矩陣乘法——數(shù)據(jù)劃分策略if(taskid==MASTER){

//讀取矩陣a和b

average_row=ROW_A/numworkers;

extra=ROW_A%numworkers;offset=0;

message_type=FROM_MASTER;for(dest=1;dest<numworkers;dest++){rows=(dest<=extra)?average_row+1:average_row;MPI_Send(&offset,1,MPI_INT,dest,message_type,MPI_COMM_WORLD);

MPI_Send(&rows,1,MPI_INT,dest,message_type,MPI_COMM_WORLD);count=rows*COLUMN_A;

MPI_Send(&a[offset][0],count,MPI_DOUBLE,dest,message_type,MPI_COMM_WORLD);count=COLUMN_A*COLUMN_B;

MPI_Send(&b,count,MPI_DOUBLE,dest,message_type,MPI_COMM_WORLD);offset=offset+rows;}

message_type=FROM_WORKER;

for(i=1;i<numworkers;i++){source=i;

MPI_Recv(&offset,1,MPI_INT,source,message_type,MPI_COMM_WORLD,&status);

MPI_Recv(&rows,1,MPI_INT,source,message_type,MPI_COMM_WORLD,&status);count=rows*COLUMN_B;

MPI_Recv(&c[offset][0],count,MPI_DOUBLE,dest,message_type,MPI_COMM_WORLD,&status);}}

并行程序設(shè)計(jì)943.4負(fù)載平衡【例】矩陣乘法——數(shù)據(jù)劃分策略if(taskid>MASTER){message_type=FROM_MASTER;source=MASTER;

MPI_Recv(&offset,1,MPI_INT,source,message_type,MPI_COMM_WORLD,&status);

MPI_Recv(&rows,1,MPI_INT,source,message_type,MPI_COMM_WORLD,&status);count=rows*COLUMN_A;

MPI_Recv(&a,count,MPI_DOUBLE,source,message_type,MPI_COMM_WORLD,&status);count=COLUMN_A*COLUMN_B;

MPI_Recv(&b,count,MPI_DOUBLE,source,message_type,MPI_COMM_WORLD,&status);

for(k=0;k<COLUMN_B;k++)for(i=0;i<rows;i++){c[i