中國人民大學(xué)RenminUniversityofChina分布式計(jì)算原理中國人民大學(xué)統(tǒng)計(jì)學(xué)院王夢(mèng)天目錄并行計(jì)算1分布式計(jì)算框架2MapReduce3MapReduce統(tǒng)計(jì)計(jì)算案例—矩陣乘法4并行與分布式計(jì)算1并行計(jì)算是——同時(shí)使用多種計(jì)算資源解決計(jì)算問題的過程。流水線—時(shí)間并行多個(gè)處理器并發(fā)計(jì)算—空間并行并行計(jì)算并行計(jì)算的適用情況DATATree1Tree2……TreeNSchematicsofBoostingSchematicsofBagging可以并行無法并行分布式計(jì)算1、數(shù)據(jù)量大，內(nèi)存不足

數(shù)據(jù)分塊讀取到多個(gè)內(nèi)存中2、硬盤讀寫速度是計(jì)算瓶頸

多個(gè)硬盤，同時(shí)讀寫3、單個(gè)處理器計(jì)算能力有限

多個(gè)處理器完成龐大的計(jì)算任務(wù)，平衡負(fù)載馮-諾依曼結(jié)構(gòu)為什么要分布式計(jì)算？這里太小這里太慢這里太忙分布式計(jì)算框架——MapReduce分布式計(jì)算分布式計(jì)算——利用分散系統(tǒng)進(jìn)行計(jì)算。分散系統(tǒng)是一組計(jì)算機(jī)，通過計(jì)算機(jī)網(wǎng)絡(luò)相互鏈接與通信后形成的系統(tǒng)。把需要進(jìn)行大量計(jì)算的工程數(shù)據(jù)分區(qū)成小塊，由多臺(tái)計(jì)算機(jī)分別計(jì)算，在上傳運(yùn)算結(jié)果后，將結(jié)果統(tǒng)一合并得出數(shù)據(jù)結(jié)論。MapReduceMapReduceMapReduce的核心（Key,Value）MapReduce核心——ShuffleShuffle是MapReduce的核心，鏈接Map與Reduce的中間過程。Map負(fù)責(zé)過濾分發(fā)，而Reduce則是歸并整理，從Map輸出到Reduce的輸入的這個(gè)過程稱為Shuffle過程。這個(gè)階段是Hadoop自動(dòng)完成的階段，具有相同key的value被分到同一個(gè)Iterable中，形成<key,Iterable(value)>對(duì)，再傳遞給reduce。對(duì)于我們來說，設(shè)計(jì)MapReduce程序最核心的就是設(shè)計(jì)鍵值對(duì)<key,value>MapReduce示例——矩陣乘法矩陣乘法矩陣的存儲(chǔ)格式——MapReduce示例矩陣乘法以a12為例，它將會(huì)在c11、c12……c1p的計(jì)算中使用。也就是說，在Map階段，當(dāng)我們從分布式文件系統(tǒng)取出一行記錄時(shí)，如果該記錄是A的元素，則需要存儲(chǔ)成p個(gè)<key,value>對(duì)，并且這p個(gè)key互不相同；如果該記錄是B的元素，則需要存儲(chǔ)成m個(gè)<key,value>對(duì)，同樣的，m個(gè)key也應(yīng)互不相同；m×n的矩陣A，與n×p的矩陣B相乘，結(jié)果為m×p的矩陣C。MapReduce示例把來自矩陣A的元素aij，標(biāo)識(shí)成p條<key,value>的形式 key="i,k",（其中k=1,2,...,p），value="a:j,aij"；把來自矩陣B的元素bij，標(biāo)識(shí)成m條<key,value>形式 key="k,j"（其中k=1,2,...,m），value="b:i,bij"。MapReducekey(i,j)中的數(shù)據(jù)對(duì)，就是其在矩陣C中的位置，第i行j列。Key(i,j)