并行計算基礎

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

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

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

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

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

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

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

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

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

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