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

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

每秒2千5百多萬億次浮點運算，近20年性能提高3千多倍億億千萬億百萬億十萬億萬億千億百億十億億提高計算機性能的主要手段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為什么需要并行計算？提高計算機性能的主要手段2.提高集成度摩爾定律：芯片集成度每18個月翻一倍，計算性能提高一倍為什么需要并行計算？為什么需要并行計算？提高計算機性能的主要手段3.流水線等微體系結(jié)構(gòu)技術(shù)

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

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

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

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

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

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

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

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

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

雙核: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)為什么需要并行計算？單處理器向多核并行計算發(fā)展成為必然趨勢多核/眾核并行計算

Intel實驗芯片

SingleCloudChip,SCC：48核

Teraflops,80核

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

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

NVIDIAGPU

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

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

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

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

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

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

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

軟件工程技術(shù)

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

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

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

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

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

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

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

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

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

最常用，TOP500

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

位級并行（Bit-LevelParallelism）

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

線程級并行（Thread-LevelParallelism）

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

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

任務級并行：一個大的計算任務劃分為子任務分

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

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

多核處理器，SMP……

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

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

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

各個處理器使用本地獨立的存儲器

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

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

或Chip-levelmultiprocessing,CMP

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

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

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

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

集群（Cluster）

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

網(wǎng)格（Grid）

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

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

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

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

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

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

計算密集型并行計算

(Computation-IntensiveParallelComputing)

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

如：3-D建模與渲染，氣象預報，科學計算……

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

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

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

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

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

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

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

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

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

1975-1985

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

1986-1995

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

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

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

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

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

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

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

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

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

主要研究處理器間互聯(lián)拓撲結(jié)構(gòu)，尤其在包含大量處理器的并行計算系統(tǒng)中，需要具有良好的互聯(lián)結(jié)構(gòu)，以保證大量處理器能真正有效地協(xié)同工作，獲得應有的并行計算效率。共享總線連接（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）……并行計算的主要技術(shù)問題存儲訪問體系結(jié)構(gòu)

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

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

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

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

言）上增加一些并行計算宏

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

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

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

大型并行計算系統(tǒng)使用大量計算機,因此,節(jié)點出錯或失效是常態(tài)，不能因為一個節(jié)點失效導致數(shù)據(jù)丟失、程序終止或系統(tǒng)崩潰，因此，系統(tǒng)需要具有良好的可靠性設(shè)計和有效的失效檢測和恢復技術(shù)

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

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

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

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

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

阿貢國家實驗室和密西西比大學

最早的完整MPI標準實現(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實現(xiàn)版本廠商實現(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語言實現(xiàn)C/C++JavaPython.NETMPI并行程序設(shè)計MPI主要功能用常規(guī)語言編程方式，所有節(jié)點運行同一個程序，但處理不同的數(shù)據(jù)提供點對點通信(Point-pointcommunication)提供同步通信功能（阻塞通信）提供異步通信功能（非阻塞通信）提供節(jié)點集合通信(Collectivecommunication)提供一對多的廣播通信提供多節(jié)點計算同步控制提供對結(jié)果的規(guī)約(Reduce)計算功能提供用戶自定義的復合數(shù)據(jù)類型傳輸MPI并行程序設(shè)計MPI基本程序結(jié)構(gòu)MPI程序頭文件初始化MPI環(huán)境并行計算與通信關(guān)閉MPI環(huán)境#include<mpi.h>main(intargc,char**argv){intnumtasks,rank;

MPI_Init(&argc,&argv);

……

并行計算程序體……

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

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

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

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

任何一個MPI程序都要用MPI—Init和MPI—Finalize來指定并行計算開始和結(jié)束的地方；同時在運行時，這兩個函數(shù)將完成MPI計算環(huán)境的初始化設(shè)置以及結(jié)束清理工作。處于兩者之間的程序即被認為是并行化的，將在每個機器上被執(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!在一個有5個處理器的系統(tǒng)中，輸出為MPI并行程序設(shè)計MPI并行程序設(shè)計接口基本編程接口通信組（Communicator）為了在指定的范圍內(nèi)進行通信，可以將系統(tǒng)中的處理器劃分為不同的通信組；一個處理器可以同時參加多個通信組；MPI定義了一個最大的缺省通信組:MPI_COMM_WORLD，指明系統(tǒng)中所有的進程都參與通信。一個通信組中的總進程數(shù)可以由MPI_Comm_Size調(diào)用來確定。進程標識

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

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

MPI_Send

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

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

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

因而可能導致系統(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ù)傳輸確實完成MPI并行程序設(shè)計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è)計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)/*其他進程，向0進程發(fā)送HelloWorld信息*/

{strcpy(message,“HelloWorld!”);

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

}else/*0進程負責從其他進程接受信息并輸出*/

{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è)計MPI編程示例消息傳遞MPI編程示例2--計算大數(shù)組元素的開平方之和設(shè)系統(tǒng)中共有5個進程，進程號：0，1，2，3，40號進程作主節(jié)點，負責分發(fā)數(shù)據(jù)，不參加子任務計算1-4號進程作為子節(jié)點從主進程接受數(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=∑各子進程的SqrtSumIamprocess1.Irecvtotal251dataitemsfromprocess0,andSqrtSum=111.11Iamprocess2.Irecvtotal251dataitemsfromprocess0,andSqrtSum=222.22Iamprocess3.Irecvtotal250dataitemsfromprocess0,andSqrtSum=333.33Iamprocess4.Irecvtotal250dataitemsfromprocess0,andSqrtSum=444.44Iamprocess0.Irecvtotal0dataitemsfromprocess0,andSqrtSum=1111.10MPI并行程序設(shè)計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ù)分配時除去0號主節(jié)點*/

if(myid==0)/*0號主節(jié)點，主要負責數(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é)點接受數(shù)據(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é)點*/}printf("Iamprocess%d.Irecvtotal%dfromprocess0,andSqrtSum=%f.\n",myid,C,SqrtSum);

MPI_Finalize();

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

MonteCarlo方法計算圓周率

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

2,π≈4m/nMPI并行程序設(shè)計MPI編程示例消息傳遞MPI編程示例3—MonteCarlo方法計算圓周率#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è)置隨機種子*/

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

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

for(i=0;i<count;i++)/*隨機產(chǎn)生一個點(x,y)，判斷并計算落在圓內(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è)計MPI編程示例消息傳遞MPI編程示例3—MonteCarlo方法計算圓周率pi=4.0*m/count;

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

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

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

else/*主節(jié)點接受各從節(jié)點的結(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é)點輸出結(jié)果*/

}

MPI_Finalize();

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

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

同步(Barrier)

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

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

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

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

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è)計節(jié)點集合通信接口規(guī)約操作編程示例-計算積分

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

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

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

個x取值對應小矩形面積為：y*10/N

求和所有矩形面積，當N足夠大時即

為近似積分值。

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

010MPI并行程序設(shè)計MPI編程示例規(guī)約操作編程示例—計算積分#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è)計MPI編程示例規(guī)約操作編程示例—計算積分

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

{/*每個節(jié)點計算一個顏色組的矩形面積并累加*/

x=a+i*dx+dx/2;/*以每個矩形的中心點x值計算矩形高度*/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é)點上的累加和并送到主節(jié)點0*/

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

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

}

MPI_Finalize();

}Theintegal

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

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

100TB數(shù)據(jù)順序讀一遍需要多少時間？設(shè)硬盤讀取訪問速率128MB/秒1TB/128MB約2.17小時100TB/128MB=217小時=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ù)隱含著更準確的事實

信息檢索、自然語言理解和機器學習的三個要素：

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

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

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

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

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

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

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