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

Ch.1.并行計(jì)算技術(shù)簡(jiǎn)介MapReduce海量數(shù)據(jù)并行處理南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系主講人：黃宜華2011年春季學(xué)期鳴謝：本課程得到Google公司(北京）中國(guó)大學(xué)合作部精品課程計(jì)劃資助Ch.1.并行計(jì)算技術(shù)簡(jiǎn)介1.為什么需要并行計(jì)算？2.并行計(jì)算技術(shù)的分類3.并行計(jì)算的主要技術(shù)問(wèn)題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ī)：中國(guó)天河一號(hào)，2010年底世界TOP500強(qiáng)第1名

每秒2千5百多萬(wàn)億次浮點(diǎn)運(yùn)算，近20年性能提高3千多倍億億千萬(wàn)億百萬(wàn)億十萬(wàn)億萬(wàn)億千億百億十億億提高計(jì)算機(jī)性能的主要手段1.提高處理器字長(zhǎng)：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)指令級(jí)并行(Instruction-LevelParallelism,

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

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

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

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

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

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

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

2005年Intel全面轉(zhuǎn)入多核計(jì)算技術(shù)，采用多核/眾核構(gòu)架，簡(jiǎn)化單處理器的復(fù)雜設(shè)計(jì),代之以單個(gè)芯片上設(shè)計(jì)多個(gè)簡(jiǎn)化的處理器核,以多核/眾核并行計(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ā)展成為必然趨勢(shì)多核/眾核并行計(jì)算

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

SingleCloudChip,SCC：48核

Teraflops,80核

CitefromIntelwebsite:/projectdetails.aspx?id=151ASCIRed：1996，第一個(gè)達(dá)到1TFlops(10萬(wàn)億次浮點(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ā)展成為必然趨勢(shì)多核/眾核并行計(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ù)雜度大幅提高爆炸性增長(zhǎng)的Web規(guī)模數(shù)據(jù)量Google從2004年每天處理100TB數(shù)據(jù)到2008年每天處理20PB2009年eBays數(shù)據(jù)倉(cāng)庫(kù)，一個(gè)有2PB用戶數(shù)據(jù)，另一個(gè)6.5PB用戶數(shù)據(jù)包含170TB記錄且每天增長(zhǎng)150GB個(gè)記錄；Facebook：2.5PB用戶數(shù)據(jù)，每天增加15TB世界最大電子對(duì)撞機(jī)每年產(chǎn)生15PB(1千5百萬(wàn)GB)數(shù)據(jù)2015年落成的世界最大觀天望遠(yuǎn)鏡主鏡頭像素為3.2G，每年將產(chǎn)生6PB天文圖像數(shù)據(jù)；歐洲生物信息研究中心(EBI)基因序列數(shù)據(jù)庫(kù)容量已達(dá)5PB；中國(guó)深圳華大基因研究所成為全世界最大測(cè)序中心，每天產(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年!特殊場(chǎng)景每幀可能需要60個(gè)小時(shí)(影片“星艦騎兵”中數(shù)千只蜘蛛爬行的場(chǎng)面),用橫向4096象素分辨率進(jìn)行渲染時(shí)，如果以每幀60個(gè)小時(shí)的速度，則1秒的放映量（24幀）需要60天的渲染時(shí)間,1分鐘則需要100年！世界著名的數(shù)字工作室DigitalDomain公司用了一年半的時(shí)間，使用了300多臺(tái)SGI超級(jí)工作站，50多個(gè)特技師一天24小時(shí)輪流制作「泰坦尼克號(hào)」中的電腦特技為什么需要并行計(jì)算？解決方案?并行計(jì)算!!!SMPMPPClusterGRIDCloudMulticoreManycore為什么需要并行計(jì)算？并行計(jì)算技術(shù)的發(fā)展趨勢(shì)和影響越來(lái)越多的研究和應(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ù)將對(duì)傳統(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ù)庫(kù)等系統(tǒng)軟件技術(shù)

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

軟件工程技術(shù)

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

人工智能各種應(yīng)用軟件開發(fā)很多傳統(tǒng)的串行算法和計(jì)算方法都將需要重新研究和設(shè)計(jì)其并行化算法和計(jì)算方法；在最近我系未來(lái)三年的研究規(guī)劃報(bào)告會(huì)上，很多研究領(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ù)簡(jiǎn)介1.為什么需要并行計(jì)算？2.并行計(jì)算技術(shù)的分類3.并行計(jì)算的主要技術(shù)問(wèn)題4.MPI并行程序設(shè)計(jì)5.為什么需要大規(guī)模數(shù)據(jù)并行處理？2.并行計(jì)算技術(shù)的分類經(jīng)過(guò)多年的發(fā)展，出現(xiàn)了不同類型的并行計(jì)算技術(shù)和系統(tǒng)，同時(shí)也存在不同的分類方法按數(shù)據(jù)和指令處理結(jié)構(gòu)：弗林(Flynn)分類按并行類型按存儲(chǔ)訪問(wèn)構(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：?jiǎn)沃噶顔螖?shù)據(jù)流

傳統(tǒng)的單處理器串行處理SIMD：?jiǎn)沃噶疃鄶?shù)據(jù)流

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

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

最常用，TOP500

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

位級(jí)并行（Bit-LevelParallelism）

指令級(jí)并行（ILP：Instruction-LevelParallelism）

線程級(jí)并行（Thread-LevelParallelism）

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

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

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

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

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

多核處理器，SMP……

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

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

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

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

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

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

或Chip-levelmultiprocessing,CMP

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

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

大規(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)的特征和對(duì)比

從MC到Grid，耦合度越來(lái)越低，但可擴(kuò)展性越來(lái)越高，系統(tǒng)規(guī)模越來(lái)越大，而能耗也越來(lái)越高M(jìn)C處理器核通過(guò)NOC(片上網(wǎng)絡(luò))集成在一個(gè)芯片上，通常使用混合式內(nèi)存訪問(wèn)機(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ò)，難以升級(jí)和擴(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ì)算相對(duì)簡(jiǎn)單的并行處理

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

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

(Computation-IntensiveParallelComputing)

數(shù)據(jù)量相對(duì)不是很大、但計(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)

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

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

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

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

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

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

存儲(chǔ)訪問(wèn)體系結(jié)構(gòu)

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

數(shù)據(jù)同步訪問(wèn)和通信控制可靠性設(shè)計(jì)與容錯(cuò)技術(shù)并行計(jì)算軟件框架平臺(tái)系統(tǒng)性能評(píng)價(jià)和程序并行度評(píng)估并行計(jì)算的主要技術(shù)問(wèn)題多核/多處理器網(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ù)問(wèn)題存儲(chǔ)訪問(wèn)體系結(jié)構(gòu)

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

LustreGoogleGFS(GoogleFileSystem)HadoopHDFS(HadoopDistributedFileSystem)并行計(jì)算的主要技術(shù)問(wèn)題并行計(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ù)，或者對(duì)于復(fù)雜的計(jì)算任務(wù)可橫向分解為多次并行處理過(guò)程。并行計(jì)算的主要技術(shù)問(wèn)題并行程序設(shè)計(jì)模型和方法

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

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

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

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

使用函數(shù)庫(kù)提供并行計(jì)算編程接口，如MPI(消息傳遞接口)，CUDA(NVIDIAGPU)并行編譯與優(yōu)化技術(shù)編譯程序需要考慮編譯時(shí)的自動(dòng)化并行性處理，以及為提高計(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ù)問(wèn)題數(shù)據(jù)同步訪問(wèn)和通信控制如何解決并行化計(jì)算中共享數(shù)據(jù)訪問(wèn)和節(jié)點(diǎn)數(shù)據(jù)通信問(wèn)題共享數(shù)據(jù)訪問(wèn)和同步控制在包含共享存儲(chǔ)器結(jié)構(gòu)的系統(tǒng)中，不同處理器/線程訪問(wèn)共享存儲(chǔ)區(qū)時(shí)，可能會(huì)導(dǎo)致數(shù)據(jù)訪問(wèn)的不確定性(競(jìng)爭(zhēng)狀態(tài)，racecondition),因此需要考慮使用同步機(jī)制(互斥信號(hào)，條件變量等)保證共享數(shù)據(jù)和資源訪問(wèn)的正確性，還要解決同步可能引起的死鎖問(wèn)題。分布存儲(chǔ)結(jié)構(gòu)下的數(shù)據(jù)通信和同步控制在包含分布存儲(chǔ)器結(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ù)問(wèn)題可靠性設(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ì)和有效的失效檢測(cè)和恢復(fù)技術(shù)

設(shè)1萬(wàn)個(gè)服務(wù)器節(jié)點(diǎn),每個(gè)服務(wù)器的平均無(wú)故障時(shí)間(MTBF,Mean-TimeBetweenFailures)是1千天,則平均每天10個(gè)服務(wù)器出錯(cuò)！數(shù)據(jù)失效恢復(fù)：大量的數(shù)據(jù)存儲(chǔ)在很多磁盤中，當(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)行,因此,需要有很好的失效檢測(cè)和隔離技術(shù),并進(jìn)行計(jì)算任務(wù)的重新調(diào)度以保證計(jì)算任務(wù)正常進(jìn)行。并行計(jì)算的主要技術(shù)問(wèn)題并行計(jì)算軟件框架平臺(tái)并行計(jì)算軟件技術(shù)跟不上并行計(jì)算硬件系統(tǒng)規(guī)模的發(fā)展,需要研究有效的并行計(jì)算軟件框架、平臺(tái)和軟件設(shè)計(jì)方法提供自動(dòng)化并行處理能力現(xiàn)有的OpenMP、MPI、CUDA等并行程序設(shè)計(jì)方法需要程序員考慮和處理數(shù)據(jù)存儲(chǔ)管理、數(shù)據(jù)和任務(wù)劃分和調(diào)度執(zhí)行、數(shù)據(jù)同步和通信、結(jié)果收集、出錯(cuò)恢復(fù)處理等幾乎所有技術(shù)細(xì)節(jié)，非常繁瑣需要研究一種具有自動(dòng)化并行處理能力的并行計(jì)算軟件框架和平臺(tái)，提供自動(dòng)化的并行處理，能屏蔽并行化處理的諸多系統(tǒng)底層細(xì)節(jié)，交由軟件框架來(lái)處理，提供必要的編程接口，簡(jiǎn)化程序員的編程，讓程序員從系統(tǒng)底層細(xì)節(jié)中解放出來(lái)，專注于應(yīng)用問(wèn)題本身的計(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ù)問(wèn)題系統(tǒng)性能評(píng)估和程序并行度評(píng)估系統(tǒng)性能評(píng)估用標(biāo)準(zhǔn)性能評(píng)估(Benchmark)方法評(píng)估一個(gè)并行計(jì)算系統(tǒng)的浮點(diǎn)計(jì)算能力。High-PerformanceLinpackBenchmark是最為知名的評(píng)估工具，TOP500用其進(jìn)行評(píng)估和排名程序并行度評(píng)估程序能得到多大并行加速依賴于該程序有多少可并行計(jì)算的比例。經(jīng)典的程序并行加速評(píng)估公式Amdahl定律：

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

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

阿貢國(guó)家實(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語(yǔ)言實(shí)現(xiàn)C/C++JavaPython.NETMPI并行程序設(shè)計(jì)MPI主要功能用常規(guī)語(yǔ)言編程方式，所有節(jié)點(diǎn)運(yùn)行同一個(gè)程序，但處理不同的數(shù)據(jù)提供點(diǎn)對(duì)點(diǎn)通信(Point-pointcommunication)提供同步通信功能（阻塞通信）提供異步通信功能（非阻塞通信）提供節(jié)點(diǎn)集合通信(Collectivecommunication)提供一對(duì)多的廣播通信提供多節(jié)點(diǎn)計(jì)算同步控制提供對(duì)結(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è)最基本的編程接口，理論上任何并行程序都可以通過(guò)這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)識(shí)號(hà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)程號(hào)，source：源進(jìn)程標(biāo)識(shí)號(hào)，tag：消息標(biāo)簽MPI并行程序設(shè)計(jì)MPI并行程序設(shè)計(jì)接口基本編程接口MPI并行計(jì)算初始化與結(jié)束

任何一個(gè)MPI程序都要用MPI—Init和MPI—Finalize來(lái)指定并行計(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)用來(lái)確定。進(jìn)程標(biāo)識(shí)

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

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

MPI_Send

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

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

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

因而可能導(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編程示例簡(jiǎn)單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)程號(hào)：0，1，2，3，40號(hào)進(jìn)程作主節(jié)點(diǎn)，負(fù)責(zé)分發(fā)數(shù)據(jù)，不參加子任務(wù)計(jì)算1-4號(hào)進(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號(hào)主節(jié)點(diǎn)*/

if(myid==0)/*0號(hào)主節(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ù)雜問(wèn)題近似求解。設(shè)r取值為0.5，為了提高π計(jì)算精度，需要計(jì)算盡量大的隨機(jī)點(diǎn)數(shù)，我們考慮在一個(gè)并行系統(tǒng)中讓每臺(tái)機(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ù)移動(dòng)(Datamovement)MPI_BCAST:一對(duì)多的廣播式發(fā)送MPI_GATHER：多個(gè)進(jìn)程的消息以某種次序收集到一個(gè)進(jìn)程MPI_SCATTER：將一個(gè)信息劃分為等長(zhǎng)的段依次發(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趨向無(wú)窮大時(shí)的）面積之和構(gòu)成。因此,選取足夠大的N可近似計(jì)算積分。

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

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

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

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

為近似積分值。

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

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

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

即使用百萬(wàn)元高速磁盤陣列(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ù)簡(jiǎn)介為什么需要海量數(shù)據(jù)并行處理技術(shù)？海量數(shù)據(jù)隱含著更準(zhǔn)確的事實(shí)

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

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

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

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

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

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

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

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