MapReduce海量數(shù)據(jù)并行處理ch.01

Ch.1.并行計(jì)算技術(shù)簡介MapReduce海量數(shù)據(jù)并行處理南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系主講人：黃宜華2011年春季學(xué)期鳴謝：本課程得到Google公司(北京）中國大學(xué)合作部精品課程計(jì)劃資助Ch.1.并行計(jì)算技術(shù)簡介1.為什么需要并行計(jì)算？2.并行計(jì)算技術(shù)的分類3.并行計(jì)算的主要技術(shù)問題4.MPI并行程序設(shè)計(jì)5.為什么需要大規(guī)模數(shù)據(jù)并行處理？1.為什么需要并行計(jì)算？貫穿整個(gè)計(jì)算機(jī)技術(shù)發(fā)展的核心目標(biāo)：提高計(jì)算性能！Intel微處理器每秒1千8百億次浮點(diǎn)運(yùn)算！近20年性能提高3千多倍巨型機(jī)：中國天河一號，2010年底世界TOP500強(qiáng)第1名

每秒2千5百多萬億次浮點(diǎn)運(yùn)算，近20年性能提高3千多倍億億千萬億百萬億十萬億萬億千億百億十億億提高計(jì)算機(jī)性能的主要手段1.提高處理器字長：70-80年代：Intel處理器：71年，4004，4bits；78年，8086，8bits；82年，80286:16bits；85年~90s，80386,486,Pentium,P2,P3,P4:32bits05年~，PentiumD往后-Corei3,i5,i7：64bits為什么需要并行計(jì)算？提高計(jì)算機(jī)性能的主要手段2.提高集成度摩爾定律：芯片集成度每18個(gè)月翻一倍，計(jì)算性能提高一倍為什么需要并行計(jì)算？為什么需要并行計(jì)算？提高計(jì)算機(jī)性能的主要手段3.流水線等微體系結(jié)構(gòu)技術(shù)

實(shí)現(xiàn)指令級并行(Instruction-LevelParallelism,

ILP）RISC結(jié)構(gòu)5級流水線

為什么需要并行計(jì)算？提高計(jì)算機(jī)性能的主要手段3.流水線等微體系結(jié)構(gòu)技術(shù)分支預(yù)測,寄存器重命名，超長指令字（VLIW），超標(biāo)量(Superscalar)，亂序執(zhí)行，Cache……

Pentium4(CISC結(jié)構(gòu)）采用了20級復(fù)雜流水線為什么需要并行計(jì)算？提高計(jì)算機(jī)性能的主要手段4.提高處理器頻率：1990s-2004：為什么需要并行計(jì)算？所有這些技術(shù)極大地提高了微處理器的計(jì)算性能，但2004后處理器的性能不再像人們預(yù)期的那樣提高單核處理器性能提升接近極限！集成度性能為什么需要并行計(jì)算？單核處理器性能提升接近極限1.VLSI集成度不可能無限制提高芯片集成度已進(jìn)入極小尺度級別，集成度不可能無限制提高1nm(納米)約頭發(fā)直徑的6萬分之一或4個(gè)原子長度10-20nm僅有幾百個(gè)原子的長度為什么需要并行計(jì)算？單核處理器性能提升接近極限2.處理器的指令級并行度提升接近極限

長指令字，流水線，分支預(yù)測，寄存器命名，超標(biāo)量，亂序執(zhí)行，動態(tài)發(fā)射，高速緩沖（Cache）……

高級流水線等各種復(fù)雜的微體系結(jié)構(gòu)技術(shù)都已得到研究應(yīng)用，難以進(jìn)一步挖掘更多的指令級并行性ILP墻為什么需要并行計(jì)算？單核處理器性能提升接近極限3.處理器速度和存儲器速度差異越來越大

處理器性能每2年翻一倍，而存儲器性能每6年翻一倍

為了匹配兩者間速度差異，處理器需要做越來越大的Cache存儲墻CPU計(jì)算速度：~1ns級別主存訪問速度：100ns級別為什么需要并行計(jì)算？單核處理器性能提升接近極限4.功耗和散熱大幅增加超過芯片承受能力晶體管密度不斷提高，單位面積功耗和散熱大幅增加主頻提高導(dǎo)致功耗和散熱急劇增加功耗P=CV2f，C：時(shí)鐘跳變時(shí)門電路電容，V：電壓，f：主頻晶體管數(shù)越多，電容越大=>功耗越大；主頻越高=>功耗越大功耗墻CitefromEdwardL.Bosworth,ThePowerWall,2010為什么需要并行計(jì)算？單核處理器性能提升接近極限2005年前，人們預(yù)期可以一直提升處理器主頻但2004年5月Intel處理器TejasandJayhawk(4GHz)因無法解決散熱問題最終放棄，標(biāo)志著升頻技術(shù)時(shí)代的終結(jié)CitefromEdwardL.Bosworth,ThePowerWall,20102005年前人們預(yù)計(jì)的主頻提升路線圖2007年人們大大降低了主頻提升預(yù)期2005年后Intel轉(zhuǎn)入多核技術(shù)為什么需要并行計(jì)算？單處理器向多核并行計(jì)算發(fā)展成為必然趨勢多核/眾核并行計(jì)算

2005年Intel全面轉(zhuǎn)入多核計(jì)算技術(shù)，采用多核/眾核構(gòu)架，簡化單處理器的復(fù)雜設(shè)計(jì),代之以單個(gè)芯片上設(shè)計(jì)多個(gè)簡化的處理器核,以多核/眾核并行計(jì)算提升計(jì)算性能

雙核:PentiumD(05),EE(06),Xeon(06)Core2DuoE系列,T系列(06)Corei3,i5(10)

4核:Core2QuadQ系列（07）Corei5,i7(08,09,10)

6核:Corei7970/980(10)

8核:AMDBulldozer(10)典型的雙核處理器結(jié)構(gòu)為什么需要并行計(jì)算？單處理器向多核并行計(jì)算發(fā)展成為必然趨勢多核/眾核并行計(jì)算

Intel實(shí)驗(yàn)芯片

SingleCloudChip,SCC：48核

Teraflops,80核

CitefromIntelwebsite:/projectdetails.aspx?id=151ASCIRed：1996，第一個(gè)達(dá)到1TFlops(10萬億次浮點(diǎn)運(yùn)算)的并行計(jì)算系統(tǒng)，使用了10,000顆PentiumPro處理器(200MHz),耗電500kW，外加500kW用于機(jī)房散熱Teraflops:達(dá)到1.01TFlops(3.16GHz)1.81TFlops(5.7GHz)

功耗62W！為什么需要并行計(jì)算？單處理器向多核并行計(jì)算發(fā)展成為必然趨勢多核/眾核并行計(jì)算根據(jù)摩爾定律，Intel預(yù)計(jì)其通用的眾核并行計(jì)算芯片2015年：128核2017年：256核2019年：512核2023年：2024核

NVIDIAGPU

GraphicProcessingUnit，主要用于圖形圖像并行處理

TeslaM2050/2070:448核S20501UGPU處理系統(tǒng):4個(gè)M2050/2070,1792核為什么需要并行計(jì)算？應(yīng)用領(lǐng)域計(jì)算規(guī)模和復(fù)雜度大幅提高爆炸性增長的Web規(guī)模數(shù)據(jù)量Google從2004年每天處理100TB數(shù)據(jù)到2008年每天處理20PB2009年eBays數(shù)據(jù)倉庫，一個(gè)有2PB用戶數(shù)據(jù)，另一個(gè)6.5PB用戶數(shù)據(jù)包含170TB記錄且每天增長150GB個(gè)記錄；Facebook：2.5PB用戶數(shù)據(jù)，每天增加15TB世界最大電子對撞機(jī)每年產(chǎn)生15PB(1千5百萬GB)數(shù)據(jù)2015年落成的世界最大觀天望遠(yuǎn)鏡主鏡頭像素為3.2G，每年將產(chǎn)生6PB天文圖像數(shù)據(jù)；歐洲生物信息研究中心(EBI)基因序列數(shù)據(jù)庫容量已達(dá)5PB；中國深圳華大基因研究所成為全世界最大測序中心，每天產(chǎn)生300GB基因序列數(shù)據(jù)（每年100TB）為什么需要并行計(jì)算？應(yīng)用領(lǐng)域計(jì)算規(guī)模和復(fù)雜度大幅提高超大的計(jì)算量/計(jì)算復(fù)雜度用SGI工作站進(jìn)行電影渲染時(shí)，每幀一般需要1～2小時(shí)一部2小時(shí)的電影渲染需要：

2小時(shí)x3600秒x24幀x(1~2小時(shí))/24小時(shí)=20~40年!特殊場景每幀可能需要60個(gè)小時(shí)(影片“星艦騎兵”中數(shù)千只蜘蛛爬行的場面),用橫向4096象素分辨率進(jìn)行渲染時(shí)，如果以每幀60個(gè)小時(shí)的速度，則1秒的放映量（24幀）需要60天的渲染時(shí)間,1分鐘則需要100年！世界著名的數(shù)字工作室DigitalDomain公司用了一年半的時(shí)間，使用了300多臺SGI超級工作站，50多個(gè)特技師一天24小時(shí)輪流制作「泰坦尼克號」中的電腦特技為什么需要并行計(jì)算？解決方案?并行計(jì)算!!!SMPMPPClusterGRIDCloudMulticoreManycore為什么需要并行計(jì)算？并行計(jì)算技術(shù)的發(fā)展趨勢和影響越來越多的研究和應(yīng)用領(lǐng)域?qū)⑿枰褂貌⑿杏?jì)算技術(shù)

并行計(jì)算技術(shù)將滲透到每個(gè)計(jì)算應(yīng)用領(lǐng)域，尤其是涉及到大規(guī)模數(shù)據(jù)和復(fù)雜計(jì)算的應(yīng)用領(lǐng)域并行計(jì)算技術(shù)將對傳統(tǒng)計(jì)算技術(shù)產(chǎn)生革命性的影響并行計(jì)算技術(shù)將影響傳統(tǒng)計(jì)算技術(shù)的各個(gè)層面，與傳統(tǒng)計(jì)算技術(shù)相互結(jié)合產(chǎn)生很多新的研究熱點(diǎn)和課題：

體系結(jié)構(gòu)技術(shù)

操作系統(tǒng)、編譯技術(shù)、數(shù)據(jù)庫等系統(tǒng)軟件技術(shù)

程序設(shè)計(jì)技術(shù)和方法

軟件工程技術(shù)

圖形圖像和多媒體信息處理

人工智能各種應(yīng)用軟件開發(fā)很多傳統(tǒng)的串行算法和計(jì)算方法都將需要重新研究和設(shè)計(jì)其并行化算法和計(jì)算方法；在最近我系未來三年的研究規(guī)劃報(bào)告會上，很多研究領(lǐng)域都明確需要基于并行計(jì)算技術(shù)進(jìn)行研究為什么需要并行計(jì)算？為什么需要學(xué)習(xí)并行計(jì)算技術(shù)？軟件開發(fā)/程序設(shè)計(jì)人員面臨挑戰(zhàn)！20-30年里程序設(shè)計(jì)技術(shù)的最大的革命是面向?qū)ο蠹夹g(shù)

Therevolutioninmainstreamsoftwaredevelopmentfromstructuredprogrammingtoobject-orientedprogrammingwasthegreatestsuchchangeinthepast20to30years下一個(gè)程序設(shè)計(jì)技術(shù)的革命將是并行程序設(shè)計(jì)

Concurrencyisthenextmajorrevolutioninhowwewritesoftware今天絕大多數(shù)程序員不懂并行設(shè)計(jì)技術(shù)，就像15年前絕大多數(shù)程序員不懂面向?qū)ο蠹夹g(shù)一樣

Thevastmajorityofprogrammerstodaydon’tgrokconcurrency,justasthevastmajorityofprogrammers15yearsagodidn’tyetgrokobjectsCitefromHerbSutter,TheFreeLunchIsOver-AFundamentalTurnTowardConcurrencyinSoftwareDr.Dobb'sJournal,30(3),March2005Ch.1.并行計(jì)算技術(shù)簡介1.為什么需要并行計(jì)算？2.并行計(jì)算技術(shù)的分類3.并行計(jì)算的主要技術(shù)問題4.MPI并行程序設(shè)計(jì)5.為什么需要大規(guī)模數(shù)據(jù)并行處理？2.并行計(jì)算技術(shù)的分類經(jīng)過多年的發(fā)展，出現(xiàn)了不同類型的并行計(jì)算技術(shù)和系統(tǒng)，同時(shí)也存在不同的分類方法按數(shù)據(jù)和指令處理結(jié)構(gòu)：弗林(Flynn)分類按并行類型按存儲訪問構(gòu)架按系統(tǒng)類型按計(jì)算特征按并行程序設(shè)計(jì)模型/方法并行計(jì)算技術(shù)的分類按數(shù)據(jù)和指令處理結(jié)構(gòu)分類：弗林(Flynn)分類

1966年，斯坦福大學(xué)教授Flynn提出的經(jīng)典的計(jì)算機(jī)結(jié)構(gòu)分類，從最抽象的指令和數(shù)據(jù)處理結(jié)構(gòu)的角度進(jìn)行分類SISD：單指令單數(shù)據(jù)流

傳統(tǒng)的單處理器串行處理SIMD：單指令多數(shù)據(jù)流

向量機(jī)，信號處理系統(tǒng)MISD：多指令單數(shù)據(jù)流

很少使用MIMD：多指令多數(shù)據(jù)流

最常用，TOP500

基本都屬于MIMD類型弗林(Flynn)分類SISDMIMDSIMD并行計(jì)算技術(shù)的分類CitefromJimmyLin,Whatiscloudcomputing,2008并行計(jì)算技術(shù)的分類按并行類型分類

位級并行（Bit-LevelParallelism）

指令級并行（ILP：Instruction-LevelParallelism）

線程級并行（Thread-LevelParallelism）

數(shù)據(jù)級并行：一個(gè)大的數(shù)據(jù)塊劃分為小塊，分別

由不同的處理器/線程處理

任務(wù)級并行：一個(gè)大的計(jì)算任務(wù)劃分為子任務(wù)分

別由不同的處理器/線程來處理按存儲訪問結(jié)構(gòu)分類A.共享內(nèi)存（SharedMemory)

所有處理器通過總線共享內(nèi)存

多核處理器，SMP……

也稱為UMA結(jié)構(gòu)

(UniformMemoryAccess)B.分布共享存儲體系結(jié)構(gòu)各個(gè)處理器有本地存儲器

同時(shí)再共享一個(gè)全局的存儲器C.分布式內(nèi)存（DistributedMemory)

各個(gè)處理器使用本地獨(dú)立的存儲器

B和C也統(tǒng)稱為NUMA結(jié)構(gòu)(Non-UniformMemoryAccess)并行計(jì)算技術(shù)的分類共享存儲器……總線共享存儲器……MMMABC并行計(jì)算技術(shù)的分類按系統(tǒng)類型分類

多核/眾核并行計(jì)算系統(tǒng)MC(Multicore/Manycore)

或Chip-levelmultiprocessing,CMP

對稱多處理系統(tǒng)SMP(SymmetricMultiprocessing)

多個(gè)相同類型處理器通過總線連接并共享存儲器

大規(guī)模并行處理MPP(MassiveParallelProcessing)

專用內(nèi)聯(lián)網(wǎng)連接一組處理器形成的一個(gè)計(jì)算系統(tǒng)

集群（Cluster）

網(wǎng)絡(luò)連接的一組商品計(jì)算機(jī)構(gòu)成的計(jì)算系統(tǒng)

網(wǎng)格（Grid）

用網(wǎng)絡(luò)連接遠(yuǎn)距離分布的一組異構(gòu)計(jì)算機(jī)構(gòu)成的

計(jì)算系統(tǒng)緊密耦合度松散低可擴(kuò)展性高低能耗高并行計(jì)算技術(shù)的分類按系統(tǒng)類型分類

不同系統(tǒng)的特征和對比

從MC到Grid，耦合度越來越低，但可擴(kuò)展性越來越高，系統(tǒng)規(guī)模越來越大，而能耗也越來越高M(jìn)C處理器核通過NOC(片上網(wǎng)絡(luò))集成在一個(gè)芯片上，通常使用混合式內(nèi)存訪問機(jī)制(本地緩存加全局內(nèi)存)，功耗很低SMP使用獨(dú)立的處理器和共享內(nèi)存，以總線結(jié)構(gòu)互聯(lián)，運(yùn)行一個(gè)操作系統(tǒng),定制成本高,難以擴(kuò)充,規(guī)模較小(2-8處理器）MPP使用獨(dú)立的處理器及獨(dú)立的內(nèi)存、OS，專用的高速內(nèi)聯(lián)網(wǎng)絡(luò)，難以升級和擴(kuò)充，規(guī)模中等(TOP500中有84個(gè))Cluster使用商品化的刀片或機(jī)架服務(wù)器，以網(wǎng)絡(luò)互聯(lián)為一個(gè)物理上緊密的計(jì)算系統(tǒng)，可擴(kuò)展性強(qiáng)，規(guī)?？尚】纱?，是目前高性能并行計(jì)算最常用的形式（TOP500中有414個(gè)）Grid則為地理上廣泛分布的異構(gòu)計(jì)算資源構(gòu)成的一個(gè)極為松散的計(jì)算系統(tǒng)，主要用于并行度很低的大規(guī)?？茖W(xué)計(jì)算任務(wù)并行計(jì)算技術(shù)的分類按計(jì)算特征分類數(shù)據(jù)密集型并行計(jì)算(Data-IntensiveParallelComputing)

數(shù)據(jù)量極大、但計(jì)算相對簡單的并行處理

如：大規(guī)模Web信息搜索

計(jì)算密集型并行計(jì)算

(Computation-IntensiveParallelComputing)

數(shù)據(jù)量相對不是很大、但計(jì)算較為復(fù)雜的并行處理

如：3-D建模與渲染，氣象預(yù)報(bào)，科學(xué)計(jì)算……

數(shù)據(jù)密集與計(jì)算密集混合型并行計(jì)算

兼具數(shù)據(jù)密集型和計(jì)算密集型特征的并行計(jì)算，

如3—D電影渲染并行計(jì)算技術(shù)的分類按并行程序設(shè)計(jì)模型/方法分類共享內(nèi)存變量(SharedMemoryVariables)

多線程共享存儲器變量方式進(jìn)行并行程序設(shè)計(jì),會引起數(shù)據(jù)不一致性,導(dǎo)致數(shù)據(jù)和資源訪問沖突，需要引入同步控制機(jī)制;Pthread,OpenMP:共享內(nèi)存式多處理并行編程接口消息傳遞方式(MessagePassing）

對于分布式內(nèi)存結(jié)構(gòu)，為了分發(fā)數(shù)據(jù)和收集計(jì)算結(jié)果，

需要在各個(gè)計(jì)算節(jié)點(diǎn)間進(jìn)行數(shù)據(jù)通信，最常用的是消息

傳遞方式；MPI：消息傳遞并行編程接口標(biāo)準(zhǔn)MapReduce方式Google公司提出的MapReduce并行程序設(shè)計(jì)模型，是目

前最易于使用的并行程序設(shè)計(jì)方法，廣泛使用于搜索引

擎等大規(guī)模數(shù)據(jù)并行處理并行計(jì)算技術(shù)的分類不同類型并行計(jì)算技術(shù)和系統(tǒng)的發(fā)展歷史和現(xiàn)狀主要發(fā)展歷史階段

1975-1985

主要是向量機(jī)技術(shù)，如Cray1,Cray2。但基于多線程的并行計(jì)算也逐步引入。

1986-1995

大規(guī)模并行處理MPP成為主流并行計(jì)算技術(shù),消息傳遞編程接口MPI得到開發(fā)應(yīng)用。目前TOP500中有84個(gè)基于MPP。1995-現(xiàn)在

Cluster和Grid并行計(jì)算技術(shù)成為主流，但目前Grid的發(fā)展已呈下降趨勢，目前TOP500中有414個(gè)基于Cluster。并行計(jì)算技術(shù)的分類不同類型并行計(jì)算技術(shù)和系統(tǒng)的發(fā)展歷史和現(xiàn)狀主要發(fā)展趨勢SMP作為共享內(nèi)存式小規(guī)模并行計(jì)算技術(shù)一直活躍

60-70年代基于大型機(jī)的SMP系統(tǒng)，80年代基于80386/80486的SMP系統(tǒng)，90年代到目前基于多核的個(gè)人電腦、服務(wù)器大都基于SMP多核/眾核并行計(jì)算成為重要發(fā)展趨勢

由于單核處理器性能發(fā)展的瓶頸，同時(shí)由于多核/眾核計(jì)算計(jì)算自身具有的體積小、功耗低等諸多技術(shù)特點(diǎn)和優(yōu)勢，今后多核/眾核并行計(jì)算會稱為必然趨勢并行計(jì)算軟件技術(shù)遠(yuǎn)遠(yuǎn)落后于硬件發(fā)展速度

并行計(jì)算硬件技術(shù)水平和規(guī)模發(fā)展迅速，但并行計(jì)算軟件技術(shù)遠(yuǎn)遠(yuǎn)跟不上硬件發(fā)展水平和速度，缺少有效的并行計(jì)算軟件框架、編程模型和方法Ch.1.并行計(jì)算技術(shù)簡介1.為什么需要并行計(jì)算？2.并行計(jì)算技術(shù)的分類3.并行計(jì)算的主要技術(shù)問題4.MPI并行程序設(shè)計(jì)5.為什么需要大規(guī)模數(shù)據(jù)并行處理？3.并行計(jì)算的主要技術(shù)問題數(shù)據(jù)怎么存？怎么算？硬件構(gòu)架軟件構(gòu)架并行算法3.并行計(jì)算的主要技術(shù)問題依賴于所采用的并行計(jì)算體系結(jié)構(gòu)，不同類型的并行計(jì)算系統(tǒng)，在硬件構(gòu)架、軟件構(gòu)架和并行算法方面會涉及到不同的技術(shù)問題，但概括起來，主要有以下技術(shù)問題：

多核/多處理器網(wǎng)絡(luò)互連結(jié)構(gòu)技術(shù)

存儲訪問體系結(jié)構(gòu)

分布式數(shù)據(jù)與文件管理并行計(jì)算任務(wù)分解與算法設(shè)計(jì)并行程序設(shè)計(jì)模型和方法

數(shù)據(jù)同步訪問和通信控制可靠性設(shè)計(jì)與容錯(cuò)技術(shù)并行計(jì)算軟件框架平臺系統(tǒng)性能評價(jià)和程序并行度評估并行計(jì)算的主要技術(shù)問題多核/多處理器網(wǎng)絡(luò)互連結(jié)構(gòu)技術(shù)

主要研究處理器間互聯(lián)拓?fù)浣Y(jié)構(gòu)，尤其在包含大量處理器的并行計(jì)算系統(tǒng)中，需要具有良好的互聯(lián)結(jié)構(gòu)，以保證大量處理器能真正有效地協(xié)同工作，獲得應(yīng)有的并行計(jì)算效率。共享總線連接（SharedBus）交叉開關(guān)矩陣（CrossbarSwitch）環(huán)形結(jié)構(gòu)（Torus）Mesh網(wǎng)絡(luò)結(jié)構(gòu)（MeshNetwork）片上網(wǎng)絡(luò)（NOC，Network-on-chip）……并行計(jì)算的主要技術(shù)問題存儲訪問體系結(jié)構(gòu)

主要研究不同的存儲結(jié)構(gòu)，以及在不同存儲結(jié)構(gòu)下的特定技術(shù)問題共享存儲器體系結(jié)構(gòu)(SharedMemory)共享數(shù)據(jù)訪問與同步控制分布存儲體系結(jié)構(gòu)(DistributedMemory)數(shù)據(jù)通信控制和節(jié)點(diǎn)計(jì)算同步控制分布共享存儲結(jié)構(gòu)(DistributedSharedMemory)Cache的一致性問題數(shù)據(jù)訪問/通信的時(shí)間延遲并行計(jì)算的主要技術(shù)問題分布式數(shù)據(jù)與文件管理并行計(jì)算的一個(gè)重要問題是，在大規(guī)模集群環(huán)境下，如何解決大數(shù)據(jù)塊的劃分、存儲和訪問管理；尤其是數(shù)據(jù)密集型并行計(jì)算時(shí)，理想的情況是提供分布式數(shù)據(jù)與文件管理系統(tǒng)，如RedHatGFS(GlobalFileSystem)IBMGPFSSun

LustreGoogleGFS(GoogleFileSystem)HadoopHDFS(HadoopDistributedFileSystem)并行計(jì)算的主要技術(shù)問題并行計(jì)算任務(wù)的分解與算法設(shè)計(jì)一個(gè)大型計(jì)算任務(wù)如何從數(shù)據(jù)上或者是計(jì)算方法上進(jìn)行適當(dāng)?shù)膭澐?，分解為一組子任務(wù)以便分配給各個(gè)節(jié)點(diǎn)進(jìn)行并行處理，如何搜集各節(jié)點(diǎn)計(jì)算的局部結(jié)果數(shù)據(jù)劃分如何將特大的數(shù)據(jù)進(jìn)行劃分并分配給各節(jié)點(diǎn)進(jìn)行處理。算法分解與設(shè)計(jì)一個(gè)大的尤其是計(jì)算密集型的計(jì)算任務(wù)，首先需要尋找并確定其可并行計(jì)算的部分，然后進(jìn)一步尋找好的分解算法：可把一個(gè)整體的算法縱向分解為一組并行的子任務(wù)，或者對于復(fù)雜的計(jì)算任務(wù)可橫向分解為多次并行處理過程。并行計(jì)算的主要技術(shù)問題并行程序設(shè)計(jì)模型和方法

根據(jù)不同的硬件構(gòu)架，不同的并行計(jì)算系統(tǒng)可能需要不同的并行程序設(shè)計(jì)模型、方法、語言和編譯技術(shù)。并行程序設(shè)計(jì)模型和方法共享內(nèi)存式并行程序設(shè)計(jì):為共享內(nèi)存結(jié)構(gòu)并行計(jì)算系統(tǒng)提供的程序設(shè)計(jì)方法,需提供數(shù)據(jù)訪問同步控制機(jī)制(如互斥信號,鎖等）消息傳遞式并行程序設(shè)計(jì):為分布內(nèi)存結(jié)構(gòu)并行計(jì)算系統(tǒng)提供的、以消息傳遞方式完成節(jié)點(diǎn)間數(shù)據(jù)通信的程序設(shè)計(jì)方法MapReduce并行程序設(shè)計(jì):為解決前兩者在并行程序設(shè)計(jì)上的缺陷，提供一個(gè)綜合的編程框架，為程序員提供了一種簡便易用的并行程序設(shè)計(jì)方法并行計(jì)算的主要技術(shù)問題并行程序設(shè)計(jì)模型和方法并行程序設(shè)計(jì)語言語言級擴(kuò)充：使用宏指令在

普通的程序設(shè)計(jì)語言（如C語

言）上增加一些并行計(jì)算宏

指令，如OpenMP（提供C,C++,Fortran語言擴(kuò)充，Linux&Windows）并行計(jì)算庫函數(shù)與編程接口：

使用函數(shù)庫提供并行計(jì)算編程接口，如MPI(消息傳遞接口)，CUDA(NVIDIAGPU)并行編譯與優(yōu)化技術(shù)編譯程序需要考慮編譯時(shí)的自動化并行性處理，以及為提高計(jì)算性能進(jìn)行并行計(jì)算優(yōu)化處理intmain(intargc,char*argv[]){constintN=100000;inti,a[N];

#pragmaompparallelforfor(i=0;i<N;i++)a[i]=2*i;return0;}并行計(jì)算的主要技術(shù)問題數(shù)據(jù)同步訪問和通信控制如何解決并行化計(jì)算中共享數(shù)據(jù)訪問和節(jié)點(diǎn)數(shù)據(jù)通信問題共享數(shù)據(jù)訪問和同步控制在包含共享存儲器結(jié)構(gòu)的系統(tǒng)中，不同處理器/線程訪問共享存儲區(qū)時(shí)，可能會導(dǎo)致數(shù)據(jù)訪問的不確定性(競爭狀態(tài)，racecondition),因此需要考慮使用同步機(jī)制(互斥信號，條件變量等)保證共享數(shù)據(jù)和資源訪問的正確性，還要解決同步可能引起的死鎖問題。分布存儲結(jié)構(gòu)下的數(shù)據(jù)通信和同步控制在包含分布存儲器結(jié)構(gòu)的系統(tǒng)中，不同處理器/線程需要?jiǎng)澐趾瞳@取計(jì)算數(shù)據(jù)，這些數(shù)據(jù)通常需要由主節(jié)點(diǎn)傳送到各個(gè)從節(jié)點(diǎn)；由于各個(gè)節(jié)點(diǎn)計(jì)算速度不同，為了保證計(jì)算的同步，還需要考慮各節(jié)點(diǎn)并行計(jì)算的同步控制(如Barrier,同步障）并行計(jì)算的主要技術(shù)問題可靠性設(shè)計(jì)與容錯(cuò)技術(shù)

大型并行計(jì)算系統(tǒng)使用大量計(jì)算機(jī),因此,節(jié)點(diǎn)出錯(cuò)或失效是常態(tài)，不能因?yàn)橐粋€(gè)節(jié)點(diǎn)失效導(dǎo)致數(shù)據(jù)丟失、程序終止或系統(tǒng)崩潰，因此，系統(tǒng)需要具有良好的可靠性設(shè)計(jì)和有效的失效檢測和恢復(fù)技術(shù)

設(shè)1萬個(gè)服務(wù)器節(jié)點(diǎn),每個(gè)服務(wù)器的平均無故障時(shí)間(MTBF,Mean-TimeBetweenFailures)是1千天,則平均每天10個(gè)服務(wù)器出錯(cuò)！數(shù)據(jù)失效恢復(fù)：大量的數(shù)據(jù)存儲在很多磁盤中，當(dāng)出現(xiàn)磁盤出錯(cuò)和數(shù)據(jù)損壞時(shí)，需要有良好的數(shù)據(jù)備份和數(shù)據(jù)失效恢復(fù)機(jī)制，保證數(shù)據(jù)不丟失以及數(shù)據(jù)的正確性。系統(tǒng)和任務(wù)失效恢復(fù)：一個(gè)節(jié)點(diǎn)失效不能導(dǎo)致系統(tǒng)崩潰,而且要能保證程序的正常運(yùn)行,因此,需要有很好的失效檢測和隔離技術(shù),并進(jìn)行計(jì)算任務(wù)的重新調(diào)度以保證計(jì)算任務(wù)正常進(jìn)行。并行計(jì)算的主要技術(shù)問題并行計(jì)算軟件框架平臺并行計(jì)算軟件技術(shù)跟不上并行計(jì)算硬件系統(tǒng)規(guī)模的發(fā)展,需要研究有效的并行計(jì)算軟件框架、平臺和軟件設(shè)計(jì)方法提供自動化并行處理能力現(xiàn)有的OpenMP、MPI、CUDA等并行程序設(shè)計(jì)方法需要程序員考慮和處理數(shù)據(jù)存儲管理、數(shù)據(jù)和任務(wù)劃分和調(diào)度執(zhí)行、數(shù)據(jù)同步和通信、結(jié)果收集、出錯(cuò)恢復(fù)處理等幾乎所有技術(shù)細(xì)節(jié)，非常繁瑣需要研究一種具有自動化并行處理能力的并行計(jì)算軟件框架和平臺，提供自動化的并行處理，能屏蔽并行化處理的諸多系統(tǒng)底層細(xì)節(jié)，交由軟件框架來處理，提供必要的編程接口，簡化程序員的編程，讓程序員從系統(tǒng)底層細(xì)節(jié)中解放出來，專注于應(yīng)用問題本身的計(jì)算和算法的實(shí)現(xiàn)。如Google和HadoopMapReduce高可擴(kuò)展性和系統(tǒng)性能提升

并行計(jì)算框架允許方便地增加節(jié)點(diǎn)擴(kuò)充系統(tǒng),但系統(tǒng)節(jié)點(diǎn)的增加不影響程序的編寫,并且要能保證節(jié)點(diǎn)增加后系統(tǒng)性能有線性的提升

MapReduce并行計(jì)算框架保證系統(tǒng)性能幾乎隨節(jié)點(diǎn)的增加線性提升并行計(jì)算的主要技術(shù)問題系統(tǒng)性能評估和程序并行度評估系統(tǒng)性能評估用標(biāo)準(zhǔn)性能評估(Benchmark)方法評估一個(gè)并行計(jì)算系統(tǒng)的浮點(diǎn)計(jì)算能力。High-PerformanceLinpackBenchmark是最為知名的評估工具，TOP500用其進(jìn)行評估和排名程序并行度評估程序能得到多大并行加速依賴于該程序有多少可并行計(jì)算的比例。經(jīng)典的程序并行加速評估公式Amdahl定律：

其中，S是加速比，P是程序可并行比例N是處理器數(shù)目S=并行計(jì)算的主要技術(shù)問題系統(tǒng)性能評估和程序并行度評估

根據(jù)Amdahl定律：一個(gè)并行程序可加速程度是有限制的，并非可無限加速，并非處理器越多越好并行比例vs加速比50%=>最大2倍75%=>最大4倍90%=>最大10倍95%=>最大20倍Citefrom/wiki/Amdahl%27s_lawCh.1.并行計(jì)算技術(shù)簡介1.為什么需要并行計(jì)算？2.并行計(jì)算技術(shù)的分類3.并行計(jì)算的主要技術(shù)問題4.MPI并行程序設(shè)計(jì)5.為什么需要大規(guī)模數(shù)據(jù)并行處理？4.MPI并行程序設(shè)計(jì)MPI簡介MessagePassingInterface，基于消息傳遞的高性能并行計(jì)算編程接口在處理器間以消息傳遞方式進(jìn)行數(shù)據(jù)通信和同步，以庫函數(shù)形式為程序員提供了一組易于使用的編程接口。93年由一組來自大學(xué)、國家實(shí)驗(yàn)室、高性能計(jì)算廠商發(fā)起組織和研究，94年公布了最早的版本MPI1.0，經(jīng)過MPI1.1-1.3,目前版本MPI2.2,MPI3版本正在設(shè)計(jì)中特點(diǎn)：提供可靠的、面向消息的通信；在高性能科學(xué)計(jì)算領(lǐng)域廣泛使用，適合于處理計(jì)算密集型的科學(xué)計(jì)算；獨(dú)立于語言的編程規(guī)范，可移植性好MPI并行程序設(shè)計(jì)開放領(lǐng)域/機(jī)構(gòu)實(shí)現(xiàn)MPICH

阿貢國家實(shí)驗(yàn)室和密西西比大學(xué)

最早的完整MPI標(biāo)準(zhǔn)實(shí)現(xiàn).LAM OhioSupercomputercenterMPICH/NTMississippiStateUniversityMPI-FMIllinois(Myrinet)MPI-AMUCBerkeley(Myrinet)MPI-PMRWCP,Japan(Myrinet)MPI-CCLCaliforniaInstituteofTechnologyCRI/EPCCMPICrayResearchandEdinburgh ParallelComputingCentreMPI-APAustralianNationalUniversity- CAPResearchProgram(AP1000)W32MPIIllinois,ConcurrentSystemsRACE-MPIHughesAircraftCo.MPI-BIPINRIA,France(Myrinet)MPI實(shí)現(xiàn)版本廠商實(shí)現(xiàn)HP-MPI

HewlettPackard;ConvexSPPMPI-F IBMSP1/SP2Hitachi/MPIHitachiSGI/MPI SGIPowerChallengeseriesMPI/DE NEC.INTEL/MPIIntel.Paragon(iCClib)T.MPI TelmatMultinodeFujitsu/MPIFujitsuAP1000EPCC/MPICray&EPCC,T3D/T3E語言實(shí)現(xiàn)C/C++JavaPython.NETMPI并行程序設(shè)計(jì)MPI主要功能用常規(guī)語言編程方式，所有節(jié)點(diǎn)運(yùn)行同一個(gè)程序，但處理不同的數(shù)據(jù)提供點(diǎn)對點(diǎn)通信(Point-pointcommunication)提供同步通信功能（阻塞通信）提供異步通信功能（非阻塞通信）提供節(jié)點(diǎn)集合通信(Collectivecommunication)提供一對多的廣播通信提供多節(jié)點(diǎn)計(jì)算同步控制提供對結(jié)果的規(guī)約(Reduce)計(jì)算功能提供用戶自定義的復(fù)合數(shù)據(jù)類型傳輸MPI并行程序設(shè)計(jì)MPI基本程序結(jié)構(gòu)MPI程序頭文件初始化MPI環(huán)境并行計(jì)算與通信關(guān)閉MPI環(huán)境#include<mpi.h>main(intargc,char**argv){intnumtasks,rank;

MPI_Init(&argc,&argv);

……

并行計(jì)算程序體……

MPI_Finalize();exit(0);}MPI并行程序設(shè)計(jì)MPI并行程序設(shè)計(jì)接口基本編程接口MPI提供了6個(gè)最基本的編程接口，理論上任何并行程序都可以通過這6個(gè)基本API實(shí)現(xiàn)1.MPI_Init

(argc,argv):初始化MPI，開始MPI并行計(jì)算程序體2.MPI_Finalize:終止MPI并行計(jì)算3.MPI_Comm_Size(comm,size):確定指定范圍內(nèi)處理器/進(jìn)程數(shù)目4.MPI_Comm_Rank(comm,rank):確定一個(gè)處理器/進(jìn)程的標(biāo)識號5.MPI_Send

(buf,count,datatype,dest,tag,comm):發(fā)送一個(gè)消息6.MPI_Recv(buf,count,datatype,source,tag,comm,status)

:接受消息size:進(jìn)程數(shù)，rank：指定進(jìn)程的IDcomm：指定一個(gè)通信組(communicator)Dest：目標(biāo)進(jìn)程號，source：源進(jìn)程標(biāo)識號，tag：消息標(biāo)簽MPI并行程序設(shè)計(jì)MPI并行程序設(shè)計(jì)接口基本編程接口MPI并行計(jì)算初始化與結(jié)束

任何一個(gè)MPI程序都要用MPI—Init和MPI—Finalize來指定并行計(jì)算開始和結(jié)束的地方；同時(shí)在運(yùn)行時(shí)，這兩個(gè)函數(shù)將完成MPI計(jì)算環(huán)境的初始化設(shè)置以及結(jié)束清理工作。處于兩者之間的程序即被認(rèn)為是并行化的，將在每個(gè)機(jī)器上被執(zhí)行。#include<mpi.h>#include<stdio.h>main(intargc,char**argv){intnumtasks,rank;

MPI_Init(&argc,&argv);

printf(“Helloparallelworld!\n”);

MPI_Finalize();exit(0);}Helloparallelworld!Helloparallelworld!Helloparallelworld!Helloparallelworld!Helloparallelworld!在一個(gè)有5個(gè)處理器的系統(tǒng)中，輸出為MPI并行程序設(shè)計(jì)MPI并行程序設(shè)計(jì)接口基本編程接口通信組（Communicator）為了在指定的范圍內(nèi)進(jìn)行通信，可以將系統(tǒng)中的處理器劃分為不同的通信組；一個(gè)處理器可以同時(shí)參加多個(gè)通信組；MPI定義了一個(gè)最大的缺省通信組:MPI_COMM_WORLD，指明系統(tǒng)中所有的進(jìn)程都參與通信。一個(gè)通信組中的總進(jìn)程數(shù)可以由MPI_Comm_Size調(diào)用來確定。進(jìn)程標(biāo)識

為了在通信時(shí)能準(zhǔn)確指定一個(gè)特定的進(jìn)程，需要為每個(gè)進(jìn)程分配一個(gè)進(jìn)程標(biāo)識，一個(gè)通信組中每個(gè)進(jìn)程標(biāo)識號由系統(tǒng)自動編號（從0開始）；進(jìn)程標(biāo)識號可以由MPI_Comm_Rank調(diào)用來確定。MPI并行程序設(shè)計(jì)MPI并行程序設(shè)計(jì)接口點(diǎn)對點(diǎn)通信

同步通信：阻塞式通信，等待通信操作完成后才返回

MPI_Send

(buf,count,datatype,dest,tag,comm):發(fā)送一個(gè)消息

MPI_Recv(buf,count,datatype,source,tag,comm,status)

:接受消息同步通信時(shí)一定要等到通信操作完成，這會造成處理器空閑，

因而可能導(dǎo)致系統(tǒng)效率下降，為此MPI提供異步通信功能

異步通信：非阻塞式通信，不等待通信操作完成即返回

MPI_ISend

(buf,count,datatype,dest,tag,comm,request):異步發(fā)送

MPI_IRecv(buf,count,datatype,source,tag,comm,status,request)

異步接受消息

MPI_Wait(request,status):等待非阻塞數(shù)據(jù)傳輸完成

MPI_Test(request,flag,status)

:檢查是否異步數(shù)據(jù)傳輸確實(shí)完成MPI并行程序設(shè)計(jì)MPI編程示例簡單MPI編程示例#include<mpi.h>#include<stdio.h>main(intargc,char**argv){intnum,rk;MPI_Init(&argc,&argv);MPI_Comm_size(MPI_COMM_WORLD,&num);MPI_Comm_rank(MPI_COMM_WORLD,&rk);printf("HelloworldfromProcess%dof%d\n",rk,num);MPI_Finalize();}HelloworldfromProcess0of5HelloworldfromProcess1of5HelloworldfromProcess2of5HelloworldfromProcess3of5HelloworldfromProcess4of5MPI并行程序設(shè)計(jì)MPI編程示例消息傳遞MPI編程示例1#include<stdio.h>#include<mpi.h>

intmain(intargc,char**argv)

{

intmyid,numprocs,source;

MPI_Statusstatus;charmessage[100];

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

if(myid！=0)/*其他進(jìn)程，向0進(jìn)程發(fā)送HelloWorld信息*/

{strcpy(message,“HelloWorld!”);

MPI_Send(message,strlen(message)+1,MPI_CHAR,0,99,MPI_COMM_WORLD);

}else/*0進(jìn)程負(fù)責(zé)從其他進(jìn)程接受信息并輸出*/

{for(source=1;source<numprocs;source++)

{MPI_Recv(message,100,MPI_CHAR,source,99,MPI_COMM_WORLD,&status);

printf("Iamprocess%d.Irecvstring'%s'fromprocess%d.\n",myid,message,source);

}

}

MPI_Finalize();

}Iamprocess0.Irecvstring‘HelloWorld’fromprocess1.Iamprocess0.Irecvstring‘HelloWorld’fromprocess2.Iamprocess0.Irecvstring‘HelloWorld’fromprocess3.MPI并行程序設(shè)計(jì)MPI編程示例消息傳遞MPI編程示例2--計(jì)算大數(shù)組元素的開平方之和設(shè)系統(tǒng)中共有5個(gè)進(jìn)程，進(jìn)程號：0，1，2，3，40號進(jìn)程作主節(jié)點(diǎn)，負(fù)責(zé)分發(fā)數(shù)據(jù)，不參加子任務(wù)計(jì)算1-4號進(jìn)程作為子節(jié)點(diǎn)從主進(jìn)程接受數(shù)組數(shù)據(jù)：#1:data[0,4,8,…]#2:data[1,5,9,…]各自求開平方后累加=>本地SqrtSum#3:data[2,6,10,…]#4:data[3,7,11,…]#0:SqrtSum=∑各子進(jìn)程的SqrtSumIamprocess1.Irecvtotal251dataitemsfromprocess0,andSqrtSum=111.11Iamprocess2.Irecvtotal251dataitemsfromprocess0,andSqrtSum=222.22Iamprocess3.Irecvtotal250dataitemsfromprocess0,andSqrtSum=333.33Iamprocess4.Irecvtotal250dataitemsfromprocess0,andSqrtSum=444.44Iamprocess0.Irecvtotal0dataitemsfromprocess0,andSqrtSum=1111.10MPI并行程序設(shè)計(jì)MPI編程示例消息傳遞MPI編程示例2#include<stdio.h>#include<mpi.h>#include<math.h>#defineN=1002

intmain(int

argc,char**argv)

{

int

myid,P,source,C=0；doubledata[N],SqrtSum=0.0;

MPI_Statusstatus;charmessage[100];MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&myid);MPI_Comm_size(MPI_COMM_WORLD,&numprocs);--numprocs;/*數(shù)據(jù)分配時(shí)除去0號主節(jié)點(diǎn)*/

if(myid==0)/*0號主節(jié)點(diǎn)，主要負(fù)責(zé)數(shù)據(jù)分發(fā)和結(jié)果收集*/

{

for(int

i=0;i<N;++i;))/*數(shù)據(jù)分發(fā):0,*/

MPI_Send(data[i],1,MPI_DOUBLE,N%numprocs+1,1,MPI_COMM_WORLD);for(intsource=1;source<=numprocs;++source;)/*結(jié)果收集*/

｛

MPI_Recv(&d,1,MPI_DOUBLE,source,99,MPI_COMM_WORLD,&status);SqrtSum+=d;｝

}else{for(i=0;i<N;i=i+numprocs;)/*各子節(jié)點(diǎn)接受數(shù)據(jù)計(jì)算開平方，本地累加*/

｛

MPI_Recv(&d,1,MPI_DOUBLE,0,1,MPI_COMM_WORLD,&status);SqrtSum+=sqrt(d);｝

MPI_Send(SqrtSum,1,MPI_DOUBLE,0,99,MPI_COMM_WORLD);/*本地累加結(jié)果送回主節(jié)點(diǎn)*/}printf("Iamprocess%d.Irecvtotal%dfromprocess0,andSqrtSum=%f.\n",myid,C,SqrtSum);

MPI_Finalize();

}MPI并行程序設(shè)計(jì)MPI編程示例消息傳遞MPI編程示例3

MonteCarlo方法計(jì)算圓周率

MonteCarlo是一種隨機(jī)抽樣統(tǒng)計(jì)方法，可用于解決難以用數(shù)學(xué)公式計(jì)算結(jié)果的復(fù)雜問題近似求解。設(shè)r取值為0.5，為了提高π計(jì)算精度，需要計(jì)算盡量大的隨機(jī)點(diǎn)數(shù)，我們考慮在一個(gè)并行系統(tǒng)中讓每臺機(jī)器都各自算一個(gè)π，然后匯總求一個(gè)平均值作一個(gè)直徑為2r的圓及其外切正方形，在其中隨機(jī)產(chǎn)生n個(gè)點(diǎn)，落在圓內(nèi)的點(diǎn)數(shù)記為m。根據(jù)概率理論，當(dāng)隨機(jī)點(diǎn)數(shù)足夠大時(shí)，m與n的比值可近似看成是圓與正方形面積之比。故有：m/n≈πxr2/(2r)

2,π≈4m/nMPI并行程序設(shè)計(jì)MPI編程示例消息傳遞MPI編程示例3—MonteCarlo方法計(jì)算圓周率#include“mpi.h”

#include<stdio.h>

#include<stdlib.h>

main(intargc,char**argv)

{

intmyid,numprocs;

intnamelen,source;

longcount=1000000;

MPI_Statusstatus;

MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

srand((int)time(0));/*設(shè)置隨機(jī)種子*/

doubley,x,pi=0.0,n=0.0;

longm=0,m1=0,i=0,p=0;

for(i=0;i<count;i++)/*隨機(jī)產(chǎn)生一個(gè)點(diǎn)(x,y)，判斷并計(jì)算落在圓內(nèi)的次數(shù)*/

{x=(double)rand()/(double)RAND_MAX;

y=(double)rand()/(double)RAND_MAX;

if((x-0.5)*(x-0.5)+(y-0.5)*(y-0.5)<0.25)++m;

}MPI并行程序設(shè)計(jì)MPI編程示例消息傳遞MPI編程示例3—MonteCarlo方法計(jì)算圓周率pi=4.0*m/count;

printf(“Process%dof%pi=%f\n”,myid,numprocs,pi);

if(myid!=0)/*從節(jié)點(diǎn)將本地計(jì)算的π結(jié)果發(fā)送到主節(jié)點(diǎn)*/

{MPI_Send(&m,1,MPI_DOUBLE,0,1,MPI_COMM_WORLD);}

else/*主節(jié)點(diǎn)接受各從節(jié)點(diǎn)的結(jié)果并累加*/

{p=m;

for(source=1;source<numprocs;source++)

{MPI_Recv(&m1,1,MPI_DOUBLE,source,1,MPI_COMM_WORLD,&status);

p=p+m1;

}

printf(“pi=%f\n”,4.0*p/(count*numprocs));/*各節(jié)點(diǎn)輸出結(jié)果*/

}

MPI_Finalize();

}Process0of3pi=3.14135Process1of3pi=3.14312Process2of3pi=3.14203pi=3.14216匯總平均值MPI并行程序設(shè)計(jì)節(jié)點(diǎn)集合通信接口

提供一個(gè)進(jìn)程與多個(gè)進(jìn)程間同時(shí)通信的功能BufferBufferTransmissionSendBufferBufferReceiveMPI并行程序設(shè)計(jì)節(jié)點(diǎn)集合通信接口三種類型的集合通信功能

同步(Barrier)

MPI_Barrier：設(shè)置同步障使所有進(jìn)程的執(zhí)行同時(shí)完成

數(shù)據(jù)移動(Datamovement)MPI_BCAST:一對多的廣播式發(fā)送MPI_GATHER：多個(gè)進(jìn)程的消息以某種次序收集到一個(gè)進(jìn)程MPI_SCATTER：將一個(gè)信息劃分為等長的段依次發(fā)送給其它進(jìn)程

數(shù)據(jù)規(guī)約(Reduction)MPI_Reduce：將一組進(jìn)程的數(shù)據(jù)按照指定的操作方式規(guī)約到一起并傳送給一個(gè)進(jìn)程MPI并行程序設(shè)計(jì)節(jié)點(diǎn)集合通信接口數(shù)據(jù)規(guī)約操作

將一組進(jìn)程的數(shù)據(jù)按照指定的操作方式規(guī)約到一起并傳送給一個(gè)進(jìn)程

MPI_Reduce(sendbuf,recvbuf,count,datatype,op,root,comm)其中規(guī)約操作op可設(shè)為下表定義的操作之一：MPI_MAX 求最大值 MPI_MIN 求最小值MPI_SUM 求和 MPI_PROD 求積MPI_LAND 邏輯與 MPI_BAND 按位與MPI_LOR 邏輯或 MPI_BOR 按位或MPI_LXOR 邏輯異或 MPI_BXOR 按位異或MPI_MAXLOC最大值和位置 MPI_MINLOC 最小值和位置

MPI并行程序設(shè)計(jì)節(jié)點(diǎn)集合通信接口規(guī)約操作編程示例-計(jì)算積分

根據(jù)微積分原理，任一函數(shù)f(x)在區(qū)間[a,b]上的積分是由各個(gè)x處的y值為高構(gòu)成的N個(gè)小矩形(當(dāng)N趨向無窮大時(shí)的）面積之和構(gòu)成。因此,選取足夠大的N可近似計(jì)算積分。

設(shè)y=x2，求其在[0,10]區(qū)間的積分。

先把[0,10]分為N個(gè)小區(qū)間，則對每

個(gè)x取值對應(yīng)小矩形面積為：y*10/N

求和所有矩形面積，當(dāng)N足夠大時(shí)即

為近似積分值。

我們用n個(gè)節(jié)點(diǎn)來分工計(jì)算N個(gè)區(qū)間的面積。如圖所示，根據(jù)總結(jié)點(diǎn)數(shù)目，每個(gè)節(jié)點(diǎn)將求和一個(gè)顏色的小矩形塊。

010MPI并行程序設(shè)計(jì)MPI編程示例規(guī)約操作編程示例—計(jì)算積分#defineN100000000#defineda0#definedb10

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include“mpi.h”

intmain(intargc,char**argv)

{

intmyid,numprocs;

inti;

doublelocal=0.0,dx=(b-a)/N;/*小矩形寬度*/

doubleinte,x;MPI_Init(&argc,&argv);

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);MPI并行程序設(shè)計(jì)MPI編程示例規(guī)約操作編程示例—計(jì)算積分

for(i=myid;i<N;i=i+numprocs)/*根據(jù)節(jié)點(diǎn)數(shù)目將N個(gè)矩形分為圖示的多個(gè)顏色組*/

{/*每個(gè)節(jié)點(diǎn)計(jì)算一個(gè)顏色組的矩形面積并累加*/

x=a+i*dx+dx/2;/*以每個(gè)矩形的中心點(diǎn)x值計(jì)算矩形高度*/local+=x*x*dx;/*矩形面積=高度x寬度=y*dx*/}

MPI_Reduce(&local,&inte,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);

if(myid==0)/*規(guī)約所有節(jié)點(diǎn)上的累加和并送到主節(jié)點(diǎn)0*/

{/*主節(jié)點(diǎn)打印累加和*/

printf("Theintegalofx*xinregion[%d,%d]=%16.15f\n",a,b,inte);

}

MPI_Finalize();

}Theintegal

ofx*xinregion[0,10]=33.33345MPI并行程序設(shè)計(jì)MPI的特點(diǎn)和不足MPI的特點(diǎn)靈活性好，適合于各種計(jì)算密集型的并行計(jì)算任務(wù)獨(dú)立于語言的編程規(guī)范，可移植性好有很多開放機(jī)構(gòu)或廠商實(shí)現(xiàn)并支持MPI的不足無良好的數(shù)據(jù)和任務(wù)劃分支持缺少分布文件系統(tǒng)支持分布數(shù)據(jù)存儲管理通信開銷大，當(dāng)計(jì)算問題復(fù)雜、節(jié)點(diǎn)數(shù)量很大時(shí)，難以處理，性能大幅下降無節(jié)點(diǎn)失效恢復(fù)機(jī)制，一旦有節(jié)點(diǎn)失效，可能導(dǎo)致計(jì)算過程無效缺少良好的構(gòu)架支撐，程序員需要考慮以上所有細(xì)節(jié)問題，程序設(shè)計(jì)較為復(fù)雜Ch.1.并行計(jì)算技術(shù)簡介1.為什么需要并行計(jì)算？2.并行計(jì)算技術(shù)的分類3.并行計(jì)算的主要技術(shù)問題4.MPI并行程序設(shè)計(jì)5.為什么需要大規(guī)模數(shù)據(jù)并行處理？5.海量數(shù)據(jù)并行處理技術(shù)簡介為什么需要海量數(shù)據(jù)并行處理技術(shù)？海量數(shù)據(jù)及其處理已經(jīng)成為現(xiàn)實(shí)世界的急迫需求Google從2004年每天處理100TB數(shù)據(jù)到2008年每天處理20PB百度存儲20PB數(shù)據(jù)，每日新增10TB，每天處理數(shù)據(jù)1PB2009年eBays數(shù)據(jù)倉庫，一個(gè)有2PB用戶數(shù)據(jù)，另一個(gè)6.5PB用戶數(shù)據(jù)包含170TB記錄且每天增長150GB個(gè)記錄；Facebook：2.5PB用戶數(shù)據(jù)，每天增加15TB世界最大電子對撞機(jī)每年產(chǎn)生15PB(1千5百萬GB)數(shù)據(jù)2015年落成的世界最大觀天望遠(yuǎn)鏡主鏡頭像素為3.2G，每年將產(chǎn)生6PB天文圖像數(shù)據(jù)歐洲生物信息研究中心(EBI)基因序列數(shù)據(jù)庫容量已達(dá)5PB；中國深圳華大基因研究所成為全世界最大測序中心，每天產(chǎn)生300GB基因序列數(shù)據(jù)（每年100TB）AtChinaMobile,thesizeofitsnetworknaturallyleadstolargeamountsofdatacreated.Everydaythenetworkgenerates5TBto8TBofCDRdata.AbranchcompanyofChinaMobilecanhavemorethan20millionsubscribers,leadingtomorethan100GBofCDRdataforvoicecallsandbetween100GBto200GBofCDRdataforSMSeveryday.Inaddition,atypicalbranchcompanygeneratesaround48GBofdataperdayforGeneralPacketRadioService(GPRS)signalingand300GBofdataperdayfor3Gsignaling.海量數(shù)據(jù)并行處理技術(shù)簡介為什么需要海量數(shù)據(jù)并行處理技術(shù)？處理數(shù)據(jù)的能力大幅落后于數(shù)據(jù)增長，需要尋找有效的數(shù)據(jù)密集型并行計(jì)算方法

磁盤容量增長遠(yuǎn)遠(yuǎn)快過存儲訪問帶寬和延遲：80年代中期數(shù)十MB到今天1-2TB，增長10萬倍，而延遲僅提高2倍，帶寬僅提高50倍！

100TB數(shù)據(jù)順序讀一遍需要多少時(shí)間？設(shè)硬盤讀取訪問速率128MB/秒1TB/128MB約2.17小時(shí)100TB/128MB=217小時(shí)=9天！

即使用百萬元高速磁盤陣列(800MB/s),仍需1.5天！NumbersEveryoneShouldKnow*L1cachereference0.5nsBranchmispredict5nsL2cachereference7nsMutexlock/unlock25nsMainmemoryreference100nsSend2Kbytesover1Gbpsnetwork(100MB/s)20,000ns(20μs)Read1MBsequentiallyfrommemory(4GB/s)250,000ns(0.25ms)Roundtripwithinsamedatacenter(2GB/s)500,000ns(0.5ms)Diskseek10,000,000ns(10ms)Read1MBsequentiallyfromdisk(100MB/s)10,000,000ns(10ms)1MBdatavia100Mbnetwork80,000,000ns(80ms)1MBdatavia1000Mbnetwork8,000,000ns(8ms)SendpacketCA→Netherlands→CA150,000,000ns(0.15s)*AccordingtoJeffDean(LADIS2009keynote)*AccordingtoJeffDean(LADIS2009keynote)海量數(shù)據(jù)并行處理技術(shù)簡介為什么需要海量數(shù)據(jù)并行處理技術(shù)？海量數(shù)據(jù)隱含著更準(zhǔn)確的事實(shí)

信息檢索、自然語言理解和機(jī)器學(xué)習(xí)的三個(gè)要素：

數(shù)據(jù)，特征，與算法

2001,BankoandBrill發(fā)表了一篇自然語言領(lǐng)域的經(jīng)典研究論文，探討訓(xùn)練數(shù)據(jù)集大小對分類精度的影響，發(fā)現(xiàn)數(shù)據(jù)越大，精度越高；更有趣的發(fā)現(xiàn)是，他們發(fā)現(xiàn)當(dāng)數(shù)據(jù)不斷增長時(shí)，不同算法的分類精度趨向于相同，使得小數(shù)據(jù)集時(shí)不同算法在精度上的差別基本消失！

結(jié)論引起爭論：算法不再要緊，數(shù)據(jù)更重要！不再需要研究復(fù)雜算法，找更多數(shù)據(jù)就行了！海量數(shù)據(jù)并行處理技術(shù)簡介為什么需要海量數(shù)據(jù)并行處理技術(shù)？海量數(shù)據(jù)隱含著更準(zhǔn)確的事實(shí)2001年,一個(gè)基于事實(shí)的簡短問答研究,如提問:WhoshotAbrahamLincoln？在很大的數(shù)據(jù)集時(shí),只要使用簡單的模式匹配方法,找到在“shotAbrahamLincoln”前面的部分即可快速得到準(zhǔn)確答案：JohnWilkesBooth2007,Brantsetal.描述了一個(gè)基于2萬億個(gè)單詞訓(xùn)練數(shù)據(jù)集的語言模型，比較了當(dāng)時(shí)最先進(jìn)的Kneser-Neysmoothing算法與他們稱之為“stupidbackoff“(愚蠢退避)的簡單算法,最后發(fā)現(xiàn),后者在小數(shù)據(jù)集時(shí)效果不佳，但在大數(shù)據(jù)集時(shí)，該算法最終居然產(chǎn)生了更好的語言模型！

結(jié)論：大數(shù)據(jù)集上的簡單算法能比小數(shù)據(jù)集上的復(fù)雜算法產(chǎn)生更好的結(jié)果！海量數(shù)據(jù)并行處理技術(shù)簡介為什么需要MapReduce？并行計(jì)算技術(shù)和并行程序設(shè)計(jì)的復(fù)雜性

依賴于不同類型的計(jì)算問題、數(shù)據(jù)特征、計(jì)算要求、和系統(tǒng)構(gòu)架，并行計(jì)算技術(shù)較為復(fù)雜,程序設(shè)計(jì)需要考慮數(shù)據(jù)劃分，計(jì)算任務(wù)和算法劃分，數(shù)據(jù)訪問和通信同步控制,軟件開發(fā)難度大,難以找到統(tǒng)一和易于使用的計(jì)算框架和編程模型與工具海量數(shù)據(jù)處理需要有效的并行處理技術(shù)

海量數(shù)據(jù)處理時(shí)，依靠MPI等并行處理技術(shù)難以湊效MapReduce是目前面向海量數(shù)據(jù)處理最為成功的技術(shù)

MapReduce是目前業(yè)界和學(xué)界公認(rèn)的最為有效和最易于使用的海量數(shù)據(jù)并行處理技術(shù),目前尚無其它更有效的技術(shù)Google,Yahoo,IBM,Amazon,百度等國內(nèi)外公司普遍使用Google:超過7千個(gè)程序基于MapReduce開發(fā)！海量數(shù)據(jù)并行處理技術(shù)簡介MapReduce簡介問題與需求：如何對巨量的Web文檔建立索引、根據(jù)網(wǎng)頁鏈接計(jì)算網(wǎng)頁排名，從上百萬文檔中訓(xùn)練垃圾郵件過濾器，運(yùn)行氣象模擬，數(shù)十億字符串的排序？解決方案：如果你想學(xué)習(xí)如果編寫程序完成這些巨量數(shù)據(jù)的處理問題，MapReduce將為你提供一個(gè)強(qiáng)大的分布式計(jì)算環(huán)境和構(gòu)架，讓你僅需關(guān)注你的應(yīng)用問題本身，編寫很少的程序代碼即可完成看似難以完成的任務(wù)！什么是MapReduce？MapReduce是Google公司發(fā)明的一種面向大規(guī)模海量數(shù)據(jù)處理的高性能并行計(jì)算平臺和軟件編程框架，是目前最為成功和最易于使用的大規(guī)模海量數(shù)據(jù)并行處理技術(shù)，廣泛應(yīng)用于搜索引擎（文檔倒排索引，網(wǎng)頁鏈接圖分析與頁面排序等）、Web日志分析、文檔分析處理、機(jī)器學(xué)習(xí)、機(jī)器翻譯等各種大規(guī)模數(shù)據(jù)并行計(jì)算應(yīng)用領(lǐng)域海量數(shù)據(jù)并行處理技術(shù)簡介MapReduce簡介什么是MapReduce？MapReduce是面向