分布式與并行計(jì)算報(bào)告-在線瀏覽
2024-09-11 18:52本頁面
【正文】 nication of ACM》上。而不能被并行化部分工作量占總工作量的相對(duì)比例f會(huì)相應(yīng)減小。這個(gè)公式不是一個(gè)精細(xì)的性能評(píng)估公式，而是一個(gè)思想性的公式，它揭示了大規(guī)模并行的要旨：并行計(jì)算機(jī)的實(shí)際性能和它所運(yùn)行的并行程序特征密切相關(guān)。在提高大規(guī)模并行計(jì)算使用效率的過程中，能否設(shè)計(jì)出可擴(kuò)展并行算法和可擴(kuò)展并行程序，與大規(guī)模并行計(jì)算機(jī)系統(tǒng)的研制同等重要。于是基于經(jīng)濟(jì)學(xué)中產(chǎn)生率的概念和效用理論逐漸取代了以往單一的計(jì)算性能評(píng)價(jià)模型。該效能度量模型綜合考慮了并行系統(tǒng)開發(fā)（Development）和運(yùn)行（Execution）兩種狀態(tài)，將開發(fā)的時(shí)間和系統(tǒng)運(yùn)行的時(shí)間統(tǒng)一到問題解決時(shí)間T中。3 并行編程模型并行編程可以調(diào)用系統(tǒng)函數(shù)啟動(dòng)多線程，也可以利用并行編程模型，如常用的并行模型有MPI、PVM、OpenMP、TBB及Cilk++等。消息傳遞指的是并行執(zhí)行的各個(gè)進(jìn)程具有自己獨(dú)立的堆棧和代碼段，作為互補(bǔ)相關(guān)的多個(gè)程序獨(dú)立執(zhí)行，進(jìn)程之間的通信通過顯式地調(diào)用通信函數(shù)來完成。MPI_Finalize則是結(jié)束MPI執(zhí)行環(huán)境。②MPI_Comm_rank 來表示各個(gè)MPI進(jìn)程。整數(shù)指標(biāo)，返回相應(yīng)進(jìn)程組中的進(jìn)程數(shù)。時(shí)間消耗可以用下面的式子表示： （4）其中，、分別表示程序總用時(shí)、通信用時(shí)和串行部分用時(shí)。（3） 解決負(fù)載均衡問題 在并行計(jì)算中，若各個(gè)處理器上的執(zhí)行時(shí)間不同，因同步會(huì)使先完成的處理器等待未完成的處理器，此時(shí)應(yīng)該考慮負(fù)載均衡問題，是的資源得到合理利用。靜態(tài)負(fù)載均衡使用與計(jì)算前可以準(zhǔn)確估算總的負(fù)載，且這些負(fù)載容易平均劃分給各個(gè)進(jìn)程的情況。 PVM簡介PVM是一個(gè)在網(wǎng)絡(luò)上的虛擬并行機(jī)系統(tǒng)的軟件包，它允許將網(wǎng)絡(luò)上基于UNIX操作系統(tǒng)的并行機(jī)和單處理機(jī)的集合當(dāng)成一臺(tái)單一的并行虛擬機(jī)來使用。計(jì)算以任務(wù)為單位，一個(gè)任務(wù)就是一個(gè)UNIX進(jìn)程，每個(gè)任務(wù)都有一個(gè)taskid來標(biāo)識(shí)（不同于進(jìn)程號(hào)）。 OpenMP簡介OpenMp是一種面向共享內(nèi)存及分布式共享內(nèi)存的多處理器多線程并行編程語言，它也是一種能夠用于顯示指導(dǎo)多線程、共享內(nèi)存并行的應(yīng)用程序編程接口。OpenMP 的執(zhí)行模型采用Fork － Join 形式，F(xiàn)ork － Join 執(zhí)行模式在開始執(zhí)行的時(shí)候，只有一個(gè)主線程存在。在并行執(zhí)行的時(shí)候，主線程和派生線程共同工作。 Intel TBB（Threading Building Block）簡介Intel TBB 是一個(gè)用來支撐可擴(kuò)展編程的庫，TBB 的工作層次要高于裸線程，它為C + + 程序提供了豐富而完備的方法來表達(dá)并行語義。TBB 運(yùn)用自己的調(diào)度算法把任務(wù)分配到各個(gè)線程，高效合理地利用處理器資源。TBB 中還支持算法模板，如基于遞歸區(qū)間的面向循環(huán)算法，根據(jù)需求來遞歸地劃分問題，從而獲得并行任務(wù)的正確層次。線程構(gòu)建模塊的函數(shù)都定義在空間tbb 中，TBB 提供parallel_for 與parallel_reduce 泛型并行算法，可以負(fù)載均衡地對(duì)固定數(shù)目的獨(dú)立循環(huán)迭代體進(jìn)行并行執(zhí)行。Cilk + + 語言特別適合但不限于分而治之算法，把任務(wù)分解成子問題( 任務(wù)) ，可以獨(dú)立地加以解決。這些任務(wù)會(huì)在不同循環(huán)迭代。Cilk ++ 語言比較適合“二分法”算法，將問題分解成若干獨(dú)立子問題，再將這些執(zhí)行結(jié)果合并起來。Cilk ++ 的關(guān)鍵詞能有效地標(biāo)識(shí)可并行執(zhí)行的函數(shù)調(diào)用和循環(huán)，Cilk ++ 的運(yùn)行環(huán)境能有效地將這些任務(wù)調(diào)度到空閑的處理器上運(yùn)行。連接設(shè)備、實(shí)時(shí)數(shù)據(jù)流、SOA 的采用以及搜索、開放協(xié)作、社會(huì)網(wǎng)絡(luò)和移動(dòng)商務(wù)等都是推動(dòng)云計(jì)算技術(shù)發(fā)展的推動(dòng)因素。在性能方面，并行計(jì)算主要追求較高的加速比，而云計(jì)算則單機(jī)的計(jì)算能力要求較低，此系統(tǒng)通過將分散的結(jié)點(diǎn)統(tǒng)一，根據(jù)相應(yīng)調(diào)度算法合理調(diào)度，從而獲得巨大的計(jì)算能力，而且還能根據(jù)客戶的需求變化進(jìn)行調(diào)整。對(duì)于大型應(yīng)用系統(tǒng)實(shí)施云計(jì)算的主要內(nèi)容就是實(shí)施并行計(jì)算。這3 個(gè)技術(shù)主要應(yīng)用于并行程序的開發(fā)， 和其他并行策略（如SOA）一起，用于從根本上實(shí)現(xiàn)應(yīng)用的并行化。對(duì)于條件成熟的應(yīng)用，擬從業(yè)務(wù)并行開始，在開發(fā)層面即實(shí)現(xiàn)并行計(jì)算。 大圖數(shù)據(jù)背景下的并行計(jì)算模型及其優(yōu)化技術(shù)大數(shù)據(jù)時(shí)代背景下，數(shù)十億頂點(diǎn)級(jí)別大規(guī)模圖的不斷涌現(xiàn)以及云計(jì)算基礎(chǔ)設(shè)施的持續(xù)完善，推動(dòng)著圖數(shù)據(jù)處理的研究重心由單機(jī)圖算法的高度優(yōu)化逐漸轉(zhuǎn)向分布式并行大圖處理的優(yōu)化。由于Mapreduce在應(yīng)用定位與設(shè)計(jì)目標(biāo)上主要是針對(duì)模式自由（schemafree）的數(shù)據(jù)對(duì)象實(shí)現(xiàn)高吞吐的批量處理，因此其缺乏有效處理大圖的內(nèi)部機(jī)制。其顯著的特征是提供了對(duì)圖計(jì)算中最常見的迭代操作的支持和實(shí)現(xiàn)了直觀易用的以頂點(diǎn)為中心的編程抽象。在分布內(nèi)存架構(gòu)下，目前具有代表性的大圖并行計(jì)算模型有Pregel、HAMA、Giraph、Distributed GraphLab以及Trinity等。部分大圖處理系統(tǒng)采用經(jīng)典的劃分方法，如ParMetis，也有其他一些系統(tǒng)探索了新的劃分方法，如GraphX和PowerGraph均采用vertexcut的劃分方法緩解自然圖中高度數(shù)（highdegree）頂點(diǎn)通信集中的問題；Trinity采用多層標(biāo)簽傳遞的劃分方法，借助圖的語義有效支持了十億頂點(diǎn)級(jí)別大圖的劃分；而GPS和Mizan都利用動(dòng)態(tài)的劃分方法緩解了大圖計(jì)算過程中負(fù)載失衡時(shí)的頂點(diǎn)重分配的問題。鑒于此，一些研究
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1