分布式與并行計(jì)算

第一章引論1

分布式系統(tǒng)與并行計(jì)算

第一章引論2

參考書(shū)

(References)

分布式系統(tǒng)作者:李西寧出版:科學(xué)出版社分布式算法導(dǎo)論作者：GerardTel霍紅衛(wèi)譯出版：機(jī)械工業(yè)出版社分布式系統(tǒng)原理與范型作者：AndrewSTanenbaum楊劍鋒等譯出版：清華大學(xué)出版社并行計(jì)算—結(jié)構(gòu)算法編程作者：陳國(guó)良出版：高等教育出版社

第一章引論3莫爾定律GordonMoore(1965)

第一章引論4第一章：引論分布式系統(tǒng)之定義發(fā)展歷史分布式系統(tǒng)之應(yīng)用分布式系統(tǒng)之特征設(shè)計(jì)目標(biāo)和用戶需求并行計(jì)算之定義和應(yīng)用第一章引論5分布式系統(tǒng)之定義(1)：一個(gè)分布式系統(tǒng)是一組由網(wǎng)絡(luò)聯(lián)接的具有獨(dú)立功能的計(jì)算機(jī)，在一套特殊軟件的管理下，整個(gè)系統(tǒng)在用戶面前呈現(xiàn)為一個(gè)透明的整體。(Tanenbaumetal.2002)第一章引論6分布式系統(tǒng)之定義(2)：一個(gè)分布式系統(tǒng)是一組位于網(wǎng)絡(luò)計(jì)算機(jī)上的并發(fā)構(gòu)件，這些構(gòu)件之間的通信以及任務(wù)協(xié)調(diào)都只能通過(guò)信件傳遞進(jìn)行，其目的是實(shí)現(xiàn)資源共享。(Coulourisetal.2005)第一章引論7單機(jī)系統(tǒng)用戶共享一臺(tái)計(jì)算機(jī)可以訪問(wèn)所有資源單一時(shí)鐘單一系統(tǒng)控制單一地理位置單一故障點(diǎn)第一章引論8分布式系統(tǒng)一組由網(wǎng)絡(luò)互聯(lián)的、自治的計(jì)算機(jī)和資源資源為用戶所共享可以集中控制，也可以分布控制計(jì)算機(jī)可以同構(gòu)，也可以異構(gòu)分散的地理位置分布式故障點(diǎn)沒(méi)有全局時(shí)鐘沒(méi)有共享內(nèi)存（大多數(shù)情況）第一章引論9分布式系統(tǒng)的發(fā)展簡(jiǎn)史系統(tǒng)名稱組織機(jī)構(gòu)網(wǎng)絡(luò)要求計(jì)算機(jī)研制日期CM*卡內(nèi)基.·梅隆大學(xué)層次總線PDP1975CambridgeDCS劍橋大學(xué)劍橋環(huán)LSI-41979Locus加州大學(xué)洛杉磯分校以太網(wǎng)PC1980VSystem斯坦福大學(xué)以太網(wǎng)Sun1982Mach卡內(nèi)基.·梅隆大學(xué)以太網(wǎng)Sun,PC1985CORBAOMG互聯(lián)網(wǎng)任何機(jī)器1990DistributedCOM微軟公司互聯(lián)網(wǎng)PC1996JINISunMicrosystems互聯(lián)網(wǎng)任何機(jī)器2000第一章引論10基于CORBA的分布式應(yīng)用開(kāi)發(fā)IDL編譯器（C++,Java）IDLStubSkeleton客戶程序服務(wù)程序IDL接口應(yīng)用開(kāi)發(fā)者客戶應(yīng)用對(duì)象實(shí)現(xiàn)C++,Java編譯器服務(wù)器應(yīng)用C++,Java編譯器OrbLib第一章引論11客戶過(guò)程以正常的方式調(diào)用客戶存根;客戶存根生成一個(gè)消息,然后調(diào)用本地操作系統(tǒng);客戶端操作系統(tǒng)將消息發(fā)送給遠(yuǎn)程操作系統(tǒng);遠(yuǎn)程操作系統(tǒng)將消息交給服務(wù)器存根;服務(wù)器存根將參數(shù)提取出來(lái),然后調(diào)用服務(wù)器;服務(wù)器執(zhí)行要求的操作,操作完成后將結(jié)果返回給服務(wù)器存根;服務(wù)器存根將結(jié)果打包成一個(gè)消息,然后調(diào)用本地操作系統(tǒng);服務(wù)器操作系統(tǒng)將含有結(jié)果的消息發(fā)送回客戶端操作系統(tǒng);客戶端操作系統(tǒng)將消息交給客戶存根;客戶存根將結(jié)果從消息中提取出來(lái),返回給調(diào)用它的客戶過(guò)程.第一章引論12殺手應(yīng)用：以計(jì)算為主的問(wèn)題

（分布式計(jì)算）：

數(shù)學(xué)計(jì)算，環(huán)境模擬，生物和仿生，經(jīng)濟(jì)和財(cái)政模型，氣象預(yù)報(bào)，動(dòng)畫(huà)制作，

…以數(shù)據(jù)為主的問(wèn)題

（分布式數(shù)據(jù)）：

數(shù)據(jù)挖掘,信息檢索，保險(xiǎn)分析，圖像處理，

…以通信為主的問(wèn)題

（網(wǎng)絡(luò)應(yīng)用）：

事務(wù)處理，電子商務(wù)，遠(yuǎn)程文件交換，電子信件，…第一章引論13經(jīng)典分布式應(yīng)用：網(wǎng)格計(jì)算云計(jì)算移動(dòng)計(jì)算ATM（銀行自動(dòng)取款機(jī)）分布式數(shù)據(jù)庫(kù)WWW（萬(wàn)維網(wǎng)）全球定位系統(tǒng)自動(dòng)售貨終端機(jī)航空管制系統(tǒng)網(wǎng)絡(luò)拍賣系統(tǒng)第一章引論14SETI:搜索外星人探索外星文明射電天文望遠(yuǎn)鏡:Arecibo(305m)地理位置:PuertoRico（波多黎各）接收

4,000,000無(wú)線電波段下載屏保程序作數(shù)據(jù)分析中央控制系統(tǒng)分布數(shù)據(jù)UCBerkeley第一章引論15射電望遠(yuǎn)鏡:Arecibo(305m)波多黎各第一章引論16DRC5破譯RSA實(shí)驗(yàn)室給出的密碼，找出密鑰獎(jiǎng)金:$10,000美元RC_56:250天破譯(1997)RC_64:1,757天破譯

(2002)RC_72:?例如:RC_64采用64位密鑰，一共有18,446,744,073,709,551,616 可能的密鑰組合有上百萬(wàn)臺(tái)計(jì)算機(jī)參與這個(gè)項(xiàng)目第一章引論17對(duì)等計(jì)算第一章引論18第一章引論19CERN:歐洲核研究組織CERN是世界上最大的核物理研究中心，科學(xué)家們?cè)噲D通過(guò)對(duì)粒子的研究尋找宇宙的起源。

一臺(tái)大型強(qiáng)子碰撞機(jī):LargeHadronCollider可能產(chǎn)生的數(shù)據(jù):10,000,000GB需要20,000,000張CD來(lái)存儲(chǔ)解決方法：網(wǎng)格計(jì)算，IBM分布式虛擬存儲(chǔ)和文件管理技術(shù)第一章引論20第一章引論21第一章引論22什么是網(wǎng)格通常講，網(wǎng)格（Grid）將網(wǎng)絡(luò)上地理分布的各種資源聚合為一體，支持應(yīng)用問(wèn)題合作求解系統(tǒng)的構(gòu)造集成計(jì)算、數(shù)據(jù)、存儲(chǔ)、設(shè)備、軟件和人員等各種資源；思想：資源共享和協(xié)同，強(qiáng)調(diào)統(tǒng)一和橫向設(shè)計(jì)；方法：建立廣泛的資源共享標(biāo)準(zhǔn)和協(xié)議第一章引論23第一章引論24云計(jì)算Legend:

Clustercomputing,

Gridcomputing,

Cloudcomputing第一章引論25CloudComputing25第一章引論26UserCentricDatastoredinthe“Cloud”Datafollowsyou&your

devicesDataaccessibleanywhereDatacanbeshared

withothersmusicpreferencesmapsnewscontactsmessagesmailinglistsphotoe-mailscalendarphonenumbersinvestments第一章引論27新概念層出不窮SaaSUtilityComputingSaaS=SoftwareasaService??VirtualizationGridComputingClusterComputingCloudComputing第一章引論28可以分為兩類CloudComputingSaaSGridComputingClusterComputingUtilityComputing使用模式基礎(chǔ)設(shè)施Virtualization第一章引論29

云計(jì)算是并行計(jì)算(ParallelComputing)、分布式計(jì)算(DistributedComputing)和網(wǎng)格計(jì)算(GridComputing)的發(fā)展，或者說(shuō)是這些計(jì)算機(jī)科學(xué)概念的商業(yè)實(shí)現(xiàn)。云計(jì)算是虛擬化(Virtualization)、效用計(jì)算(UtilityComputing)、IaaS(基礎(chǔ)設(shè)施即服務(wù))、PaaS(平臺(tái)即服務(wù))、SaaS(軟件即服務(wù))等概念混合演進(jìn)并躍升的結(jié)果。云計(jì)算的技術(shù)背景第一章引論30云計(jì)算的服務(wù)類型第一章引論31AmazonSimpleStorageService$.15perGBpermonthstorage

Object-BasedStorage1B–5GB/objectFast,Reliable,ScalableRedundant,Dispersed99.99%AvailabilityGoalPrivateorPublicPer-objectURLs&ACLsBitTorrentSupport$.10-$.18perGBdatatransfer$.01for1000to10000requests第一章引論32AmazonElasticComputeCloud$.10perserverhour

VirtualComputeCloudElasticCapacity1.7GHzx861.7GBRAM160GBDisk250MB/SecondNetworkNetworkSecurityModelTimeorTraffic-basedScaling,Loadtesting,SimulationandAnalysis,Rendering,SoftwareasaServicePlatform,Hosting$.10-$.18perGBdatatransfer第一章引論33管理交流工作共享GoogleCharts另一個(gè)成功的例子：Google第一章引論34Microsoft的云端計(jì)算Cloud(云)+Client(終端設(shè)備)

用戶選擇合理的計(jì)算資源分布。有些計(jì)算資源應(yīng)該放在云上，有些應(yīng)該放在用戶終端，或混合方式第一章引論35云計(jì)算的特點(diǎn)超大規(guī)模虛擬化高可靠性通用性高可擴(kuò)展性按需服務(wù)極其廉價(jià)第一章引論36網(wǎng)格計(jì)算與云計(jì)算的比較網(wǎng)格計(jì)算異構(gòu)資源不同機(jī)構(gòu)虛擬組織科學(xué)計(jì)算為主高性能計(jì)算機(jī)緊耦合問(wèn)題免費(fèi)標(biāo)準(zhǔn)化科學(xué)界云計(jì)算同構(gòu)資源單一機(jī)構(gòu)虛擬機(jī)數(shù)據(jù)處理為主服務(wù)器/PC松耦合問(wèn)題按量計(jì)費(fèi)尚無(wú)標(biāo)準(zhǔn)商業(yè)社會(huì)第一章引論37移動(dòng)計(jì)算移動(dòng)計(jì)算是當(dāng)前網(wǎng)絡(luò)領(lǐng)域中一個(gè)重要的研究課題；移動(dòng)計(jì)算是將計(jì)算機(jī)網(wǎng)絡(luò)和移動(dòng)通信技術(shù)結(jié)合起來(lái)，為用戶提供移動(dòng)的計(jì)算環(huán)境和新的計(jì)算模式，其作用是在任何時(shí)間都能夠及時(shí)、準(zhǔn)確地將有用信息提供給在任何地理位置的用戶；移動(dòng)計(jì)算技術(shù)可以使用戶在汽車、飛機(jī)或火車?yán)镫S時(shí)隨地辦公，從事遠(yuǎn)程事務(wù)處理、現(xiàn)場(chǎng)數(shù)據(jù)采集、股市行情分析、戰(zhàn)場(chǎng)指揮、異地實(shí)時(shí)控制等。第一章引論38“計(jì)算”這個(gè)詞在不同的時(shí)代有不同的內(nèi)涵；20世紀(jì)初，圖靈設(shè)計(jì)的第一個(gè)理論計(jì)算機(jī)模型和第一臺(tái)電子計(jì)算機(jī)ENIAC問(wèn)世，從那時(shí)以來(lái)，人類開(kāi)始進(jìn)入了計(jì)算機(jī)計(jì)算時(shí)代；需求和計(jì)算機(jī)能力迅速交替上升,而每一次計(jì)算能力的重大進(jìn)步都會(huì)對(duì)科學(xué)和人類生活帶來(lái)重大的影響；電子郵件、Web服務(wù)、電子商務(wù)與IP電話己給我們的生活帶來(lái)了很多變化，但是這僅僅是一個(gè)開(kāi)始；網(wǎng)絡(luò)帶寬迅速地增長(zhǎng)，軟件越來(lái)越豐富，網(wǎng)絡(luò)用戶數(shù)與日劇增，人們的生活、學(xué)習(xí)和工作將離不開(kāi)網(wǎng)絡(luò)，21世紀(jì)人類將進(jìn)入的網(wǎng)絡(luò)計(jì)算時(shí)代；第一章引論39網(wǎng)絡(luò)時(shí)代的“計(jì)算”已經(jīng)有了更為廣泛的含義；網(wǎng)絡(luò)將被看作是最強(qiáng)有力的超級(jí)計(jì)算環(huán)境，它包含了豐富的計(jì)算、數(shù)據(jù)、存儲(chǔ)、傳輸?shù)雀黝愘Y源，用戶可以在任何地方登錄，處理以前不能完成的問(wèn)題；人們可以在不同的地點(diǎn)，很多人共同完成大型的科學(xué)計(jì)算和工程設(shè)計(jì)；學(xué)生可以在網(wǎng)上聽(tīng)世界任何一家其他大學(xué)知名教授的講座，查閱全球的數(shù)字圖書(shū)館的圖書(shū)、文獻(xiàn)；電話、電視機(jī)、收音機(jī)、空調(diào)和家庭安全裝置等各種信息家電都可以聯(lián)入網(wǎng)絡(luò)，可以用戶在異地和移動(dòng)過(guò)程中控制和管理。

第一章引論40移動(dòng)計(jì)算網(wǎng)絡(luò)的主要研究?jī)?nèi)容蜂窩式數(shù)字分組數(shù)據(jù)通信平臺(tái)的應(yīng)用

無(wú)線局域網(wǎng)的應(yīng)用Adhoc網(wǎng)絡(luò)的研究與應(yīng)用無(wú)線傳感器網(wǎng)絡(luò)無(wú)線應(yīng)用協(xié)議WAP和WIFI第一章引論41第一章引論42普適計(jì)算普適計(jì)算(ubiquitouscomputing):指無(wú)所不在、隨時(shí)隨地可以進(jìn)行的一種計(jì)算方式基本特征：無(wú)所不在性，即隨時(shí)隨地訪問(wèn)信息的能力透明性，通過(guò)在物理環(huán)境中提供多個(gè)傳感器、嵌入式設(shè)備、移動(dòng)設(shè)備和其他有計(jì)算能力的設(shè)備，從而在用戶感覺(jué)不到的情況下進(jìn)行計(jì)算通信，并提供各種服務(wù)以人為本，而不是以計(jì)算機(jī)為中心第一章引論43系統(tǒng)設(shè)計(jì)目標(biāo)：資源共享透明性開(kāi)放性可調(diào)節(jié)性特殊系統(tǒng)：安全性可靠性數(shù)據(jù)一致性第一章引論44ISORM-ODP所定義的八種透明性形式

透明性描述訪問(wèn)隱蔽數(shù)據(jù)表達(dá)方法和資源訪問(wèn)方法的不同之處位置隱蔽資源所處的物理位置遷移隱蔽資源的物理移動(dòng)重定位隱蔽正在使用的資源遷移復(fù)制隱蔽資源的復(fù)制并發(fā)隱蔽若干用戶共享同一資源所產(chǎn)生的競(jìng)爭(zhēng)故障隱蔽資源的故障與排錯(cuò)恢復(fù)持續(xù)隱蔽軟件資源所處的存儲(chǔ)空間：內(nèi)存或磁盤(pán)第一章引論45可調(diào)節(jié)性：中央控制機(jī)制概念例子中央式服務(wù)

所有客戶共享一臺(tái)服務(wù)器中央式數(shù)據(jù)

一本聯(lián)機(jī)的電話目錄中央式算法

集中式資源管理程序第一章引論46可調(diào)節(jié)性：分布式控制機(jī)制任何一臺(tái)計(jì)算機(jī)都不可能掌握全局狀態(tài)

任何一臺(tái)計(jì)算機(jī)都根據(jù)自己的局部信息做出決定

一臺(tái)計(jì)算機(jī)的故障不會(huì)導(dǎo)致全局崩潰

不存在全局時(shí)鐘

調(diào)節(jié)對(duì)象：系統(tǒng)功能，系統(tǒng)規(guī)模，管理結(jié)構(gòu)調(diào)節(jié)方法：隱蔽通信延遲，資源分布，資源復(fù)制等第一章引論47用戶需求系統(tǒng)能夠提供何種服務(wù)？系統(tǒng)是否容易管理？系統(tǒng)能夠提供多少好處？性能/價(jià)格比如何？系統(tǒng)是否可靠？系統(tǒng)的安全性如何？第一章引論48并行計(jì)算并行計(jì)算(ParallelComputing),高性能計(jì)算（HighPerformanceComputing）,超級(jí)計(jì)算（SuperComputing）定義：通過(guò)網(wǎng)絡(luò)相互聯(lián)接的兩個(gè)以上的處理機(jī)相互協(xié)調(diào)，同時(shí)計(jì)算同一個(gè)任務(wù)的不同部分，從而提高問(wèn)題求解速度，或者求解單機(jī)無(wú)法求解的大規(guī)模問(wèn)題。兩個(gè)目的：提高速度；擴(kuò)大問(wèn)題求解規(guī)模第一章引論49SingleProcessor2hours，100MB第一章引論50

networkParallelProgrammingParallelAlgorithmFourProcessor0.5hours，25MB/each第一章引論51計(jì)算速度要求問(wèn)題:科學(xué)和工程問(wèn)題的數(shù)值模擬與仿真計(jì)算密集數(shù)據(jù)密集網(wǎng)絡(luò)密集三種混合要求:在合理的時(shí)限內(nèi)完成計(jì)算任務(wù)秒級(jí) 制造業(yè)分鐘級(jí) 短時(shí)天氣預(yù)報(bào)(當(dāng)天)小時(shí)級(jí) 中期天氣預(yù)報(bào)(3~10日)盡可能快 長(zhǎng)期天氣預(yù)報(bào)(氣候)可計(jì)算 湍流模擬第一章引論52問(wèn)題的規(guī)模第一章引論53IBMBuildsOneoftheWorld'sFastestSupercomputertoSimulateNuclearTestingforU.S.EnergyDepartment第一章引論54以動(dòng)物的食物鏈為例第一章引論55第一章引論56GPU簡(jiǎn)介：GPU前途無(wú)限光明GPU將摩爾定律的定義大大擴(kuò)展。一塊工作頻率為3.0GHz的Pentium4處理器，其晶體管數(shù)目為1.25億個(gè)，而同期的一塊NV40GPU就有2.22億個(gè)晶體管。GPU擁有自己的獨(dú)立子存儲(chǔ)系統(tǒng)--顯存，它擁有比系統(tǒng)主內(nèi)存高得多的帶寬。GPU具備強(qiáng)大的并行處理能力和極高的存儲(chǔ)器帶寬，如果被抽象成一個(gè)“流處理器”，可用于諸如科學(xué)運(yùn)算、數(shù)據(jù)分析、線性代數(shù)、流體模擬等需要大量重復(fù)的數(shù)據(jù)集運(yùn)算和密集的內(nèi)存存取的應(yīng)用程序，正是因?yàn)檫@些優(yōu)勢(shì)，使得GPU比CPU更適用于流處理計(jì)算。第一章引論57GPU的工作原理和作用GPU的工作原理

GPU所采用的核心技術(shù)有硬體T&L、立方環(huán)境材質(zhì)貼圖和頂點(diǎn)混合、紋理壓縮和凹凸映射貼圖、雙重紋理四像素256位渲染引擎等，而硬體T&L技術(shù)可以說(shuō)是GPU的標(biāo)志。簡(jiǎn)單說(shuō)GPU是能夠從硬件上支持T&L（TransformandLighting,多邊形轉(zhuǎn)換與光源處理）的顯示芯片。第一章引論58GPU的作用GPU使顯卡減少了對(duì)CPU的依賴，并進(jìn)行部分原本CPU的工作，尤其是在3D圖形處理時(shí)。GPU是顯示卡的“大腦”，它決定了該顯卡的檔次和大部分性能，同時(shí)也是2D顯示卡和3D顯示卡的區(qū)別依據(jù)。今天，GPU已經(jīng)不再局限于3D圖形處理，在通用方面也逐漸嶄露頭角，事實(shí)也證明在浮點(diǎn)運(yùn)算、并行計(jì)算等部分計(jì)算方面，GPU可以提供數(shù)十倍乃至于上百倍于CPU性能。第一章引論59游戲運(yùn)行流程第一章引論60第一章引論61第一章引論62GPUVS．CPU兩者的處理器微結(jié)構(gòu)存在很大的差別

CPU中大量的晶體管用作高速緩存（cache）、邏輯控制單元（control），只有少量的用作計(jì)算單元（ALU）。而GPU則把更多的晶體管用作了計(jì)算單元，只有少量晶體管用作了高速緩存（Cache）和邏輯控制單元，這使得GPU比CPU更適合完成密集計(jì)算任務(wù)第一章引論63第一章引論64第一章引論65CUDAC的開(kāi)發(fā)環(huán)境支持CUDA的圖形處理器NVIDIA設(shè)備驅(qū)動(dòng)程序CUDA開(kāi)發(fā)工具箱標(biāo)準(zhǔn)C編譯器第一章引論66Hadoop項(xiàng)目簡(jiǎn)介Apache的解決方案Google云計(jì)算MapReduceBigTableGFSChubbyGFS-->HDFSMapReduce-->Hadoop

BigTable-->HBase

第一章引論67HDFS為了做到可靠性（reliability）創(chuàng)建了多份數(shù)據(jù)塊（datablocks）的復(fù)制（replicas），并將它們放置在服務(wù)器群的計(jì)算節(jié)點(diǎn)中（computenodes），MapReduce就可以在它們所在的節(jié)點(diǎn)上處理這些數(shù)據(jù)了。第一章引論68HadoopVS.Google技術(shù)架構(gòu)的比較數(shù)據(jù)結(jié)構(gòu)化管理組件：Hbase→BigTable并行計(jì)算模型：MapReduce→MapReduce分布式文件系統(tǒng)：HDFS→GFSHadoop缺少分布式鎖服務(wù)ChubbyHBaseMapReduceHDFSBigTableMapReduceGFSHadoop云計(jì)算應(yīng)用ChubbyGoogle云計(jì)算應(yīng)用第一章引論69Hadoop集群搭建一、實(shí)驗(yàn)環(huán)境1、n臺(tái)PC機(jī)，Linux操作系統(tǒng)

2、Hadoop安裝包（/core/releases.html）3、安裝jdk1.5以上版本第一章引論70Cloudsim仿真軟件介紹2009年4月8日，澳大利亞墨爾本大學(xué)的網(wǎng)格實(shí)驗(yàn)室和Gridbus項(xiàng)目宣布推出云計(jì)算仿真軟件，稱為CloudSim。它是在離散事件模擬包SimJava上開(kāi)發(fā)的函數(shù)庫(kù)，可在Windows和Linux系統(tǒng)上跨平臺(tái)運(yùn)行第一章引論7