论文部分内容阅读
【摘要】针对网格计算中任务调度的特点和目标，阐述了目前网格任务调度的现状，结合超图理论，对超图理论在网格任务调度中的应用进行总结，最后针对目前超图任务调度提出相关问题和研究展望。
【关键词】网格；任务调度；超图
引言
20世纪90年代，网格技术随着计算机网络技术的发展而起源，它是继Internet技术，web技术之后的第三大技术浪潮，它是将世界各个地区的资源进行资源共享，这些资源有硬件资源，也有软件资源，比如：计算机硬件系统，软件系统，专家资源，通信系统，文件系统，共享文档，知识资源等等。通过网格技术，人们可以获得最优的资源分配。网格在不断的发展中，被称为是下一代的网络技术。
在网络环境中，网格资源分布在世界各个角落，如何管理资源，并获得最优的资源，是网格技术中必须要考虑的现实问题，因此资源的分配和任务调度是网格技术中比较重要的环节。
1.任务调度特点和目标
网格任务调度具有面向异构平台、大规模、非集中式、不干涉网格节点内部、可扩展性等特点。异构平台，网格资源种类各异，它们是异构的，可运行在各种操作系统下，因此调度必须面向异构平台；大规模、集中式，网格系统是整个Internet系统，要实现统一管理、集中调度很困难，必须以分布式、并行式管理与调度；不干涉内部节点，网格结点的内部调度是自治的，不同节点有不同的调度策略，也体现了节点的自主性；可扩展性，随着计算机的不断加入，系统的计算规模也随之扩大，在不降低网格系统的性能前提下，网格系统的任务调度必须具有可扩展性。
网格任务调度的最终目标就是要对用户提交的任务实现最优调度，并设法提高网格系统的总体吞吐率。具体的目标包括：最优跨度（Optimal Makespan），服务质量QoS（Quality of Service），负载均衡（Load Balancing），经济原则（Economic Principles）。
（1）最优跨度
跨度是一个最为常见的目标，是指任务调度完成的时间，即从第一个任务调度开始到最后一个任务调度完成所经历的时间，跨度越小，任务调度的时间越小。最优跨度就是最小的任务调度时间。
（2）服务质量
在任务调度的过程中，必须要保障网格相应的服务质量，这样才能确保调度过程顺利有序的进行。
（3）负载均衡
负载均衡是指任务调度到资源上时，确保大多数资源都能被任务所占用，也就是充分利用网格资源，这样才能提高整个网络的整体性能。
（4）经济原则
现实生活中的市场经济原则使消费双方互惠互利，长久发展。在网格环境中，不同资源的使用费用也是不相同的，市场经济驱动的资源管理与任务调度必须使网格资源的提供者和消费者互惠互利，才能使网格系统长久发展下去。
2.任务调度现状
网格计算中任务调度已被证明是完全问题，需要使用启发式方法来获得最优或近优解。我们依据任务间关系，将任务调度分为元任务和依赖任务调度。元任务是指相互独立的任务，彼此之间没有通信要求，依赖任务是指任务之间有制约关系，存在先后依赖关系，即可执行条件制约在前任务执行完毕的情况下。
元任务的经典算法有Min-min算法、Max-min算法、Sufferage算法。这些算法虽然经典，但是也有一定缺陷，因此，在经典算法的基础上提出的新算法也是非常多的。如文献[4]，针对Min-min算法的负载不均衡，提出了改进算法Sect-Min算法，采用“分段”的思想，把任务分成若干小任务，不仅减少了执行时间，提高了资源的有效性，而且负载均衡性得到显著提高。文献[5]提出了一种扩展的QD-Sufferage算法，该算法在Sufferage算法基础上，融入了Qos优先级分组和Deadline约束的思想，相比同类算法有更短的makespan和获得更高的任务接受率。
对于依赖任务大多采用有向无环图（Directed
Acyclic Graph，DAG）来表达任务间的依赖关系。对于依赖任务的调度一种有效常用的方法是将依赖任务分解成独立的元任务，然后进行调度。如GS算法[6]，该算法的思想就是根据DAG节点的优先级，将依赖任务集合转换成若干个内部包含独立任务的任务集合，对于此集合，可以使用Min-min、Max-min、Sufferage等算法进行调度。
目前，随机化搜索算法比如遗传算法[7]、模拟退火算法[8]和蚁群算法[9]等等，通过有导向的随机选择，不断结合先前搜索的结果和特征去寻找问题的解空间，最终生成良好的调度结果，此类方法在复杂的计算系统中有着明显优势。
3.超图理论
20世纪70年代C.Berge在《图与超图》中首次系统地阐述了超图的概念[10]。超图是图论的一个分支，具有图论不具备的性质，它是一种有限集的组合学，研究多元子集问题或者有限集中各元之间的多元关系，描述最具一般性的离散结构关系。
超图（Hypergraph）是二元对，其中表示超图的n个顶点，表示超图的m条超边。超边集E为定义在顶点集V上的子集簇，即，并且满足：
（1）
（2）
超图相对与一般图论而言一个显著的不同是：超边能够表达定点之间更为一般的关系，而一般图只能表示两个顶点之间的关系。
超图分为无向超图和有向超图，无向超图即为上述超图，有向超图是在无向超图中每条超边的基础上添加方向所得。自20世纪60年代以来，经过几十年的发展，无向超图理论已经建立起比较完备的学科体系。虽然有向超图研究的历史并不长，但是基于无向超图的理论，这对于有向超图的研究工作也是非常有益的。
目前，超图已经在数据挖掘、工作流管理、网络综合、电路分析等多方面得到应用，并取得了可观的成绩。文献[11]基于有向超图，提出了一种工作流资源分配均衡优化方法，文献[12]将超图融入电路分析中，对电路的设计分析等有奠基的效果。在网格任务调度方面，超图亦有非常好的发展前景。 4.超图在网格任务调度中的应用
针对网格任务和资源的特点，应用超图理论构建分类模型，这样能对任务和资源进行统一的管理和调度，同时也可对超图模型进行优化，从而降低调度长度。
4.1 超图任务模型
对于以往的任务大多采用有向无环图（Directed Acyclic Graph，DAG）来表达任务间的关系。应用超图来表达，能够更好的反映任务的特点和任务之间的关系，不论在表现形式还是内容上，都进行了扩展和优化，不仅使任务的关系表达更方便直接，而且通过超图进行优化，不但可以简化计算，还能降低时间复杂度，提高调度性能。
超图的任务关系及其矩阵表示：
4.2 超图资源模型
网格环境下的资源数量巨大，具有广域性、动态性、异构性等多种特点，相比传统的分布式系统更加复杂，如果用传统的多处理机系统的调度算法，时间开销大，不能发挥出网格的优势，应用超图理论来构建资源模型，不但能够统一管理，还能在超图的基础上作优化，如超边的合并或分解，来简化任务调度的映射过程，从而降低调度长度。
5.研究展望
任务调度是网格计算的重要组成部分，对于它的研究仍然十分重要。超图理论，在各方面不断发挥新作用，在网格任务调度方面，更是开辟了一条新路径。虽然已取得了些成果[13]，但是还有新问题需要我们探索与解决。如，超边的合并与划分还可以进一步优化。因此，该领域的研究还有待进一步发展和完善。
参考文献
[1]张林波.并行计算导论[M].清华大学出版社，2006.
[2]王瑞军.网格计算中任务调度算法的分析和研究[M].北京化工大学，2011.
[3]杜玉霞.Min-min调度算法的研究与改进[J].计算机工程与应用，2010，46（24）：107-109.
[4]罗宇平.基于Min-min改进后的网格调度算法[J].微电子学与计算机，2009，26（3）：86-88.
[5]陈俊.网格环境下工作流任务的调度算法[D].中南大学，2008.
[6]Carter B R.Generational scheduling for dynamic task managent in heterogeneous computingsystems.Joumal of Information Sciences，1998，106（1）：219-236
[7]Wu A S.An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling.IEEE Transactions on Parallel and Distributed Systems，2004，15（9）：824-834.
[8]Ryden N.Fast Simulated Annealing Inversion of Surface Waves on Pavement using Phase-velocity Spectra.Geophysics.2006，71（4）：49-58.
[9]Zhihong Xu.An Algorithm based Task Scheduling in Grid Computing[C].CCECE 2003-Canadian Conf on Electrical and Computer Engineering，Montreal，Canada，2003，2（5）：1107-1110.
[10]C Berge.Graphs and Hypergraphs[M].North Holland，
Amsterdam，1973.
[11]孙雪冬.基于有向超图的工作流资源分配均衡优化方法[J].电子学报，2005，8：1370-1374.
[12]许小满.超图理论及其应用[J].电子学报，1994，8：65-71.
[13]杨博.网格任务调度与优化机制研究[D].中南大学，2008.
【关键词】网格；任务调度；超图
引言
20世纪90年代，网格技术随着计算机网络技术的发展而起源，它是继Internet技术，web技术之后的第三大技术浪潮，它是将世界各个地区的资源进行资源共享，这些资源有硬件资源，也有软件资源，比如：计算机硬件系统，软件系统，专家资源，通信系统，文件系统，共享文档，知识资源等等。通过网格技术，人们可以获得最优的资源分配。网格在不断的发展中，被称为是下一代的网络技术。
在网络环境中，网格资源分布在世界各个角落，如何管理资源，并获得最优的资源，是网格技术中必须要考虑的现实问题，因此资源的分配和任务调度是网格技术中比较重要的环节。
1.任务调度特点和目标
网格任务调度具有面向异构平台、大规模、非集中式、不干涉网格节点内部、可扩展性等特点。异构平台，网格资源种类各异，它们是异构的，可运行在各种操作系统下，因此调度必须面向异构平台；大规模、集中式，网格系统是整个Internet系统，要实现统一管理、集中调度很困难，必须以分布式、并行式管理与调度；不干涉内部节点，网格结点的内部调度是自治的，不同节点有不同的调度策略，也体现了节点的自主性；可扩展性，随着计算机的不断加入，系统的计算规模也随之扩大，在不降低网格系统的性能前提下，网格系统的任务调度必须具有可扩展性。
网格任务调度的最终目标就是要对用户提交的任务实现最优调度，并设法提高网格系统的总体吞吐率。具体的目标包括：最优跨度（Optimal Makespan），服务质量QoS（Quality of Service），负载均衡（Load Balancing），经济原则（Economic Principles）。
（1）最优跨度
跨度是一个最为常见的目标，是指任务调度完成的时间，即从第一个任务调度开始到最后一个任务调度完成所经历的时间，跨度越小，任务调度的时间越小。最优跨度就是最小的任务调度时间。
（2）服务质量
在任务调度的过程中，必须要保障网格相应的服务质量，这样才能确保调度过程顺利有序的进行。
（3）负载均衡
负载均衡是指任务调度到资源上时，确保大多数资源都能被任务所占用，也就是充分利用网格资源，这样才能提高整个网络的整体性能。
（4）经济原则
现实生活中的市场经济原则使消费双方互惠互利，长久发展。在网格环境中，不同资源的使用费用也是不相同的，市场经济驱动的资源管理与任务调度必须使网格资源的提供者和消费者互惠互利，才能使网格系统长久发展下去。
2.任务调度现状
网格计算中任务调度已被证明是完全问题，需要使用启发式方法来获得最优或近优解。我们依据任务间关系，将任务调度分为元任务和依赖任务调度。元任务是指相互独立的任务，彼此之间没有通信要求，依赖任务是指任务之间有制约关系，存在先后依赖关系，即可执行条件制约在前任务执行完毕的情况下。
元任务的经典算法有Min-min算法、Max-min算法、Sufferage算法。这些算法虽然经典，但是也有一定缺陷，因此，在经典算法的基础上提出的新算法也是非常多的。如文献[4]，针对Min-min算法的负载不均衡，提出了改进算法Sect-Min算法，采用“分段”的思想，把任务分成若干小任务，不仅减少了执行时间，提高了资源的有效性，而且负载均衡性得到显著提高。文献[5]提出了一种扩展的QD-Sufferage算法，该算法在Sufferage算法基础上，融入了Qos优先级分组和Deadline约束的思想，相比同类算法有更短的makespan和获得更高的任务接受率。
对于依赖任务大多采用有向无环图（Directed
Acyclic Graph，DAG）来表达任务间的依赖关系。对于依赖任务的调度一种有效常用的方法是将依赖任务分解成独立的元任务，然后进行调度。如GS算法[6]，该算法的思想就是根据DAG节点的优先级，将依赖任务集合转换成若干个内部包含独立任务的任务集合，对于此集合，可以使用Min-min、Max-min、Sufferage等算法进行调度。
目前，随机化搜索算法比如遗传算法[7]、模拟退火算法[8]和蚁群算法[9]等等，通过有导向的随机选择，不断结合先前搜索的结果和特征去寻找问题的解空间，最终生成良好的调度结果，此类方法在复杂的计算系统中有着明显优势。
3.超图理论
20世纪70年代C.Berge在《图与超图》中首次系统地阐述了超图的概念[10]。超图是图论的一个分支，具有图论不具备的性质，它是一种有限集的组合学，研究多元子集问题或者有限集中各元之间的多元关系，描述最具一般性的离散结构关系。
超图（Hypergraph）是二元对，其中表示超图的n个顶点，表示超图的m条超边。超边集E为定义在顶点集V上的子集簇，即，并且满足：
（1）
（2）
超图相对与一般图论而言一个显著的不同是：超边能够表达定点之间更为一般的关系，而一般图只能表示两个顶点之间的关系。
超图分为无向超图和有向超图，无向超图即为上述超图，有向超图是在无向超图中每条超边的基础上添加方向所得。自20世纪60年代以来，经过几十年的发展，无向超图理论已经建立起比较完备的学科体系。虽然有向超图研究的历史并不长，但是基于无向超图的理论，这对于有向超图的研究工作也是非常有益的。
目前，超图已经在数据挖掘、工作流管理、网络综合、电路分析等多方面得到应用，并取得了可观的成绩。文献[11]基于有向超图，提出了一种工作流资源分配均衡优化方法，文献[12]将超图融入电路分析中，对电路的设计分析等有奠基的效果。在网格任务调度方面，超图亦有非常好的发展前景。 4.超图在网格任务调度中的应用
针对网格任务和资源的特点，应用超图理论构建分类模型，这样能对任务和资源进行统一的管理和调度，同时也可对超图模型进行优化，从而降低调度长度。
4.1 超图任务模型
对于以往的任务大多采用有向无环图（Directed Acyclic Graph，DAG）来表达任务间的关系。应用超图来表达，能够更好的反映任务的特点和任务之间的关系，不论在表现形式还是内容上，都进行了扩展和优化，不仅使任务的关系表达更方便直接，而且通过超图进行优化，不但可以简化计算，还能降低时间复杂度，提高调度性能。
超图的任务关系及其矩阵表示：
4.2 超图资源模型
网格环境下的资源数量巨大，具有广域性、动态性、异构性等多种特点，相比传统的分布式系统更加复杂，如果用传统的多处理机系统的调度算法，时间开销大，不能发挥出网格的优势，应用超图理论来构建资源模型，不但能够统一管理，还能在超图的基础上作优化，如超边的合并或分解，来简化任务调度的映射过程，从而降低调度长度。
5.研究展望
任务调度是网格计算的重要组成部分，对于它的研究仍然十分重要。超图理论，在各方面不断发挥新作用，在网格任务调度方面，更是开辟了一条新路径。虽然已取得了些成果[13]，但是还有新问题需要我们探索与解决。如，超边的合并与划分还可以进一步优化。因此，该领域的研究还有待进一步发展和完善。
参考文献
[1]张林波.并行计算导论[M].清华大学出版社，2006.
[2]王瑞军.网格计算中任务调度算法的分析和研究[M].北京化工大学，2011.
[3]杜玉霞.Min-min调度算法的研究与改进[J].计算机工程与应用，2010，46（24）：107-109.
[4]罗宇平.基于Min-min改进后的网格调度算法[J].微电子学与计算机，2009，26（3）：86-88.
[5]陈俊.网格环境下工作流任务的调度算法[D].中南大学，2008.
[6]Carter B R.Generational scheduling for dynamic task managent in heterogeneous computingsystems.Joumal of Information Sciences，1998，106（1）：219-236
[7]Wu A S.An Incremental Genetic Algorithm Approach to Multiprocessor Scheduling.IEEE Transactions on Parallel and Distributed Systems，2004，15（9）：824-834.
[8]Ryden N.Fast Simulated Annealing Inversion of Surface Waves on Pavement using Phase-velocity Spectra.Geophysics.2006，71（4）：49-58.
[9]Zhihong Xu.An Algorithm based Task Scheduling in Grid Computing[C].CCECE 2003-Canadian Conf on Electrical and Computer Engineering，Montreal，Canada，2003，2（5）：1107-1110.
[10]C Berge.Graphs and Hypergraphs[M].North Holland，
Amsterdam，1973.
[11]孙雪冬.基于有向超图的工作流资源分配均衡优化方法[J].电子学报，2005，8：1370-1374.
[12]许小满.超图理论及其应用[J].电子学报，1994，8：65-71.
[13]杨博.网格任务调度与优化机制研究[D].中南大学，2008.