并行計算大學(xué)課件1

第二章并行計算機及并行計算的性能評價并行計算機Flynn分類法并行計算機類型MPMD和SPMD并行程序結(jié)構(gòu)并行計算的性能評價并行計算相關(guān)的基本概念加速比定律一、并行計算機Flynn分類法并行計算機類型MPMD和SPMD并行程序結(jié)構(gòu)Flynn分類法Flynn(1966年)分類法是根據(jù)系統(tǒng)的指令流(instructionstreams)和數(shù)據(jù)流(datastreams)對計算機系統(tǒng)進(jìn)行分類的一種方法。計算機在單個時間點上能夠處理的指令流的數(shù)量計算機在單個時間點上能夠處理的數(shù)據(jù)流的數(shù)量多指令流單數(shù)據(jù)流MISD多指令流多數(shù)據(jù)流MIMD單指令流單數(shù)據(jù)流SISD單指令流多數(shù)據(jù)流SIMD指令流數(shù)據(jù)流SISD：傳統(tǒng)的單處理機系統(tǒng)。由程序生成的一個單指令流，在任意時刻處理單獨的數(shù)據(jù)項。SIMD：如：陣列處理機系統(tǒng)(ProcessorArrays)。由一個控制器負(fù)責(zé)從存儲器中取出指令并將這些指令發(fā)送給各個處理器，每個處理器同時執(zhí)行相同的指令，但操作不同的數(shù)據(jù)。MISD：相當(dāng)于在指令一級并行，而在被操作的數(shù)據(jù)級串行的情況，實際上這種模型是不能實現(xiàn)的。MIMD：當(dāng)今絕大多數(shù)并行計算機都屬于這一類。每個處理器擁有一個單獨的程序（段），每個程序（段）為每一個處理器生成一個指令流，每條指令對不同的數(shù)據(jù)進(jìn)行操作。Flynn分類法實際上并不能對所有計算機進(jìn)行分類，如流水線向量處理機就難于按Flynn分類法簡單地歸為上述四類之一。一、并行計算機Flynn分類法并行計算機類型MPMD和SPMD并行程序結(jié)構(gòu)1972年,誕生了第一臺并行計算機ILLIACⅣ(IllinoisIntegratorandAutomaticComputer)

伊利諾斯(理工學(xué)院)積分儀和自動計算機由Illinois大學(xué)和Burrouphs公司合作研制成功的運算速度為1.5億次/秒(150M次/秒)由64臺處理器組成的陣列機(ArrayComputer)可對數(shù)組進(jìn)行并行計算它是當(dāng)時性能最高的CDC7600機器速度的2—6倍。并行計算機類型并行計算機類型1）并行向量處理機2）對稱多處理機3）大規(guī)模并行處理機4）分布式共享存儲多處理機系統(tǒng)5）機群系統(tǒng)并行向量處理機(ParallelVectorProcessorsPVP)1976年，出現(xiàn)了具有實用價值的向量處理機Cray-1單處理機模式，向量寄存器運算速度：3—160Mflops平均速度：20—80Mflops向量點積速度：22Mflops利用大量的向量寄存器快速地實現(xiàn)向量運算；1985年，CrayInc.推出Cray-2超級計算機，該機的向量處理速度是Cray-1的12倍(1Gflops)；80年代中、后期是PVP的時代，有很多PVP相繼問世。PVP結(jié)構(gòu)模型VPVPVP…交叉開關(guān)SMSMSM…VP:VectorProcessorSM:SharedMemory對稱多處理機

(SymmetricMultiprocessorSMP)將各處理器經(jīng)由高速總線（或交叉開關(guān)）網(wǎng)與共享存儲器相連；每個處理器對共享存儲器具有同等的訪問權(quán)利；每個處理器對I/O設(shè)備和其它系統(tǒng)資源享有同等的訪問權(quán)利；在SMP系統(tǒng)中一般要求每個處理機是相同的；因此稱之為對稱多處理機。對稱多處理機結(jié)構(gòu)模型P/C…總線或交叉開關(guān)I/OSMSM…P/CP/CP/C:Processor/CacheSM:SharedMemoryI/O:Input/Output典型SMP機型SGI公司的SGIOnyx系統(tǒng)和SGIPowerChallengeSequentConputerSystem,Inc.的SequentSymmetryS-81系統(tǒng)IBM公司的ES/9000系統(tǒng)和R50Sun公司的SparcCenter2000我國的曙光1號大規(guī)模并行處理機(MassivelyParallelProcessorsMPP)采用松耦合體系結(jié)構(gòu)連接各種不同的處理器即各處理器以使用自己的局部內(nèi)存為主，處理器之間進(jìn)行同步通信實現(xiàn)數(shù)據(jù)交換大規(guī)模并行處理機結(jié)構(gòu)模型LM1LM2LMnP/C1P/C2P/Cn……

專用互連網(wǎng)絡(luò)P/C:Processor/CacheLM:LocalMemoryMPP的優(yōu)點：突破了只看到一個統(tǒng)一的存儲空間的方式具有良好的可擴展性MPP的缺點：分布存儲要求用戶必須將被操作的數(shù)據(jù)分配到各局部存儲器中運算過程中用戶要考慮數(shù)據(jù)在各節(jié)點間的傳送和同步典型的MPP機型：Intel公司的ParagonXP/SMasPar公司的MP-2ThinkingMachine公司的CM-5IBM公司的SP2Cray公司的CrayT3D我國的曙光1000分布式共享存儲多處理機系統(tǒng)(DistributedSharedMemoryDSM)DSM系統(tǒng)具有以下特點：存儲器在物理上分布于各處理器附近，但在邏輯上可由多個處理器共享整個內(nèi)存DSM系統(tǒng)實際上是SMP和MPP結(jié)構(gòu)的折中DSM的優(yōu)點：避免了集中式存儲結(jié)構(gòu)中處理器和存儲器的復(fù)雜連接有良好的可擴展性相對MPP來說，更容易編程分布式共享存儲多處理機系統(tǒng)LM1LM2LMnP/C1P/C2P/Cn……專用互連網(wǎng)絡(luò)DSM的優(yōu)點：避免了集中式存儲結(jié)構(gòu)中處理器和存儲器的復(fù)雜連接有良好的可擴展性相對MPP來說，更容易編程DSM系統(tǒng)需著重考慮的問題：系統(tǒng)應(yīng)具有維持存儲器訪問一致性的硬件支持相對SMP系統(tǒng)來說，其訪問非物理局部存儲器的時間要更長。典型的DSM機型：Cray公司的CrayT3ESGI/Cray公司的Origon2000BBN公司的TC2000機群系統(tǒng)（工作站機群）(ClusterOfWorkstationsCOW,NetworkedOfWorkstationsNOW)COW的結(jié)構(gòu)特點：每一個節(jié)點機都是一個完整的工作站或PC機各節(jié)點機通過成本較低的商業(yè)網(wǎng)絡(luò)連接起來各節(jié)點內(nèi)都有本地磁盤一個完整的操作系統(tǒng)駐留在每個節(jié)點中工作站機群結(jié)構(gòu)模型LM1LM2LMnP/C1P/C2P/Cn……通用互連網(wǎng)絡(luò)LD1LD2LDn…P/C:Processor/CacheLM:LocalMemoryLD:LocalDiskCOW結(jié)構(gòu)的優(yōu)點：系統(tǒng)開發(fā)周期短，用戶投資風(fēng)險小系統(tǒng)價格低，節(jié)約系統(tǒng)資源系統(tǒng)的擴展性好，用戶編程方便COW系統(tǒng)應(yīng)考慮的主要問題：如何減少節(jié)點機間的通信開銷如何改善并行程序設(shè)計環(huán)境如何充分利用全局資源并行向量處理機PVP對稱多處理機SMP大規(guī)模并行處理機MPP分布式共享存儲多處理機DSM工作站機群COW共享存儲多處理機系統(tǒng)分布式共享存儲器系統(tǒng)消息傳遞多計算機系統(tǒng)消息傳遞多計算機系統(tǒng)共享存儲的多處理機（系統(tǒng)）MP與

分布存儲的多計算機（系統(tǒng)）MC的比較性能多處理機(MP)多計算機(MC)存儲器編址單地址多地址處理機間的數(shù)據(jù)傳送共享變量消息傳遞數(shù)據(jù)傳遞的同步緊（同步）松（同步）或異步編程容易復(fù)雜可擴展性差好一、并行計算機Flynn分類法并行計算機類型MPMD和SPMD并行程序結(jié)構(gòu)SIMD和MIMD計算機SIMD：由一個控制器負(fù)責(zé)從存儲器中取出指令并將這些指令發(fā)送給各個處理器，每個處理器同步執(zhí)行相同的指令，但操作不同的數(shù)據(jù)。數(shù)據(jù)陣列計算、圖像處理MIMD：每個處理器擁有一個單獨的程序，每個程序為每一個處理器生成一個指令流，每條指令對不同的數(shù)據(jù)進(jìn)行操作。MPMD和SPMD并行程序結(jié)構(gòu)進(jìn)程：完成一定功能的一段程序的一次運行活動。在并行計算中，進(jìn)程的并行執(zhí)行方式：MPMD(MultiplePrograms&MultipleData)控制并行結(jié)構(gòu)：在這種并行結(jié)構(gòu)中各進(jìn)程執(zhí)行的程序不同，操作的數(shù)據(jù)也不同。各進(jìn)程既可以是異步執(zhí)行的，也可以以同步方式執(zhí)行。SPMD(SingleProgram&MultipleData)數(shù)據(jù)域并行結(jié)構(gòu)：在分布存儲并行系統(tǒng)上執(zhí)行的程序，每個進(jìn)程執(zhí)行相同的程序，但處理不同的數(shù)據(jù)。MPMD和SPMD并行程序結(jié)構(gòu)在SPMD程序設(shè)計中，所有節(jié)點機得到相同的程序副本，但程序中可以含有條件語句來決定哪個節(jié)點機執(zhí)行某段程序與否。SPMD和SIMD的區(qū)別SIMD計算機上執(zhí)行的并行程序往往是由硬件來保障各處理器同步執(zhí)行指令的過程，它是緊同步的。而SPMD結(jié)構(gòu)的并行程序，既可以緊同步形式執(zhí)行，同時也可以松散同步的形式執(zhí)行。P1P2P3Pp……時間并行程序執(zhí)行時間第二章并行計算機及并行計算的性能評價并行計算機Flynn分類法并行計算機類型MPMD和SPMD并行程序結(jié)構(gòu)并行計算的性能評價并行計算相關(guān)的基本概念加速比定律二、并行計算的性能評價并行計算相關(guān)的基本概念加速比定律適用于固定計算負(fù)載的Amdahl定律適用于擴展問題的Gustsfson定律并行計算相關(guān)的基本概念并行計算(parallelcomputing)—在緊耦合并行機上的計算分布計算(distributedcomputing)—在松耦合（異地）并行機上的計算網(wǎng)格計算(gridcomputing)—屬于分布計算范疇，利用互聯(lián)網(wǎng)把分散在不同地理位置的性能較高的計算機組織成一個“虛擬的超級計算機”，來完成的計算。超強的數(shù)據(jù)處理能力；能夠充分利用網(wǎng)絡(luò)上的閑置處理能力（計算、存儲）。并行計算相關(guān)的基本概念云計算(cloudcomputing)狹義云計算是指通過網(wǎng)絡(luò)以按需、易擴展的方式獲得所需的資源（硬件、平臺、軟件）。提供資源的網(wǎng)絡(luò)被稱為“云”。“云”中的資源在使用者看來是可以無限擴展的，并且可以隨時獲取，按需使用，隨時擴展，按使用付費。這種特性經(jīng)常被稱為像水電一樣使用IT基礎(chǔ)設(shè)施。廣義云計算是指通過網(wǎng)絡(luò)以按需、易擴展的方式獲得所需的服務(wù)。這種服務(wù)可以是IT和軟件、互聯(lián)網(wǎng)相關(guān)的，也可以是任意其他的服務(wù)。云計算是并行計算、分布式計算和網(wǎng)格計算的發(fā)展，或者說是這些計算機科學(xué)概念的商業(yè)實現(xiàn)。云計算的特點超大規(guī)?！霸啤本哂邢喈?dāng)?shù)囊?guī)模，Google云計算已經(jīng)擁有100多萬臺服務(wù)器，Amazon、IBM、微軟、Yahoo等的“云”均擁有幾十萬臺服務(wù)器。虛擬化——云計算支持用戶在任意位置、使用各種終端獲取應(yīng)用服務(wù)。用戶只需要一臺筆記本或者一個手機，就可以通過網(wǎng)絡(luò)服務(wù)來實現(xiàn)我們需要的一切，甚至包括超級計算這樣的任務(wù)。高可靠性——“云”使用了數(shù)據(jù)多副本容錯、計算節(jié)點同構(gòu)可互換等措施來保障服務(wù)的高可靠性。通用性——云計算不針對特定的應(yīng)用，在“云”的支撐下可以構(gòu)造出千變?nèi)f化的應(yīng)用，同一個“云”可以同時支撐不同的應(yīng)用運行。云計算的特點（續(xù)）高可擴展性——“云”的規(guī)?？梢詣討B(tài)伸縮，滿足應(yīng)用和用戶規(guī)模增長的需要。按需服務(wù)——“云”是一個龐大的資源池，你按需購買；云可以象自來水，電，煤氣那樣計費。極其廉價——由于“云”的特殊容錯措施可以采用極其廉價的節(jié)點來構(gòu)成云，“云”的自動化集中式管理使大量企業(yè)無需負(fù)擔(dān)日益高昂的數(shù)據(jù)中心管理成本，“云”的通用性使資源的利用率較之傳統(tǒng)系統(tǒng)大幅提升，因此用戶可以充分享受“云”的低成本優(yōu)勢，經(jīng)常只要花費幾百美元、幾天時間就能完成以前需要數(shù)萬美元、數(shù)月時間才能完成的任務(wù)。微操作級并行化串行處理程序級并行化子程序級并行化語句級并行化操作級并行化粗粒度中粒度細(xì)粒度二、并行計算的性能評價并行處理(parallelProcessing)：在同一時間段內(nèi)，在多個處理機中執(zhí)行同一任務(wù)的不同部分。多道處理(multiprocessing)：強調(diào)由一臺計算機利用一個處理機同時交錯地執(zhí)行多道程序。并發(fā)處理(concurrent)：與多道處理類似。并行計算相關(guān)的基本概念巨型(超級)計算機(supercomputer)：超級計算機是一個相對概念，不同的年代它的性能是不一樣的。它是運算速度特別快，數(shù)據(jù)輸入/輸出能力特別強的大型計算機系統(tǒng)。1993年6月世界第一的計算機：59.7Gflops，

第500名：0.42Gflops2011年6月世界第一的計算機：8162Tflops，

第500名：40.19Tflops數(shù)據(jù)并行(dataparallelism)：利用多個處理器對一個數(shù)據(jù)集上的不同元素同時進(jìn)行相同的操作?？刂撇⑿?controlparallelism)：為了完成一個任務(wù)要對不同的數(shù)據(jù)元素同時進(jìn)行不同的操作。并行計算相關(guān)的基本概念并行計算機存儲器訪問模型分為兩大類：共享存儲型(sharedmemory)

在這種并行機中，每個處理器都可以經(jīng)由互連網(wǎng)絡(luò)對共用內(nèi)存進(jìn)行存取操作。系統(tǒng)對共享內(nèi)存各模塊進(jìn)行統(tǒng)一編址。均勻存儲訪問模型UMA和非均勻存儲訪問模型NUMA非共享(分布)存儲型(distributedmemory)

在這種并行機中，每個處理器擁有自己的局部內(nèi)存。并行計算相關(guān)的基本概念（并行算法的）加速比

(speedup)或加速系數(shù)(speedupfactor)：完成計算的最佳串行算法所需的時間與完成相同任務(wù)的并行算法所需的時間之比。并行效率(parallelefficiency)：加速比與所用處理機個數(shù)之比。并行效率表示在并行機執(zhí)行并行算法時，平均每個處理機的執(zhí)行效率。并行計算相關(guān)的基本概念為了對一個并行任務(wù)評估，通常我們使用在單處理機上運行最快的已知算法的執(zhí)行時間與并行任務(wù)的執(zhí)行時間進(jìn)行比較，即加速比。加速比S(p)=使用單處理器最佳串行算法執(zhí)行時間在具有p臺處理機的系統(tǒng)上算法的執(zhí)行時間對于

p

個處理器來說，其最大加速比為p。當(dāng)計算任務(wù)可被分成相等執(zhí)行時間的進(jìn)程時，一個進(jìn)程映射到一個處理器上時，若此時沒有其它開銷就可獲得最大加速比p。一般表示p：并行系統(tǒng)中處理器的個數(shù)(thenumberofprocessors)W：問題規(guī)?；蚬ぷ髫?fù)載(workload)Ws：應(yīng)用問題中必須串行執(zhí)行的部分Wp

：應(yīng)用問題中可并行執(zhí)行的部分

W=Ws+Wpf：串行執(zhí)行部分

Ws占全部工作負(fù)載W的比例

f=Ws/W

一般表示ts

：整個任務(wù)在串行機上執(zhí)行所需的時間tp

：整個任務(wù)在并行機上執(zhí)行所需的時間Ts：完成Ws

所需要的時間Tp：在并行機上完成Wp

所需要的時間S：加速比：S(p)=ts/tp

E：并行效率：E=S(p)/p*100%加速比定律適用于固定計算負(fù)載的Amdahl定律適用于擴展問題的Gustsfson定律適用于固定計算負(fù)載的Amdahl定律當(dāng)并行計算機中處理器數(shù)目增加時，固定負(fù)載就被分配給更多的處理器去并行執(zhí)行，其主要目的是想盡可能快地的得出結(jié)果，即計算任務(wù)的實時性要求更高。Amdahl定律(1967)：設(shè)f為給定計算任務(wù)中必須串行執(zhí)行的部分所占比例(0≤f≤1)，對于一臺含有p

個處理器的并行計算機，其最大可能的加速比為：S=1f+(1-f)/p……ts(1-f)tsfts多處理機：：：p個處理機單處理機串行部分可并行化部分tp(1-f)ts/p……S=Ws+WpWs+Wp/p=fW

+(1-f)WfW

+((1-f)W)

/p=f+(1-f)f+(1-f)

/p=1f+(1-f)

/pS=tsf*ts+(1-f)ts/p=1f+(1-f)

/p在假設(shè)算法中每個計算步的執(zhí)行時間是相等的情況下，算法的執(zhí)行時間也常用計算步來計算。WpWpWpWpWpWpWpWpWsWsWsWsWsWsWsWs12345678處理機個數(shù)W工作負(fù)載

Ts

TsTs

Ts

Ts

Ts

Ts

TsTpTpTpTpTpTpTpTp12345678處理機個數(shù)T執(zhí)行時間篩法求質(zhì)數(shù)的例子問題----篩法求質(zhì)數(shù)對給定的正整數(shù)N，求出2到N內(nèi)所有的質(zhì)數(shù)。23456789101112131415161718192021222324252627282930234567891011121314151617181920212223242526272829302923191713117532

最終結(jié)果2345678910111213141516171819202122232425262728293023456789101112131415161718192021222324252627282930篩法求質(zhì)數(shù)的例子篩法求質(zhì)數(shù)的順序算法需要三個關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)：1、對應(yīng)于自然數(shù)2，3，4，…,N

的布爾數(shù)組；2、目前找到的下一個質(zhì)數(shù)；3、用于標(biāo)記當(dāng)前質(zhì)數(shù)倍數(shù)的循環(huán)變量。篩法求質(zhì)數(shù)串行算法fori:=2toNdoS[i]:=true;//初始化UpLimit:=sqrt(N);NextPrime:=2;whileNextPrime<=UpLimitdobeginfori:=NextPrimetoNdivNextPrimedoS[i*NextPrime]:=false;//篩掉當(dāng)前質(zhì)數(shù)的倍數(shù)

repeat//找下一個新質(zhì)數(shù)

NextPrime:=NextPrime+1;untilS[NextPrime]end;考慮在帶有I/O設(shè)備的共享存儲型并行機上數(shù)據(jù)并行算法I/O設(shè)備當(dāng)前質(zhì)數(shù)234567N共享存儲器P0

循環(huán)變量P1

循環(huán)變量Pp-1

循環(huán)變量…當(dāng)N=106時，其串行算法要完成：1）對質(zhì)數(shù)倍數(shù)標(biāo)記的次數(shù)為2,122,0482）需要輸出78,498個質(zhì)數(shù)假設(shè)標(biāo)記質(zhì)數(shù)的倍數(shù)一次和輸出一個質(zhì)數(shù)的時間均為1個單位時間，則串行算法的執(zhí)行時間為：2,122,048+78,498=2,200,546

f=78,498/2,200,546=0.0357在具有p個處理器的并行機上可能獲得的最大加速比為:10.0357+0.9643

/p加速比161284148121620242832處理器個數(shù)1

4

812處理機個數(shù)時間計算時間I/O時間S=S(p)=1f+(1-f)

/p當(dāng)p

無限增加時，加速比趨于1/f。從剛才的例子中看出：f=0.0357，那么可獲得的最大加速比不會超過1/0.0357≈28，它與處理機的個數(shù)無關(guān)。即當(dāng)處理機的個數(shù)超過一定數(shù)量后，加速比不會隨著其增加而增加。Amdahl定律曾經(jīng)給并行計算理論的研究帶來了很大的負(fù)面影響。適用于擴展問題的Gustsfson定律Amdahl定律的一個主要缺點：固定負(fù)載妨礙了并行機性能可擴展性的開發(fā)。有些計算任務(wù)要求在給定的時間內(nèi)希望提高計算精度，即在給定的時間內(nèi)增加處理器的數(shù)量使計算量提高，如我們希望數(shù)值天氣預(yù)報的數(shù)據(jù)采樣模型的單位更小。在精度占主導(dǎo)位置的應(yīng)用領(lǐng)域中，我們希望象在小機器上解小問題一樣，在大機器上能解規(guī)模大的問題，并使二者所花費的時間大體相同。Gustafson定律(1988)：對于一臺并行計算機，當(dāng)問題中可并行部分?jǐn)U大p

倍時，其加速比也隨之增長：S’=p+(1-p)f=f+(1-f)p適用于擴展問題的Gustsfson定律=Ws+pWpWs+WpS’=Ws+pWpWs+pWp/p若我們用f

來表示，可將上式變?yōu)椋篠’=fW

+p(1-f)WfW

+p(1-f)W/p=f

+p(1-f)f

+(1-f)=f

+p(1-f)=p+(1-p)f12345678處理機個數(shù)W工作負(fù)載WsWsWsWsWsWsWsWsWpWpWpWpWpWpWpWpTpTpTpTpTpTpTpTpTsTsTsTsTsTsTsTs12345678處理機個數(shù)T執(zhí)行時間例：設(shè)某應(yīng)用問題在單節(jié)點機器上求解時需要執(zhí)行的運算量為1107次浮點運算（工作負(fù)載）,其中有1105次浮點運算必須順序執(zhí)行?，F(xiàn)考慮在一包含10個節(jié)點的多計算機系統(tǒng)求解該問題，同時將工作負(fù)載按以下兩種情況進(jìn)行調(diào)整：總運算量為1107次浮點運算，其中1105次浮點運算可由任一節(jié)點執(zhí)行；可并行的部分按節(jié)點數(shù)擴大為9.9107次浮點運算，而必須順序執(zhí)行的1105次浮點運算可由任一節(jié)點執(zhí)行。試計算a)和b)兩種情況下獲得的加速比。a)已知：p=10

，W=1107，

Ws=1105，可得：Wp=1107-1105=99105f=Ws/W=0.01總運算量為1107次浮點運算，其中1105次浮點運算可由任一結(jié)點執(zhí)行；a)屬于工作負(fù)載不變的情況，應(yīng)使用Amdahl定律求其加速比：S(p)=1/(f+(1-f)/p)=1/(0.01+0.99/10)=9.17b)已知：

p=10

，原W=1107，

Ws

=1105，可得：

f=Ws/W=0.01現(xiàn)Wp=(1107-1105)

p=99105*10=

9.9107總運算量增加到9.9107+1105=9.91107次浮點運算，其中的1105次浮點運算可由任一結(jié)點執(zhí)行。b)屬于工作負(fù)載隨處理機個數(shù)增加而增加的情況，應(yīng)使用Gustsfson定律求其加速比：S'=(Ws+Wp*p)/(Ws+Wp)=f+(1-f)*p=0.01+0.99*10=9.91篩法求質(zhì)數(shù)--并行算法控制并行算法數(shù)據(jù)域并行算法有共享存儲器的數(shù)據(jù)并行算法沒有共享存儲器的數(shù)據(jù)并行算法帶I/O操作的數(shù)據(jù)并行算法(已解釋）1)控制并行算法當(dāng)前質(zhì)數(shù)234567N共享存儲器互連網(wǎng)絡(luò)P0

循環(huán)變量P1

循環(huán)變量Pp-1

循環(huán)變量…算法中每一個處理機重復(fù)做兩件：找下一個質(zhì)數(shù)從該質(zhì)數(shù)的平方開始標(biāo)記該質(zhì)數(shù)的倍數(shù)各處理機直到遇到下一個質(zhì)數(shù)>sqrt(N)為止。處理機P0從22開始標(biāo)記2的倍數(shù)；處理機P1從32開始標(biāo)記3的倍數(shù)；處理機P2從52開始標(biāo)記5的倍數(shù)；……假設(shè)每一次標(biāo)記質(zhì)數(shù)的倍數(shù)

花費1個單位時間串行算法的執(zhí)行時間ts：假設(shè)有k個≤Sqrt(N)

的質(zhì)數(shù):1,2,…,kts

=N-12+11N-22+12N-k2+1k++…+=N+1-121N+1-222N+1-k2k++…+=N-32N-83N+1-k2k++…+當(dāng)N=1000時,其串行算法的時間為1411(單位時間)?？刂撇⑿兴惴ǖ膱?zhí)行時間：假設(shè)有k個≤Sqrt(N)

的質(zhì)數(shù):1,2,…,k01002003004005006007008009001000110012001300140015002357111317--31177213115311321375加速比=1411/706≈2并行效率≈2/2≈1加速比=1411/499≈2.83并行效率≈2.83/3≈0.94控制并行算法的執(zhí)行時間當(dāng)處理器的個數(shù)為2時：加速比=1411/706≈2，并行效率=2/2=1當(dāng)處理器的個數(shù)為3時：加速比=1411/499≈2.83并行效率=2.83/3=0.94當(dāng)處理器的個數(shù)為4時：加速比=1411/499≈2.83并行效率=2.83/4=0.71這個并行算法的加速比的上限為2.83。并行效率隨著處理器的個數(shù)（p>2）的增加而下降。2)數(shù)據(jù)并行算法數(shù)據(jù)并行算法可分為下列兩種情況：基于共享存儲并行機模型的并行算法基于分布存儲并行機模型的并行算法共享存儲型----數(shù)據(jù)并行算法當(dāng)前質(zhì)數(shù)234567N共享存儲器互連網(wǎng)絡(luò)P0

循環(huán)變量P1

循環(huán)變量Pp-1

循環(huán)變量…在共享存儲器并行機上，算法思路如下:當(dāng)一個處理器處于空閑時，它首先找下一個質(zhì)數(shù);所有的處理器同時對布爾數(shù)組進(jìn)行相同的操作----篩掉當(dāng)前質(zhì)數(shù)的倍數(shù)，只是每個處理器負(fù)責(zé)布爾數(shù)組的一段。第k

個處理器對應(yīng)的語句為：

fori:=k+NextPrimeto(NdivNextPrime)stepp

doS[i*NextPrime]:=false;

其中假設(shè)處理器的編號為0到p-1。在共享存儲型并行機上篩法求質(zhì)數(shù)算法的運行時間：假設(shè)系統(tǒng)有

p

個處理器，且N

是p的整倍數(shù)。tdp

=N-12+11*pN-22+12*pN-k2+1k*p++…+=N-32*pN-83*pN+1-k2k*p++…+當(dāng)N=1000、p=8時，其并行算法的時間為：1411/8=177(單位時間)加速比S(p)=1411/177≈8數(shù)據(jù)域并行算法（分布存儲）互連網(wǎng)絡(luò)P1

當(dāng)前質(zhì)數(shù)循環(huán)變量

234N/pP2

當(dāng)前質(zhì)數(shù)循環(huán)變量

N/p+12N/pPp

當(dāng)前質(zhì)數(shù)循環(huán)變量

(p-1)N/p+1N我們可以做如下假設(shè)：布爾