第2章第1節(jié)2004年11月25日

1、哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院并行處理與體系結(jié)構(gòu)并行處理與體系結(jié)構(gòu)哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院第第2 2章章 并行并行編程基礎(chǔ)編程基礎(chǔ)n 1 1 并行編程綜述并行編程綜述n 2 2 進程任務(wù)和線程進程任務(wù)和線程n 3 3 并行性問題并行性問題n 4 4 交互和通信問題交互和通信問題哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院 1 并行編程綜述并行編程綜述n并行編程處于令人遺憾的狀況：并行編程處于令人遺憾的狀況：q并行軟件開發(fā)遠落后于并行硬件的進展。并行軟件開發(fā)遠落后于并行硬件的進展。缺少合適的并行軟件是阻礙主流用戶接缺少合適的并行軟件是阻礙主流用戶接納并行計算的主要原因。納并行計算的主要原因。

2、 q與順序計算相比，當(dāng)今的并行系統(tǒng)軟件與順序計算相比，當(dāng)今的并行系統(tǒng)軟件和應(yīng)用軟件不僅數(shù)量很少和應(yīng)用軟件不僅數(shù)量很少, ,而且功能性也而且功能性也相當(dāng)原始。相當(dāng)原始。 n隧道之末總有陽光。隧道之末總有陽光。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院一、一、并行編程緣何艱難并行編程緣何艱難n在并行編程中有許多不同的模型。是在并行編程中有許多不同的模型。是一個更復(fù)雜的智力活動。一個更復(fù)雜的智力活動。n并行程序的編譯器、調(diào)試程序、以及并行程序的編譯器、調(diào)試程序、以及特征分析器特征分析器(profiler)(profiler)要比串行程序要比串行程序落后得多。落后得多。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院哈爾濱

3、工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n1.1.順序編程順序編程q長期以來已建立了許多算法范例長期以來已建立了許多算法范例q一些實現(xiàn)指導(dǎo)用戶從事算法設(shè)計。一些實現(xiàn)指導(dǎo)用戶從事算法設(shè)計。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.2.并行編程并行編程 n并行編程處于初級階段；并行編程處于初級階段；q對于并行問題的應(yīng)用，不太可對于并行問題的應(yīng)用，不太可能有一個現(xiàn)成的并行代碼；能有一個現(xiàn)成的并行代碼；q并行代碼的機器不同。并行代碼的機器不同。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院q并行編程也不支持成熟、通用和穩(wěn)并行編程也不支持成熟、通用和穩(wěn)定的工具；定的工具；q并行算法范例仍未能被很好地理解并行算法范例仍未能被很好地理

4、解或被廣泛地接受；或被廣泛地接受；q不存在單一、通用的機器模型；不存在單一、通用的機器模型；q并行編程的模型有兩級，而在每一并行編程的模型有兩級，而在每一級上又有許多不同模型。級上又有許多不同模型。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院q與順序語言在編程或自然模型級上與順序語言在編程或自然模型級上缺少代可擴展和異構(gòu)可擴展的能力缺少代可擴展和異構(gòu)可擴展的能力n這些并行語言大多數(shù)在當(dāng)前系統(tǒng)上使這些并行語言大多數(shù)在當(dāng)前系統(tǒng)上使用的并行語言均是用的并行語言均是FortranFortran或或C C的某種的某種擴展。擴展。q一個編程模型即是程序員在開發(fā)一一個編程模型即是程序員在開發(fā)一個并行程序時所見到和使用

5、的模型。個并行程序時所見到和使用的模型。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院q一個自然模型是由一個特定并行計算機平一個自然模型是由一個特定并行計算機平臺所提供的、用戶可見的最低層的編程模臺所提供的、用戶可見的最低層的編程模型。其他的編程模型可在此自然模型上加型。其他的編程模型可在此自然模型上加以實現(xiàn)。以實現(xiàn)。n例如，在一個例如，在一個SGI SGI PowerChallengePowerChallenge計算機上計算機上( (它是它是SMP)SMP)， 自然模型為共享變量模型自然模型為共享變量模型( (如如SGIPowerCSGIPowerC) )。n數(shù)據(jù)并行數(shù)據(jù)并行( (如如HPF)HPF)和

6、消息傳送和消息傳送( (如如MPlMPl) )可在其可在其頂部實現(xiàn)。頂部實現(xiàn)。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院3.3.并行編程進展并行編程進展n盡管以上的回顧較為悲觀，但在并行盡管以上的回顧較為悲觀，但在并行編程領(lǐng)域已有了許多進步：編程領(lǐng)域已有了許多進步：n已開發(fā)了許多并行算法。已開發(fā)了許多并行算法。q盡管大多數(shù)算法基于非現(xiàn)實的盡管大多數(shù)算法基于非現(xiàn)實的PRAMPRAM模型，模型，但其中某些在作適當(dāng)修正后可以實用。但其中某些在作適當(dāng)修正后可以實用。n已涌現(xiàn)一小批簡單的并行算法范例，已涌現(xiàn)一小批簡單的并行算法范例，且已逐步為用戶所接受。且已逐步為用戶所接受。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n

7、自然模型正集中趨向于兩種模型：自然模型正集中趨向于兩種模型：q適用于適用于PVPPVP、SMPSMP和和DSMDSM的單地址空間的單地址空間的共享變量模型；的共享變量模型；q適用于適用于MPPMPP和機群的多地址空間的消和機群的多地址空間的消息傳遞模型。息傳遞模型。qSIMDSIMD模型已從主流、通用并行計算模型已從主流、通用并行計算機淡出，但對于如同語言、圖象和機淡出，但對于如同語言、圖象和多媒體處理的專用嵌入式應(yīng)用仍非多媒體處理的專用嵌入式應(yīng)用仍非常有用常有用。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n高層并行編程模型高層并行編程模型 趨向于趨向于3 3種標(biāo)準(zhǔn)模型：種標(biāo)準(zhǔn)模型：q數(shù)據(jù)并行數(shù)據(jù)并行

8、( (如如HPF)HPF)、q消息傳遞消息傳遞( (如如HPVMHPVM和和MPlMPl) )q共享變量共享變量( (如如HANSI X3H5)HANSI X3H5)。 此外還有一種模型此外還有一種模型-串轉(zhuǎn)并；串轉(zhuǎn)并；q用戶只需編寫順序程序，其中的蘊式并行用戶只需編寫順序程序，其中的蘊式并行性由并行化編譯器性由并行化編譯器( (如如KapKap) )進行析取進行析取。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n4.4.吞吐率處理吞吐率處理 n在一個問題的處理上在一個問題的處理上, ,并行少并行少, ,串行串行多。多。n增加多個獨立順序作業(yè)的系統(tǒng)吞吐增加多個獨立順序作業(yè)的系統(tǒng)吞吐率。率。q順序程序并行

9、系統(tǒng)順序程序并行系統(tǒng)(SPPS)(SPPS)模型，也稱模型，也稱為吞吐率處理。為吞吐率處理。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n二、并行編程環(huán)境二、并行編程環(huán)境n1. 1. 一個典型的并行處理系統(tǒng)一個典型的并行處理系統(tǒng)n如圖所示的結(jié)構(gòu)如圖所示的結(jié)構(gòu)n無論是算法還是源代碼均需顯式地并無論是算法還是源代碼均需顯式地并行化。行化。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n編譯器將源代碼翻譯成二進制代碼編譯器將源代碼翻譯成二進制代碼在并行平臺上運行，在并行平臺上運行，q該平臺包含操作系統(tǒng)和在它之下的并該平臺包含操作系統(tǒng)和在它之下的并行計算機硬件。行計算機硬件。n任何編程語言

10、均有運行時間支持系任何編程語言均有運行時間支持系統(tǒng)，它是與用戶代碼連接程序。統(tǒng)，它是與用戶代碼連接程序。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n2.2.環(huán)境工具環(huán)境工具 n一個環(huán)境工具是指任何硬件和軟件的實用一個環(huán)境工具是指任何硬件和軟件的實用程序，以幫助用戶程序的開發(fā)和執(zhí)行。程序，以幫助用戶程序的開發(fā)和執(zhí)行。n編程環(huán)境編程環(huán)境( (或簡稱環(huán)境或簡稱環(huán)境) )：所有這類工具集：所有這類工具集合。合。n工具的實例包括操作系統(tǒng)實用程序、程序工具的實例包括操作系統(tǒng)實用程序、程序設(shè)計語言、編譯器以及運行時間庫等。設(shè)計語言、編譯器以及運行時間庫等。n環(huán)境工具是那些通常與操作系統(tǒng)或程序設(shè)環(huán)境工具是那些通常與操

11、作系統(tǒng)或程序設(shè)計語言無關(guān)的工具集。計語言無關(guān)的工具集。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n環(huán)境工具包括以下類型：環(huán)境工具包括以下類型：n作業(yè)管理工具作業(yè)管理工具 q包括網(wǎng)絡(luò)排隊系統(tǒng)包括網(wǎng)絡(luò)排隊系統(tǒng)(NQS)(NQS)和負載共享和負載共享工具工具(LSF(LSF) )。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n調(diào)試工具調(diào)試工具 n性能工具性能工具q它們用來監(jiān)控用戶應(yīng)用程序以識它們用來監(jiān)控用戶應(yīng)用程序以識別性能瓶頸之所在。別性能瓶頸之所在。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n三、并行編程方法三、并行編程方法目前在實際的并行計算機中廣泛目前在實際的并行計算機中廣泛使用的并行編程模型有使用的并行編程模型有4

12、 4種：種：q蘊式；蘊式；q數(shù)據(jù)并行；數(shù)據(jù)并行；q消息傳遞；消息傳遞；q共享變量。共享變量。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n有三種擴展方法：有三種擴展方法：n庫子程序、新語言構(gòu)造以及編譯庫子程序、新語言構(gòu)造以及編譯器命令。器命令。 n庫子程序庫子程序q除了在順序語言中可用的標(biāo)準(zhǔn)庫外，除了在順序語言中可用的標(biāo)準(zhǔn)庫外，加入一組新的庫函數(shù)，以支持并行加入一組新的庫函數(shù)，以支持并行化和交互操作?；徒换ゲ僮?。q這種庫的實例包括這種庫的實例包括MPIMPI消息傳遞以消息傳遞以及及POSIX POSIX PthreadsPthreads多線程庫。多線程庫。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n新構(gòu)造新構(gòu)

13、造q擴展程序設(shè)計語言使其具有某些新擴展程序設(shè)計語言使其具有某些新構(gòu)造，以支持并行化和交互。例如構(gòu)造，以支持并行化和交互。例如Fortran 90Fortran 90中密集數(shù)據(jù)操作。中密集數(shù)據(jù)操作。n編譯器命令編譯器命令q程序設(shè)計語言不變，但加入稱為編程序設(shè)計語言不變，但加入稱為編譯器命令譯器命令( (或或pragmaspragmas) )的格式化注的格式化注解。解。哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n示例：示例：n用一段簡單代碼來說明這些方法。用一段簡單代碼來說明這些方法。n所有所有3 3個并行程序均執(zhí)行相同的如圖個并行程序均執(zhí)行相同的如圖所示的串行所示的串行C C代碼的計算。代碼的計算。哈爾

14、濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n串行代碼段串行代碼段nfor ( i = 0; i N; i + ) Ai = bi * bi+1;nfor(i=0;iN;i+) ci=Ai+Ai+1;n使用庫例程的等效并行代碼使用庫例程的等效并行代碼nid = my_process_id();np = number of processes();nfor(i=id;iN;i=i+p) Ai=bi*bi+1;nbarrier();nfor(i=id;iN;i=i+p) ci=Ai +Ai+1;哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n串行代碼段串行代碼段nfor ( i = 0; i N; i + ) Ai = b

15、i * bi+1;nfor(i=0;iN;i+) ci=Ai+Ai+1;nFortran90Fortran90中使用數(shù)組操作的等效代中使用數(shù)組操作的等效代碼碼nmy-processid(), number_of_processes(), and barrier()nA(0:N-1) = b(0:N-1) * b(1:N)nc = A(0:N-1) + A(1:N)哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n串行代碼段串行代碼段nfor ( i = 0; i N; i + ) Ai = bi * bi+1;nfor(i=0;iN;i+) ci=Ai+Ai+1;nSGI SGI powerCpowerC中

16、使用中使用pragmapragma的等效代碼的等效代碼n# pragma paralleln#pragma shared ( A,b,c)n#pragma local ( i )n#pragma pfor iterate (i=0; N:1)n for(i=0;iN;i+)n#pragma synchronizen#pragma pfor iterate (i=0; N:1)n for(i=0;iN;i+) ci=Ai+Ai+1;哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院三種方法的比較：三種方法的比較：哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院n可用可用3 3種方法實現(xiàn)任何編程模種方法實現(xiàn)任何編程模型型n在任何并行平臺上，在任何并行平臺上，3 3種方法和編種方法和編程模型可以各種方式組合。程模型可