关键字 |
| 网格调度器，Makespan, Flowtime，延迟，NP-Complete。 |
介绍 |
| “网格”是不同机器的集合，其中所有机器都将资源组合作为一个完整的单元。网格计算的基本目标是创建一个大型而强大的虚拟计算机的幻觉，该虚拟计算机是异构系统的集合。“网格”计算关注的是对我们来说是虚拟的大规模资源的共享。与高端计算系统[1]相反，在网格中连接的系统可以是便宜的，并且位于世界各地。它允许应用程序在另一台机器上运行，而该机器现有的机器可能很忙。 |
| 网格调度是负责将用户作业分配到可用的网格资源上的过程。这个过程的目标是最大化各种优化标准，如机器使用率、公平性或保证服务质量。调度过程应该灵活而快速，以便能够有效地对Grid环境中的动态变化(作业到达、失败、不精确的作业运行时估计等)作出反应。 |
| 网格环境下的有效调度是当今生产系统中尚未完全有效解决的复杂问题。最优解的寻找是一个NP完全问题，它实际上是难以解决的大型作业集。调度器在网格环境中的基本工作是自动选择合适的机器来执行网格系统发送的特定任务。例如Nimrod-G Grid Resource Broker, AppleS, STORM, Silver Meta scheduler, ST-ORM, CONDOR-G。 |
| 本文采用最小-最小、最大-最小、最小完成时间(MCT)和最小执行时间(MET)四种调度算法求解网格环境下的调度问题，并对最大完工时间(makespan)、流量时间(flowtime)和延迟(delay)等优化准则进行了评价。调度的最终目标是实现最大的资源利用率。 |
| 本文的其余部分组织如下。第二节讨论了其他研究者在网格调度问题上所做的相关工作。第三节给出了问题的陈述。第四节简要介绍了四种静态网格调度算法。第五节概述了我们的实验研究结果，最后在第六节给出了本文的结论。 |
相关工作 |
| 作业的最优资源选择问题是一个np完全问题。由于完全搜索往往会失败，因此进行了广泛的研究，并在文献[2][3][4]中提出和研究了许多算法。它们可以大致分为两类，即决定论和元启发式。确定性算法包括Min-Min、Max-Min、Suffrage等。 |
| 在论文[5]中，作者提出了一种新的调度算法RASA。本文利用MINMIN算法和MAX-MIN算法的优点，并尽量避免它们的缺点。算法在资源Rj上构建一个矩阵C, Cij表示任务Ti的完成时间。如果可用资源数为奇数，则采用Min-min策略分配第一个任务，否则采用Max-min策略。其余任务由两种策略中的一种分配到相应的资源。Min-min和Max-min算法适用于小型分布式系统。而RASA可以应用于大规模的分布式系统。 |
| 元启发式算法类包括禁忌搜索[6]，蚂蚁算法[7]，粒子群优化[8]，模拟退火[9]，遗传算法[10]和智能水滴算法[11]。这些本质上是随机的。 |
| 最初，算法的元启发式类随机生成潜在解决方案的总体。在随后的迭代中，执行某些预定义的操作，以寻找最优或接近最优的解决方案。当解满足适应度准则时，算法终止。适应度准则用于评估候选解。 |
问题陈述 |
| 假设网格环境中有n个作业和m个资源。那么我们的任务调度挑战就是找到最好或最优的资源。评估网格调度器性能的主要目标函数是Makespan, Flowtime和Tardiness[13]。“Makespan”为第一个任务开始时间与最后一个任务结束时间的时间差。我们也可以将其视为周转时间，即提交第一个任务和完成最后一个任务之间的时间间隔。实际上，最大完工时间(Makespan)是衡量异构计算系统吞吐量的指标。 |
| 设任务集T = t1, t2, t3，…，tn为提交给调度器的任务组，设资源集R = r1, r2, r3，…，rm为任务到达时可用的资源集，任意算法对调度产生的makespan可计算如下: |
| (1) makespan = max(CT (ti, rj)) |
| 2) CTij = RTj+ETij |
| 其中CTij为任务i在资源j上的完成时间，ETij为任务i在资源j上的预期执行时间，RTj为资源j的就绪时间或可用时间;机器rj完成之前分配的所有任务执行的时间。 |
| 流动时间(Fi)也被称为循环时间。这是一个人在车间工作的时间。是作业ti的释放时间rei(作业被释放到作业车间的时间)与作业ti的完成时间Ci之间的时间间隔: |
| (3) Fi = Ci - rei |
| 拖延时间:(Ti) -工作的拖延时间Ti是指完成时间超过到期日di的非负时间量。每项工作的完成时间和到期日之间的差异。 |
| (4) Ti = max [0， (Ci - di)] |
| 一个特定问题的资源利用率是用公式计算的， |
 |
在哪里 |
| 任务完成时间 |
| ruj=资源j的资源利用率 |
| tei =任务i的结束时间 |
| tsi =任务i的开始时间 |
| TQRU =使用的资源总量 |
 |
网格调度算法 |
| 网格调度算法主要分为批处理模式或离线模式和即时模式或在线模式。在批处理模式下，任务被分组在元任务(MT)中，然后批处理被安排在一些预定义的时间，称为映射事件，而在立即模式下，任务一到达系统就被映射。Min- Min, Max-Min算法是批处理模式映射的例子，而最小执行时间(MET)和最小完成时间(MCT)是立即模式映射的例子。 |
| A. Min-Min调度算法 |
| Min-Min算法的任务调度分为两个阶段。在第一阶段，它首先为给定资源的所有任务找到最短完成时间集。第二阶段包括从第一阶段创建的最小任务集中选择最小值，并将所选的最小任务分配给预期资源。重复这些步骤，直到所有任务都映射到资源。最小-最小调度算法的局限性之一是负载不平衡。该算法的时间复杂度为O(RT2)时间。 |
| B.最大最小调度算法 |
| Max-Min算法类似于Min-Min算法。它也有两个任务调度阶段。在第一阶段，它首先为给定资源的所有任务找到最短完成时间集。第二阶段涉及从第一阶段为给定资源计算的最小任务集中选择最大完成时间值。重复这些步骤，直到所有任务都映射到资源。该算法的复杂度为O(RT2)时间。 |
| C.最短执行时间 |
| 该算法查找执行时间最短的任务，并根据先到先得的原则将任务分配给资源。该算法的主要缺点之一是负载不平衡。它不考虑资源的可用性及其负载。将给定的作业映射到预期的机器需要O(R)时间。 |
| D.最短完工时间 |
| 该算法为特定任务寻找具有最小完成时间的机器。它根据完成时间将任务分配给资源。完成时间是通过将资源的执行时间和准备时间相加来计算的。将给定的作业映射到预期的资源需要O(R)时间。 |
结果与讨论 |
| 为了分析这四种调度算法，我们考虑有两个资源R1和R2的问题，任务组Ti由五个任务T1, T2, T3, T4和T5组成。表1给出了任务的执行时间和到期时间。针对上述给定矩阵，采用Min-Min、Max-Min、MET、MCT算法计算了作业的完工时间、流动时间和延迟率。表2给出了各自算法的计算值。 |
| 图1、图2、图3分别是Min-Min、Max-Min、MET和MCT基于Makespan、Flowtime和Tardiness的性能分析。 |
| 与“最小执行时间算法”相比，“最小完成时间算法”使最大完成时间最小。在重任务较多、轻任务较少的情况下，Min-Min算法的性能更好。此外，Max-Min在重任务较少、轻任务较多的情况下表现更好。 |
| 最大最小算法对目标的最大完工时间和流动时间都有较好的效果，但对延迟性目标的优化得到了最大化。 |
结论 |
| 为了实现网格异构环境下的高吞吐量计算，需要一种高效的网格调度算法，为用户提交给网格的作业找到最优的资源。本文研究了四种这样的常规调度算法。本文试图识别他们的表现。本研究仅集中在完工时间，流动时间和延迟。许多问题仍然悬而未决。我们没有考虑到每个任务的截止日期、每个资源的执行成本、沟通成本和许多其他可以成为研究主题的情况。最后，我们可以将这些算法与新的调度启发式算法混合在实际环境中进行实际评估。 |
表格一览 |
 |
|
| 表1 |
表2 |
|
数字一览 |
|
|
参考文献 |
- Foster和Kesselman.C，“网格2:新计算基础设施的蓝图”，Morgan Kaufmann，美国，2003年。
- HesamIzakian, Ajith Abraham, VáclavSnášel，“在异构分布式环境中调度独立任务的启发式比较”，第1卷，pp.8-12, 2009年国际计算科学与优化联合会议，2009。
- T. D. Braun, H. J. Siegel, N. Beck, L. L. Boloni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen和R. F.Freund，“将一类独立任务映射到异构分布式计算系统的11种静态启发式的比较”，《并行与分布式计算杂志》，第61卷，第6期，810-837页，2001年6月。
- Thilagavathi, D.和Antony SelvadossThanamani。“基于启发式算法的网格环境下动态作业调度研究”，《计算机工程学报》，第3卷，第4期，pp.531-536, 2012。
- Ajith Abraham, Liu Hongbo, Zhang Weishi和tai - gyu Chang，“模糊粒子swarmalg算法在计算网格上调度作业”，KES2006第十届基于知识的智能信息与工程系统国际会议，伯恩茅斯国际会议中心，pp.500-507, 2006年10月。
- M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen和R. F. Freund，“异构计算系统上一类独立任务的动态匹配和调度，第8届异构计算研讨会，第30-44页，2001年4月。
- 张瑞生，张俊生，林培生，“基于蚁群算法的网格平衡作业调度”，《计算机工程学报》，Vol.25, pp.20-27, 2009年1月。
- SaeedParsa, Reza Entezari-Maleki, RASA:一种新的网格任务调度算法，国际数字内容技术及其应用杂志第3卷，第4期，2009年12月。
- G. Attiya和Y. Hamam。“分布式系统可靠性最大化的任务分配:一种模拟退火方法”，《并行与分布式计算》，2006年第66期，第1259 - 1266页。
- 高勇，荣宏，黄建忠，“基于遗传算法的自适应网格作业调度”，未来计算机系统，vol.21,pp。2005年1月151-161号。
- Thilagavathi, D.和Antony SelvadossThanamani。“基于萤火虫算法和智能水滴算法的高性能计算环境调度”国际工程趋势与技术杂志(IJETT) 2014年8月第14卷第1期
- Mohd KamirYusof和MuhamadAzaharStapa，利用gridsim仿真工具实现网格计算调度技术中的禁忌搜索算法:有限资源下的多任务，国际网格与分布式计算杂志第3卷第4期，2010年12月。
- Thilagavathi, D.和Antony SelvadossThanamani。“网格计算环境中调度问题性能度量的一个印象”。国际计算机应用与机器人研究杂志ISSN 2320-7345。第二卷，第8期，页40-45,2014年8月。
|
菜单
