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

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

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

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

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

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

第500名：0.42Gflops2011年6月世界第一的計(jì)算機(jī)：8162Tflops，

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

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

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

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

p

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

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

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

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

f=Ws/W

一般表示ts

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

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

所需要的時(shí)間Tp：在并行機(jī)上完成Wp

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

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

個(gè)處理器的并行計(jì)算機(jī)，其最大可能的加速比為：S=1f+(1-f)/p……ts(1-f)tsfts多處理機(jī)：：：p個(gè)處理機(jī)單處理機(jī)串行部分可并行化部分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è)算法中每個(gè)計(jì)算步的執(zhí)行時(shí)間是相等的情況下，算法的執(zhí)行時(shí)間也常用計(jì)算步來(lái)計(jì)算。WpWpWpWpWpWpWpWpWsWsWsWsWsWsWsWs12345678處理機(jī)個(gè)數(shù)W工作負(fù)載

Ts

TsTs

Ts

Ts

Ts

Ts

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

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

的布爾數(shù)組；2、目前找到的下一個(gè)質(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//找下一個(gè)新質(zhì)數(shù)

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

循環(huán)變量P1

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

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

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

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

4

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

/p當(dāng)p

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

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

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

，W=1107，

Ws=1105，可得：Wp=1107-1105=99105f=Ws/W=0.01總運(yùn)算量為1107次浮點(diǎn)運(yùn)算，其中1105次浮點(diǎn)運(yùn)算可由任一結(jié)點(diǎn)執(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總運(yùn)算量增加到9.9107+1105=9.91107次浮點(diǎn)運(yùn)算，其中的1105次浮點(diǎn)運(yùn)算可由任一結(jié)點(diǎn)執(zhí)行。b)屬于工作負(fù)載隨處理機(jī)個(gè)數(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ù)域并行算法有共享存儲(chǔ)器的數(shù)據(jù)并行算法沒(méi)有共享存儲(chǔ)器的數(shù)據(jù)并行算法帶I/O操作的數(shù)據(jù)并行算法(已解釋）1)控制并行算法當(dāng)前質(zhì)數(shù)234567N共享存儲(chǔ)器互連網(wǎng)絡(luò)P0

循環(huán)變量P1

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

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

花費(fèi)1個(gè)單位時(shí)間串行算法的執(zhí)行時(shí)間ts：假設(shè)有k個(gè)≤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時(shí),其串行算法的時(shí)間為1411(單位時(shí)間)?？刂撇⑿兴惴ǖ膱?zhí)行時(shí)間：假設(shè)有k個(gè)≤Sqrt(N)

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

循環(huán)變量P1

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

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

個(gè)處理器對(duì)應(yīng)的語(yǔ)句為：

fori:=k+NextPrimeto(NdivNextPrime)stepp

doS[i*NextPrime]:=false;

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

p

個(gè)處理器，且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時(shí)，其并行算法的時(shí)間為：1411/8=177(單位時(shí)間)加速比S(p)=1411/177≈8數(shù)據(jù)域并行算法（分布存儲(chǔ)）互連網(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è)：布爾