哈工大并行計算課件第二章

第2章并行編程基礎

1并行編程綜述

2進程任務和線程

3并行性問題

4交互和通信問題哈爾濱工業(yè)大學計算機科學與技術學院

1并行編程綜述并行編程處于令人遺憾的狀況：并行軟件開發(fā)遠落后于并行硬件的進展。缺少合適的并行軟件是阻礙主流用戶接納并行計算的主要原因。與順序計算相比，當今的并行系統(tǒng)軟件和應用軟件不僅數(shù)量很少,而且功能性也相當原始。隧道之末總有陽光。哈爾濱工業(yè)大學計算機科學與技術學院一、并行編程緣何艱難在并行編程中有許多不同的模型。是一個更復雜的智力活動。并行程序的環(huán)境要比串行程序落后得多。分為4個小問題來介紹哈爾濱工業(yè)大學計算機科學與技術學院哈爾濱工業(yè)大學計算機科學與技術學院1.順序編程長期以來已建立了許多算法范例能指導用戶從事算法設計。哈爾濱工業(yè)大學計算機科學與技術學院2.并行編程

并行編程處于初級階段；對于并行問題的應用，不太可能有一個現(xiàn)成的并行代碼；并行代碼的機器不同。并行編程也不支持成熟、通用和穩(wěn)定的工具；并行算法范例仍未能被很好地理解或被廣泛地接受；不存在單一、通用的機器模型；哈爾濱工業(yè)大學計算機科學與技術學院與順序語言在編程或自然模型級上相比,缺少代可擴展和異構可擴展的能力這些并行語言大多數(shù)在當前系統(tǒng)上使用的并行語言均是Fortran或C的某種擴展。一個編程模型即是程序員在開發(fā)一個并行程序時所見到和使用的模型。哈爾濱工業(yè)大學計算機科學與技術學院自然模型的定義：是由一個特定并行計算機平臺所提供的、用戶可見的最低層的編程模型。其他的編程模型可在此自然模型上加以實現(xiàn)。例如，在一個SGIPowerChallenge計算機上(它是SMP)，自然模型為共享變量模型(如SGIPowerC)。數(shù)據(jù)并行(如HPF)和消息傳送(如MPl)可在其頂部實現(xiàn)。哈爾濱工業(yè)大學計算機科學與技術學院3.并行編程進展較為悲觀，但在并行編程領域已有了許多進步：已開發(fā)了許多并行算法盡管大多數(shù)算法基于非現(xiàn)實的PRAM模型，但其中某些在作適當修正后可以實用。已涌現(xiàn)一小批簡單的并行算法范例，且已逐步為用戶所接受哈爾濱工業(yè)大學計算機科學與技術學院底層：自然模型正集中趨向于兩種模型：適用于PVP、SMP和DSM的單地址空間的共享變量模型；適用于MPP和機群的多地址空間的消息傳遞模型。其他模型專用化、小量化。哈爾濱工業(yè)大學計算機科學與技術學院高層并行編程模型

共有4種標準模型：數(shù)據(jù)并行(如HPF)、消息傳遞(如HPVM和MPl)共享變量(如HANSIX3H5)。蘊式用戶只需編寫順序程序，其中的蘊式并行性由并行化編譯器(如Kap)進行析取。哈爾濱工業(yè)大學計算機科學與技術學院4.吞吐率處理

順序程序并行系統(tǒng)(SPPS)模型，也稱為吞吐率處理在一個問題的處理上,并行少,串行多一個并行系統(tǒng)能夠提高處理速度，又能增加獨立順序作業(yè)的處理，提高系統(tǒng)的吞吐率哈爾濱工業(yè)大學計算機科學與技術學院二、并行編程環(huán)境1.一個典型的并行處理系統(tǒng)如圖所示的結構無論是算法還是源代碼均需顯式地并行化。哈爾濱工業(yè)大學計算機科學與技術學院哈爾濱工業(yè)大學計算機科學與技術學院編譯器將源代碼翻譯成二進制代碼在并行平臺上運行，該平臺包含操作系統(tǒng)和在它之下的并行計算機硬件。任何編程語言均有運行時間支持系統(tǒng)與用戶代碼連接的程序。哈爾濱工業(yè)大學計算機科學與技術學院2.環(huán)境工具

一個環(huán)境工具是指任何硬件和軟件的實用程序，以幫助用戶程序的開發(fā)和執(zhí)行。環(huán)境工具是那些通常與操作系統(tǒng)或程序設計語言無關的工具集作業(yè)管理工具調(diào)試工具性能工具哈爾濱工業(yè)大學計算機科學與技術學院作業(yè)管理工具包括網(wǎng)絡排隊系統(tǒng)(NQS)和負載共享工具(LSF)調(diào)試工具性能工具它們用來監(jiān)控用戶應用程序以識別性能瓶頸之所在。哈爾濱工業(yè)大學計算機科學與技術學院三、并行編程方法

目前在實際的并行計算機中廣泛使用的并行編程模型有4種：蘊式；數(shù)據(jù)并行；消息傳遞；共享變量。哈爾濱工業(yè)大學計算機科學與技術學院主要有三種擴展方法：新語言構造庫子程序編譯器命令哈爾濱工業(yè)大學計算機科學與技術學院1.新語言構造擴展程序設計語言使其具有某些新構造，以支持并行化和交互。例如Fortran90中密集數(shù)據(jù)操作。這種模型對應的是數(shù)據(jù)并行模型哈爾濱工業(yè)大學計算機科學與技術學院數(shù)據(jù)并行模型可以在SIMD計算機上實現(xiàn)，著重開發(fā)指令級細粒度的并行性也可以在SPMD計算機上實現(xiàn)，這取決于粒度大小。著重開發(fā)子程序級中粒度的并行性?？梢灾匦戮幾g用于MIMD結構其思想是開發(fā)一個源到源的預編譯器來實現(xiàn)程序之間的轉換結論：這種模型既適用于同步的SIMD計算機，也適用于緊耦合的MIMD計算機哈爾濱工業(yè)大學計算機科學與技術學院示例：用一段簡單代碼來說明該方法：串行代碼段for(i=0;i<N;i++)A[i]=b[i]*b[i+1];for(i=0;i<N;i++)c[i]=A[i]+A[i+1];Fortran90中使用數(shù)組操作的等效代碼my-processid(),number_of_processes(),andbarrier()A(0:N-1)=b(0:N-1)*b(1:N)c=A(0:N-1)+A(1:N)哈爾濱工業(yè)大學計算機科學與技術學院關于通信和同步數(shù)據(jù)并行程序設計強調(diào)的是局部計算和數(shù)據(jù)選路操作，它比較適合于使用規(guī)則網(wǎng)絡、模板和多維信號及圖像數(shù)據(jù)集來求解細粒度的應用問題。數(shù)據(jù)并行操作的同步是在編譯時而不是在運行時完成的。硬件同步則是通過控制器執(zhí)行SIMD程序的鎖步操作完成的。在同步的SIMD程序中，所有PE間的通信則直接由硬件控制，除所有PE間操作需鎖步外，PE間的數(shù)據(jù)通信也是以鎖步方式進行的。這些同步指令的執(zhí)行和數(shù)據(jù)選路操作，使得SIMD計算機在開發(fā)大型數(shù)組、大型網(wǎng)格或網(wǎng)狀數(shù)據(jù)的空間并行性時相當有效。哈爾濱工業(yè)大學計算機科學與技術學院數(shù)據(jù)并行模型具有以下特點之一：①單線程：從程序員的觀點，一個數(shù)據(jù)并行程序中由一個進程執(zhí)行，具有單一控制線；使得一個數(shù)據(jù)并行程序就像一個順序程序。②并行操作子聚合數(shù)據(jù)結構上：數(shù)據(jù)并行程序的一個單步(語句)，可指定同時作用在不同數(shù)據(jù)組元素或其他聚合數(shù)據(jù)結構上的多個操作。③松散同步(LooselySynchronous)：在數(shù)據(jù)并行程序的每條語句之后，均有一個隱含的同步，這種語句級的同步是松散的(相對于SIMD機器每條指令之后的緊同步而言)。哈爾濱工業(yè)大學計算機科學與技術學院數(shù)據(jù)并行模型具有以下特點之二：④全局命名空間：數(shù)據(jù)并行程序中的所有變量均駐留在單一地址空間內(nèi)，所有語句可訪問任何變量，只要滿足通常的變量作用域規(guī)則。⑤隱式相互作用：因為數(shù)據(jù)并行程序的每條語句之末存在著一個隱含的路障，所以不需要一個顯式同步；通信可由變量指派而隱含地完成。⑥隱式數(shù)據(jù)分配(ImplicitDataAllocation)：程序員不必要明確地指定如何分配數(shù)據(jù)，可將改進數(shù)據(jù)局部性和減少通信的數(shù)據(jù)分配方法揭示給編譯器。哈爾濱工業(yè)大學計算機科學與技術學院2.庫子程序除了在順序語言中可用的標準庫外，加入一組新的庫函數(shù)，以支持并行化和交互操作。這種模型對應的是消息傳遞模型

(MessagePassing)

模型中駐留在不同節(jié)點上的進程可以通過網(wǎng)絡傳遞消息相互通信。消息可以是指令、數(shù)據(jù)、同步信號或中斷信號等。哈爾濱工業(yè)大學計算機科學與技術學院串行代碼段for(i=0;i<N;i++)A[i]=b[i]*b[i+1];for(i=0;i<N;i++)c[i]=A[i]+A[i+1];使用庫例程的等效并行代碼id=my_process_id();p=numberofprocesses();for(i=id;i<N;i=i+p)A[i]=b[i]*b[i+1];barrier();for(i=id;i<N;i=i+p)c[i]=A[i]+A[i+1];哈爾濱工業(yè)大學計算機科學與技術學院說明：在消息傳遞并行程序中，用戶必須明確地為進程分配數(shù)據(jù)和負載，它比較適合于開發(fā)大粒度的并行性，這些程序是多線程的和異步的，要求顯式同步(如路障等)，以確保正確地執(zhí)行順序。這些進程均有其分開的地址空間。消息傳遞模型比數(shù)據(jù)并行模型靈活；兩種標準庫PVM和MPI，使消息傳遞程序大大地增強了可移植性。消息傳遞不僅可執(zhí)行在共享變量的多處理機上，而且可執(zhí)行在分布存儲的多計算機上。哈爾濱工業(yè)大學計算機科學與技術學院消息傳遞模型特點之一：①多線程：消息傳遞程序系由多個進程組成，每個進程都有其自己的控制線，且可執(zhí)行不同的代碼；控制并行(如MPMD)和數(shù)據(jù)并行(如SPMD)均可支持。②異步并行性(AsynchronousParallelism)：消息傳遞程序的諸線程彼此異步地執(zhí)行，使用諸如路障和阻塞通信的方法來同步各個進程。③分開的地址空間(Separate—AddressSpace)：并行程序的進程駐留在不同地址空間內(nèi)。一個進程中的數(shù)據(jù)變量在其他進程是不可見的，因此一個進程不能讀／寫另一進程中的變量，進程的相互作用通過執(zhí)行特殊的消息傳遞操作實現(xiàn)。哈爾濱工業(yè)大學計算機科學與技術學院消息傳遞模型特點之二：④顯式相互作用(ExplicitInteraction)：程序員必須解決包括數(shù)據(jù)映射、通信、同步和聚合等相互作用問題；負載分配通常通過屬主—計算(Owner—Compute)規(guī)則來完成，即進程只在其所擁有的數(shù)據(jù)上執(zhí)行計算。⑤顯式分配(ExplicitAllocation)：負載和數(shù)據(jù)均由用戶顯式地分配給進程，為了減少設計和編碼的復雜性，用戶常使用單一代碼方法編寫SPMD應用程序。哈爾濱工業(yè)大學計算機科學與技術學院3.編譯器命令程序設計語言不變，但加入稱為編譯器命令(或pragmas)的格式化注解。這種模型對應的是共享變量模型，在該模型中，駐留在各處理器上的進程可以通過讀／寫公共存儲器中的共享變量相互通信。哈爾濱工業(yè)大學計算機科學與技術學院示例：串行代碼段for(i=0;i<N;i++)A[i]=b[i]*b[i+1];for(i=0;i<N;i++)c[i]=A[i]+A[i+1];SGIpowerC中使用pragma的等效代碼#pragmaparallel#pragmashared(A,b,c)#pragmalocal(i){#pragma

pforiterate(i=0;N；1)

for(i=0;i<N;i++)A[i]=b[i]*b[i+1];#pragmasynchronize#pragma

pforiterate(i=0;N；1)

for(i=0;i<N;i++)c[i]=A[i]+A[i+1];}哈爾濱工業(yè)大學計算機科學與技術學院幾點說明：它與數(shù)據(jù)并行模型的相似之處在于它有一個單一的全局名字空間；它與消息傳遞模型的相似之處在于它是多線程的和異步的。然而，數(shù)據(jù)是駐留在單一共享地址空間中，因此不需要顯式分配數(shù)據(jù)，而工作負載既可顯式也可隱式分配。通信通過共享的讀寫變量隱式完成，而同步必須是顯式的，以保持進程執(zhí)行的正確順序。共享變量模型尚無一個可廣泛接受的標準。例如，一個為SGIPowerChallenge編寫的程序，不能直接運行在ConvexExemplar上；一個為SMP或DSM開發(fā)的共享變量程序，不能運行在諸如MPP和機群的多計算機上。哈爾濱工業(yè)大學計算機科學與技術學院關于共享變量模型尚須說明以下三點：①一個廣泛流傳的錯誤概念是共享變量模型運行細粒度(FineGranularity)的并行性比消息傳遞模型好要注意共享變量模型是一種并行編程模型，它可以實現(xiàn)在PVP、SMP、DSM、MPP或甚至機群的任意并行平臺上。支持細粒度并行性的平臺應具有有效的通信／同步機制，一個共享變量的程序可能遭到，高的相互作用開銷，從而遠比運行在機群、MPP甚至SMP上的消息傳遞程序慢得多。哈爾濱工業(yè)大學計算機科學與技術學院②一個普遍的說法是共享變量編程比消息傳遞編程容易此說法雖不錯，但科學試驗的事實尚未完全建立。為了開發(fā)一個新的、有效的、松散同步的、通信模式規(guī)則的并行程序，共享變量的方法未必比消息傳遞方法容易。當然對于非規(guī)則的并行程序，使用消息傳遞原語很難指明所需要的相互作用；同時共享變量模型允許全局指針操作，而消息傳遞模型是無此能力的；此外，共享變量編程雖不必明顯地劃分和分配數(shù)據(jù)，但這也可能傷害性能。哈爾濱工業(yè)大學計算機科學與技術學院③就查錯而論，共享變量程序可能比消息傳遞程序更困難共享變量程序中的所有進程都駐留在單地址空間中，而且訪問共享數(shù)據(jù)必須由同步結構(如鎖和臨界區(qū))加以保護。同步錯誤易出現(xiàn)，而且一旦出現(xiàn)就難以查找；但在消息傳遞程序中，此類錯誤出現(xiàn)的頻度大大減少，因為諸進程不共享單一地址空間。哈爾濱工業(yè)大學計算機科學與技術學院4.三種方法的比較：哈爾濱工業(yè)大學計算機科學與技術學院可用3種方法實現(xiàn)任何編程模型在任何并行平臺上，3種方法和編程模型可行以各種方式組合例題：CrayMPP編程模型，設計一個稱為CrayCraft的集成編程工具；使用上述所有3種方法(新構造、庫函數(shù)和編譯器命令)實現(xiàn)了數(shù)據(jù)并行(Fortran90)、共享變量(工作共享)以及消息傳遞(PVM)編程模型。哈爾濱工業(yè)大學計算機科學與技術學院第2章并行編程基礎

1并行編程綜述

2進程任務和線程

3并行性問題

4交互和通信問題哈爾濱工業(yè)大學計算機科學與技術學院

2進程、任務和線程一、進程、任務和線程在并行計算機上，用戶的應用程序是以進程、任務或線程方式執(zhí)行的。進程:是正在執(zhí)行的程序。哈爾濱工業(yè)大學計算機科學與技術學院1.抽象進程的定義在兩個層次上考慮進程概念是很有用的。抽象觀點既簡單又能很好地適合于并行計算機的用戶。進程的實現(xiàn)工作原理哈爾濱工業(yè)大學計算機科學與技術學院進程的定義:一個進程P是一個4元組(P，C，D，S),其中P是程序(或代碼)，C是控制狀態(tài)，D為數(shù)據(jù)狀態(tài)以及S為進程P的狀態(tài)。進程是動態(tài)的。

哈爾濱工業(yè)大學計算機科學與技術學院程序(代碼)

任何進程與一個程序相關?？刂坪蛿?shù)據(jù)狀態(tài)

大多數(shù)程序基于命令式機器模型，中心概念是狀態(tài)更新。一個命令式程序可看成是一個狀態(tài)機(或一個自動機)。哈爾濱工業(yè)大學計算機科學與技術學院下面定義某些術語程序變量集的定義：一個程序使用兩個變量集：數(shù)據(jù)變量由程序員聲明用來保存數(shù)據(jù)值的變量?？刂谱兞渴潜４婵刂菩畔⒌淖兞?，它們不需要顯式說明?？刂谱兞勘４娴氖怯嘘P下一步應執(zhí)行什么操作的信息。哈爾濱工業(yè)大學計算機科學與技術學院配對集的定義：在任何時候，一個程序的每個數(shù)據(jù)或控制變量需與一個值配為一對，該值可能是一個未定義的特殊值。在時間t時所有(數(shù)據(jù)變量，數(shù)據(jù)值)的配對集定義了時間t的程序的數(shù)據(jù)狀態(tài)。類似地，時間t的所有(控制變量，控制值)配對集定義了時間t的程序的控制狀態(tài)。時間t的程序狀態(tài)是t時間的數(shù)據(jù)狀態(tài)和控制狀態(tài)的和。哈爾濱工業(yè)大學計算機科學與技術學院程序的最后狀態(tài)和發(fā)散狀態(tài)定義：程序從初始狀態(tài)啟動當執(zhí)行了程序的一個原子操作后，程序就從當前狀態(tài)轉為下一狀態(tài)。程序不斷執(zhí)行原子操作并不斷更新其狀態(tài)，直至終止。此時程序處在最后狀態(tài)。當一個程序進入一個被確認不會終結的狀態(tài)時，則說該程序進入了發(fā)散狀態(tài)。哈爾濱工業(yè)大學計算機科學與技術學院進程狀態(tài)在任何時間，進程具有某個狀態(tài)(status)。下圖畫出了某些重要狀態(tài)以及它們之間的轉換。

哈爾濱工業(yè)大學計算機科學與技術學院哈爾濱工業(yè)大學計算機科學與技術學院進程狀態(tài)轉換圖的說明：開始時，進程為不存在狀態(tài)。當它的創(chuàng)建者，父進程執(zhí)行進程創(chuàng)建操作后，它才出現(xiàn)。一個新創(chuàng)建的子進程準備執(zhí)行，但僅在被調(diào)度后，它方可開始運行(執(zhí)行其代碼)。在進程運行中可能發(fā)生以上幾種狀態(tài)。

哈爾濱工業(yè)大學計算機科學與技術學院在實現(xiàn)進程時，必須考慮以下各方面：執(zhí)行方式;地址空間;進程現(xiàn)場;進程描述符;進程控制。哈爾濱工業(yè)大學計算機科學與技術學院二.進程的變異

傳統(tǒng)的操作系統(tǒng)進程有分離的地址空間；分離的地址空間概念將使進程管理非常耗時。哈爾濱工業(yè)大學計算機科學與技術學院Unix進程為重量級進程例如，當一個Unix進程執(zhí)行一個fork()系統(tǒng)調(diào)用以創(chuàng)建一個子進程時，它必須為子進程創(chuàng)建一個新的地址空間。這意味著必須分配存儲器，復制父進程的數(shù)據(jù)段和描述符，并為子進程設置一個運行時間堆棧。因此，進程創(chuàng)建和切換的高開銷會對并行處理造成有害影響。哈爾濱工業(yè)大學計算機科學與技術學院重量級的并行進程不適用于可擴展并行計算機，除非并行進程具有粗計算粒度。要開發(fā)較細粒度并行性，必須使用輕量級進程。在許多操作系統(tǒng)、線程庫和并行語言中已提出了輕量級進程(也稱為線程)概念并已得到實現(xiàn)。哈爾濱工業(yè)大學計算機科學與技術學院OS進程和線程間的主要差別：在重量級的OS進程中，多個線程能共存于進程(包括進程描述符)的同一地址空間，并且共享。當創(chuàng)建一個(重量級)進程時，通常它有一個單線程，稱為基本線程。通過執(zhí)行一個線程創(chuàng)建操作，任何進程能創(chuàng)建另外的線程。哈爾濱工業(yè)大學計算機科學與技術學院典型的線程創(chuàng)建操作形式如下：threalcreate(foo，argument1，……，argumentn)；這種操作與過程調(diào)用非常類似。該操作創(chuàng)建一個進程，它將用給定的n個參量執(zhí)行函數(shù)和;創(chuàng)建一個線程要比創(chuàng)建一個重量級進程快得多。哈爾濱工業(yè)大學計算機科學與技術學院結論：在一般的并行描述里：任務=進程=重量級進程=操作系統(tǒng)進程

只用術語進程來表示重量級進程或線程：

輕量級進程=線程哈爾濱工業(yè)大學計算機科學與技術學院第2章并行編程基礎

1并行編程綜述

2進程任務和線程

3并行性問題

4交互和通信問題哈爾濱工業(yè)大學計算機科學與技術學院

3

并行性問題并行編程帶來的許多額外問題。重點討論在用戶程序中由于對并行性所作的說明而引起的問題。哈爾濱工業(yè)大學計算機科學與技術學院一、進程中的同構性

指并行程序中各分進程的類似性。有3種可能的基本類似：SPMD：在單程序多數(shù)據(jù)(SPMD)程序中的分進程是同構的。因為多個進程在不同的數(shù)據(jù)范疇內(nèi)執(zhí)行相同代碼。MPMD：在多程序多數(shù)據(jù)(MPMD)程序中的分進程是異構的。因為多個進程可以執(zhí)行不同代碼。哈爾濱工業(yè)大學計算機科學與技術學院SPMD和MPMD程序，兩者都是MIMD類型的。SIMD：SIMD程序與SPMD有區(qū)別，SIMD程序是SPMD程序的一個特例。結論：將著重MPMD程序的研究。哈爾濱工業(yè)大學計算機科學與技術學院數(shù)據(jù)并行程序--是指SPMD程序，尤其是此程序只用數(shù)據(jù)并行構造(如Fortran90中所采用的)時。功能并行程序(也稱為任務并行或控制并行程序)--通常是MPMD程序的同義詞。在一個并行程序中，MPMD(功能并行)和SPMD(數(shù)據(jù)并行)風格可以混合使用。哈爾濱工業(yè)大學計算機科學與技術學院1.并行塊(parallelblock)表達MPMD程序的方法是：使用parbegin和parend構造。這種結構化的構造最初是由DUkstra提議的，也稱為cobegin和coend。哈爾濱工業(yè)大學計算機科學與技術學院ParbeginS1，S2，…，Sn

Parend當并行塊執(zhí)行時，它的n個分進程S1，S2，…，Sn就開始同時執(zhí)行。它們的執(zhí)行是互相獨立的，以不同速率進行。當所有n個分進程終止時，并行塊也就終止。哈爾濱工業(yè)大學計算機科學與技術學院2、并行循環(huán)(Parallelloop)當并行塊中的所有進程共享相同代碼時，用一個稱為并行循環(huán)的速記記號來標明并行塊如下：

哈爾濱工業(yè)大學計算機科學與技術學院ParbeginProcess(1)······Process(n)Parend可簡化成如下的并行循環(huán)：Parfor(i=1；i<=n：i++){Process(i)}并行循環(huán)常用來說明SPMD并行程序。哈爾濱工業(yè)大學計算機科學與技術學院可以用SPMD來仿真MPMD。例如MPMD代碼：ParbeginA；B；C；parend表示成一個SPMD的并行循環(huán)parfor(i=0；i<3；i++){if(i=0)A；If(i=1)B；If(i=2)C；}哈爾濱工業(yè)大學計算機科學與技術學院3.多代碼與單代碼(Multi-CodeversusSingleCode)

MPP和COW上，許多編程語言不提供并行塊或并行循環(huán)構造。哈爾濱工業(yè)大學計算機科學與技術學院例如，ParbeginA；B；C；parend，用多代碼進行說明：runAOnnode1runBOnnode2runCOnnode3程序A、B和C僅是順序程序加上進行交互的庫調(diào)用。哈爾濱工業(yè)大學計算機科學與技術學院SPMD程序可用單代碼方法加以說明。例如，要說明并行循環(huán)parfor(i=0：i<N；i++){foo(i)}，用戶只需編寫如下的一個程序：Pid=my_processid()；Numproc=number_of_processes();for(i：=pid；i<N；i=i+numproc)foo(i)；哈爾濱工業(yè)大學計算機科學與技術學院數(shù)據(jù)并行構造在Fortran90和HPF中，SPMD并行性可用數(shù)據(jù)并行構造加以說明。例如，一個并行循環(huán)：parlor(i:=1;i<=N;++){c[i]=A[i]+B[i];}用戶可用1條數(shù)組賦值語句：C=A+B或用以下循環(huán)來表示:

forall(i=1，N)C[i]=A[i]+B[i]哈爾濱工業(yè)大學計算機科學與技術學院二、靜態(tài)和動態(tài)并行性1.靜態(tài)并行性如果一個程序的結構以及組成進程的個數(shù)在運行時間之前(如在編譯時間，連接時間或裝載時間)就可確定。2.動態(tài)并行性這就蘊含著那些進程要在運行時間內(nèi)創(chuàng)建和終止。哈爾濱工業(yè)大學計算機科學與技術學院3.動態(tài)并行性的操作：fork/join(派生和匯合）fork/join操作加以表示。它們也可用單代碼或多代碼方法加以說明。

哈爾濱工業(yè)大學計算機科學與技術學院例：下列程序有3個進程，其中A是主進程，當程序開始執(zhí)行時，自動創(chuàng)建進程：ProcessA:BeginZ:=1Fork(B);T:=foo(3)end哈爾濱工業(yè)大學計算機科學與技術學院ProcessB:BeginFork(C);X:=foo(3);Join(C);Output(X+Y);end哈爾濱工業(yè)大學計算機科學與技術學院ProcessC:BeginY:=boo(Z);end哈爾濱工業(yè)大學計算機科學與技術學院三、進程編組一個進程組是進程的一個有序集。進程中的成員數(shù)稱為組的大小每個組有一個組標識符(ID)，它唯一地識別并行程序中的組。哈爾濱工業(yè)大學計算機科學與技術學院為支持組的概念，并行編程語言需要提供管理進程組的功能如創(chuàng)建和毀滅組、詢問組的ID、組的成員以及組員的排序等。哈爾濱工業(yè)大學計算機科學與技術學院四、分配問題任何并行程序必須在某些數(shù)據(jù)對象上完成某些計算(工作負載)。分配是指將數(shù)據(jù)和工作負載劃分到進程中并將進程映射到結點(處理器)上。哈爾濱工業(yè)大學計算機科學與技術學院1.并行性并行程序的并行度(degreeofparallelism，DOP)通常定義為可同時執(zhí)行的分進程數(shù)。哈爾濱工業(yè)大學計算機科學與技術學院2.顆粒度

是指在兩次并行性操作或交互操作之間所執(zhí)行的計算負載。按計算的操作數(shù)大小,可粗略地估計。粒度大小分為：細粒度-計算的操作數(shù)小于200；中粒度-計算的操作數(shù)200-2000；粗粒度-計算的操作數(shù)大于2000。哈爾濱工業(yè)大學計算機科學與技術學院3.隱式和顯式分配

顯式分配用戶需要顯式說明如何分配數(shù)據(jù)和工作負載。隱式分配此任務將由編譯器和運行時間系統(tǒng)來完成，可以有各種組合分配方式。哈爾濱工業(yè)大學計算機科學與技術學院例：在對稱式多處理機中通常的分配方法是讓數(shù)據(jù)留駐在一個中央共享存儲器中以使所有進程都可加以訪問。工作負載的分配可以用靜態(tài)方式也可用動態(tài)方式。當一個進程分得一個工作負載后，它所需的數(shù)據(jù)可從共享存儲器得到。哈爾濱工業(yè)大學計算機科學與技術學院第2章并行編程基礎

1并行編程綜述

2進程任務和線程

3并行性問題

4通信問題哈爾濱工業(yè)大學計算機科學與技術學院

4通信問題交互操作稱為通信這里討論范圍廣一些：在并行系統(tǒng)中需支持的通信操作通信方式和模式競爭通信和合作通信哈爾濱工業(yè)大學計算機科學與技術學院一、通信操作分為三種：數(shù)據(jù)交換（通信）同步聚集操作這些操作常統(tǒng)稱為通信它們對體系結構和編程的支持有著不同的要求哈爾濱工業(yè)大學計算機科學與技術學院通信的定義通信操作是指在兩個或多個進程間傳送數(shù)據(jù)。分類：在共享存儲程序中的通信使用過程級并行性的多處理機程序用派生過程在多計算機模型中的通信哈爾濱工業(yè)大學計算機科學與技術學院二、同步操作分三個大的方面來討論：同步的定義、高級同步結構和低級同步原語1.同步的定義同步會成為系統(tǒng)性能的瓶頸

將導致進程的相互等待；允許正在等待的進程去繼續(xù)執(zhí)行。哈爾濱工業(yè)大學計算機科學與技術學院同步的分類：原子操作數(shù)據(jù)同步控制同步他們之間的關系如下圖哈爾濱工業(yè)大學計算機科學與技術學院同步原子操作控制同步數(shù)據(jù)同步路障“我找到了”互斥信號燈和鎖產(chǎn)-銷池、隊列哈爾濱工業(yè)大學計算機科學與技術學院原子性是指:進程常需要以單原子操作方式完成一串操作：Parfor(i：=1；i<n；i++){Atomic{X=X+1；y=y-1；}}完成隱式同步哈爾濱工業(yè)大學計算機科學與技術學院2.高級同步結構現(xiàn)今的多處理器系統(tǒng)的并行程序設計環(huán)境，提供了四種類型的同步原語：事件:用于實現(xiàn)產(chǎn)—銷同步路障:用在柵欄同步中鎖/信號燈：用于實現(xiàn)互斥形式原子性臨界區(qū):用于實現(xiàn)互斥形式原子性哈爾濱工業(yè)大學計算機科學與技術學院（1）信號燈和鎖鎖的普通用法就是通過互斥將臨界區(qū)轉換成原子操作。信號燈S是一個非負0或1的布爾量，對其能進行兩個原子操作P(S)和V(S)：①若s不為0，P(S)操作使S減1；②若s不為1，V(S)操作將S值加1。S是二元信號燈，取值為真或假，也稱之為鎖。相應地，對于鎖S，其P(S)和V(S)常寫做lock(S)和unlock(S)哈爾濱工業(yè)大學計算機科學與技術學院(2)鎖的副作用鎖的主要優(yōu)點是它已由大多數(shù)多處理器支持之，并且已研究得相當深入。鎖是一種非常靈活的機制，幾乎能實現(xiàn)任何同步。然而，互斥鎖技術用于實現(xiàn)原子時，具有某些嚴重的缺點，從而導致如下8點問題：①非結構性：鎖不是一種結構化的結構，容易用錯它，如果lock／unlock語句漏掉或冗余，則編譯器不能查出它；②重疊說明：鎖不是用戶所真正想要的，它只是達到原子性的一種方法。鎖損害了程序的可移植性，且使代碼難于理解；哈爾濱工業(yè)大學計算機科學與技術學院③狀態(tài)相關：鎖引入了信號燈S及使用條件原子操作lock(S)，一個進程能否穿過lock(S)，依賴于信號燈變量S之值，一般而言，像這樣的與狀態(tài)有關的數(shù)據(jù)是難于理解的；④順序執(zhí)行：對于有些事務處理操作，即使可并行訪問，但由于使用鎖互斥，它們只能一次執(zhí)行一個，同樣這種順序執(zhí)行也不是用戶想要的；⑤鎖開銷：順序執(zhí)行l(wèi)ock(S)和unlock(S)也存在著附加的開銷，而且當n個進程每個都執(zhí)行l(wèi)ock(S)操作時，它們中至多一個能成功，其余者均必須重復訪問S而再試；哈爾濱工業(yè)大學計算機科學與技術學院⑥優(yōu)先倒置(Prioritylnversion)：當一個保持了高優(yōu)先進程所需鎖的低優(yōu)先進程被搶先時，高優(yōu)先進程并不能前進，因為它被鎖鎖住了；⑦護送阻塞當一個保持鎖的進程因缺頁或超時被中斷時，其他的進程因等待鎖不能前進；⑧死鎖(Deadlock)：假定兩進程P與Q，欲進行X與Y操作：當進程P已為X保持了一把鎖并想為Y申請一把鎖；而進程Q已為Y保持了一把鎖并想為X申請一把鎖時，此時沒有任何進程在其得到鎖之前釋放一把鎖，結果誰也得不到所要求的鎖。哈爾濱工業(yè)大學計算機科學與技術學院（3）臨界區(qū)是指OS所使用的臨界區(qū)，其語法結構如下：

critical-regionresource{／*進入點*／S1;S2;…;Sn;／*臨界區(qū)*／

}／*退出點*／其中，resource代表一組共享變量。所有共享相同資源的臨界區(qū)必須互斥執(zhí)行。哈爾濱工業(yè)大學計算機科學與技術學院并行程序設計所使用的臨界區(qū)做了兩點修改：①resource部分不是真正有用的，所以被略去。使用在真正多處理機中的臨界區(qū)，其語法結構及其等效鎖代碼表示如下：等效鎖代碼lock(S)S1；S2；…；Sn;unlock(S)critical_region{S1；S2；…；Sn;}哈爾濱工業(yè)大學計算機科學與技術學院②多處理機中的臨界區(qū)變成了鎖結構方式，系統(tǒng)自動說明和初始化一個隱含的信號燈S，并產(chǎn)生正確的lock／unlock語句。臨界區(qū)比鎖有很多優(yōu)點，它是結構化的、與狀態(tài)無關的，因而易于使用。臨界區(qū)只是一段被互斥執(zhí)行的代碼，并非必須使用鎖。哈爾濱工業(yè)大學計算機科學與技術學院

(4)路障并行循環(huán)程序中另一個常用的同步操作是設置路障，它強使所有的進程在路障處等待，當所有的進程均到達后，才拆除路障，并釋放全部進程，以形成同步。實現(xiàn)路障同步一般要使用兩把旋轉鎖：一個用來記錄到達路障的進程數(shù)；另一個用來封鎖進程，直至最后一個進程到達。路障的實現(xiàn)中，要不停地探測指定的變量，直到滿足條件為止。哈爾濱工業(yè)大學計算機科學與技術學院例子：路障的實現(xiàn)過程，其中，lock和unlock提供基本的旋轉鎖，total為進程總數(shù)。lock(counterlock)；／*上鎖確定原子性*／if(count==0)release=0；／*第一個進程設置release*／count=count+1；／*進程計數(shù)*／unclock(counterlock)；／*開鎖*／if(count==total)；{Count=0；／*重置計數(shù)器*／Release=1；／*釋放進程*／}Else{／*還有別的進程未到*／

spin(release=1);／*等待其他進程到達*／}哈爾濱工業(yè)大學計算機科學與技術學院

對counterlock加鎖，保證增量操作的原子性，變量count記錄著已到達的進程數(shù)，變量release用來封鎖進程，直到最后一個進程到達路障為止，函數(shù)spin(release=1)使進程等待，直到所有進程到達路障為止?？偨Y：同步的缺點：同步原語操作本身要花費較長的時間，而同步操作最嚴重的問題是進程的順序化(串行性)，當出現(xiàn)競爭時，就引起了串行性問題。哈爾濱工業(yè)大學計算機科學與技術學院3.低級同步原語很多處理機的硬件都能確保單獨讀／寫初等變量的操作的原子性；絕大多數(shù)多處理機硬件都提供了某些原子性指令，它們可對初等變量執(zhí)行單一的讀-修改-寫操作。原子操作有許多種，最常用的有三種低級同步結構：Test＆Set、Compare＆Swap、Fetch＆Add。哈爾濱工業(yè)大學計算機科學與技術學院

(1)測試并設置(Test&Set)

Test＆Set(S，temp)是一個原子操作指令，它將共享變量S讀入局部變量temp，然后將S置為1，Definition：Test-and-Set(address，bit-position)BeginTemp:=Memory[address].bit-position；Memory[address].bit-position：=1；Condition-code:=Temp.bit-position；enddefinition；哈爾濱工業(yè)大學計算機科學與技術學院應用：封鎖共享變量Lock(shared-datum)；Update(shared-datum)；Unlock(shared-datum)哈爾濱工業(yè)大學計算機科學與技術學院例子：

while(S)；／*這三行執(zhí)行l(wèi)ock(S)操作*／

Test＆Set(S，temp)；

while(temp)Test＆Set(S，temp)；

..／*臨界區(qū)*／.S=False；／*

unlock(S)*／哈爾濱工業(yè)大學計算機科學與技術學院說明：上例中，使用了Test＆Set操作執(zhí)行l(wèi)ock(S)，其中第一個while循環(huán)檢查鎖S是否已由別的進程釋放。由于每次執(zhí)行Test＆Set都要寫共享變量S，所以可能導致頻繁的存儲器訪問。哈爾濱工業(yè)大學計算機科學與技術學院

(2)比較并交換(Compare&Swap)Compare＆Swap(S，old，new，flag)也是一條原子操作指令，它將共享變量S與局部變量old進行比較：若S與old一致，則S=new，且flag=True，以指明S被修改；若S與old不一致，則old=S，且flag=False，其主要用途也是執(zhí)行鎖功能。示例對照如下：0ld=balance[x]；／*讀共享變量*／

do{new=0ld-100；／*修改*／Compare＆Swap(balance[x]，0ld，new，flag);／*寫*／}while(flag==False)；哈爾濱工業(yè)大學計算機科學與技術學院上述操作可以用鎖實現(xiàn)如下：lock(S);balance[x]=balance[x]-100；／*讀-修改-寫*／unlock(S);上述鎖功能使讀、寫這一整個過程是互斥的。使用Compare＆Swap的優(yōu)點是臨界區(qū)的長度減至只一條指令。哈爾濱工業(yè)大學計算機科學與技術學院(3)取并加(Fetch&Add)Fetch＆Add(S，V)也是一條原子操作指令，它返回共享變量S給局部變量Result，然后將局部值V加向S，其語法結構如下：

Fetch＆Add(S，V)Result=S；S=S+V；ReturnResult；哈爾濱工業(yè)大學計算機科學與技術學院該指令不僅簡單，而且快速，例如：上節(jié)示例的代碼段只用一條Fetch＆Add指令，即可實現(xiàn)：Fetch＆Add(balance[x]，100)哈爾濱工業(yè)大學計算機科學與技術學院三、聚集(aggregation)

由并行程序中的各分進程計算所得的部分結果，需要用聚集操作加以合并以得到一個完整結果。哈爾濱工業(yè)大學計算機科學與技術學院聚集的主要特征是：它由一