第12章：并行程序設(shè)計(jì)基礎(chǔ).ppt

十二 并行程序設(shè)計(jì)基礎(chǔ) 并行計(jì)算 講授 曾碧卿教授 博士單位 信息工程與技術(shù)系 2 2020 2 20 并行程序設(shè)計(jì)基礎(chǔ) 12 1并行程序設(shè)計(jì)概述12 2進(jìn)程12 3線程12 4同步12 5通信12 6并行程序設(shè)計(jì)模型 3 2020 2 20 并行程序設(shè)計(jì)概述 并行程序設(shè)計(jì)難的原因并行語(yǔ)言的構(gòu)造方法并行性問(wèn)題交互 通信問(wèn)題五種并行編程風(fēng)范計(jì)算圓周率的樣本程序 4 2020 2 20 1并行程序設(shè)計(jì)難的原因 技術(shù)先行 缺乏理論指導(dǎo)程序的語(yǔ)法 語(yǔ)義復(fù)雜 需要用戶自已處理任務(wù) 數(shù)據(jù)的劃分 分配數(shù)據(jù)交換同步和互斥性能平衡并行語(yǔ)言缺乏代可擴(kuò)展和異構(gòu)可擴(kuò)展 程序移植困難 重寫代碼難度太大環(huán)境和工具缺乏較長(zhǎng)的生長(zhǎng)期 缺乏代可擴(kuò)展和異構(gòu)可擴(kuò)展 5 2020 2 20 2并行語(yǔ)言的構(gòu)造方法 串行代碼段for i 0 i N i A i b i b i 1 for i 0 i N i c i A i A i 1 a 使用庫(kù)例程構(gòu)造并行程序id my process id p number of processes for i id i N i i p A i b i b i 1 barrier for i id i N i i p c i A i A i 1 例子 MPI PVM Pthreads b 擴(kuò)展串行語(yǔ)言my process id number of processes andbarrier A 0 N 1 b 0 N 1 b 1 N c A 0 N 1 A 1 N 例子 Fortran90 c 加編譯注釋構(gòu)造并行程序的方法 pragmaparallel pragmashared A b c pragmalocal i pragmapforiterate i 0 N 1 for i 0 i N i A i b i b i 1 pragmasynchronize pragmapforiterate i 0 N 1 for i 0 i N i c i A i A i 1 例子 SGIpowerC 6 2020 2 20 三種并行語(yǔ)言構(gòu)造方法比較 2并行語(yǔ)言的構(gòu)造方法 7 2020 2 20 3并行性問(wèn)題 3 1進(jìn)程的同構(gòu)性SIMD 所有進(jìn)程在同一時(shí)間執(zhí)行相同的指令MIMD 各個(gè)進(jìn)程在同一時(shí)間可以執(zhí)行不同的指令SPMD 各個(gè)進(jìn)程是同構(gòu)的 多個(gè)進(jìn)程對(duì)不同的數(shù)據(jù)執(zhí)行相同的代碼 一般是數(shù)據(jù)并行的同義語(yǔ) 常對(duì)應(yīng)并行循環(huán) 數(shù)據(jù)并行結(jié)構(gòu) 單代碼MPMD 各個(gè)進(jìn)程是異構(gòu)的 多個(gè)進(jìn)程執(zhí)行不同的代碼 一般是任務(wù)并行 或功能并行 或控制并行的同義語(yǔ) 常對(duì)應(yīng)并行塊 多代碼要為有1000個(gè)處理器的計(jì)算機(jī)編寫一個(gè)完全異構(gòu)的并行程序是很困難的 8 2020 2 20 并行塊parbeginS1S2S3 SnparendS1S2S3 Sn可以是不同的代碼并行循環(huán) 當(dāng)并行塊中所有進(jìn)程共享相同代碼時(shí)parbeginS1S2S3 SnparendS1S2S3 Sn是相同代碼簡(jiǎn)化為parfor i 1 i n i S i 進(jìn)程的同構(gòu)性 3并行性問(wèn)題 9 2020 2 20 用單代碼方法說(shuō)明SPMD要說(shuō)明以下SPMD程序 parfor i 0 i N i foo i 用戶需寫一個(gè)以下程序 pid my process id numproc number of processes parfor i pid i N i i numproc foo i 此程序經(jīng)編譯后生成可執(zhí)行程序A 用shell腳本將它加載到N個(gè)處理結(jié)點(diǎn)上 runA numnodesN SPMD程序的構(gòu)造方法 用數(shù)據(jù)并行程序的構(gòu)造方法要說(shuō)明以下SPMD程序 parfor i 0 i N i C i A i B i 用戶可用一條數(shù)據(jù)賦值語(yǔ)句 C A B或forall i 1 N C i A i B i 進(jìn)程的同構(gòu)性 3并行性問(wèn)題 10 2020 2 20 用SPMD偽造MPMD要說(shuō)明以下MPMD程序 parbeginS1S2S3parend可以用以下SPMD程序 parfor i 0 i 3 i if i 0 S1if i 1 S2if i 2 S3 因此 對(duì)于可擴(kuò)展并行機(jī)來(lái)說(shuō) 只要支持SPMD就足夠了 MPMD程序的構(gòu)造方法 用多代碼方法說(shuō)明MPMD對(duì)不提供并行塊或并行循環(huán)的語(yǔ)言要說(shuō)明以下MPMD程序 parbeginS1S2S3parend用戶需寫3個(gè)程序 分別編譯生成3個(gè)可執(zhí)行程序S1S2S3 用shell腳本將它們加載到3個(gè)處理結(jié)點(diǎn)上 runS1onnode1runS2onnode1runS3onnode1S1 S2和S3是順序語(yǔ)言程序加上進(jìn)行交互的庫(kù)調(diào)用 進(jìn)程的同構(gòu)性 3并行性問(wèn)題 11 2020 2 20 3 2靜態(tài)和動(dòng)態(tài)并行性程序的結(jié)構(gòu) 由它的組成部分構(gòu)成程序的方法 靜態(tài)并行性的例子 parbeginP Q Rparend其中P Q R是靜態(tài)的 動(dòng)態(tài)并行性的例子 while C 0 beginfork foo C C boo C end 3并行性問(wèn)題 靜態(tài)并行性 程序的結(jié)構(gòu)以及進(jìn)程的個(gè)數(shù)在運(yùn)行之前 如編譯時(shí) 連接時(shí)或加載時(shí) 就可確定 就認(rèn)為該程序具有靜態(tài)并行性 動(dòng)態(tài)并行性 否則就認(rèn)為該程序具有動(dòng)態(tài)并行性 即意味著進(jìn)程要在運(yùn)行時(shí)創(chuàng)建和終止 12 2020 2 20 ProcessA beginZ 1fork B T foo 3 end ProcessB beginfork C X foo Z join C output X Y end ProcessC beginY foo Z end 開(kāi)發(fā)動(dòng)態(tài)并行性的一般方法 Fork Join 靜態(tài)和動(dòng)態(tài)并行性 3并行性問(wèn)題 Fork 派生一個(gè)子進(jìn)程Join 強(qiáng)制父進(jìn)程等待子進(jìn)程 13 2020 2 20 3 3進(jìn)程編組目的 支持進(jìn)程間的交互 常把需要交互的進(jìn)程調(diào)度在同一組中一個(gè)進(jìn)程組成員由 組標(biāo)識(shí)符 成員序號(hào)唯一確定 3 4劃分與分配原則 使系統(tǒng)大部分時(shí)間忙于計(jì)算 而不是閑置或忙于交互 同時(shí)不犧牲并行性 度 劃分 切割數(shù)據(jù)和工作負(fù)載分配 將劃分好的數(shù)據(jù)和工作負(fù)載映射到計(jì)算結(jié)點(diǎn) 處理器 上分配方式顯式分配 由用戶指定數(shù)據(jù)和負(fù)載如何加載隱式分配 由編譯器和運(yùn)行時(shí)支持系統(tǒng)決定就近分配原則 進(jìn)程所需的數(shù)據(jù)靠近使用它的進(jìn)程代碼 3并行性問(wèn)題 14 2020 2 20 并行度 DegreeofParallelism DOP 同時(shí)執(zhí)行的分進(jìn)程數(shù) 并行粒度 Granularity 兩次并行或交互操作之間所執(zhí)行的計(jì)算負(fù)載 指令級(jí)并行塊級(jí)并行進(jìn)程級(jí)并行任務(wù)級(jí)并行并行度與并行粒度大小?；榈箶?shù) 增大粒度會(huì)減小并行度 增加并行度會(huì)增加系統(tǒng) 同步 開(kāi)銷 3并行性問(wèn)題 15 2020 2 20 4交互 通信問(wèn)題 交互 進(jìn)程間的相互影響4 1交互的類型通信 兩個(gè)或多個(gè)進(jìn)程間傳送數(shù)的操作通信方式 共享變量父進(jìn)程傳給子進(jìn)程 參數(shù)傳遞方式 消息傳遞 16 2020 2 20 同步 導(dǎo)致進(jìn)程間相互等待或繼續(xù)執(zhí)行的操作同步方式 原子同步控制同步 路障 臨界區(qū) 數(shù)據(jù)同步 鎖 條件臨界區(qū) 監(jiān)控程序 事件 例子 原子同步parfor i 1 i n i atomic x x 1 y y 1 路障同步parfor i 1 i n i PibarrierQi 臨界區(qū)parfor i 1 i n i critical x x 1 y y 1 數(shù)據(jù)同步 信號(hào)量同步 parfor i 1 i n i lock S x x 1 y y 1 unlock S 4交互 通信問(wèn)題 17 2020 2 20 聚集 aggregation 用一串超步將各分進(jìn)程計(jì)算所得的部分結(jié)果合并為一個(gè)完整的結(jié)果 每個(gè)超步包含一個(gè)短的計(jì)算和一個(gè)簡(jiǎn)單的通信或 和同步 聚集方式 歸約掃描 交互的類型 4交互 通信問(wèn)題 例子 計(jì)算兩個(gè)向量的內(nèi)積parfor i 1 i n i X i A i B i inner product aggregate sum X i 18 2020 2 20 4 2交互的方式 4交互 通信問(wèn)題 相對(duì)于交互代碼C 可對(duì)進(jìn)程P定義如下?tīng)顟B(tài) 到達(dá) arrived P剛到達(dá)C 但還未進(jìn)入在內(nèi) in P在代碼中完成 finished P剛完成執(zhí)行代碼C 但還未離開(kāi)在外 out P不在代碼中 未到達(dá)或已離開(kāi) 同步的交互 所有參與者同時(shí)到達(dá)并執(zhí)行交互代碼C異步的交互 進(jìn)程到達(dá)C后 不必等待其它進(jìn)程到達(dá)即可執(zhí)行C 19 2020 2 20 交互方式與入口 出口條件的組合 4交互 通信問(wèn)題 鎖定的發(fā)送 消息已發(fā)完 但不一定已收到鎖定的接收 消息已收到非鎖定的發(fā) 收 只是發(fā)出發(fā) 收的請(qǐng)求 20 2020 2 20 4 3交互的模式按交互模式是否能在編譯時(shí)確定分為 靜態(tài)的動(dòng)態(tài)的按有多少發(fā)送者和接收者參與通信分為一對(duì)一 點(diǎn)到點(diǎn) pointtopoint 一對(duì)多 廣播 broadcast 播撒 scatter 多對(duì)一 收集 gather 歸約 reduce 多對(duì)多 全交換 TatalExchange 掃描 scan 置換 移位 permutation shift 4交互 通信問(wèn)題 21 2020 2 20 a 點(diǎn)對(duì)點(diǎn) 一對(duì)一 P1發(fā)送一個(gè)值給P3 b 廣播 一對(duì)多 P1發(fā)送一個(gè)值給全體 c 播撒 一對(duì)多 P1向每個(gè)結(jié)點(diǎn)發(fā)送一個(gè)值 d 收集 多對(duì)一 P1從每個(gè)結(jié)點(diǎn)接收一個(gè)值 4交互 通信問(wèn)題 22 2020 2 20 4交互 通信問(wèn)題 23 2020 2 20 相并行 PhaseParallel 分治并行 DivideandConquerParallel 流水線并行 PipelineParallel 主從并行 Master SlaveParallel 工作池并行 WorkPoolParallel 5五種并行編程風(fēng)范 24 2020 2 20 相并行 PhaseParallel 一組超級(jí)步 相 步內(nèi)各自計(jì)算步間通信 同步BSP 4 2 3 方便差錯(cuò)和性能分析計(jì)算和通信不能重疊 25 2020 2 20 主 從并行 Master SlaveParallel 主進(jìn)程 串行 協(xié)調(diào)任務(wù)子進(jìn)程 計(jì)算子任務(wù)劃分設(shè)計(jì)技術(shù) 6 1 與相并行結(jié)合主進(jìn)程易成為瓶頸 26 2020 2 20 分治并行 DivideandConquerParallel 父進(jìn)程把負(fù)載分割并指派給子進(jìn)程遞歸重點(diǎn)在于歸并分治設(shè)計(jì)技術(shù) 6 2 難以負(fù)載平衡 27 2020 2 20 流水線并行 PipelineParallel 一組進(jìn)程流水線作業(yè)流水線設(shè)計(jì)技術(shù) 6 5 28 2020 2 20 工作池并行 WorkPoolParallel 初始狀態(tài) 一件工作進(jìn)程從池中取任務(wù)執(zhí)行可產(chǎn)生新任務(wù)放回池中直至任務(wù)池為空易與負(fù)載平衡臨界區(qū)問(wèn)題 尤其消息傳遞 29 2020 2 20 8計(jì)算圓周率的樣本程序 30 2020 2 20 計(jì)算圓周率的c語(yǔ)言代碼段 defineN1000000main doublelocal pi 0 0 w longi w 1 0 N for i 0 i N i local i 0 5 w pi pi 4 0 1 0 local local printf piis f n pi w 31 2020 2 20 并行程序設(shè)計(jì)基礎(chǔ) 12 1并行程序設(shè)計(jì)概述12 2進(jìn)程12 3線程12 4同步12 5通信12 6并行程序設(shè)計(jì)模型 32 2020 2 20 進(jìn)程 進(jìn)程的基本概念進(jìn)程的并行執(zhí)行進(jìn)程的相互作用 33 2020 2 20 并行程序設(shè)計(jì)基礎(chǔ) 12 1并行程序設(shè)計(jì)概述12 2進(jìn)程12 3線程12 4同步12 5通信12 6并行程序設(shè)計(jì)模型 34 2020 2 20 線程 線程的基本概念線程的管理線程的同步 35 2020 2 20 并行程序設(shè)計(jì)基礎(chǔ) 12 1并行程序設(shè)計(jì)概述12 2進(jìn)程12 3線程12 4同步12 5通信12 6并行程序設(shè)計(jì)模型 36 2020 2 20 同步 原子和互斥高級(jí)同步結(jié)構(gòu)低級(jí)同步原語(yǔ) 37 2020 2 20 并行程序設(shè)計(jì)基礎(chǔ) 12 1并行程序設(shè)計(jì)概述12 2進(jìn)程12 3線程12 4同步12 5通信12 6并行程序設(shè)計(jì)模型 38 2020 2 20 通信 影響通信系統(tǒng)性能的因素低級(jí)通信支持TCP IP通信協(xié)議組簡(jiǎn)介 39 2020 2 20 并行程序設(shè)計(jì)基礎(chǔ) 12 1并行程序設(shè)計(jì)概述12 2進(jìn)程12 3線程12 4同步12 5通信12 6并行程序設(shè)計(jì)模型 40 2020 2 20 并行程序設(shè)計(jì)模型 隱式并行模型數(shù)據(jù)并行模型消息傳遞模型共享變量模型 41 2020 2 20 并行程序設(shè)計(jì)模型 隱式并行 ImplicitParallel 數(shù)據(jù)并行 DataParallel 共享變量 SharedVariable 消息傳遞 MessagePassing 42 2020 2 20 隱式并行 ImplicitParallel 概況 程序員用熟悉的串行語(yǔ)言編程編譯器或運(yùn)行支持系統(tǒng)自動(dòng)轉(zhuǎn)化為并行代碼特點(diǎn) 語(yǔ)義簡(jiǎn)單可移植性好單線程 易于調(diào)試