第三讲并行计算模型与pram算法

1、1Research on Resource-Sharing byDistributed Systems Laboratory at University of Chicago计算机学院张一鸣2006.42主要内容n1 DSL简介n2 DSL近年关于资源共享方面的研究n3 关于课题的思考31 DSL简介 1简介n芝加哥大学计算机系的DSL实验室由Ian Foster领导，有两名研究人员，7个在读研究生，此外有7名博士已从DSL毕业。nDSL重点研究分布式系统的设计、实现、评测、协议和应用等内容。41 DSL简介 2Projects GriPhyN（Grid Physics Network）： 由

2、实验物理学家和IT研究者联合进行的P比特级的数据密集型科学研究的计算环境的设计与实现。 beta-Grid： 定义标准的“Grid-enabled cluster”的行为，包括协议、调度和性能特性等，并开发实现上述标准行为的标准软件包。51 DSL简介 2Projects（续） GrADS（Grid Application Development Software） 通过研究WWW简化Internet上的信息共享的方法，寻找简化分布式异构计算的实现途径。希望使网格应用的开发和调试成为“an everyday practice”。DiPerF (distributed performance t

3、esting framework)： 研究服务性能的分布式测量方法。62 DSL近年关于资源共享方面的研究DSL在重要会议发表的关于资源共享方面的文章n资源选择与定位n资源预测与调度n基于网络特性的资源发现（Iamnitchi） 72 DSL近年关于资源共享方面的研究n资源选择与定位n非集中式的、自适应的副本定位机制（02 HDPC ）n资源选择框架研究与评价（02 HDPC ）nGiggle：可扩展的副本定位服务框架（02 SC ）nDI-GRUBER：Grid中资源代理的分布方法(05 SC)n资源预测与调度n基于网络特性的资源发现（Iamnitchi） 8资源选择与定位 非集中式的、自适

4、应的副本定位机制（02 HDPC ）nsoft-state 协议：分离节点状态，获得鲁棒性n扁平的overlay网络：获得真正的分布性和可靠性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提出了一种通用的资源选择框架，通过定义一种资源选择服务RS

5、S，来定位符合应用需求的网格资源，其核心是一种基于set matching技术的声明性语言。n传统网格信息服务功能由Monitoring and Discovery Service (MDS-2)提供，其组件Grid Index Information Service (GIIS)和Grid Resource Information Service (GRIS)提供了资源的可达性和配置信息。Network Weather Service (NWS)动态预测网络和计算等资源的性能。 10资源选择与定位nset matcher：使用set-matching算法，匹配资源请求和资源nmapper：确

6、定资源拓扑，分配工作负载 nresource monitor：类似于GRIS，查询MDS以获取资源信息 11资源选择与定位 Giggle：可扩展的副本定位服务框架（02 SC ）n把副本定位服务RLS定义为一个维护和提供副本的物理位置信息系统。RLS通常作为数据网格的一个组成部分。nLRC：local replica catalog，本地副本目录，用于维护本节点所保存的副本信息nRLI：Replica Location Indices，副本定位索引，每个RLI包含多个指向LRC的表项，用于支持副本定位查询。12资源选择与定位nLRC：local replica catalog，本地副本目录，用

7、于维护本节点所保存的副本信息nRLI：Replica Location Indices，副本定位索引，每个RLI包含多个指向LRC的表项，用于支持副本定位查询。 13资源选择与定位 DI-GRUBER：Grid中资源代理的分布方法(05 SC)n在成百上千的作业和站点上维护一个统一的应用服务级协定（USLA，usage service level agreements）管理决策将成为性能和可靠性的瓶颈。nDI-GRUBER是GRUBER代理框架的扩展，是一个分布式的基于网格USLA的资源代理，允许多个决策点同时存在并协作。nDI-GRUBER研究了USLA在大规模分布式环境下的存储、检索和分发

8、问题。 nDI-GRUBER的关键是可扩展性和性能问题。 14资源选择与定位 DI-GRUBER：Grid中资源代理的分布方法(续)n集中式单决策点模型External SchedulerLocal Scheduler15资源选择与定位 DI-GRUBER：Grid中资源代理的分布方法(续)nDI-GRUBER的分布式多决策点模型External SchedulerLocal Scheduler162 DSL近年关于资源共享方面的研究n资源选择与定位n资源预测与调度n计算调度与数据迁移调度的分离(02 HDPC)n共享计算资源的CPU负载预测(03 IPDPS)n基于网络特性的资源发现（Iam

9、nitchi） 17预测与调度计算调度与数据迁移调度的分离(02 HDPC)n有些数据网格application包含大量的松散连接的job，需要访问并产生大量数据。本文描述了一种调度框架，使数据移动操作可以由一个独立的基于数据访问模式的process来进行。n本文发现，并不总是必须把数据迁移和计算调度关联在一起，而是可以分别进行，从而大大简化了数据网格的设计。 18预测与调度共享计算资源的CPU负载预测(03 IPDPS)n在计算网格中，对整个系统未来性能（共享计算资源的CPU负载）的预测能够：n指导applications根据系统状态调整它们的行为n指导schedulers进行合理的调度n两

10、种预测策略：n趋于平均的预测策略n基于趋势的预测策略（更好）192 DSL近年关于资源共享方面的研究n资源选择与定位n资源预测与调度n基于网络特性的资源发现nIamnitchi的博士课题：大规模分布式环境下的资源发现方法n分布式系统的通用资源发现n文件共享系统的small-world特性及应用 20大规模分布式环境下的资源发现方法n对该博士课题的理解：为具有P2P特点（large scale和unreliable）的grid设计资源发现方法n分布式系统的通用资源发现nGrid Vs P2Pn大规模P2P系统的特点以及对系统设计的启发n通用资源发现的4个方面n需要研究的问题n影响资源发现机制的性

11、能和设计的几个因素n文件共享系统的small-world特性及应用 21分布式系统的通用资源发现nGrid Vs P2P22分布式系统的通用资源发现n大规模P2P系统的特点以及对系统设计的启发（02 IEEE Internet Computing Journal）n使用一种“crawler”来得到Gnutella的应用层网络拓扑，发现：n（1）虽然Gnutella不是一个pure的power-law网络，但是它目前的configuration具有power-law结构的优点和缺点；n（2）Gnutella的网络拓扑与下层的Internet拓扑的match不好，没有很好地利用物理网络。23分布式

12、系统的通用资源发现n通用资源发现的4个方面n成员资格协议（membership protocol）：节点怎样加入网络，节点怎样知道网络中的其他节点n层叠网的构建n预处理：为提高搜索性能而进行的准备工作，例如caching不是预处理，而prefetching是预处理n资源请求的处理：在本地查找是否有符合要求的资源、把资源请求传播到邻居节点24分布式系统的通用资源发现n需要研究的问题noverlay网络拓扑怎样影响资源定位的性能？n提出有效的membership protocoln研究动态性很强的系统的有效的预处理策略n资源请求的本地处理n资源请求的传播（转发）n研究环境特性和资源发现机制设计之间

13、的关系25分布式系统的通用资源发现n影响资源发现机制的性能和设计的几个因素n资源信息的分布和密度n资源信息的动态性n资源请求的分布特性n节点的加入、离开和失效n目前的RAM-Grid考虑了节点的加入和退出，但是没有考虑failure.26大规模分布式环境下的资源发现方法n分布式系统的通用资源发现n文件共享系统的small-world特性及应用 n科学界的数据共享n在具有小世界特性的科学协作网中共享文件n小世界的文件共享Communitiesn在小世界community中基于interest的信息发布27文件共享系统的small-world特性及应用 n科学界的数据共享n科学界的数据共享的特点n

14、数据以文件的形式组织，文件以文件名标识。n数据量大。CERN的LHC试验每年产生上P的原始数据。n用户数量变化大。（同一时刻突然有很多用户）n无法假定科学家和他们感兴趣的数据在地理上相近n在数据处理的过程中可能动态产生新的文件n文件访问的特点nsmall-world的特点28文件共享系统的small-world特性及应用 n科学界的数据共享n科学界的数据共享的特点n文件访问的特点nGroup locality：同组用户，尽管可能地理上不在一起，但是更倾向于访问相同的数据集（文件）。CAN和Chord就没有利用这种特性.nTime logicality: 同一个user可能在很短的时间内多次访问

15、同一个文件。这与Gnutella中的文件访问模式是不同的，很少有人多次下载同一个文件。nsmall-world的特点29文件共享系统的small-world特性及应用 n科学界的数据共享n科学界的数据共享的特点n文件访问的特点nsmall-world的特点n大的clustering系数n小的平均路径长度n与随机图相比，科学协作网的clustering系数明显大，而平均路径长度基本相同 02年1月观察到的某科学协作网的文件共享图 30文件共享系统的small-world特性及应用 n在具有小世界特性的科学协作网中共享文件（02 IPTPS）nP2P的科学协作网络是一种small-world网络n

16、针对非集中式的科学研究数据共享环境，利用small-world特性，提出了定位数据的解决方案。nuser自然地形成基于兴趣的group。n下一步的问题：利用共同特性（small-world），把社会网中的方法，映射到科学协作网中。 31文件共享系统的small-world特性及应用 n小世界的文件共享Communities（04 Inforcom）n研究用户间基于感兴趣的文件所形成的关系。n提出了一种新的结构，用于获取用户对数据的兴趣the data-sharing graph。n研究了怎样利用这种特性进行系统设计。ncluster内部:所有节点的信息互相知道n允许基于共同兴趣动态形成clusters ，允许互相学习并自适应不断变化的兴趣ncluster之间:互连n随机法n集中法（cluster level）n基于agent的方法32文件共享系统的small-world特性及