第三講并行計(jì)算模型與pram算法

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

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

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

4、應(yīng)的副本定位機(jī)制（02 HDPC ）nsoft-state 協(xié)議：分離節(jié)點(diǎn)狀態(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資源選擇與定位 資源選擇框架研究與評(píng)價(jià)（02 HDPC ）n提出了一種通用的資源選擇框架，通過(guò)定義一種資源選擇服務(wù)RS

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

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

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

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

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

10、種預(yù)測(cè)策略：n趨于平均的預(yù)測(cè)策略n基于趨勢(shì)的預(yù)測(cè)策略（更好）192 DSL近年關(guān)于資源共享方面的研究n資源選擇與定位n資源預(yù)測(cè)與調(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對(duì)該博士課題的理解：為具有P2P特點(diǎn)（large scale和unreliable）的grid設(shè)計(jì)資源發(fā)現(xiàn)方法n分布式系統(tǒng)的通用資源發(fā)現(xiàn)nGrid Vs P2Pn大規(guī)模P2P系統(tǒng)的特點(diǎn)以及對(duì)系統(tǒng)設(shè)計(jì)的啟發(fā)n通用資源發(fā)現(xiàn)的4個(gè)方面n需要研究的問(wèn)題n影響資源發(fā)現(xiàn)機(jī)制的性

11、能和設(shè)計(jì)的幾個(gè)因素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)的特點(diǎn)以及對(duì)系統(tǒng)設(shè)計(jì)的啟發(fā)（02 IEEE Internet Computing Journal）n使用一種“crawler”來(lái)得到Gnutella的應(yīng)用層網(wǎng)絡(luò)拓?fù)?，發(fā)現(xiàn)：n（1）雖然Gnutella不是一個(gè)pure的power-law網(wǎng)絡(luò)，但是它目前的configuration具有power-law結(jié)構(gòu)的優(yōu)點(diǎn)和缺點(diǎn)；n（2）Gnutella的網(wǎng)絡(luò)拓?fù)渑c下層的Internet拓?fù)涞膍atch不好，沒有很好地利用物理網(wǎng)絡(luò)。23分布式

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

13、的關(guān)系25分布式系統(tǒng)的通用資源發(fā)現(xiàn)n影響資源發(fā)現(xiàn)機(jī)制的性能和設(shè)計(jì)的幾個(gè)因素n資源信息的分布和密度n資源信息的動(dòng)態(tài)性n資源請(qǐng)求的分布特性n節(jié)點(diǎn)的加入、離開和失效n目前的RAM-Grid考慮了節(jié)點(diǎn)的加入和退出，但是沒有考慮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ù)共享的特點(diǎn)n

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

15、同一個(gè)文件。這與Gnutella中的文件訪問(wèn)模式是不同的，很少有人多次下載同一個(gè)文件。nsmall-world的特點(diǎn)29文件共享系統(tǒng)的small-world特性及應(yīng)用 n科學(xué)界的數(shù)據(jù)共享n科學(xué)界的數(shù)據(jù)共享的特點(diǎn)n文件訪問(wèn)的特點(diǎn)nsmall-world的特點(diǎn)n大的clustering系數(shù)n小的平均路徑長(zhǎng)度n與隨機(jī)圖相比，科學(xué)協(xié)作網(wǎng)的clustering系數(shù)明顯大，而平均路徑長(zhǎng)度基本相同 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、針對(duì)非集中式的科學(xué)研究數(shù)據(jù)共享環(huán)境，利用small-world特性，提出了定位數(shù)據(jù)的解決方案。nuser自然地形成基于興趣的group。n下一步的問(wèn)題：利用共同特性（small-world），把社會(huì)網(wǎng)中的方法，映射到科學(xué)協(xié)作網(wǎng)中。 31文件共享系統(tǒng)的small-world特性及應(yīng)用 n小世界的文件共享Communities（04 Inforcom）n研究用戶間基于感興趣的文件所形成的關(guān)系。n提出了一種新的結(jié)構(gòu)，用于獲取用戶對(duì)數(shù)據(jù)的興趣the data-sharing graph。n研究了怎樣利用這種特性進(jìn)行系統(tǒng)設(shè)計(jì)。ncluster內(nèi)部:所有節(jié)點(diǎn)的信息互相知道n允許基于共同興趣動(dòng)態(tài)形成clusters ，允許互相學(xué)習(xí)并自適應(yīng)不斷變化的興趣ncluster之間:互連n隨機(jī)法n集中法（cluster level）n基于agent的方法32文件共享系統(tǒng)的small-world特性及