下载文档原格式
分布式计算系统中的任务调度优化算法一、引言随着互联网技术不断发展，分布式计算成为了大规模计算的主流方式。
分布式计算系统的优点在于它能够将计算任务分散到多个节点进行计算，多节点协同工作，从而实现计算任务的快速完成。
然而，分布式计算系统中的任务调度问题却是一个极其大的挑战，合理的任务调度能够使分布式计算系统的性能得以优化，进而提升分布式计算的效率。
二、分布式计算系统的任务调度问题在分布式计算系统中，任务调度因素直接影响分布式计算系统的运行效率。
任务调度质量的高低直接关系着分布式计算系统整体性能，同时也影响着计算任务和计算节点的负载均衡。
优秀的任务调度算法可以有效提高分布式计算系统的效率，并且减少任务执行所需的时间。
任务调度问题所涉及的计算模型可归纳为状态映射、执行模式以及资源管理。
三、分布式计算系统中的任务调度算法3.1.基于遗传算法的任务调度优化算法遗传算法是一种基于自我适应的优化算法，该算法的基本思想来自于生物学中基因遗传和进化的过程。
利用遗传算法对任务进行调度是一种有效的方式。
遗传算法可以形成一个任务调度优化模型，该模型中涉及两个基因，一个代表任务的处理节点，另一个代表任务的处理时间。
通过使用遗传算法对任务分配进行优化，从而实现了任务分配的最优解。
3.2.基于贪心算法的任务调度优化算法贪心算法是一种求解问题的方法，在这个算法中，每一次决策只考虑当前状态能够得到的最优解，而不考虑全局最优解。
该算法简单且高效，并且能够在短时间内完成任务调度。
贪心算法通过调整节点的优先级，使得任务调度时尽可能避免出现负载不均衡的情况。
3.3.基于模拟退火的任务调度优化算法模拟退火算法是一种求解优化问题的方法，它采用模拟物理退火的过程进行问题求解。
相比于其他优化算法，模拟退火算法在处理任务调度问题时具有广泛的适用性，它能够在最短的时间内得到全局最优解，同时也能够保证计算节点的负载均衡。
在实际应用中，模拟退火算法可以通过设置初始温度和温度下降规律等参数进行优化。
分布式计算中的任务调度优化研究一、引言随着计算机技术的不断发展，分布式计算已经成为了一种常见的计算模式，其可以将一个比较大的计算任务分解成若干个子任务，将这些子任务分别分配到不同的计算节点上进行计算。
分布式计算的优点是可以利用各个计算节点的计算能力，快速的完成大规模计算任务。
但是，分布式计算中任务调度的优化问题一直是一个难以解决的问题，这是因为任务调度的效率直接影响到整个计算任务的完成时间和计算结果的可靠性。
本文主要介绍分布式计算中任务调度优化的相关问题，并提出一些常用的优化策略。
二、分布式计算中任务调度的基本原理在分布式计算中，任务调度指的是将整个计算任务分解成若干个子任务，并将这些子任务分配到各个计算节点上进行计算。
任务调度的主要目的是提高整个计算任务的执行效率，同时通过任务的并行计算能够减少整个计算任务的完成时间。
任务调度通常需要解决的问题包括：任务拆分的粒度、任务的分配策略、任务的调度策略等。
任务拆分的粒度任务拆分的粒度即将整个计算任务拆分成多少个子任务，这需要根据任务的性质和计算资源的分布情况来进行决定。
一般情况下，任务拆分的粒度越小，任务的并行度越高，整个计算任务的执行效率也会越高。
但是，任务拆分的过程也会带来一些额外的开销，因此需要在拆分粒度和并行度之间进行权衡。
任务的分配策略任务的分配策略指的是将拆分出来的子任务分配到各个计算节点上的具体规则。
任务分配策略需要考虑到每个计算节点的计算能力、网络带宽、负载状况等因素。
一般而言，任务分配策略可以采用基于负载均衡的算法来进行，以使各个节点的计算任务尽可能平均。
任务调度策略任务调度策略是指按照任务执行时间和系统开销的考虑规定任务执行的先后顺序。
任务调度策略的核心问题在于如何选取合适的调度算法，这需要考虑到任务执行的时间、计算任务的复杂度、带宽等因素。
一般情况下，任务调度策略需要采用基于启发式算法的方式进行，以尽可能减少整个计算任务的执行时间。
探讨分布式计算下的任务调度算法随着云计算的普及和大数据的发展，分布式计算成为了当前互联网行业的主流发展方向。
在分布式计算的应用中，任务调度算法是其中最重要的一环，其负责将任务分派到可用的计算资源上，保证集群的利用率并缩短任务执行时间。
本文将从分布式计算的基本原理、任务调度算法的分类和分析两个方面分别探讨分布式计算下的任务调度算法。
一、分布式计算的基本原理分布式计算是指在多个计算机之间协同工作，实现共享计算资源，共同完成一个大规模的计算任务。
分布式计算通常包括以下三个要素：1.节点管理：分布式计算节点的数量较多，难以手动管理。
因此需要一套节点管理系统，负责协调各个节点之间的任务分配和数据传输，保障任务执行的正确性和效率。
2.数据管理：在分布式计算任务中，涉及到的数据通常较大。
因此需要一套数据管理系统，负责将数据分发到各个节点上，协调数据的读写，保障数据的一致性和完整性。
3.任务调度：任务调度是分布式计算中的核心问题。
它需要根据任务的性质、节点的负载和网络带宽等因素，动态地将任务分配到可用的计算资源上，以实现任务的高效执行。
二、任务调度算法的分类任务调度算法可以按照不同的分类方式进行划分，下面介绍两种常见的划分方式：1.作业调度与进程调度作业调度通常是指系统里同时存在多个需要执行的任务，如批处理作业、即时任务等，作业调度需要决定这些任务的执行顺序和执行时间。
进程调度通常是指系统里同时存在多个进程需要执行，进程调度需要决定哪个进程应该在哪个时间片内执行，并且如何分配资源。
2.静态调度与动态调度静态调度是指在任务开始之前，就根据任务的性质和不同节点的特点，通过预先设置参数进行调度决策。
动态调度是指在任务开始之后，根据实际情况对任务进行调度决策。
三、任务调度算法的分析对于分布式计算下的任务调度算法，我们除了要满足任务调度算法的基本需求外，还要关注一些特定的问题。
下面介绍一些问题及对应的算法：1.负载均衡问题负载均衡即将任务平均地分配到各个节点上，避免节点出现过载，从而提高集群的利用率。
分布式计算中的任务调度算法研究与优化近年来，随着互联网及人工智能等领域的飞速发展，分布式计算在其中起到了至关重要的作用。
对于分布式计算来说，任务调度算法是其核心之一，它是负责将任务分配给各个节点执行并监控整个任务执行过程的关键。
本文将对分布式计算中的任务调度算法进行详细的研究与优化。
一、任务调度算法的分类在分布式计算中，根据任务执行的形式和特点，我们可以将任务调度算法分为静态任务调度算法和动态任务调度算法。
静态任务调度算法指的是将任务预先安排给各个节点，固定不变，不会进行调整。
静态任务调度算法的优点是容易实现，不需要进行更多的资源分配，但是缺点也很明显，无法满足实时的任务变化，导致整个系统的效率较低。
动态任务调度算法则是根据实时变化的任务情况以及节点的负载情况，对任务进行决策和调度。
相比于静态任务调度算法，动态任务调度算法可以更加灵活地适应任务的变化，提高系统的效率。
当前的研究重点主要是针对动态任务调度算法的优化与研究。
二、任务调度算法的优化优化任务调度算法的一个重要目标是减少整个任务调度所耗费的时间。
因此，对于任务调度算法的优化，我们可以从以下几个方面进行思考和研究。
1. 负载均衡在任务调度过程中，负载均衡是非常关键的一点，它可以将任务均匀分配给各个节点，减少某些节点负载过重的情况，从而提高任务的执行效率。
在实现负载均衡的过程中，我们可以引入负载均衡算法。
常用的负载均衡算法包括随机算法、轮询算法、加权算法等。
在选择负载均衡算法的时候，需要根据实际情况进行权衡和选择，以达到最优的任务调度效果。
2. 任务优先级算法在实际的任务调度过程中，有些任务比其他任务更为重要，因此，我们需要根据任务的特点和优先级，对任务进行优先级调度。
在实现任务优先级调度的过程中，我们可以引入任务优先级算法。
常用的任务优先级算法包括静态优先级算法、动态优先级算法等。
在选择任务优先级算法的时候，同样需要根据实际情况进行权衡和选择。
分布式系统中的任务调度问题研究正文：一、前言随着互联网的发展，大数据、人工智能等新兴技术的出现，分布式系统已成为信息科学领域的研究热点。
分布式系统是由多个独立计算机组成的系统，这些计算机之间通过网络连接互相通信和协作。
分布式系统的优点是可以充分利用多台计算机的资源，提高系统的可靠性和性能。
但是，分布式系统中任务调度问题是一个非常复杂的问题，如何有效地将任务分配到各个计算机上，是一个值得研究的问题。
二、任务调度问题的定义任务调度问题指的是如何将任务分配到各个计算机节点上，使得所有计算机的负载达到平衡，并且在不同计算机之间进行任务的协作和调度，以实现系统的高效运行。
三、任务调度问题的挑战任务调度问题在分布式系统中具有以下挑战：1. 负载均衡问题在分布式系统中，计算机节点的性能和负载不同，因此任务的分配需要考虑到负载均衡问题，使得所有计算机节点的负载达到平衡状态。
2. 任务数据的传输问题在分布式系统中，不同计算机节点之间需要传输任务数据，因此需要考虑数据传输的带宽和网络延迟等因素。
3. 节点故障问题在分布式系统中，节点故障是不可避免的，因此需要考虑任务调度中的容错性问题，即当某个节点故障时如何重新分配任务。
4. 调度算法问题任务调度算法需要考虑多方面的因素，如任务的类型、计算机节点的性能、负载均衡等问题，因此需要采用高效的调度算法。
四、任务调度问题的解决方案针对以上挑战，我们可以采用以下几种解决方案：1. 负载均衡算法为了解决负载均衡问题，可以采用动态负载均衡算法，该算法可以根据计算机节点的负载情况动态调整任务分配策略，保证各个节点负载均衡。
2. 数据传输优化为了解决数据传输问题，可以采用优化传输算法，该算法可以根据网络带宽和延迟等因素调整数据传输的策略，保证数据传输的高效性。
3. 容错性设计为了保证系统的容错性，可以采用容错性设计，即当某个节点出现故障时，系统可以根据备用节点重新分配任务，保证系统的正常运行。
分布式计算中的任务调度算法研究与优化一、引言随着云计算和大数据时代的到来，分布式计算作为一种重要的计算模式得到了广泛的应用。
在分布式计算中，任务调度算法对于提高系统性能和资源利用率起着至关重要的作用。
本文将介绍分布式计算中的任务调度算法的研究现状，并提出一些优化思路。
二、任务调度算法的研究现状任务调度算法是指根据任务的特征和系统的状态，合理地分配资源并安排任务的执行顺序。
在分布式计算中，主要有以下几种任务调度算法：1.静态调度算法：在任务执行前就确定整个执行过程。
这种算法的优点是对系统的压力小，调度精确，适用于任务执行时间可预测且系统负载较低的情况。
缺点是对于系统负载变化频繁或任务执行时间不可预测的情况效果不佳。
2.动态调度算法：根据系统的状态和负载动态地调整任务的执行顺序。
这种算法的优点是能够适应系统负载变化的情况，提高资源利用率。
缺点是调度过程相对复杂，调度效果依赖于系统状态的监测和预测。
3.启发式调度算法：基于启发式规则对任务进行调度。
这种算法的优点是调度过程简单，调度效果稳定。
缺点是无法适应动态变化的系统负载。
三、任务调度算法的优化思路针对上述算法的不足之处，可以从以下几个方面进行优化：1.任务执行时间预测：提高对任务执行时间的预测准确性，可以更好地确定任务调度的顺序。
可以通过历史数据分析、机器学习等方法来建立任务执行时间的模型，并根据实际情况进行调整和优化。
2.资源动态调整：对系统的负载进行实时监测，并根据监测结果对资源进行动态调整。
例如，当系统负载较低时，可以选择将任务调度到负载较重的机器上执行，以提高资源利用率；当系统负载较高时，可以选择将任务调度到负载较轻的机器上执行，以均衡负载。
3.智能调度算法：结合机器学习、优化算法等方法，开发智能调度算法，以适应动态变化的系统负载。
这种算法可以根据系统的特点和任务的需求进行自适应调整，以提高任务执行效率和系统性能。
四、结论任务调度算法是分布式计算中的关键问题之一，对于提高系统性能和资源利用率具有重要意义。
解决分布式计算中的任务调度和负载均衡问题随着互联网和大数据的快速发展，分布式计算技术成为了处理海量数据、提高计算效率的重要工具。
分布式计算是一种将计算任务分配到多台计算机上并行执行的技术，能够充分利用计算资源，提高计算效率。
在分布式计算中，任务调度和负载均衡是两个重要问题，它们直接影响着整个系统的性能和稳定性。
本文将对分布式计算中的任务调度和负载均衡问题进行分析，并提出解决方案。
一、任务调度问题在分布式计算系统中，任务调度是指将计算任务分配到不同的计算节点上执行的过程。
任务调度的目标是尽可能地减少任务的执行时间，提高系统的整体性能。
任务调度中存在的问题主要包括任务调度算法的选择、任务执行节点的选择、任务执行顺序的确定等。
1.1任务调度算法的选择任务调度算法的选择直接影响着系统的性能和稳定性。
常见的任务调度算法有先来先服务（FCFS）、最短作业优先（SJF）、最高响应比优先（HRRN）、最短剩余时间优先（SRTF）、优先级调度等。
不同的调度算法适用于不同的场景，需要根据实际情况选择合适的调度算法。
1.2任务执行节点的选择任务执行节点的选择是任务调度的关键环节。
在分布式计算系统中，通常会有多个计算节点可供选择，需要根据系统的负载情况和节点的性能特点来选择合适的执行节点。
通常可以采用负载均衡算法来选择执行节点，使得各个节点的负载尽量均衡。
1.3任务执行顺序的确定在分布式计算系统中，存在着大量的并行计算任务，这些任务之间可能存在依赖关系，需要确定合适的执行顺序。
通常可以采用拓扑排序、关键路径等算法来确定任务的执行顺序，以保证任务能够顺利执行并满足依赖关系。
二、负载均衡问题在分布式计算系统中，负载均衡是指将计算任务合理地分配到各个计算节点上，使得各个节点的负载尽量均衡，系统的整体性能得到提高。
负载均衡问题涉及到节点负载的监测、负载均衡算法的选择等方面。
2.1负载均衡算法的选择负载均衡算法的选择直接影响着系统的整体性能。
分布式计算环境中的任务调度与优化研究随着计算和数据的规模不断增长，分布式计算环境（Distributed Computing Environment）已成为处理大规模计算任务的重要手段。
在分布式计算环境中，任务调度和优化是关键问题之一，直接影响着任务的执行效率和整体系统性能。
任务调度是指将任务分配给合适的计算节点的过程，以最大化任务完成率、最小化任务执行时间和最大程度地平衡计算资源的利用率。
在分布式计算环境中，任务通常由多个子任务组成，每个子任务可以由不同的计算节点执行，而任务调度是将这些子任务合理分配给可用计算节点的关键过程。
为了提高任务调度的效率和性能，研究人员提出了多种任务调度和优化策略。
以下将介绍其中几种常用的策略：1. 静态负载平衡算法：静态负载平衡算法根据计算节点之间的负载情况作出任务调度决策，以实现任务在各个计算节点之间的均衡分配。
最简单的静态负载平衡算法是将任务按照任务量的大小分配给计算节点，即任务量越大的任务分配给性能较强的计算节点。
然而，静态负载平衡算法通常无法应对任务量和节点资源动态变化的情况，因此需要结合动态负载平衡算法进行优化。
2. 动态负载平衡算法：动态负载平衡算法根据任务的执行进度和计算节点的负载情况实时调整任务的分配策略。
这些算法通常采用启发式算法、遗传算法或模拟退火算法来寻找最优的任务分配方案。
此外，一些算法还考虑了通信开销和数据传输速度等因素，以进一步优化任务调度效果。
3. 任务优先级调度算法：任务优先级调度算法根据任务的重要性和紧急程度来确定任务的执行顺序和分配策略。
这些算法通常基于任务的特定需求和约束，如任务截止日期、资源需求和计算节点的可用性等。
通过合理设置任务的优先级，并将其与计算节点的负载情况结合起来，可以实现高效的任务调度和优化。
4. 资源感知的任务调度算法：资源感知的任务调度算法通过有效利用分布式计算环境中的各种资源，如计算能力、存储容量和网络带宽等，以最大化系统性能和吞吐量。
分布式计算系统中的任务调度算法分析与改进在分布式计算系统中，任务调度算法扮演着重要的角色。
任务调度算法的性能直接影响着整个系统的效率和吞吐量。
在本文中，我们将对分布式计算系统中的任务调度算法进行分析，并提出改进方案，以进一步提高系统的性能和可靠性。
一、任务调度算法的分析在分布式计算系统中，任务调度算法的主要目标是合理地分配任务到不同的计算节点，以最大化系统的吞吐量或者减少任务完成时间。
下面我们将分析两种常用的任务调度算法：静态调度算法和动态调度算法。
1. 静态调度算法静态调度算法指的是在任务提交之前就对任务进行静态的分配和调度。
常见的静态调度算法有轮转法、最小平均完成时间算法和最小任务完全时间算法。
轮转法是一种简单的静态调度算法，它按照任务的到达顺序将任务分配给计算节点。
这种算法的优点是实现简单，但它没有考虑到节点之间的负载情况，会导致一些节点负载过重，而其他节点处于空闲状态。
最小平均完成时间算法（MAFT）是一种静态调度算法，它优先选择平均完成时间最短的计算节点来执行任务。
这种算法考虑了节点之间的负载情况，但是没有考虑任务的紧急程度和执行时间的波动性。
最小任务完全时间算法（MTFT）是一种静态调度算法，它选择任务完全时间最短的计算节点来执行任务。
该算法综合考虑了负载情况、任务的紧急程度和执行时间的波动性，但是在实际应用中，由于任务的完全时间难以准确估计，该算法不太实用。
2. 动态调度算法动态调度算法指的是在任务执行过程中根据系统实时状态来对任务进行动态的分配和调度。
常见的动态调度算法有最小平均剩余时间算法和最小开销剩余时间算法。
最小平均剩余时间算法（MART）是一种动态调度算法，它每次选择平均剩余时间最短的计算节点来执行任务。
该算法考虑了节点的负载情况和任务的剩余执行时间，能够有效地提高系统的性能。
最小开销剩余时间算法（MOST）是一种动态调度算法，它每次选择开销剩余时间最短的计算节点来执行任务。
分布式计算环境下的任务调度与优化随着计算机技术的不断发展，分布式计算环境已经成为了当今大数据时代中不可或缺的一部分。
在这个环境下，任务调度与优化显得尤为重要。
任务调度是指在分布式计算环境中，将不同的计算任务分配到不同的节点上，使得整个计算能够最高效地完成；而优化则是指在任务调度的基础上，通过各种手段提高计算的效率。
本文将从任务调度和优化两个方面来探讨分布式计算环境下的任务处理问题。
一、任务调度在分布式计算环境中，任务调度是一个非常复杂的问题。
不同的计算任务通常会涉及到不同的计算资源需求，如CPU、内存、网络等，同时还需要考虑节点的负载情况、网络带宽等因素。
因此，如何合理地进行任务分配成为了极其重要的问题。
首先，任务调度需要考虑到节点的负载情况。
由于节点之间的性能及网络带宽存在差异，因此在任务调度时需要考虑到节点的负载情况，避免任务过于集中在某些节点上，造成其他节点的闲置。
这一点可以通过使用负载均衡算法来实现，例如Round Robin等算法。
其次，任务调度还需要根据不同的计算需求进行合理的分配。
在任务调度时，需要根据任务所需的计算资源、数据传输量等因素来决定任务应该分配到的节点。
不同的任务可能有不同的计算资源需求，需要首先进行资源预算，然后再根据任务实际计算所需的资源量进行分配。
最后，任务调度还需要根据节点之间的网络带宽来制定任务调度方案。
在分布式计算环境下，各个节点之间的网络带宽是非常重要的参数。
在任务调度时，需要根据节点之间的带宽限制，将任务分配到合适的节点。
二、任务优化在任务调度的基础上，任务优化可以提高分布式计算的效率。
任务优化的实现方式很多，例如负载均衡算法、数据划分算法、任务合并算法等。
首先，负载均衡算法是一种使用较为广泛的优化方法。
在任务调度时，经常会出现任务过于集中在某些节点上，造成其他节点空闲的情况。
这时候，可以使用负载均衡算法来实现任务的动态分配。
例如Round Robin算法，就是一种简单而有效的负载均衡算法，能够平衡各个节点的负载。
2007年5月系统工程理论与实践第5期 文章编号:100026788(2007)0520119207分布式环境下多任务调度问题的分析与求解何 琨,赵 勇,陈 阳(华中科技大学控制科学与工程系系统工程研究所,武汉430074)摘要: 将约束条件归纳为任务约束、链路约束和资源约束,在允许任务复制的情况下,建立了问题的约束与目标的完整数学模型;提出了一种基于任务复制的模拟人类社会中关系演化过程的簇调度算法IRE A,包括前沿调度、动态分簇和分离图三个子算法.IRE A采用全新的优先级规则,定义了关系数、依赖度、归并度等表示簇的优先级.通过对两个经典算例的计算,发现IRE A能求出比算例所在文献算法所得解更优的解;对M JD算例,还得到了一个不同于原文献所给理论最优格局的一个新的最优格局.关键词: 调度算法;任务复制;有向无回路图;动态分簇;分离图中图分类号: TP301 文献标志码: A Analysis and S olutions for Multitasks Schedulingin Distributed EnvironmentsHE K un,ZHAO Y ong,CHE N Y ang(Institute of Systems Engineering,Department of C ontrol Science and Engineering,Huazhong University of Science and T echnology,Wuhan 430074,China)Abstract: This paper addresses the problem of static scheduling multitasks with precedence constraints representedas directed acyclic graphs for execution on distributed hom ogeneous environments.The problem is strong NP2com plete,and efficient alg orithms for it will have both highly theoretical value and highly practical value.The constraints aresummed up to task constraints,link constraints and res ource constraints.An integrated mathematical m odel withconstraints and objective is set up.And a new heuristic approach named the Interpers onal Relationships Ev olutionAlg orithm(IRE A)that is based on task duplication is proposed.IRE A resembles the ev olution of the interpers onalrelationships within the human s ociety,and includes three com ponents:cutting edge alg orithm,dynamic groupalg orithm and detach graph alg orithm.The priority rules used are new.Relationship number,dependent degree andmerge degree are defined for cluster’s priority.I t is found that IRE A could get better s olutions for tw o classicbenchmarks than the alg orithms which gave the benchmarks.Besides,IRE A gets a different optimal s olution com paredwith the theory optimal one for the M JD benchmark.K ey w ords: scheduling alg orithm;task duplication;directed acyclic graph;dymanic clustering;detach graph1 引言分布式环境下的任务调度问题是调度理论中的经典问题,包括资源匹配(matchmaking)和任务调度(scheduling)两部分,资源匹配解决在哪里执行任务,即匹配应用需求和可用资源;任务调度解决何时执行任务,即给出应用占用资源的起止时间[1].分布式环境下的任务调度,研究内容分为调度相互独立的任务和调度相互依赖的任务两类,对相互独立的任务一般采用动态调度,对相互依赖的任务一般采用静态调度.为充分利用分布式环境的并行处理与协作能力,往往根据数据依赖关系和计算要求,将应用分解为相互依赖的多个任务,采用有向无回路图(Directed Acyclic G raph,DAG)进行描述.分布式环境下相互依赖多任务的调度问题是强NP完全的,其近似算法的求解非常困难[2].目前的求收稿日期:2005205209资助项目:国家自然科学基金(70471077,60673057);高等学校博士学科点专项基金(20020487046) 作者简介:何琨,女,博士,研究方向为分布式计算、决策分析、复杂系统建模与优化;赵勇,男,博士,教授,博士生导师,研究方向为决策分析、复杂系统建模与优化;陈阳,男,博士,讲师,研究方向为决策分析、复杂系统建模与优化.解方法有基于表的算法[3]、基于簇的算法[4,5]、基于复制的算法[4,6]、遗传算法[7]、模拟退火算法[8]等.基于簇的调度方法,主要有关键路径分析、优先级列表调度和图分解技术[4].同样的调度机制,基于任务复制的(T ask Duplication Based,T DB)算法调度结果一般要优于任务不被复制的算法,T DB算法的理论基础是采用以空间换时间的策略,通过冗余地分配任务到多个资源以减少通信开销,从而减少总的调度长度.对分布式同构环境下的多任务调度问题,本文提出了一个基于任务复制的模拟人类社会中人际关系网演化过程的簇调度算法,包括前沿调度、动态分簇和分离图三个子算法.通过对文献[4]和文献[5]中两个算例的计算,均得到了比原文献算法所得解更优的解,且对M JD算例得到了一个不同于原文献所给理论最优格局的新的最优格局.2 问题描述已知一组有优先关系约束的任务和一组充分多的同构资源(例如一组同构的处理机),求一种调度方案,满足以下约束:1)任务约束:每个任务需要分配到一个资源上执行,任务的执行时间给定且在所有的资源上相同;任务是原子的,其执行过程不可中断.2)链路约束:有优先关系约束的两个任务,只有前一任务完成且生成的数据传输到后一任务所在资源,后一任务才能开始;传输时间仅与两任务间的传输量有关,若两个任务在同一资源上执行则传输延迟为0,否则为一给定的值.3)资源约束:分配到同一资源上的任务,其执行时间不能重叠.要求给出一种调度,即给出:1)资源匹配:每个任务选择的资源;2)任务调度:每个资源上任务的调度顺序和加工时间;使得该任务集的调度目标最优.调度目标一般为使应用的服务质量(Q os)最优,如处理时间、内存占用、通信带宽、截止期、优先级、安全性、费用等最优.本文的目标值为求所有任务总的运行时间(makespan)最短,即使任务集的最早开工时间与最晚完工时间之间的差尽可能的小.这是一个分布式环境下同构资源的多任务调度问题,如分布式内存机器中的多任务调度.问题可形式化地描述为:记加权有向无回路图G(V,E,μ,λ),顶点集V={1,2,…,n}表示包含的任务集(不失一般性,设1和n是“开始”哑元和“结束”哑元任务,加工时间为0);边集E={eij:i,j∈V;i→j}表示任务间的优先关系,E<V×V,一条有向边eij表示任务j必须等待i完成,且计算结果传输给j,j才能开始,称i为j的前驱,j为i的后继;μ={μi:i∈V}表示相应任务的执行时间;λ={λij:(i,j)∈E}表示有优先关系的两任务i、j不在同一资源上执行时的传输延迟.记R={1,2,…,m}(m≥n)为同构的资源集,即资源是无差异的,且数量充分多.设f1:V→R为一个多值映射,要求Πi∈V,一定存在一至多个r∈R与之对应;任务n恰有一个r∈R与之对应.设f2:(E,R)→R为一个单值映射,要求Π(i,j)∈E,Πr′∈f1(j),恰有一个r∈f1(i)与之对应.f1反映了任务到资源的分配关系,f2反映了任务分配到资源后,任务间的优先约束边的分配.令st i(r)表示任务i在资源r上的开工时间,cti(r)表示任务i在资源r上的完工时间.则要求给出f1、f2、资源上任务的执行顺序和sti (r)、cti(r)的值,在满足以下条件的前提下,使得总的完工时间尽可能的小:min ct n(r), r=f1(n),s.t.1)st i(r)≥0,ct i(r)-st i(r)=μi,i∈V,r∈f1(i),2)st j(r′)-st i(r)≥u i+δrr′・λij,r=f2(i,j,r′),δrr′=0,r=r′1,r≠r′,3)st j(r)-st i(r)≥u i∨st i(r)-st j(r)≥u j,i,j∈V,r∈f1(i),r∈f1(j). 这个问题是强NP完全的[5].对该问题,文献[4]给出了一种基于簇的且允许任务复制的算法(简记M JD算法),并给出了一个算例,如图1所示.该算例的最优解为26,采用M JD算法可以解得27,如图2所021系统工程理论与实践2007年5月示.图1 M JD 算例 图2 M JD 调度结果 3 关系演化算法基于对人类社会中人际关系组成的网络的理解与观察,本节提出一种基于贪心分簇的启发式算法———关系演化算法(Interpers onal Relationships Ev olution Alg orithm ,简记IRE A ).IRE A 是一种模拟人类社会的关系演化过程的拟人算法(mimetic alg orithms ),包括前沿调度、动态分簇和分离图三个子算法.设有一群人V ={1,2,…,n }按集团组成一个关系网,每个集团有一至多个人,初始时每个人组成一个集团;然后采用动态分簇算法进行发展,拥有关系最多的集团优先发展其关系网,不断合并与其有关系的且对其依赖程度高的其他集团.对一个集团A ,考虑与其有关系的集团B 对A 的依赖程度,B 与A 的密切程度越大,对A 的依赖程度越高;反之,B 与其他集团的密切程度越大,对A 的依赖程度越低.分离图算法是在动态分簇的基础上对当前关系网进行处理:当和平合并不再起效的情况下,采用较激烈的变革手段,对当前关系网进行改造,对每个较有实力的集团,拆离其他集团中的个体,使该个体同时存在于两个集团中,使之得以发展.关系网络最终发展成为少量的几个有实力的大集团.假设资源数充分多看上去有些不切实际,但随着合并和复制过程,使用的资源数在不断下降.最终得到一个使用少量资源且makespan 较小的调度.311 相关定义对一个DAG 实例,给出以下定义.定义1(簇C r ).为分配到同一资源r 上执行的任务集.簇内任务之间的通信延迟为0,跨簇任务之间的通信延迟为边的权λij .簇C r 的执行时间μ(r )指C r 包含任务的执行时间之和.定义2(任务复制).若同一任务被冗余地分配到多个资源,称为任务的复制.定义3(入度I r ).从其他簇进入簇C r 中任务的边的个数.定义4(出度O r ).从簇C r 中任务出发到其他簇的边的个数.定义5(关系数RN r ).其他簇与簇C r 中任务直接关联的边的个数.RN r =I r +O r .定义6(依赖度D r ′r ).簇C r ′对簇C r 的依赖程度,其值为两个簇间直接关联边的权之和减去簇C r ′与其它簇间直接关联边的权之和.簇C r ′与簇C r 之间的直接关联边越多,通信所需时间越长,对C r 的依赖程度越高;反之,簇C r ′与其他簇之间的直接关联边越多,通信时间越长,对C r 的依赖程度越低.当簇C r ′对其他簇的依赖之和高于对簇C r 的依赖时D r ′r 为负值.D r ′r =∑j ∈C r ′,i ∈C r ,e ji ∈E λji +∑j ∈C r ′,i ∈C r ,e ij ∈E λij -∑i ∈C r ′,m |C r ∨C r ′,e mi ∈E λmi -∑i ∈C r ′,m |C r ∨C r ′,e im ∈E λim . 定义7(归并簇C r ′与C r ).将簇C r ′与簇C r 合为一个新的簇C ′r .121第5期分布式环境下多任务调度问题的分析与求解定义8(归并度M (r )).指簇C r 所归并的任务个数.312 前沿调度算法和初始解前沿调度算法用于任务的资源已经匹配,任务的执行时间和任务间通信延迟确定的情况下的调度,称此问题为P 1.以下给出问题P 1上的一些定义.定义9(格局).某些任务的开始时间已经被指定,其余任务的开始时间尚未被指定,这称为一个格局.定义10(就绪任务).当算法演化到某一格局,若一个任务的所有前驱任务的开工时间与完工时间已经指定,而该任务的开工时间尚未指定,称其为当前格局下的就绪任务.定义11(关键路径).路径长度是指该路径上所有任务结点的计算时间与任务间通讯延迟的总和,关键路径即路径长度最长的路径.定义12(静态级).任务的静态级(static level )是指由该任务至结束任务的关键路径的长度.前沿调度算法采用的是前沿沉底的思想,即每次调度总是选择其前驱均已完成的就绪任务中可能开始时间最早的某个任务在该时间进行调度.最早开始时间相同时,取静态级最高的任务进行调度.生成调度的过程可以用格局演化的方式来说明:①从初始格局出发.在初始格局下,所有任务的开工时间都没有指定;②从旧格局向新格局演化时,先选择一个就绪任务,然后指定这个任务的开始时间.这样一步一步地指定完所有任务的开始时间,最后产生一个调度,从而演化到终止格局.③在终止格局下,所有任务的开始时间都被指定了.定理1 对问题P 1的任意一种解B ,总可以找到一种前沿沉底法的解B ′不比B 差(摆法B ′的终止格局的makespan 不比B 的大).证明 解B 满足链路约束,即一个任务的前驱必在该任务之前调度,而前沿沉底法每次调度的是就绪任务,即其前驱已经被调度完毕的任务,显然,B 的排列是前沿沉底法可以接受的排列.以这个排列来用前沿沉底法,可得到不比B 差的解B ′.下面用数学归纳法证明此排列得到的解B ′中的每个任务都不比解B 差(每个任务i 的开始时间st ′i 不比在解B 中的st i 大,即st ′i ≤st i ):设共有n 个任务,按照B 解的排列依次为g (1),g (2),g (3),…,g (n ),用前沿沉底法按此排列进行调度.对第1个任务g (1),它在DAG 图中没有前驱任务,前沿沉底法放入g (1)时,开始时间为0,因此第一个任务g (1)的开始时间不比它在解B 中的开始时间大,即st ′g (1)≤st g (1).设i ≤k 时,第i 个任务的开始时间不比在解B 中的大,即st ′g (i )≤st g (i ),则i =k +1时,按前沿沉底法加入第i 个任务,即任务g (k +1)时,该任务的位置有三种情况:①开始时间为0:显然任务g (k +1)的开始时间不比在解B 中的大,即st ′g (k +1)≤st g (k +1);②紧跟其前驱的某个任务g (y )(y ≤k )后调度:由于对任意一种解,任务g (k +1)都要在任务g (y )之后,因此st g (k +1)≥st g (y )+μg (y )+λy ,k +1,而解B ′中st ′g (k +1)=st ′g (y )+μg (y )+λy ,k +1,又由假设知st ′g (y )≤st g (y ),所以st ′g (k +1)≤st g (k +1);③紧跟某一已调度的任务g (z )(z ≤k )在同一处理机上调度:即有st ′g (k +1)=st ′g (z )+μg (z ).由排列的规则知道解B 中任务g (k +1)的开始时间比任务g (z )大,又因为任务g (k +1)和任务g (z )要在同一个处理机上调度,由资源执行的串行化,不能出现交叉重叠,所以st g (k +1)≥st g (z )+μg (z ).又由假设知st ′g (z )≤st g (z ),所以st ′g (k +1)≤st g (k +1);综上所述,对各种可能的情况均有st ′g (k +1)≤st g (k +1),i =k +1时命题成立.因此前沿沉底法的解B ′中每个任务i 的开始时间st ′i 不比在解B 中的开始时间st i 大(st ′i ≤st i ).因此原命题成立.证毕.算法1 C UTTI NG E DGE SCHE DU LE (G ):11初始格局:所有任务的开始时间未指定;21循环,从旧格局向新格局演化{31从当前格局下的就绪任务集中,按<最早合法开始时间,静态级,编号>的优先规则选择一个任务221系统工程理论与实践2007年5月i ,最早合法开始时间小的优先选择,最早合法开始时间一样时静态级高的优先选择,静态级一样时编号小的优先选择;41指定被选择任务i 的开始时间为其最早合法开始时间,完成时间为ct i =st i +μi ;51这样一步一步地指定完所有任务的开始时间和完成时间,从而生成一个调度;61}71在终止格局下,所有任务的开始时间和完成时间均被指定了.前沿调度算法是一个按任务的释放时间非降序调度的前沿沉底贪心算法,定理1说明该算法有可能得到问题P 1的最优解.初始时,采取最大化并行的策略,将每个任务分配到不同的资源上,然后用前沿调度算法生成初始解.M JD 算例的初始解的makespan 为52,即图1中关键路径T 2→T 4→T 7→T 9的长度.313 动态分簇算法从初始解出发,利用动态分簇算法动态地寻找拥有关系最多的点,并尝试合并关系网中与之较密切的点,合并到同一个簇的任务间边的权置为0.算法2 DY NAMIC C LUSTERI NG (G ):11依次按簇的关系数、权降序排列簇的优先级,构造簇列表cList ;21循环,while (cList 不空){31从cList 中移出第一个簇C r ;41循环,对C r 中的每个任务i ,考虑其每个前驱和后继j {51若含j 的簇C r ′,不是簇C r ,且依赖度D r ’r >0{61若合并簇C r ′到C r ,用前沿调度得到的新的makespan 不大于原来的,71则合并簇C r ′到C r ,跳出循环,返回1.81}91}101}111return G .图3 M JD 算例的动态分簇结果图3为采用动态分簇算法对M JD 算例的执行结果,每个簇对应图中的一个结点.314 分离图算法当动态分簇达到一个局部最优解后,再利用允许任务复制的分离图算法,对当前网络图进行改造.算法3 DET ACH G RAPH (G )11初始化:k =0;<(G )为空;21依次按簇的归并度降序和权升序排列簇的优先级,构造簇列表cList ;31循环,直到G 中没有点和边,或剩余的边已被标识{41从cList 中移出第一个簇C r ;51将C r 移入图G k ,并将C r 中的任务按拓朴逆序加入任务列表tList ;61循环,while (tList 不空){71从tList 中移出第一个任务i ;81若有从G 到i 的边j →i ,且以下操作不会导致前沿调度的maekspan 增加,则{91若j 有到G k 外的其他点的边,则101若j 在G k 中无对应点j ′,则复制点j 得到j ′,在G k 中加入点j ′;111将边j →i 删除,在G k 中加入边j ′→i ,并对所有到j 的边k →j ,复制边k →j ′.点j ′加入tList ;121否则321第5期分布式环境下多任务调度问题的分析与求解131将点j 和边j →i 移入G k .141点j 加入tList.151}161若有从其它{G r:r ≠k }到G k 的边,则标记此边.171}181G k 加入分离图集<(G ),k =k +1;191}201return 分离图集<(G ).其中参数G 包含动态分簇后的簇信息.图4左图为采用算法DET ACH G RAPH 对M JD 算例的第一个簇T 4+T 7+T 9进行操作后得到的分离图G 1;图4右为分离T 4+T 7+T 9后的图G .图5左为对M JD 算例的第二个簇T 3+T 8进行操作后得到的分离图G 2;图5右为分离T 3+T 8后的图G ,易知该图也是T 5+T 10的分离图G 3.图4 T 4+T 7+T 9的分离图和分离后的G 图5 T 3+T 8的分离图和分离后的G 如此得到若干分离图,每个分离图作为一个簇,分离图间由跨簇的边相连.图6为对<(G )进行前沿调度的结果,其中st i 表示任务i 的开始时间,使用了三个资源R 1、R 2、R 3.图6 对<(G )的前沿调度结果 图7 文献3给出的理论最优调度 4 实验结果与讨论本文提出了一种基于关系演化的多任务调度算法IRE A.对M JD 算例,采用IRE A 能求出最优解,优于M JD 调度得到的结果,且使用的处理机个数少于M JD 调度使用的处理机个数.而且该格局不同于文献[3]给出的理论最优格局(图7).用IRE A 算法求解另一个经典算例EZ [5](图8左).该算例的最优解为815[5],采用经典簇调度算法EZ(Edge Z eroing )算法[5]求出的makespan 为10,IRE A 算法求出的makespan 为9,如图8右所示,使用了两个资源(处理机).421系统工程理论与实践2007年5月图8 EZ 算例和IRE A 调度结果表1 算法的优度比较算例算法调度结果处理机个数M JD(图1)EZ (图8左)最优化263EZ 316M JD275IRE A263最优化8.53EZ102M JD12.54IRE A 92 用EZ 算法求解M JD 算例,用M JD 算法求解EZ 算例,求解的结果均不如原算例所在文献的算法计算的结果.三个算法的优度比较如表1所示,可见IRE A 在求解这两个算例时要优于M JD 算法和EZ 算法.参考文献:[1] Jarek N ,Jennifer M S ,Jan W ,et al.G rid Res ource Management 2S tate of the Art and Future T rends [M].N orwell ,M A ,US A :K luwer Academic Publishers ,2004.[2] 何琨,赵勇.网格环境下资源调度问题的统一建模与分析[J ].华中科技大学学报(自然科学版),2006,34(3):35-38.He K,Zhao Y.M odeling and analyzing res ource schedules in grid environments [J ].Journal of Huazhong University of Science and T echnology (Nature Science Edition ),2006,34(3):35-38.[3] Alhusaini A H ,Prasanna V K,Raghavendra C S.Unified res ource scheduling framew ork for heterogeneous com puting environments[C]ΠΠProc HCW ’99,8th Heterogeneous C om puting W orkshop.San Juan ,Puerto Rico :IEEE C om puter S ociety Press ,1999.156-165.[4] Palis M A ,Liou J C ,Wei D S L.T ask clustering and scheduling for distributed mem ory parallel architectures [J ].IEEE T rans onParallel and Distributed Systems ,1996,7(1):46-55.[5] Sarkar V.Partitioning and Scheduling Parallel Programs for Multiprocess ors [M].Cambridge ,M A ,US A :MIT Press ,1989.[6] Park C I ,Choe T Y.An optimal scheduling alg orithm based on task duplication[C]ΠΠProceedings of 8th International C on ference onParallel and Distributed Systems (ICPADS ).K y ong Ju City ,K orea :IEEE C om puter S ociety Press ,2001.9-14.[7] Wang L ,S iegel H J ,R oyehowdhury V P ,et al.T ask matching and scheduling in heterogeneous com puting environments using agenetic 2alg orithm 2based approach [J ].Journal of Parallel and Distributed C om puting ,1997,47(1):8-22.[8] Shroff P ,Wats on D W ,Flann N S ,et al.G enetic simulated annealing for scheduling data 2dependent tasks in heterogeneousenvironment [C]ΠΠ5th Heterogeneous C om puting W orkshop (HCW ’96).Sheraton Waikiki ,H onolulu ,Hawaii :IEEE C om puter S ociety Press ,1996.98-117.521第5期分布式环境下多任务调度问题的分析与求解。
