高性能計算之并行編程技術

1、高性能計算之并行編程技術,報 告 人：單 位： E - Mail：,2017年6月9日,周兆永網(wǎng)絡與教育技術中心yzz@nwsuaf.edu.cn,六、CPU/GPU/TPU概述,一、并行編程基礎知識,五、行計算優(yōu)化,四、Python并發(fā)編程方式,三、MPI程序分析及編程入門,二、MPI編程實例演示,,,,,,,,,提 綱,一、并行編程基礎知識,節(jié)點（node）：每個節(jié)點由多個處理器構成，可以直接輸入輸出互聯(lián)

2、網(wǎng)絡（interconnect network）：所有節(jié)點通過互聯(lián)網(wǎng)絡相互連接通信。內(nèi)存 （memory）：內(nèi)存由多個存儲模塊組成，這些模塊或者與節(jié)點對稱地分布在互聯(lián)網(wǎng)絡的兩側(cè)，或者位于各個節(jié)點的內(nèi)部,并行計算機組成部分,內(nèi)存模塊位于節(jié)點內(nèi)部,并行計算機體系結(jié)構,內(nèi)存模塊與節(jié)點分離,一、并行編程基礎知識,一、并行編程基礎知識,一、并行編程基礎知識,程序：實現(xiàn)特定目標或解決特定問題而用計算機語言編寫的命令序列的集合，或者稱之為：算法

3、+數(shù)據(jù)結(jié)構。進程：可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運行過程。進程是程序的一次執(zhí)行；進程可以是和別的計算并發(fā)執(zhí)行的計算；進程可以定義為一個數(shù)據(jù)結(jié)構及其能在其上進行操作的一個程序；進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動；進程是程序在一個數(shù)據(jù)集合上的運行過程，是系統(tǒng)進行資源分配和調(diào)度的獨立單位。線程：線程是進程中的一個實體，是被系統(tǒng)獨立調(diào)度和分派的基本單位。線程自己基本不擁有系統(tǒng)資源，只擁有一點在運行中必不可少

4、的資源（如程序計數(shù)器、一組寄存器和堆棧），但他與同屬于一個進程中的其他線程共享進程所擁有的全部資源。,兩個重要概念：進程與線程,一、并行編程基礎知識,并行編程通常是指軟件代碼，它促進在同一時間執(zhí)行多個計算任務的性能。For example：操場上有20個滑梯而不是一個。孩子們不必排隊等待輪到自己，因為他們可以同時玩。使用電腦鼠標，一邊聽音樂，一邊寫畢業(yè)論文，同時對個人電腦做病毒掃描，這唯一的理由就是并發(fā)編程。在這種情況下，它的多

5、重任務允許多個程序或進程訪問CPU而沒有等待。這一設置允許使用多任務共享的資源進行密集的I/O處理和有效的信號處理。并發(fā)性也可以通過實施多個計算線程發(fā)生(通常采用交錯啟動和完成點)。這叫做多線程，并且它發(fā)生在一個單一的進程或程序中。這就是為什么你可以打印一個文檔，同時繼續(xù)編輯另一個文檔。如果沒有多線程，UI會太慢,因為系統(tǒng)將無法在同一時間應對多個用戶操作。,并行編程概述,一、并行編程基礎知識,并行編程模式，主要指并行編程時，程序員將程

6、序各模塊并行執(zhí)行時，模塊間的通信方式，目前并行編程模式主要包括以下三種：共享內(nèi)存：共享內(nèi)存是進程間傳遞數(shù)據(jù)的一種高效方法。在共享內(nèi)存模型中，并行進程共享一個進行異步讀取的全局地址空間。異步并發(fā)訪問可能導致條件競爭，因此需要同步機制來避免條件競爭，這些機制包括鎖，信號量，管程（monitor）。傳統(tǒng)的多核處理器是直接支持共享內(nèi)存的，所以導致很多利用該特性的語言和庫出現(xiàn)，以OpenMP為代表；消息傳遞：在消息傳遞模型中，并行進程是通過消

7、息傳遞來交換數(shù)據(jù)的。這些通信可以是異步的，即消息可以在接收者做好準備前發(fā)送，也可以是同步的，即只有接受者準備好接收消息時才能發(fā)送。消息傳遞的CSP（Communicating sequential processes）模型使用同步通信channel來連接進程，以MPI,PVM為代表；數(shù)據(jù)并行模式：數(shù)據(jù)并行化關注在數(shù)據(jù)集上執(zhí)行的操作。一組任務對數(shù)據(jù)集進行運算，但是會對不同的分區(qū)進行運算，以Fortran為代表。,并行編程模式,一、并行編

8、程基礎知識,Massage Passing Interface:是消息傳遞函數(shù)庫的標準規(guī)范；由MPI論壇開發(fā).支持Fortran、C和C++；一種新的庫描述, 不是一種語言。,什么是MPI?,消息傳遞并行程序設計用戶必須通過顯式地發(fā)送和接收消息來實現(xiàn)處理機間的數(shù)據(jù)交換。每個并行進程均有自己獨立的地址空間，相互之間訪問不能直接進行，必須通過顯式的消息傳遞來實現(xiàn)。這種編程方式是大規(guī)模并行處理機（MPP）和機群（Cluster）采用

9、的主要編程方式。并行計算粒度大，特別適合于大規(guī)模可擴展并行算法由于消息傳遞程序設計要求用戶很好地分解問題,組織不同進程間的數(shù)據(jù)交換,并行計算粒度大,特別適合于大規(guī)?？蓴U展并行算法.消息傳遞是當前并行計算領域的一個非常重要的并行程序設計方式,一、并行編程基礎知識,下面我們以C語言的形式給出一個最簡單的MPI并行程序Hello (下頁).該程序在終端打印出Hello World!字樣.“Hello World”:一聲來自新生兒的問

10、候.,二、MPI編程實例演示,從簡單入手！,Hello world (C),#include #include "mpi.h“main( int argc, char *argv[] ){ MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize();},二、MPI編程實例

11、演示,Hello world (Fortran),二、MPI編程實例演示,program maininclude ‘mpif.h’integer ierrcall MPI_INIT( ierr )print *, 'Hello, world!'call MPI_FINALIZE( ierr )end,MPI程序的的編譯與運行,mpicc –o hello hello.c生成hello的可執(zhí)行代碼.

12、mpirun –np 4 hello4 指定np的實參,表示進程數(shù),由用戶指定.hello 要運行的MPI并行程序.,,,%小寫o,,np: The number of process.,,二、MPI編程實例演示,SPMD: Single Program Multiple Data(MIMD) ::::,#include "mpi.h"#include

13、main( int argc, char *argv[] ){ MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize();},#include "mpi.h"#include main( int argc, char *argv[] ){

14、 MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize();},#include "mpi.h"#include main( int argc, char *argv[] ){ MPI_Init( &argc, &argv );

15、printf( "Hello, world!\n" ); MPI_Finalize();},#include "mpi.h"#include main( int argc, char *argv[] ){ MPI_Init( &argc, &argv ); printf( "Hello, world!\n" );

16、 MPI_Finalize();},,,,Hello World!Hello World!Hello World!Hello World!,,,#include "mpi.h"#include main( int argc, char *argv[] ){ MPI_Init( &argc, &argv ); printf( "Hello, worl

17、d!\n" ); MPI_Finalize();},,Hello是如何被執(zhí)行的?,三、MPI程序分析及編程入門,C必須包含mpi.h.MPI 函數(shù)返回出錯代碼或 MPI_SUCCESS成功標志.MPI-前綴，且只有MPI以及MPI_標志后的第一個字母大寫，其余小寫.MPI函數(shù)的參數(shù)被標志為以下三種類型：IN：參數(shù)在例程的調(diào)用中不會被修正.OUT：參數(shù)在例程的調(diào)用中可能會被修正.INOUT：參數(shù)在一些例程

18、中為IN，而在另一些例程中為OUT.,C語言中MPI函數(shù)約定,三、MPI程序分析及編程入門,在寫MPI程序時，我們通常需要知道以下兩個問題的答案：任務由多少個進程來進行并行計算？我是哪一個進程?,開始寫MPI并行程序,三、MPI程序分析及編程入門,開始寫MPI并行程序,MPI 提供了下列函數(shù)來回答這些問題：用MPI_Comm_size 獲得進程個數(shù)pint MPI_Comm_rank(MPI_Comm comm, int

19、*rank);用MPI_Comm_rank 獲得進程的一個叫rank的值，該 rank值為0到p-1間的整數(shù),相當于進程的IDint MPI_Comm_size(MPI_Comm comm, int *size);,三、MPI程序分析及編程入門,MPI基本函數(shù),int MPI_Init (int*argc /* in/out */,char** argv[] /* in/out */)通常應該是

20、第一個被調(diào)用的MPI函數(shù)除MPI_Initialized()外，其余所有的MPI函數(shù)應該在其后被調(diào)用MPI系統(tǒng)將通過argc,argv得到命令行參數(shù),三、MPI程序分析及編程入門,MPI基本函數(shù),int MPI_Finalize (void) 退出MPI系統(tǒng)，所有進程正常退出都必須調(diào)用。表明并行代碼的結(jié)束,結(jié)束除主進程外其它進程.串行代碼仍可在主進程(rank = 0)上運行，但不能再有MPI函數(shù)（包括MPI_Init()）,三

21、、MPI程序分析及編程入門,MPI基本函數(shù),int MPI_Comm_size (MPI_Comm comm /* in */,int* size /* out */)獲得進程個數(shù) size指定一個通信子,也指定了一組共享該空間的進程, 這些進程組成該通信子的group.獲得通信子comm中規(guī)定的group包含的進程的數(shù)量.,三、MPI程序分析及編程入門,MPI基本

22、函數(shù),int MPI_Comm_rank (MPI_Comm comm /* in */, int* rank /* out */)得到本進程在通信空間中的rank值,即在組中的邏輯編號(該rank值為0到p-1間的整數(shù),相當于進程的ID)。,三、MPI程序分析及編程入門,MPI程序的基本結(jié)構,#include "mpi.h"... ...int main(int ar

23、gc, char *argv[]){int myrank, nprocs;MPI_Init(&argc,&argv);MPI_Comm_size(MPI_COMM_WORLD,&nprocs);MPI_Comm_rank(MPI_COMM_WORLD,&myrank);... ...MPI_Finalize();},三、MPI程序分析及編程入門,更新的Hello World (

24、c),#include #include "mpi.h"main( int argc, char *argv[] ){ int myid, numprocs; MPI_Init( &argc, &argv ); MPI_Comm_rank( MPI_COMM_WORLD, &myid ); MPI_Comm_size( MPI_COMM_WORLD, &am

25、p;numprocs ); printf(“I am %d of %d\n", myid, numprocs ); MPI_Finalize();},三、MPI程序分析及編程入門,mpicc –o hello1 hello1.cmpirun -np 4 hello1I am 0 of 4I am 1 of 4I am 2 of 4I am 3 of 4,,,更新后的的Hello World 的允許結(jié)果,

26、三、MPI程序分析及編程入門,MPI調(diào)用借口的總數(shù)雖然龐大，但根據(jù)實際編寫MPI的經(jīng)驗，常用的MPI調(diào)用的個數(shù)確什么有限。下面是6個最基本的MPI函數(shù)。MPI_Init(…);MPI_Comm_size(…);MPI_Comm_rank(…);MPI_Send(…);MPI_Recv(…);MPI_Finalize();,MPI_Init(…);…并行代碼;…MPI_Fainalize();只能有串行代碼;,,最基

27、本的MPI,三、MPI程序分析及編程入門,SPMD 編程模式：構成一個程序的所有進程運行的是同一份執(zhí)行代碼. 不同進程根據(jù)自己的序號可能執(zhí)行該代碼中的不同分支. MPI 編程中最常用的編程方式. 用戶只需要編寫、維護一份源代碼.MPMD 編程模式：構成一個程序的不同進程運行不同的執(zhí)行代碼. 用戶需要編寫、維護多份源代碼.主/從編程模式：它是MPMD 編程模式的一個特例, 也是MPMD 編程模式中最常見的方式. 構成一個程序的進程之一

28、負責所有進程間的協(xié)調(diào)及任務調(diào)度, 該進程稱為主進程(Master), 其余進程稱為從進程(Slave). 通常用戶需要維護兩份源代碼.,MPI編程模式,三、MPI程序分析及編程入門,MPI程序設計方法,明確并行任務設計單個任務的串行程序所有任務的統(tǒng)一表示--SPMD并行程序,,,,,,,,SPMD,三、MPI程序分析及編程入門,線程（Thread）進程 （Process）遠程分布式主機 （Distributed Node）偽線

29、程 （Pseudo－Thread）,Python并發(fā)編程四種方式,四、Pyhon并發(fā)編程方式,多線程幾乎是每一個程序猿在使用每一種語言時都會首先想到用于解決并發(fā)的工具（JS程序員請回避），使用多線程可以有效的利用CPU資源（Python例外）。然而多線程所帶來的程序的復雜度也不可避免，尤其是對競爭資源的同步問題。然而在python中由于使用了全局解釋鎖（GIL）的原因，代碼并不能同時在多核上并發(fā)的運行，也就是說，Python的多線程不能

30、并發(fā)，很多人會發(fā)現(xiàn)使用多線程來改進自己的Python代碼后，程序的運行效率卻下降了。實際上使用多線程的編程模型是很困難的，程序員很容易犯錯，這并不是程序員的錯誤，因為我們大多數(shù)人的思維是串行（精神分裂不討論），且馮諾依曼設計的計算機架構也是以順序執(zhí)行為基礎的。Python提供兩組線程的接口，一組是thread模塊，提供基礎的，低等級（Low Level）接口，使用Function作為線程的運行體。還有一組是threading模塊，提

31、供更容易使用的基于對象的接口（類似于Java），可以繼承Thread對象來實現(xiàn)線程，還提供了其它一些線程相關的對象，例如Timer，Lock。,線程（Thread）,四、Pyhon并發(fā)編程方式,由于python的全局解釋鎖問題，Python下比較好的并行方式是使用多進程，這樣可以非常有效的使用CPU資源，并實現(xiàn)真正意義上的并發(fā)。當然，進程的開銷比線程要大，也就是說如果你要創(chuàng)建數(shù)量驚人的并發(fā)進程的話，需要考慮一下你的機器是不是有一顆強大的

32、心。由于線程共享相同的地址空間和內(nèi)存，所以線程之間的通信是非常容易的，然而進程之間的通信就要復雜一些了。常見的進程間通信有：管道，消息隊列，Socket接口（TCP/IP）等等。Python的mutliprocess模塊提供了封裝好的管道和隊列，可以方便的在進程間傳遞消息。Python進程間的同步使用鎖，這一點和線程是一樣的。Python還提供了進程池Pool對象，可以方便管理和控制線程。python的mutliprocess

33、模塊和threading具有類似的接口。,線程（Thread）,四、Pyhon并發(fā)編程方式,隨著大數(shù)據(jù)時代的到臨，摩爾定理在單機上似乎已經(jīng)失去了效果，數(shù)據(jù)的計算和處理需要分布式的計算機網(wǎng)絡來運行，程序并行的運行在多個主機節(jié)點上，已經(jīng)是現(xiàn)在的軟件架構所必需考慮的問題。遠程主機間的進程間通信有幾種常見的方式（1）TCP／IP：TCP／IP是所有遠程通信的基礎，然而API比較低級別，使用起來比較繁瑣，所以一般不會考慮（2）遠程方法調(diào)用

34、Remote Function Call：RPC是早期的遠程進程間通信的手段。Python下有一個開源的實現(xiàn)RPyC（3）遠程對象 Remote Object：遠程對象是更高級別的封裝，程序可以想操作本地對象一樣去操作一個遠程對象在本地的代理。遠程對象最廣為使用的規(guī)范CORBA，（4）消息隊列 Message Queue：比起RPC或者遠程對象，消息是一種更為靈活的通信手段，常見的支持Python接口的消息機制有,遠程分布

35、式主機（Distributed Node）,四、Pyhon并發(fā)編程方式,還有一種并發(fā)手段并不常見，我們可以稱之為偽線程，就是看上去像是線程，使用的接口類似線程接口，但是實際使用非線程的方式，對應的線程開銷也不存在的。greenlet提供輕量級的coroutines來支持進程內(nèi)的并發(fā)。,偽線程（Pseudo－Thread）,四、Pyhon并發(fā)編程方式,決定性能調(diào)優(yōu)上限的兩個定律：阿曼達定律和Gustafson定律;系統(tǒng)的性能遵循木桶原

36、理，也就是整體性能是由系統(tǒng)中最短的那塊板決定;整個優(yōu)化應該采用自上而下的方法，順序一定不能亂。,并行調(diào)優(yōu)需要注意的方面,五、并行計算優(yōu)化,首先通過標準性能基準測試程序確保系統(tǒng)的工作狀態(tài)正常， 比如使用SpecInt， SpecFP，Linpack等得到處理器的性能，對比設計性能指標，可以得知CPU是否工作正常，BIOS或者操作系統(tǒng)中的相關設置是否正確。使用Stream測試程序測試內(nèi)存系統(tǒng)的性能，Netperf測試網(wǎng)絡性能，F(xiàn)io或者i

37、ozone等測試文件系統(tǒng)性能是否正常。在所有調(diào)優(yōu)開始之前，一定要先把基礎做好，一定要了解你的系統(tǒng)性能極限；再來是應用調(diào)優(yōu)，可以調(diào)節(jié)運行環(huán)境，或者有代碼的可以調(diào)整代碼；最后才會到處理器級別的調(diào)優(yōu)，這里是榨干最后一滴性能的地方。,如何自上而下并行調(diào)優(yōu),五、并行計算優(yōu)化,36/122,（一）硬件級：性能優(yōu)化的方法有很多種，第一個叫硬件級調(diào)優(yōu)，就是簡單粗暴直接換掉性能低的硬件，比如網(wǎng)卡千兆換到萬兆，硬盤從機械的換成SSD等等。很多時候這也不

38、失為一個好辦法。（二）運行級：所謂運行級調(diào)優(yōu)，從運行環(huán)境上調(diào)整，通過監(jiān)控整個系統(tǒng)的性能及各項指標看問題所在，然后看能不能通過一些運行參數(shù)的調(diào)整，比如說內(nèi)存的使用率非常高，可以試試在操作系統(tǒng)中調(diào)整內(nèi)存頁的大小。如果是網(wǎng)絡帶寬壓力特別大，可以試試將網(wǎng)絡包的處理程序綁定在某一個核上面。對于網(wǎng)絡小包特別多的情況，有一些網(wǎng)卡帶包聚合功能，等很多小包會聚合到一定的程度，再統(tǒng)一處理，大量減少中斷數(shù)量，降低系統(tǒng)消耗。這些調(diào)整的成本很低，難點在于對技術

39、人員要求很高，需要對整個系統(tǒng)非常熟。,并行計算系統(tǒng)性能調(diào)優(yōu)方法分類,五、并行計算優(yōu)化,（三）編譯器級：編譯器級調(diào)優(yōu)，需要有代碼，但是不修改代碼，使用編譯器的優(yōu)化選項，有的時候也能夠獲得巨大的性能提高。比如引入自動向量化，深度優(yōu)化，性能剖析指導的優(yōu)化（PGO）等等。需要技術人員熟悉編譯的使用，以及對優(yōu)化過程的理解。（四）代碼級：代碼級調(diào)優(yōu)就是直接改動實現(xiàn)代碼，改代碼收益或許非常大，比如換個算法，因為有的算法就是比別的算法快很多倍，甚至快

40、幾個數(shù)量級，但是修改的難度極其大，成本極高，代碼改了以后正確性要重新驗證，所有測試的步驟都要做。在原有串行單線程程序中，如果有比較明顯的計算密集型循環(huán)，可以引入OpenMPI進行并行化，結(jié)合編譯器的自動向量化編譯選項，可以只改極小一部分代碼，獲得比較大的性能收益。在性能調(diào)優(yōu)中常用的一些關鍵指標：系統(tǒng)性能指標包括CPU利用率、內(nèi)存使用率，swap分區(qū)、帶寬使用率；處理器性能指標包括CPI、浮點運算的峰值、向量化比例、cache mis

41、s、DTLB miss等。,五、并行計算優(yōu)化,并行計算系統(tǒng)性能調(diào)優(yōu)方法分類,11.串行代碼優(yōu)化從以下幾個角度分析：系統(tǒng)級：需要分析出性能控制因素，例如網(wǎng)速，利用率，負載均衡。如果CPU使用率不高且很穩(wěn)定，則需要優(yōu)化內(nèi)存帶寬，若CPU使用率忽上忽下，則需要考慮其他進程占用CPU。當然，CPU大多時候空閑，說明沒有很大程度上發(fā)揮硬件計算能力，或者，訪問帶寬太小，或者CPU在等待其他進程，線程釋放資源等。應用級別：通常有編譯選項，調(diào)用高性

42、能庫，去掉全局變量等;算法級：函數(shù)級，循環(huán)級，語句級，指令級。??,代碼級調(diào)優(yōu)之串行代碼優(yōu)化,五、并行計算優(yōu)化,CPU、GPU、TPU的區(qū)別,六、CPU/GPU/TPU概述,TPU—張量處理器Tensor Processing Unit,CPU—央處理器Central Processing Unit,GPU—圖形處理器Graphics Processing Unit,CPU vs GPU,六、CPU/GPU/TPU概述,什么類

43、型的程序適合在GPU上運行？,六、CPU/GPU/TPU概述,計算密集型的程序。所謂計算密集型(Compute-intensive)的程序，就是其大部分運行時間花在了寄存器運算上，寄存器的速度和處理器的速度相當，從寄存器讀寫數(shù)據(jù)幾乎沒有延時。可以做一下對比，讀內(nèi)存的延遲大概是幾百個時鐘周期；讀硬盤的速度就不說了，即便是SSD, 也實在是太慢了。易于并行的程序。GPU其實是一種SIMD(Single Instruction Multip

44、le Data)架構， 他有成百上千個核，每一個核在同一時間最好能做同樣的事情?！　M足以上兩點，可以考慮采用GPU做運算。 不過需要先用CUDA或者Open CL 在GPU上進行編程， 較為麻煩。 而且GPU的架構比較特殊，要想寫出高效率的程序，需要進一步深入研究。,有關并行編程的部分參考書目,六、CPU/GPU/TPU概述,黃鎧,徐志偉著,陸鑫達等譯. 可擴展并行計算技術,結(jié)構與編程. 北京:機械工業(yè)出版社, P.33~56,P.

45、227~237, 2000.陳國良著.并行計算—結(jié)構、算法、編程. 北京:高等教育出版社,1999.Barry Wilkinson and Michael Allen. Parallel Programming(Techniques and Applications using Networked Workstations and Parallel Computers). Prentice Hall, 1999.李曉梅,莫則堯等著