并行計(jì)算基礎(chǔ)

并行計(jì)算基礎(chǔ)第1頁，共47頁，2023年，2月20日，星期四本講主要內(nèi)容并行計(jì)算機(jī)體系結(jié)構(gòu)并行計(jì)算模型進(jìn)程線程并行編程環(huán)境編程語言與編譯器并行計(jì)算性能評(píng)測(cè)常用并行數(shù)值算法并行編譯器第2頁，共47頁，2023年，2月20日，星期四并行計(jì)算機(jī)體系結(jié)構(gòu)第3頁，共47頁，2023年，2月20日，星期四組成并行計(jì)算機(jī)的各個(gè)部分為：節(jié)點(diǎn)（node）：每個(gè)節(jié)點(diǎn)由多個(gè)處理器構(gòu)成，可以直接輸入輸出互聯(lián)網(wǎng)絡(luò)（interconnectnetwork）：所有節(jié)點(diǎn)通過互聯(lián)網(wǎng)絡(luò)相互連接通信。內(nèi)存（memory）：內(nèi)存由多個(gè)存儲(chǔ)模塊組成，這些模塊或者與節(jié)點(diǎn)對(duì)稱地分布在互聯(lián)網(wǎng)絡(luò)的兩側(cè)，或者位于各個(gè)節(jié)點(diǎn)的內(nèi)部第4頁，共47頁，2023年，2月20日，星期四并行計(jì)算機(jī)體系結(jié)構(gòu)示意圖，內(nèi)存模塊與節(jié)點(diǎn)分離第5頁，共47頁，2023年，2月20日，星期四并行計(jì)算機(jī)體系結(jié)構(gòu)示意圖，內(nèi)存模塊位于節(jié)點(diǎn)內(nèi)部

第6頁，共47頁，2023年，2月20日，星期四多級(jí)存儲(chǔ)體系結(jié)構(gòu)微處理器的峰值運(yùn)算速度每18個(gè)月翻一番內(nèi)存模塊的容量每年幾乎翻一番內(nèi)存模塊的訪問速度卻沒有得到平衡發(fā)展內(nèi)存的訪問速度要比處理器執(zhí)行速度慢很多內(nèi)存墻性能瓶頸 =〉多級(jí)存儲(chǔ)結(jié)構(gòu)第7頁，共47頁，2023年，2月20日，星期四多級(jí)存儲(chǔ)體系結(jié)構(gòu)第8頁，共47頁，2023年，2月20日，星期四并行計(jì)算機(jī)訪存模型UMA（UniformMemoryAccess）模型內(nèi)存模塊與節(jié)點(diǎn)分離，分別位于互聯(lián)網(wǎng)絡(luò)兩側(cè)物理存儲(chǔ)器被所有節(jié)點(diǎn)共享所有節(jié)點(diǎn)訪問任意存儲(chǔ)單元的時(shí)間相同發(fā)生訪存競爭時(shí)，仲裁策略平等對(duì)待每個(gè)節(jié)點(diǎn)各節(jié)點(diǎn)的CPU可帶有局部私有高速緩存外圍I/O設(shè)備也可以共享，且每個(gè)節(jié)點(diǎn)有平等的訪問權(quán)利第9頁，共47頁，2023年，2月20日，星期四并行計(jì)算機(jī)訪存模型NUMA（Non-UniformMemoryAccess）模型內(nèi)存模塊分布在各個(gè)節(jié)點(diǎn)內(nèi)部物理存儲(chǔ)器被所有節(jié)點(diǎn)共享，任意節(jié)點(diǎn)可以直接訪問任意內(nèi)存模塊節(jié)點(diǎn)訪問內(nèi)存模塊的速度不同發(fā)生訪存競爭時(shí)，仲裁策略對(duì)節(jié)點(diǎn)可能是不等價(jià)的各節(jié)點(diǎn)的CPU可帶有局部私有高速緩存外圍I/O設(shè)備也可以共享，但對(duì)各節(jié)點(diǎn)是不等價(jià)的第10頁，共47頁，2023年，2月20日，星期四并行計(jì)算機(jī)訪存模型COMA（Cache-OnlyMemoryAccess）模型各處理器節(jié)點(diǎn)中沒有存儲(chǔ)層次結(jié)構(gòu)利用分布的高速緩存目錄進(jìn)行遠(yuǎn)程高速緩存的訪問COMA中的高速緩存容量一般都大于2級(jí)高速緩存容量數(shù)據(jù)開始時(shí)可以任意分配，在運(yùn)行時(shí)它最終會(huì)被遷移到要用到它的地方第11頁，共47頁，2023年，2月20日，星期四并行計(jì)算機(jī)訪存模型NORMA（No-RemoteMemoryAccess）模型所有存儲(chǔ)器都是私有的絕大多數(shù)NORMA都不支持遠(yuǎn)程存儲(chǔ)器訪問第12頁，共47頁，2023年，2月20日，星期四

并行計(jì)算機(jī)系統(tǒng)的不同訪存模型分類

第13頁，共47頁，2023年，2月20日，星期四并行計(jì)算模型第14頁，共47頁，2023年，2月20日，星期四SIMD同步并行計(jì)算模型SIMD共享存儲(chǔ)模型；并行隨機(jī)存取機(jī)器假定存在著一個(gè)容量無限大的共享存儲(chǔ)器有有限或無限個(gè)功能相同的處理器均具有簡單的算術(shù)運(yùn)算和邏輯判斷功能在任何時(shí)刻各處理器均可通過共享存儲(chǔ)單元相互交換數(shù)據(jù)第15頁，共47頁，2023年，2月20日，星期四SIMD同步并行計(jì)算模型SIMD分布存儲(chǔ)模型，常見模型有：采用一維線性連接的SIMD模型采用網(wǎng)孔連接的SIMD模型采用樹形連接的SIMD模型采用樹網(wǎng)連接的SIMD模型采用立方連接的SIMD模型采用立方環(huán)連接的SIMD模型采用洗牌交換連接的SIMD模型采用多級(jí)互聯(lián)網(wǎng)絡(luò)連接的SIMD模型第16頁，共47頁，2023年，2月20日，星期四

MIMD異步并行計(jì)算模型異步PRAM模型每個(gè)處理器都有其本地存儲(chǔ)器、局部時(shí)鐘和局部程序處理器間的通信經(jīng)過共享全局存儲(chǔ)器無全局時(shí)鐘，各處理器異步地獨(dú)立執(zhí)行各自的指令處理器任何時(shí)間依賴關(guān)系需明確地在各處理器的程序中加入同步（路）障一條指令可在非確定但有限的時(shí)間內(nèi)完成第17頁，共47頁，2023年，2月20日，星期四MIMD異步并行計(jì)算模型BSP模型計(jì)算由一系列用全局同步分開的周期為L的超級(jí)步（superstep）組成在各超級(jí)步中:每個(gè)處理器均執(zhí)行局部計(jì)算通過路由器接受和發(fā)送消息然后做一全局檢查，以確定該超級(jí)步是否已由所有的處理器完成若是，則前進(jìn)到下一超級(jí)步否則下一L周期被分配給未曾完成的超級(jí)步第18頁，共47頁，2023年，2月20日，星期四MIMD異步并行計(jì)算模型LogP模型一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通信的多處理機(jī)模型其中通信網(wǎng)絡(luò)由一組參數(shù)來描述:L（Latency）表示消息從源到目的在網(wǎng)絡(luò)上的延遲o（overhead）表示處理器發(fā)送或接受一條消息消耗在網(wǎng)絡(luò)協(xié)議棧中的開銷g（Gap）表示處理器可連續(xù)進(jìn)行消息發(fā)送或接受的最小時(shí)間間隔P（Processor）表示處理器/存儲(chǔ)器模塊數(shù)

第19頁，共47頁，2023年，2月20日，星期四MIMD異步并行計(jì)算模型C3（Computation,Communication,Congestion）模型一個(gè)與體系結(jié)構(gòu)無關(guān)的粗粒度的并行計(jì)算模型強(qiáng)調(diào)用公用的通信操作來開發(fā)粗粒度的并行算法考慮到了網(wǎng)絡(luò)鏈路擁擠和處理器擁擠對(duì)并行算法性能的影響第20頁，共47頁，2023年，2月20日，星期四進(jìn)程第21頁，共47頁，2023年，2月20日，星期四進(jìn)程的定義進(jìn)程（process）可表示成四元組（P,C,D,S）P是程序代碼C是進(jìn)程的控制狀態(tài)D是進(jìn)程的數(shù)據(jù)S是進(jìn)程的執(zhí)行狀態(tài)第22頁，共47頁，2023年，2月20日，星期四進(jìn)程的狀態(tài)非存在狀態(tài)：進(jìn)程依賴的程序還沒有投入運(yùn)行就緒狀態(tài)：進(jìn)程由其父進(jìn)程調(diào)入并準(zhǔn)備運(yùn)行運(yùn)行狀態(tài)：進(jìn)程占有CPU和其它必須的計(jì)算資源，并執(zhí)行指令掛起狀態(tài)：由于CPU或其它必須的計(jì)算資源被其它進(jìn)程占有，或必須等待某類事件的發(fā)生，進(jìn)程轉(zhuǎn)入掛起狀態(tài)退出狀態(tài)：進(jìn)程正常結(jié)束或因異常退出而被廢棄第23頁，共47頁，2023年，2月20日，星期四進(jìn)程間通信進(jìn)程是操作系統(tǒng)資源調(diào)度的基本單位各進(jìn)程不能直接訪問其它進(jìn)程的局部內(nèi)存空間多個(gè)進(jìn)程之間相互交流信息的三種形式：通信：進(jìn)程間的數(shù)據(jù)傳遞稱為進(jìn)程間通信同步：同步是使位于相同或不同處理機(jī)中的多個(gè)進(jìn)程之間相互等待的操作聚集：聚集將位于相同或不同處理機(jī)中的多個(gè)進(jìn)程的局部結(jié)果綜合起來第24頁，共47頁，2023年，2月20日，星期四影響通信系統(tǒng)性能的因素通信硬件：包括節(jié)點(diǎn)存儲(chǔ)器、I/O結(jié)構(gòu)、網(wǎng)絡(luò)界面和通信網(wǎng)絡(luò)本身等通信軟件：包括通信協(xié)議結(jié)構(gòu)和算法等所提供的通信服務(wù)：包括消息傳送、流控、失效處理和保護(hù)等第25頁，共47頁，2023年，2月20日，星期四通信性能改進(jìn)BCL（BasicCommunicationLibrary）起著關(guān)鍵的作用三種有代表性的BCL：雙拷貝（2－Copy）單拷貝（1-Copy）零拷貝（Zero-Copy）第26頁，共47頁，2023年，2月20日，星期四線程第27頁，共47頁，2023年，2月20日，星期四線程將一個(gè)進(jìn)程分解成兩個(gè)部分：一部分由其資源特征構(gòu)成，仍稱之為進(jìn)程一部分由其執(zhí)行特征構(gòu)成，稱之為線程進(jìn)程可由單個(gè)線程來執(zhí)行進(jìn)程也可由多個(gè)線程來并行執(zhí)行多個(gè)線程將共享該進(jìn)程的所有資源特征第28頁，共47頁，2023年，2月20日，星期四線程單進(jìn)程多線程執(zhí)行示意圖

第29頁，共47頁，2023年，2月20日，星期四并行編程環(huán)境第30頁，共47頁，2023年，2月20日，星期四特征消息傳遞共享存儲(chǔ)數(shù)據(jù)并行典型代表MPI,PVMOpenMPHPF可移植性主流并行計(jì)算機(jī)SMP,DSMSMP,DSM,MPP并行粒度進(jìn)程級(jí)大粒度線程級(jí)細(xì)粒度進(jìn)程級(jí)細(xì)粒度并行操作方式異步異步松散同步數(shù)據(jù)存儲(chǔ)模式分布式存儲(chǔ)共享存儲(chǔ)共享存儲(chǔ)數(shù)據(jù)分配方式顯式隱式半隱式學(xué)習(xí)入門難度較難容易偏易可擴(kuò)展性好較差一般第31頁，共47頁，2023年，2月20日，星期四編程語言與編譯器第32頁，共47頁，2023年，2月20日，星期四自動(dòng)并行研究始于20世紀(jì)70年代的自動(dòng)向量化支持將程序移植到向量計(jì)算機(jī)上重要技術(shù)就是依賴分析搜索確定對(duì)同一數(shù)據(jù)結(jié)構(gòu)的哪些引用對(duì)是訪問同一存儲(chǔ)單元的第33頁，共47頁，2023年，2月20日，星期四HPF：數(shù)據(jù)并行編程思想：使數(shù)據(jù)管理的多數(shù)細(xì)節(jié)自動(dòng)并行化它提供了一個(gè)指令集用戶可在程序中插入指令，以描述數(shù)據(jù)布局HPF提供了注釋形式的指令來擴(kuò)展變量類型的說明，能夠?qū)?shù)組的數(shù)據(jù)布局進(jìn)行相當(dāng)詳細(xì)的控制第34頁，共47頁，2023年，2月20日，星期四OpenMP：共享存儲(chǔ)并行編程一個(gè)與FORTRAN77和C綁定的非正式并行編程接口OpenMP指令在單機(jī)編譯器上被當(dāng)作注釋而忽略O(shè)penMP提供鎖變量用于線程間的細(xì)粒度同步在多處理機(jī)工作站機(jī)群上，OpenMP通常和MPI同時(shí)使用，OpenMP用于節(jié)點(diǎn)內(nèi)，MPI用于節(jié)點(diǎn)間的消息傳遞第35頁，共47頁，2023年，2月20日，星期四并行計(jì)算性能評(píng)測(cè)第36頁，共47頁，2023年，2月20日，星期四并行程序執(zhí)行時(shí)間 從并行程序開始執(zhí)行到所有進(jìn)程執(zhí)行完畢，墻上時(shí)鐘走過的時(shí)間，包括下面幾個(gè)部分：計(jì)算CPU時(shí)間：進(jìn)程指令執(zhí)行所花費(fèi)的CPU時(shí)間通信CPU時(shí)間：進(jìn)程通信花費(fèi)的CPU時(shí)間同步開銷時(shí)間：進(jìn)程同步花費(fèi)的時(shí)間進(jìn)程空閑時(shí)間：當(dāng)一個(gè)進(jìn)程阻塞式等待其他進(jìn)程的消息時(shí)，CPU通常是空閑的第37頁，共47頁，2023年，2月20日，星期四加速比性能定律并行加速比：指對(duì)于一個(gè)給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對(duì)于串行算法（或串行程序）的執(zhí)行速度加快了多少倍參數(shù)定義：p是并行系統(tǒng)中的處理器數(shù)W是問題規(guī)模Ws是應(yīng)用程序中的串行分量，Wp為W中可并行化部分f是串行分量比例Ts=T1為串行執(zhí)行時(shí)間，Tp為并行執(zhí)行時(shí)間S為加速比，E為效率第38頁，共47頁，2023年，2月20日，星期四Amdahl定律隨著處理器數(shù)目的無限增大，并行系統(tǒng)所能達(dá)到的加速上限為1/f

第39頁，共47頁，2023年，2月20日，星期四Gustafson定律歸一化后可得

隨著處理器數(shù)目的增加，加速幾乎與處理器數(shù)成比例的線性增加第40頁，共47頁，2023年，2月20日，星期四Sun和Ni定律基本思想：只要存儲(chǔ)空間許可，應(yīng)盡可能增大問題規(guī)模以產(chǎn)生更好或更精確的解

第41頁，共47頁，2023年，2月20日，星期四并行程序性能評(píng)價(jià)方法浮點(diǎn)峰值性能與實(shí)際浮點(diǎn)性能浮點(diǎn)峰值性能=CPU內(nèi)部浮點(diǎn)乘加指令流水線的條數(shù)╳每條流水線每個(gè)時(shí)鐘周期完成的浮點(diǎn)運(yùn)算次數(shù)╳處理器主頻數(shù)值效率和并行效率第42頁，共47頁，2023年，2月20日，星期四程序性能優(yōu)化第43頁，共47頁，2023年，2月20日，星期四串行程序性能優(yōu)化調(diào)用高性能庫選擇適當(dāng)?shù)木幾g器優(yōu)化選項(xiàng)合理定義數(shù)組維數(shù)注意嵌套循環(huán)的順序數(shù)據(jù)分塊