第三講并行計算模型與pram算法

1、1Research on Resource-Sharing byDistributed Systems Laboratory at University of Chicago計算機學(xué)院張一鳴2006.42主要內(nèi)容n1 DSL簡介n2 DSL近年關(guān)于資源共享方面的研究n3 關(guān)于課題的思考31 DSL簡介 1簡介n芝加哥大學(xué)計算機系的DSL實驗室由Ian Foster領(lǐng)導(dǎo)，有兩名研究人員，7個在讀研究生，此外有7名博士已從DSL畢業(yè)。nDSL重點研究分布式系統(tǒng)的設(shè)計、實現(xiàn)、評測、協(xié)議和應(yīng)用等內(nèi)容。41 DSL簡介 2Projects GriPhyN（Grid Physics Network）： 由

2、實驗物理學(xué)家和IT研究者聯(lián)合進行的P比特級的數(shù)據(jù)密集型科學(xué)研究的計算環(huán)境的設(shè)計與實現(xiàn)。 beta-Grid： 定義標準的“Grid-enabled cluster”的行為，包括協(xié)議、調(diào)度和性能特性等，并開發(fā)實現(xiàn)上述標準行為的標準軟件包。51 DSL簡介 2Projects（續(xù)） GrADS（Grid Application Development Software） 通過研究WWW簡化Internet上的信息共享的方法，尋找簡化分布式異構(gòu)計算的實現(xiàn)途徑。希望使網(wǎng)格應(yīng)用的開發(fā)和調(diào)試成為“an everyday practice”。DiPerF (distributed performance t

3、esting framework)： 研究服務(wù)性能的分布式測量方法。62 DSL近年關(guān)于資源共享方面的研究DSL在重要會議發(fā)表的關(guān)于資源共享方面的文章n資源選擇與定位n資源預(yù)測與調(diào)度n基于網(wǎng)絡(luò)特性的資源發(fā)現(xiàn)（Iamnitchi） 72 DSL近年關(guān)于資源共享方面的研究n資源選擇與定位n非集中式的、自適應(yīng)的副本定位機制（02 HDPC ）n資源選擇框架研究與評價（02 HDPC ）nGiggle：可擴展的副本定位服務(wù)框架（02 SC ）nDI-GRUBER：Grid中資源代理的分布方法(05 SC)n資源預(yù)測與調(diào)度n基于網(wǎng)絡(luò)特性的資源發(fā)現(xiàn)（Iamnitchi） 8資源選擇與定位 非集中式的、自適

4、應(yīng)的副本定位機制（02 HDPC ）nsoft-state 協(xié)議：分離節(jié)點狀態(tài)，獲得魯棒性n扁平的overlay網(wǎng)絡(luò)：獲得真正的分布性和可靠性nBloom Filters：使用概率的方法表示副本定位信息。These are well-known techniques; the merit of this paper is to put them together in a flexible design and investigate emerging synergies. 9資源選擇與定位 資源選擇框架研究與評價（02 HDPC ）n提出了一種通用的資源選擇框架，通過定義一種資源選擇服務(wù)RS

5、S，來定位符合應(yīng)用需求的網(wǎng)格資源，其核心是一種基于set matching技術(shù)的聲明性語言。n傳統(tǒng)網(wǎng)格信息服務(wù)功能由Monitoring and Discovery Service (MDS-2)提供，其組件Grid Index Information Service (GIIS)和Grid Resource Information Service (GRIS)提供了資源的可達性和配置信息。Network Weather Service (NWS)動態(tài)預(yù)測網(wǎng)絡(luò)和計算等資源的性能。 10資源選擇與定位nset matcher：使用set-matching算法，匹配資源請求和資源nmapper：確

6、定資源拓撲，分配工作負載 nresource monitor：類似于GRIS，查詢MDS以獲取資源信息 11資源選擇與定位 Giggle：可擴展的副本定位服務(wù)框架（02 SC ）n把副本定位服務(wù)RLS定義為一個維護和提供副本的物理位置信息系統(tǒng)。RLS通常作為數(shù)據(jù)網(wǎng)格的一個組成部分。nLRC：local replica catalog，本地副本目錄，用于維護本節(jié)點所保存的副本信息nRLI：Replica Location Indices，副本定位索引，每個RLI包含多個指向LRC的表項，用于支持副本定位查詢。12資源選擇與定位nLRC：local replica catalog，本地副本目錄，用

7、于維護本節(jié)點所保存的副本信息nRLI：Replica Location Indices，副本定位索引，每個RLI包含多個指向LRC的表項，用于支持副本定位查詢。 13資源選擇與定位 DI-GRUBER：Grid中資源代理的分布方法(05 SC)n在成百上千的作業(yè)和站點上維護一個統(tǒng)一的應(yīng)用服務(wù)級協(xié)定（USLA，usage service level agreements）管理決策將成為性能和可靠性的瓶頸。nDI-GRUBER是GRUBER代理框架的擴展，是一個分布式的基于網(wǎng)格USLA的資源代理，允許多個決策點同時存在并協(xié)作。nDI-GRUBER研究了USLA在大規(guī)模分布式環(huán)境下的存儲、檢索和分發(fā)

8、問題。 nDI-GRUBER的關(guān)鍵是可擴展性和性能問題。 14資源選擇與定位 DI-GRUBER：Grid中資源代理的分布方法(續(xù))n集中式單決策點模型External SchedulerLocal Scheduler15資源選擇與定位 DI-GRUBER：Grid中資源代理的分布方法(續(xù))nDI-GRUBER的分布式多決策點模型External SchedulerLocal Scheduler162 DSL近年關(guān)于資源共享方面的研究n資源選擇與定位n資源預(yù)測與調(diào)度n計算調(diào)度與數(shù)據(jù)遷移調(diào)度的分離(02 HDPC)n共享計算資源的CPU負載預(yù)測(03 IPDPS)n基于網(wǎng)絡(luò)特性的資源發(fā)現(xiàn)（Iam

9、nitchi） 17預(yù)測與調(diào)度計算調(diào)度與數(shù)據(jù)遷移調(diào)度的分離(02 HDPC)n有些數(shù)據(jù)網(wǎng)格application包含大量的松散連接的job，需要訪問并產(chǎn)生大量數(shù)據(jù)。本文描述了一種調(diào)度框架，使數(shù)據(jù)移動操作可以由一個獨立的基于數(shù)據(jù)訪問模式的process來進行。n本文發(fā)現(xiàn)，并不總是必須把數(shù)據(jù)遷移和計算調(diào)度關(guān)聯(lián)在一起，而是可以分別進行，從而大大簡化了數(shù)據(jù)網(wǎng)格的設(shè)計。 18預(yù)測與調(diào)度共享計算資源的CPU負載預(yù)測(03 IPDPS)n在計算網(wǎng)格中，對整個系統(tǒng)未來性能（共享計算資源的CPU負載）的預(yù)測能夠：n指導(dǎo)applications根據(jù)系統(tǒng)狀態(tài)調(diào)整它們的行為n指導(dǎo)schedulers進行合理的調(diào)度n兩

10、種預(yù)測策略：n趨于平均的預(yù)測策略n基于趨勢的預(yù)測策略（更好）192 DSL近年關(guān)于資源共享方面的研究n資源選擇與定位n資源預(yù)測與調(diào)度n基于網(wǎng)絡(luò)特性的資源發(fā)現(xiàn)nIamnitchi的博士課題：大規(guī)模分布式環(huán)境下的資源發(fā)現(xiàn)方法n分布式系統(tǒng)的通用資源發(fā)現(xiàn)n文件共享系統(tǒng)的small-world特性及應(yīng)用 20大規(guī)模分布式環(huán)境下的資源發(fā)現(xiàn)方法n對該博士課題的理解：為具有P2P特點（large scale和unreliable）的grid設(shè)計資源發(fā)現(xiàn)方法n分布式系統(tǒng)的通用資源發(fā)現(xiàn)nGrid Vs P2Pn大規(guī)模P2P系統(tǒng)的特點以及對系統(tǒng)設(shè)計的啟發(fā)n通用資源發(fā)現(xiàn)的4個方面n需要研究的問題n影響資源發(fā)現(xiàn)機制的性

11、能和設(shè)計的幾個因素n文件共享系統(tǒng)的small-world特性及應(yīng)用 21分布式系統(tǒng)的通用資源發(fā)現(xiàn)nGrid Vs P2P22分布式系統(tǒng)的通用資源發(fā)現(xiàn)n大規(guī)模P2P系統(tǒng)的特點以及對系統(tǒng)設(shè)計的啟發(fā)（02 IEEE Internet Computing Journal）n使用一種“crawler”來得到Gnutella的應(yīng)用層網(wǎng)絡(luò)拓撲，發(fā)現(xiàn)：n（1）雖然Gnutella不是一個pure的power-law網(wǎng)絡(luò)，但是它目前的configuration具有power-law結(jié)構(gòu)的優(yōu)點和缺點；n（2）Gnutella的網(wǎng)絡(luò)拓撲與下層的Internet拓撲的match不好，沒有很好地利用物理網(wǎng)絡(luò)。23分布式

12、系統(tǒng)的通用資源發(fā)現(xiàn)n通用資源發(fā)現(xiàn)的4個方面n成員資格協(xié)議（membership protocol）：節(jié)點怎樣加入網(wǎng)絡(luò)，節(jié)點怎樣知道網(wǎng)絡(luò)中的其他節(jié)點n層疊網(wǎng)的構(gòu)建n預(yù)處理：為提高搜索性能而進行的準備工作，例如caching不是預(yù)處理，而prefetching是預(yù)處理n資源請求的處理：在本地查找是否有符合要求的資源、把資源請求傳播到鄰居節(jié)點24分布式系統(tǒng)的通用資源發(fā)現(xiàn)n需要研究的問題noverlay網(wǎng)絡(luò)拓撲怎樣影響資源定位的性能？n提出有效的membership protocoln研究動態(tài)性很強的系統(tǒng)的有效的預(yù)處理策略n資源請求的本地處理n資源請求的傳播（轉(zhuǎn)發(fā)）n研究環(huán)境特性和資源發(fā)現(xiàn)機制設(shè)計之間

13、的關(guān)系25分布式系統(tǒng)的通用資源發(fā)現(xiàn)n影響資源發(fā)現(xiàn)機制的性能和設(shè)計的幾個因素n資源信息的分布和密度n資源信息的動態(tài)性n資源請求的分布特性n節(jié)點的加入、離開和失效n目前的RAM-Grid考慮了節(jié)點的加入和退出，但是沒有考慮failure.26大規(guī)模分布式環(huán)境下的資源發(fā)現(xiàn)方法n分布式系統(tǒng)的通用資源發(fā)現(xiàn)n文件共享系統(tǒng)的small-world特性及應(yīng)用 n科學(xué)界的數(shù)據(jù)共享n在具有小世界特性的科學(xué)協(xié)作網(wǎng)中共享文件n小世界的文件共享Communitiesn在小世界community中基于interest的信息發(fā)布27文件共享系統(tǒng)的small-world特性及應(yīng)用 n科學(xué)界的數(shù)據(jù)共享n科學(xué)界的數(shù)據(jù)共享的特點n

14、數(shù)據(jù)以文件的形式組織，文件以文件名標識。n數(shù)據(jù)量大。CERN的LHC試驗每年產(chǎn)生上P的原始數(shù)據(jù)。n用戶數(shù)量變化大。（同一時刻突然有很多用戶）n無法假定科學(xué)家和他們感興趣的數(shù)據(jù)在地理上相近n在數(shù)據(jù)處理的過程中可能動態(tài)產(chǎn)生新的文件n文件訪問的特點nsmall-world的特點28文件共享系統(tǒng)的small-world特性及應(yīng)用 n科學(xué)界的數(shù)據(jù)共享n科學(xué)界的數(shù)據(jù)共享的特點n文件訪問的特點nGroup locality：同組用戶，盡管可能地理上不在一起，但是更傾向于訪問相同的數(shù)據(jù)集（文件）。CAN和Chord就沒有利用這種特性.nTime logicality: 同一個user可能在很短的時間內(nèi)多次訪問

15、同一個文件。這與Gnutella中的文件訪問模式是不同的，很少有人多次下載同一個文件。nsmall-world的特點29文件共享系統(tǒng)的small-world特性及應(yīng)用 n科學(xué)界的數(shù)據(jù)共享n科學(xué)界的數(shù)據(jù)共享的特點n文件訪問的特點nsmall-world的特點n大的clustering系數(shù)n小的平均路徑長度n與隨機圖相比，科學(xué)協(xié)作網(wǎng)的clustering系數(shù)明顯大，而平均路徑長度基本相同 02年1月觀察到的某科學(xué)協(xié)作網(wǎng)的文件共享圖 30文件共享系統(tǒng)的small-world特性及應(yīng)用 n在具有小世界特性的科學(xué)協(xié)作網(wǎng)中共享文件（02 IPTPS）nP2P的科學(xué)協(xié)作網(wǎng)絡(luò)是一種small-world網(wǎng)絡(luò)n

16、針對非集中式的科學(xué)研究數(shù)據(jù)共享環(huán)境，利用small-world特性，提出了定位數(shù)據(jù)的解決方案。nuser自然地形成基于興趣的group。n下一步的問題：利用共同特性（small-world），把社會網(wǎng)中的方法，映射到科學(xué)協(xié)作網(wǎng)中。 31文件共享系統(tǒng)的small-world特性及應(yīng)用 n小世界的文件共享Communities（04 Inforcom）n研究用戶間基于感興趣的文件所形成的關(guān)系。n提出了一種新的結(jié)構(gòu)，用于獲取用戶對數(shù)據(jù)的興趣the data-sharing graph。n研究了怎樣利用這種特性進行系統(tǒng)設(shè)計。ncluster內(nèi)部:所有節(jié)點的信息互相知道n允許基于共同興趣動態(tài)形成clusters ，允許互相學(xué)習(xí)并自適應(yīng)不斷變化的興趣ncluster之間:互連n隨機法n集中法（cluster level）n基于agent的方法32文件共享系統(tǒng)的small-world特性及