并行計算基礎(chǔ)

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

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

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

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

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

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

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

第三十九頁，共四十七頁，2022年，8月28日Gustafson定律歸一化后可得

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

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