齐秀国:网格任务调度算法的多目标模型 |
| 2012-10-16 10:20 作者：齐秀国 来源：硅谷网 HV： 编辑： 【搜索试试】
|
|
【硅谷网10月16日讯】据《科技与生活》杂志2012年第16期刊文称，在很多情况下处于相互独立或者冲突的情况，使网格任务出现了一个难题，就是多目标约束的问题。本文采用的模型建立和求解方法不同于其它文献的建模方法。这种建模方式的优点在于从系统建模时就可以解决多目标间的相互冲突问题。
网格技术的研究当中，任务调度算法的设计处于重要的位置。而任务调度的目的就是网络中，用最完善调度策略进行任务的分配，最终出色的完成计算任务。但由于在很多情况下处于相互独立或者冲突的情况，使网格任务出现了一个难题，就是多目标约束的问题。当前的网格任务调度算法研究主要采用调度启发式来直接构造最终调度方案，存在一些特定的缺陷，完全解决网格中用户对多个目标的需求。因此本文主要探讨多目标网格任务调度模型的求解问题。
1国内外研究概况、水平和发展趋势
网格计算作为一种新兴的计算机技术，正在快速发展中，各国政府、相应的国际组织及大型企业投入了大量的资金和人力进行网格的研究和基础设施的建设。美国用于网格技术的研究经费超过5亿美元；英国政府投入超过一亿英镑的资金建设英国国家网格；欧洲联盟也投入巨资建设欧洲网格；亚洲的中国、日本、韩国等国家也开始着手网格的科研和建设工作。
目前国际上具备较高影响力的网格计算研究项目为：
1）Globus是一个由全美12所大学与研究机构参与的项目，该研究项目在美国阿岗国家实验室的领导下进行。Globus的目标是：①对网格计算中的关键理论，包括资源管理、信息服务、数据管理、安全管理等进行研究；②开发能跨平台运行的网格计算工具软件，以及适合在大型系统中运行的大规模网格应用程序，并建立实验床来帮助组建大型网格实验平台。Globus近期的发展成果是结合万维网与网格计算的研究成果而发布的开放网格服务体系OGSA，它将网格中一切资源都封装为服务，从而支持异构计算环境中的服务发现和组合。
2）Legion是弗吉尼大学将面向对象技术应用到网格计算领域中的一个中间件研究项目，是一个为网格应用而设计的基于对象的系统软件。它的设计目标是让用户在legion环境中仅感知到一台世界范围、抽象的大型计算机的存在，从而网格用户能在这台大型计算机上进行程序设计。
3）Condor是一个解决如何在网格中利用空闲工作站的应用工具，提供队列机制、资源监控与管理、资源调度策略等功能。主要应用于作业间不需要进行相互通信的计算密集型作业，我们可以将它认为是一个专用的计算密集型负载管理系统。
4）DataGrid是欧盟支持的一个项目，目的是实现对隶属于不同机构的、地域上广泛分布的计算能力的访问，从而将生成的海量数据分散到全球范围的计算机上处理。DataGrid的主要功能为：负载调度和管理、数据管理、系统监控、海量存储管理、构造层管理等。该项目包含的三个应用领域为地球观测、生物及医学图像处理、高能量物理。
目前中国网格计算的研究主要集中于中科院计算技术研究所、清华大学等几家在高性能计算方面有较强实力的研究单位，已具规模的“五大网格”有：中国国家网格（CNGrid），国家空间信息网格ChinaSpatialmformatlonGrid），国家自然科学基金委网格（NSFcGrid），中国教育科研网格（chinaGrid）及上海信息网格（ShanghaiGrid）。
1.1网格任务调度系统的概况、水平和发展趋势
到目前为止，国际上很多的组织机构都对网格资源调度进行了深入研究，并将其成果应用于各自的网格系统之中。现已在计算网格的资源管理和任务调度中广泛使用的网格资源管理和任务调度系统有LSF、Nimrod/G和AppLeS等。
1）LSF是一个资源管理和工作负载调度系统，由PlatformComputingCorporation开发。LSF可以利用包括台式电脑、服务器和大型机等在内的计算资源，来确保获取资源的优先权服务级。LSFV6支持一系列的计算机体系结构和操作系统，包括IBM、HP、Intel、Sun、SGI和NEC等。一个LSF集群有一个主控主机和若干个执行主机。主控主机是整个集群的中心协调者。它负责任务的调度和分配；执行主机用来执行任务；提交主机负责将任务送至LSF集群，提交主机也可以变成执行主机。一旦主控主机出现故障，集群中的另一个LSF服务器将变成主控主机。
2）Nimrod/G是一个网格化的资源管理和调度系统，它支持期限和参数扫描应用的基于经济的计算，也支持一种参数声明建模语言用于表达实验的参数。包括Nimrod/G客户端、参数引擎、调度者和分配者几个部分。Nimrod/G在资源管理上遵循的是分级的和计算的市场模型。Nimrod/G与网格中间件系统（如Globus等）交互，提供了资源发现，资源交易，任务映射，结果收集。用户可以指定QoS要求，调度策略是面向应用程序的，负载平衡由周期性的调度来完成。
3）AppLeS是一个运用于网格上的自适应的应用级网格调度系统，并不是一个资源管理系统，每一个提交给网格的应用都有自己的AppLeS。AppLeS的设计哲学是系统性能和利用的所有方面都起源于使用系统对应用的一种预见。AppLes包括了网络气象服务（NWS）、用户规范、模型、资源选择者、计划者、性能评估者、协调者、执行者等组件。为了取得应用效果，AppLeS对特定资源点上的应用性能进行度量，并利用这种信息来进行资源选择和调度安排。AppLeS以并行的主-从式应用为目标。
1.2网格任务调度模型的概况、水平和发展趋势
目前的任务调度模型主要分为以下三种：
1）任务模型：任务模型仅仅和应用相关，和计算平台无关。根据应用是否可分解，存在两种情况：一是应用本身不可划分，此时一个应用对应一个任务；二是应用可以划分，根据划分情况可以分为不同大小，相同大小和任意大小3种任务。任务之间可能具有依赖关系，也可能没有依赖关系。
2）计算平台模型：传统任务调度和网格任务调度的主要区别在于计算平台不同。多数研究认为异构和分布是网格计算平台最主要的特点。它主要包括两个部分：处理机和网络。
处理机模型化为Q=（M，a，b，c，d），其中m∈M表示网络中的处理机，权值a（m）表示计算的速度，b（m）表示处理机的类型，c（m）表示任务的启动开销，d（m）表示内存的大小。
网络模型主要涉及延迟、拓扑和带宽，可以表N=（M，b，C），其中m∈M表示处理机，其中b（m）表示处理机m发送一个任务开销，c（mi，mj）∈C表示处理机mi和mj和之间的通信能力。
3）性能模型：目前性能模型可以大致分为两类：基于系统的目标和基于用户的目标。由于这些目标可能并不一致，最近已经提出多目标模型和多QoS限制的性能模型。
1.3网格调度算法的概况、水平和发展趋势
网格计算中，任务调度的实质就是将n个相互独立的任务分配到m个异构可用资源上，使得总任务的完成时间最小以及资源得到充分利用。根据目前网格任务调度算法研究的发展，单一目标的网格任务调度算法已经不能满足网格发展的需要。大多数算法虽然提出了改进，但仍然是单一目标调度算法。
2多目示任务模型的建立
2.1任务调度模型
首先我们假设所有的任务都具有相同的大小。并且利用入度为零的节点作为所有任务的输入节点。且由它对其他节点进行安全姓和可靠性及时间等约束指标的重要度的注册。而且我们继续假设每个约束指标可以预测出它与其它约束指标之间的相对重要程序。
这样，我们可以得到一个多目标的向图，以此来表示网格中的i个计算节点，第m个节点我们可以表示成：rm={D，Wm，O}。m∈n，其中用D表示为rm节点，节点rn的优先级为wn；wm∈W。为节点集的优先级向量，为节点rm的h个约束指标。
，其中用ey={ra，rb，T（y）1，T（y）2}表示第y个边，ey的开始顶点用ra表示，ey的结束顶点用rb表示，一个任务从ra传输到rb所用的时间表示为T（y）1，顶点rb计算一个任务所用的时间为T（y）2。
这样我们就可由下式求得最优调度数：
Sum（m）=M×wm
通过上式可以看出其中关键问题是对计算节点rm的多约束优先级的求解。
2.2求解模型算法基本思想
约束指标的相对重要度表示为：，，，
约束指标表示为：，，。
这样我们可以利应用，，对列向量进行归一化，可得到矩阵。
对矩阵进行，，运算，可以得出：
因此，就可以得到计算节点在约束指标下的优先级向量。
3结束语
本文采用的模型建立和求解方法不同于其它文献的建模方法。这种建模方式的优点在于从系统建模时就可以解决多目标间的相互冲突问题，它通过约束指标判断矩阵计算来个表示计算结点在约束指标下的重要程度，然后再应用多目标冲突度算法解决该模型下网格任务调度问题。
作者简介
齐秀国（1982-），男，黑龙江科技术学院计算机专业研究生在读，助理讲师，就职于七台河职业学院。
|
|
|
|
【对“齐秀国:网格任务调度算法的多目标模型”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
