哈工大并行計(jì)算課件第二章

第2章并行編程基礎(chǔ)

1并行編程綜述

2進(jìn)程任務(wù)和線程

3并行性問(wèn)題

4交互和通信問(wèn)題哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

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

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

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

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

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

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

(MessagePassing)

模型中駐留在不同節(jié)點(diǎn)上的進(jìn)程可以通過(guò)網(wǎng)絡(luò)傳遞消息相互通信。消息可以是指令、數(shù)據(jù)、同步信號(hào)或中斷信號(hào)等。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院串行代碼段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];使用庫(kù)例程的等效并行代碼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è)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院說(shuō)明：在消息傳遞并行程序中，用戶必須明確地為進(jìn)程分配數(shù)據(jù)和負(fù)載，它比較適合于開(kāi)發(fā)大粒度的并行性，這些程序是多線程的和異步的，要求顯式同步(如路障等)，以確保正確地執(zhí)行順序。這些進(jìn)程均有其分開(kāi)的地址空間。消息傳遞模型比數(shù)據(jù)并行模型靈活；兩種標(biāo)準(zhǔn)庫(kù)PVM和MPI，使消息傳遞程序大大地增強(qiáng)了可移植性。消息傳遞不僅可執(zhí)行在共享變量的多處理機(jī)上，而且可執(zhí)行在分布存儲(chǔ)的多計(jì)算機(jī)上。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院消息傳遞模型特點(diǎn)之一：①多線程：消息傳遞程序系由多個(gè)進(jìn)程組成，每個(gè)進(jìn)程都有其自己的控制線，且可執(zhí)行不同的代碼；控制并行(如MPMD)和數(shù)據(jù)并行(如SPMD)均可支持。②異步并行性(AsynchronousParallelism)：消息傳遞程序的諸線程彼此異步地執(zhí)行，使用諸如路障和阻塞通信的方法來(lái)同步各個(gè)進(jìn)程。③分開(kāi)的地址空間(Separate—AddressSpace)：并行程序的進(jìn)程駐留在不同地址空間內(nèi)。一個(gè)進(jìn)程中的數(shù)據(jù)變量在其他進(jìn)程是不可見(jiàn)的，因此一個(gè)進(jìn)程不能讀／寫(xiě)另一進(jìn)程中的變量，進(jìn)程的相互作用通過(guò)執(zhí)行特殊的消息傳遞操作實(shí)現(xiàn)。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院消息傳遞模型特點(diǎn)之二：④顯式相互作用(ExplicitInteraction)：程序員必須解決包括數(shù)據(jù)映射、通信、同步和聚合等相互作用問(wèn)題；負(fù)載分配通常通過(guò)屬主—計(jì)算(Owner—Compute)規(guī)則來(lái)完成，即進(jìn)程只在其所擁有的數(shù)據(jù)上執(zhí)行計(jì)算。⑤顯式分配(ExplicitAllocation)：負(fù)載和數(shù)據(jù)均由用戶顯式地分配給進(jìn)程，為了減少設(shè)計(jì)和編碼的復(fù)雜性，用戶常使用單一代碼方法編寫(xiě)SPMD應(yīng)用程序。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.編譯器命令程序設(shè)計(jì)語(yǔ)言不變，但加入稱為編譯器命令(或pragmas)的格式化注解。這種模型對(duì)應(yīng)的是共享變量模型，在該模型中，駐留在各處理器上的進(jìn)程可以通過(guò)讀／寫(xiě)公共存儲(chǔ)器中的共享變量相互通信。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院示例：串行代碼段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è)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院幾點(diǎn)說(shuō)明：它與數(shù)據(jù)并行模型的相似之處在于它有一個(gè)單一的全局名字空間；它與消息傳遞模型的相似之處在于它是多線程的和異步的。然而，數(shù)據(jù)是駐留在單一共享地址空間中，因此不需要顯式分配數(shù)據(jù)，而工作負(fù)載既可顯式也可隱式分配。通信通過(guò)共享的讀寫(xiě)變量隱式完成，而同步必須是顯式的，以保持進(jìn)程執(zhí)行的正確順序。共享變量模型尚無(wú)一個(gè)可廣泛接受的標(biāo)準(zhǔn)。例如，一個(gè)為SGIPowerChallenge編寫(xiě)的程序，不能直接運(yùn)行在ConvexExemplar上；一個(gè)為SMP或DSM開(kāi)發(fā)的共享變量程序，不能運(yùn)行在諸如MPP和機(jī)群的多計(jì)算機(jī)上。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院關(guān)于共享變量模型尚須說(shuō)明以下三點(diǎn)：①一個(gè)廣泛流傳的錯(cuò)誤概念是共享變量模型運(yùn)行細(xì)粒度(FineGranularity)的并行性比消息傳遞模型好要注意共享變量模型是一種并行編程模型，它可以實(shí)現(xiàn)在PVP、SMP、DSM、MPP或甚至機(jī)群的任意并行平臺(tái)上。支持細(xì)粒度并行性的平臺(tái)應(yīng)具有有效的通信／同步機(jī)制，一個(gè)共享變量的程序可能遭到，高的相互作用開(kāi)銷，從而遠(yuǎn)比運(yùn)行在機(jī)群、MPP甚至SMP上的消息傳遞程序慢得多。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院②一個(gè)普遍的說(shuō)法是共享變量編程比消息傳遞編程容易此說(shuō)法雖不錯(cuò)，但科學(xué)試驗(yàn)的事實(shí)尚未完全建立。為了開(kāi)發(fā)一個(gè)新的、有效的、松散同步的、通信模式規(guī)則的并行程序，共享變量的方法未必比消息傳遞方法容易。當(dāng)然對(duì)于非規(guī)則的并行程序，使用消息傳遞原語(yǔ)很難指明所需要的相互作用；同時(shí)共享變量模型允許全局指針操作，而消息傳遞模型是無(wú)此能力的；此外，共享變量編程雖不必明顯地劃分和分配數(shù)據(jù)，但這也可能傷害性能。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院③就查錯(cuò)而論，共享變量程序可能比消息傳遞程序更困難共享變量程序中的所有進(jìn)程都駐留在單地址空間中，而且訪問(wèn)共享數(shù)據(jù)必須由同步結(jié)構(gòu)(如鎖和臨界區(qū))加以保護(hù)。同步錯(cuò)誤易出現(xiàn)，而且一旦出現(xiàn)就難以查找；但在消息傳遞程序中，此類錯(cuò)誤出現(xiàn)的頻度大大減少，因?yàn)橹T進(jìn)程不共享單一地址空間。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.三種方法的比較：哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院可用3種方法實(shí)現(xiàn)任何編程模型在任何并行平臺(tái)上，3種方法和編程模型可行以各種方式組合例題：CrayMPP編程模型，設(shè)計(jì)一個(gè)稱為CrayCraft的集成編程工具；使用上述所有3種方法(新構(gòu)造、庫(kù)函數(shù)和編譯器命令)實(shí)現(xiàn)了數(shù)據(jù)并行(Fortran90)、共享變量(工作共享)以及消息傳遞(PVM)編程模型。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第2章并行編程基礎(chǔ)

1并行編程綜述

2進(jìn)程任務(wù)和線程

3并行性問(wèn)題

4交互和通信問(wèn)題哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

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

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院程序(代碼)

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

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

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

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

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

只用術(shù)語(yǔ)進(jìn)程來(lái)表示重量級(jí)進(jìn)程或線程：

輕量級(jí)進(jìn)程=線程哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第2章并行編程基礎(chǔ)

1并行編程綜述

2進(jìn)程任務(wù)和線程

3并行性問(wèn)題

4交互和通信問(wèn)題哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

3

并行性問(wèn)題并行編程帶來(lái)的許多額外問(wèn)題。重點(diǎn)討論在用戶程序中由于對(duì)并行性所作的說(shuō)明而引起的問(wèn)題。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院一、進(jìn)程中的同構(gòu)性

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

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

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

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

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

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

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

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

1并行編程綜述

2進(jìn)程任務(wù)和線程

3并行性問(wèn)題

4通信問(wèn)題哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

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

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

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

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

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

spin(release=1);／*等待其他進(jìn)程到達(dá)*／}哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

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

(1)測(cè)試并設(shè)置(Test&Set)

Test＆Set(S，temp)是一個(gè)原子操作指令，它將共享變量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è)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院應(yīng)用：封鎖共享變量Lock(shared-datum)；Update(shared-datum)；Unlock(shared-datum)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院例子：

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

Test＆Set(S，temp)；

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

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

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

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

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

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

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