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

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

1并行編程綜述

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

3并行性問題

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

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

并行編程處于初級階段；對于并行問題的應(yīng)用，不太可能有一個(gè)現(xiàn)成的并行代碼；并行代碼的機(jī)器不同。并行編程也不支持成熟、通用和穩(wěn)定的工具；并行算法范例仍未能被很好地理解或被廣泛地接受；不存在單一、通用的機(jī)器模型；哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院與順序語言在編程或自然模型級上相比,缺少代可擴(kuò)展和異構(gòu)可擴(kuò)展的能力這些并行語言大多數(shù)在當(dāng)前系統(tǒng)上使用的并行語言均是Fortran或C的某種擴(kuò)展。一個(gè)編程模型即是程序員在開發(fā)一個(gè)并行程序時(shí)所見到和使用的模型。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院自然模型的定義：是由一個(gè)特定并行計(jì)算機(jī)平臺所提供的、用戶可見的最低層的編程模型。其他的編程模型可在此自然模型上加以實(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)步：已開發(fā)了許多并行算法盡管大多數(shù)算法基于非現(xiàn)實(shí)的PRAM模型，但其中某些在作適當(dāng)修正后可以實(shí)用。已涌現(xià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)式用戶只需編寫順序程序，其中的蘊(yùn)式并行性由并行化編譯器(如Kap)進(jìn)行析取。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.吞吐率處理

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

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

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

(MessagePassing)

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

1并行編程綜述

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

3并行性問題

4交互和通信問題哈爾濱工業(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)既簡單又能很好地適合于并行計(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ù)語程序變量集的定義：一個(gè)程序使用兩個(gè)變量集：數(shù)據(jù)變量由程序員聲明用來保存數(shù)據(jù)值的變量?？刂谱兞渴潜４婵刂菩畔⒌淖兞?，它們不需要顯式說明?？刂谱兞勘４娴氖怯嘘P(guān)下一步應(yīng)執(zhí)行什么操作的信息。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院配對集的定義：在任何時(shí)候，一個(gè)程序的每個(gè)數(shù)據(jù)或控制變量需與一個(gè)值配為一對，該值可能是一個(gè)未定義的特殊值。在時(shí)間t時(shí)所有(數(shù)據(jù)變量，數(shù)據(jù)值)的配對集定義了時(shí)間t的程序的數(shù)據(jù)狀態(tài)。類似地，時(shí)間t的所有(控制變量，控制值)配對集定義了時(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)不會終結(jié)的狀態(tài)時(shí)，則說該程序進(jìn)入了發(fā)散狀態(tài)。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院進(jìn)程狀態(tài)在任何時(shí)間，進(jìn)程具有某個(gè)狀態(tài)(status)。下圖畫出了某些重要狀態(tài)以及它們之間的轉(zhuǎn)換。

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

只用術(shù)語進(jìn)程來表示重量級進(jìn)程或線程：

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

1并行編程綜述

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

3并行性問題

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

3

并行性問題并行編程帶來的許多額外問題。重點(diǎ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就開始同時(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)的速記記號來標(biāo)明并行塊如下：

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院ParbeginProcess(1)······Process(n)Parend可簡化成如下的并行循環(huán)：Parfor(i=1；i<=n：i++){Process(i)}并行循環(huán)常用來說明SPMD并行程序。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院可以用SPMD來仿真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上，許多編程語言不提供并行塊或并行循環(huán)構(gòu)造。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院例如，ParbeginA；B；C；parend，用多代碼進(jìn)行說明：runAOnnode1runBOnnode2runCOnnode3程序A、B和C僅是順序程序加上進(jìn)行交互的庫調(diào)用。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院SPMD程序可用單代碼方法加以說明。例如，要說明并行循環(huán)parfor(i=0：i<N；i++){foo(i)}，用戶只需編寫如下的一個(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)造加以說明。例如，一個(gè)并行循環(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è)大學(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操作加以表示。它們也可用單代碼或多代碼方法加以說明。

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院例：下列程序有3個(gè)進(jìn)程，其中A是主進(jìn)程，當(dāng)程序開始執(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)識符(ID)，它唯一地識別并行程序中的組。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院為支持組的概念，并行編程語言需要提供管理進(jìn)程組的功能如創(chuàng)建和毀滅組、詢問組的ID、組的成員以及組員的排序等。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院四、分配問題任何并行程序必須在某些數(shù)據(jù)對象上完成某些計(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.隱式和顯式分配

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

1并行編程綜述

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

3并行性問題

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

4通信問題交互操作稱為通信這里討論范圍廣一些：在并行系統(tǒng)中需支持的通信操作通信方式和模式競爭通信和合作通信哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院一、通信操作分為三種：數(shù)據(jù)交換（通信）同步聚集操作這些操作常統(tǒng)稱為通信它們對體系結(jié)構(gòu)和編程的支持有著不同的要求哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院通信的定義通信操作是指在兩個(gè)或多個(gè)進(jìn)程間傳送數(shù)據(jù)。分類：在共享存儲程序中的通信使用過程級并行性的多處理機(jī)程序用派生過程在多計(jì)算機(jī)模型中的通信哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院二、同步操作分三個(gè)大的方面來討論：同步的定義、高級同步結(jié)構(gòu)和低級同步原語1.同步的定義同步會成為系統(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ù)同步路障“我找到了”互斥信號燈和鎖產(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.高級同步結(jié)構(gòu)現(xiàn)今的多處理器系統(tǒng)的并行程序設(shè)計(jì)環(huán)境，提供了四種類型的同步原語：事件:用于實(shí)現(xiàn)產(chǎn)—銷同步路障:用在柵欄同步中鎖/信號燈：用于實(shí)現(xiàn)互斥形式原子性臨界區(qū):用于實(shí)現(xiàn)互斥形式原子性哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院（1）信號燈和鎖鎖的普通用法就是通過互斥將臨界區(qū)轉(zhuǎn)換成原子操作。信號燈S是一個(gè)非負(fù)0或1的布爾量，對其能進(jìn)行兩個(gè)原子操作P(S)和V(S)：①若s不為0，P(S)操作使S減1；②若s不為1，V(S)操作將S值加1。S是二元信號燈，取值為真或假，也稱之為鎖。相應(yīng)地，對于鎖S，其P(S)和V(S)常寫做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)問題：①非結(jié)構(gòu)性：鎖不是一種結(jié)構(gòu)化的結(jié)構(gòu)，容易用錯(cuò)它，如果lock／unlock語句漏掉或冗余，則編譯器不能查出它；②重疊說明：鎖不是用戶所真正想要的，它只是達(dá)到原子性的一種方法。鎖損害了程序的可移植性，且使代碼難于理解；哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院③狀態(tài)相關(guān)：鎖引入了信號燈S及使用條件原子操作lock(S)，一個(gè)進(jìn)程能否穿過lock(S)，依賴于信號燈變量S之值，一般而言，像這樣的與狀態(tài)有關(guān)的數(shù)據(jù)是難于理解的；④順序執(zhí)行：對于有些事務(wù)處理操作，即使可并行訪問，但由于使用鎖互斥，它們只能一次執(zhí)行一個(gè)，同樣這種順序執(zhí)行也不是用戶想要的；⑤鎖開銷：順序執(zhí)行l(wèi)ock(S)和unlock(S)也存在著附加的開銷，而且當(dāng)n個(gè)進(jìn)程每個(gè)都執(zhí)行l(wèi)ock(S)操作時(shí)，它們中至多一個(gè)能成功，其余者均必須重復(fù)訪問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)程因缺頁或超時(shí)被中斷時(shí)，其他的進(jìn)程因等待鎖不能前進(jìn)；⑧死鎖(Deadlock)：假定兩進(jìn)程P與Q，欲進(jìn)行X與Y操作：當(dāng)進(jìn)程P已為X保持了一把鎖并想為Y申請一把鎖；而進(jìn)程Q已為Y保持了一把鎖并想為X申請一把鎖時(shí)，此時(shí)沒有任何進(jìn)程在其得到鎖之前釋放一把鎖，結(jié)果誰也得不到所要求的鎖。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院（3）臨界區(qū)是指OS所使用的臨界區(qū)，其語法結(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ū)，其語法結(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)說明和初始化一個(gè)隱含的信號燈S，并產(chǎn)生正確的lock／unlock語句。臨界區(qū)比鎖有很多優(yōu)點(diǎn)，它是結(jié)構(gòu)化的、與狀態(tài)無關(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è)用來記錄到達(dá)路障的進(jìn)程數(shù)；另一個(gè)用來封鎖進(jìn)程，直至最后一個(gè)進(jìn)程到達(dá)。路障的實(shí)現(xiàn)中，要不停地探測指定的變量，直到滿足條件為止。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院例子：路障的實(shí)現(xiàn)過程，其中，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)；／*開鎖*／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é)院

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

(1)測試并設(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é)院說明：上例中，使用了Test＆Set操作執(zhí)行l(wèi)ock(S)，其中第一個(gè)while循環(huán)檢查鎖S是否已由別的進(jìn)程釋放。由于每次執(zhí)行Test＆Set都要寫共享變量S，所以可能導(dǎo)致頻繁的存儲器訪問。哈爾濱工業(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í)行鎖功能。示例對照如下：0ld=balance[x]；／*讀共享變量*／

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

Fetch＆Add(S，V)Result=S；S=S+V；ReturnResult；哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院該指令不僅簡單，而且快速，例如：上節(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é)院聚集的主要特征是：它由一