Ch.1.并行計算技術簡介MapReduce海量數據并行處理南京大學計算機科學與技術系主講人：黃宜華2011年春季學期鳴謝：本課程得到Google公司(北京）中國大學合作部精品課程計劃資助Ch.1.并行計算技術簡介1.為什么需要并行計算？2.并行計算技術的分類3.并行計算的主要技術問題4.MPI并行程序設計5.為什么需要大規模數據并行處理？1.為什么需要并行計算？貫穿整個計算機技術發展的核心目標：提高計算性能！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.流水線等微體系結構技術

實現指令級并行(Instruction-LevelParallelism,

ILP）RISC結構5級流水線

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

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

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

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

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

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

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

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

Intel實驗芯片

SingleCloudChip,SCC：48核

Teraflops,80核

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

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

NVIDIAGPU

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

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

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

并行計算技術將滲透到每個計算應用領域，尤其是涉及到大規模數據和復雜計算的應用領域并行計算技術將對傳統計算技術產生革命性的影響并行計算技術將影響傳統計算技術的各個層面，與傳統計算技術相互結合產生很多新的研究熱點和課題：

體系結構技術

操作系統、編譯技術、數據庫等系統軟件技術

程序設計技術和方法

軟件工程技術

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

人工智能各種應用軟件開發很多傳統的串行算法和計算方法都將需要重新研究和設計其并行化算法和計算方法；在最近我系未來三年的研究規劃報告會上，很多研究領域都明確需要基于并行計算技術進行研究為什么需要并行計算？為什么需要學習并行計算技術？軟件開發/程序設計人員面臨挑戰！20-30年里程序設計技術的最大的革命是面向對象技術

Therevolutioninmainstreamsoftwaredevelopmentfromstructuredprogrammingtoobject-orientedprogrammingwasthegreatestsuchchangeinthepast20to30years下一個程序設計技術的革命將是并行程序設計

Concurrencyisthenextmajorrevolutioninhowwewritesoftware今天絕大多數程序員不懂并行設計技術，就像15年前絕大多數程序員不懂面向對象技術一樣

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

1966年，斯坦福大學教授Flynn提出的經典的計算機結構分類，從最抽象的指令和數據處理結構的角度進行分類SISD：單指令單數據流

傳統的單處理器串行處理SIMD：單指令多數據流

向量機，信號處理系統MISD：多指令單數據流

很少使用MIMD：多指令多數據流

最常用，TOP500

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

位級并行（Bit-LevelParallelism）

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

線程級并行（Thread-LevelParallelism）

數據級并行：一個大的數據塊劃分為小塊，分別

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

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

別由不同的處理器/線程來處理按存儲訪問結構分類A.共享內存（SharedMemory)

所有處理器通過總線共享內存

多核處理器，SMP……

也稱為UMA結構

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

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

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

B和C也統稱為NUMA結構(Non-UniformMemoryAccess)并行計算技術的分類共享存儲器……總線共享存儲器……MMMABC并行計算技術的分類按系統類型分類

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

或Chip-levelmultiprocessing,CMP

對稱多處理系統SMP(SymmetricMultiprocessing)

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

大規模并行處理MPP(MassiveParallelProcessing)

專用內聯網連接一組處理器形成的一個計算系統

集群（Cluster）

網絡連接的一組商品計算機構成的計算系統

網格（Grid）

用網絡連接遠距離分布的一組異構計算機構成的

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

不同系統的特征和對比

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

數據量極大、但計算相對簡單的并行處理

如：大規模Web信息搜索

計算密集型并行計算

(Computation-IntensiveParallelComputing)

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

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

數據密集與計算密集混合型并行計算

兼具數據密集型和計算密集型特征的并行計算，

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

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

對于分布式內存結構，為了分發數據和收集計算結果，

需要在各個計算節點間進行數據通信，最常用的是消息

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

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

擎等大規模數據并行處理并行計算技術的分類不同類型并行計算技術和系統的發展歷史和現狀主要發展歷史階段

1975-1985

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

1986-1995

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

Cluster和Grid并行計算技術成為主流，但目前Grid的發展已呈下降趨勢，目前TOP500中有414個基于Cluster。并行計算技術的分類不同類型并行計算技術和系統的發展歷史和現狀主要發展趨勢SMP作為共享內存式小規模并行計算技術一直活躍

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

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

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

多核/多處理器網絡互連結構技術

存儲訪問體系結構

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

數據同步訪問和通信控制可靠性設計與容錯技術并行計算軟件框架平臺系統性能評價和程序并行度評估并行計算的主要技術問題多核/多處理器網絡互連結構技術

主要研究處理器間互聯拓撲結構，尤其在包含大量處理器的并行計算系統中，需要具有良好的互聯結構，以保證大量處理器能真正有效地協同工作，獲得應有的并行計算效率。共享總線連接（SharedBus）交叉開關矩陣（CrossbarSwitch）環形結構（Torus）Mesh網絡結構（MeshNetwork）片上網絡（NOC，Network-on-chip）……并行計算的主要技術問題存儲訪問體系結構

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

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

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

普通的程序設計語言（如C語

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

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

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

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

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

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

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

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

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

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

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

最早的完整MPI標準實現.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實現版本廠商實現HP-MPI

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

MPI_Init(&argc,&argv);

……

并行計算程序體……

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

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

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

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

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

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

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

MPI_Send

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

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

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

因而可能導致系統效率下降，為此MPI提供異步通信功能

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

MPI_ISend

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

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

異步接受消息

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

MPI_Test(request,flag,status)

:檢查是否異步數據傳輸確實完成MPI并行程序設計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并行程序設計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進程發送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并行程序設計MPI編程示例消息傳遞MPI編程示例2--計算大數組元素的開平方之和設系統中共有5個進程，進程號：0，1，2，3，40號進程作主節點，負責分發數據，不參加子任務計算1-4號進程作為子節點從主進程接受數組數據：#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并行程序設計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;/*數據分配時除去0號主節點*/

if(myid==0)/*0號主節點，主要負責數據分發和結果收集*/

{

for(int

i=0;i<N;++i;))/*數據分發:0,*/

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

｛

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

}else{for(i=0;i<N;i=i+numprocs;)/*各子節點接受數據計算開平方，本地累加*/

｛

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);/*本地累加結果送回主節點*/}printf("Iamprocess%d.Irecvtotal%dfromprocess0,andSqrtSum=%f.\n",myid,C,SqrtSum);

MPI_Finalize();

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

MonteCarlo方法計算圓周率

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

2,π≈4m/nMPI并行程序設計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));/*設置隨機種子*/

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

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

for(i=0;i<count;i++)/*隨機產生一個點(x,y)，判斷并計算落在圓內的次數*/

{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并行程序設計MPI編程示例消息傳遞MPI編程示例3—MonteCarlo方法計算圓周率pi=4.0*m/count;

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

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

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

else/*主節點接受各從節點的結果并累加*/

{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));/*各節點輸出結果*/

}

MPI_Finalize();

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

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

同步(Barrier)

MPI_Barrier：設置同步障使所有進程的執行同時完成

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

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

將一組進程的數據按照指定的操作方式規約到一起并傳送給一個進程

MPI_Reduce(sendbuf,recvbuf,count,datatype,op,root,comm)其中規約操作op可設為下表定義的操作之一：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并行程序設計節點集合通信接口規約操作編程示例-計算積分

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

設y=x2，求其在[0,10]區間的積分。

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

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

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

為近似積分值。

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

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

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

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

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)/*規約所有節點上的累加和并送到主節點0*/

{/*主節點打印累加和*/

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

}

MPI_Finalize();

}Theintegal

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

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

100TB數據順序讀一遍需要多少時間？設硬盤讀取訪問速率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)海量數據并行處理技術簡介為什么需要海量數據并行處理技術？海量數據隱含著更準確的事實

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

數據，特征，與算法

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

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

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

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

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

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