基于学习的遗传算法的任务图调度

抽象的

如今，基于和分布式的环境广泛使用;因此，为了有效地使用这些环境，采用调度技术。调度算法旨在最大限度地减少并行程序的Makespan（即，完成时间）。由于调度问题的NP硬度，在文献中，已经提出了几种遗传算法来解决这个问题，这是有效的，但不够有效。一种有效的调度算法尝试最小化Mapespan和高效算法，除此之外，试图降低优化过程的复杂性。大多数现有调度算法利用有效的调度算法，在不考虑如何降低优化过程的复杂性的情况下搜索解决方案空间。本文介绍了学习者遗传算法（由LAGA表示），以解决同源计算系统中处理器的静态调度。为此目的，我们提出了两个名为最陡峭的上升学习标准的学习标准和下一个上升学习标准，我们使用惩罚和奖励的概念来学习。因此，我们可以达到一种用于解决调度问题的有效搜索方法，从而找到调度的速度可明智地改善并且被阻止陷入本地最佳状态。在调度过程中还考虑了重用空闲时间标准以减少Makespan。 The results on some benchmarks demonstrate that the LAGA provides always better scheduling against existing well-known scheduling approaches.

1.介绍

并行处理器革命正在进行中。朝着使用并行结构的移动是软件行业的最大挑战之一。2005年，英特尔公司首席技术官Justin Rattner表示，“我们在传输到多核，多线程架构的尖端，我们仍未证明易于编程的移动......”[1］.

将顺序程序良好地调度到处理器(或计算机)上，对于有效利用多处理器(或多计算机)系统的计算能力至关重要。2］.为了执行调度，一个顺序的程序用一个有向无环图(DAG)来表示，它被称为任务图。在这个图中，一个节点代表一个任务，这个任务是一组指令，这些指令从一组输入产生一组输出，并且必须在同一个处理器中串行执行。与每个节点相关的计算成本表示计算量。DAG中的边对应于任务之间的通信消息和优先级约束，因为它们显示了从一个任务到另一个任务的通信时间。这个数字称为通信成本，用表示［3.］.图中显示了一个DAG示例1．在任务图中，节点未准备好运行，直到从其父节点接收到所有所需的数据。分配给相同处理器的两个节点之间的通信成本被认为是零。

在文献中，调度被用于两个不同的性能评估领域:多处理器分布式系统和云计算。多处理器系统调度的目的是使DAG在一组同构或异构处理器上的完成时间最小化。这有助于加快顺序程序的速度。云计算还利用了调度技术，但目标不同，如响应时间、能量消耗、吞吐量和RAM效率。在这方面使用调度的一些论文有[4- - - - - -7］.本文的目的是提出一种算法来调度序列到多处理器系统，而不是云计算。

在调度问题中，完成时间是要完成程序所需的时间。数字2以图形所示的任务图的两个处理器，以甘特图的形式示出示例时间表（调度）。1．从图中可以看出，该任务图的完成时间为140。

调度算法的性能通常在完成时间和算法的运行时间方面测量。通常，这两个性能参数之间的权衡;也就是说，获得最低完成时间的努力通常会产生更高的时间复杂性。

由于调度问题的np困难，使用基于搜索的和进化的方法，如遗传算法，比其他方法更合理[2］.搜索基于算法中的搜索过程可以通过两种方式执行：全局搜索和本地搜索。基于全局搜索的方法通常会考虑整个搜索空间以找到一个很好的解决方案。这些方法具有探索搜索空间中的新区域的运营商。遗传算法是使用全局搜索策略的主要搜索方法之一。该算法没有利用能力，并且在寻找全局最优的同时，收敛速度也不足。本地搜索算法，如山坡和学习自动机，利用利用能力提高现有解决方案的质量以及收敛速度。

爬山爬山算法从初始解决方案开始，然后通过应用本地变化，从当前解决方案迭代地从当前解决方案移动到搜索空间中的邻居解决方案（要定义）。该算法中没有学习概念。学习是系统根据过去的经验改进其响应的能力。强化学习技术用于根据此选择最佳响应奖励或惩罚来自环境。学习自动机是一种基于自动机的学习方法。学习自动机通过过去的经验和与随机环境的反复交互来学习最优动作。行动是根据特定的概率分布选择的，该概率分布是根据环境响应更新的。

本文所解决的问题是各个处理器上任务图的调度，以最小化完成时间，以实现并行程序的执行中的更高性能。为实现这一目标，本文提出了一种新的学习模式，灵感来自爬山算法和学习自动机的行为。然后，我们提出了一种有效的搜索方法，该方法为遗传算法的进化过程增加了新的学习功能。这种新算法将全球搜索（遗传算法）和本地搜索（使用惩罚，奖励和邻居的概念）进行调度，以调度任务图。这导致进化过程速度，即收敛速度，大大增加，并且被阻止捕获当地最佳。因此，算法与其他算法同时，可以搜索问题的更多搜索空间，并找到具有更高质量的解决方案。此外，可以通过在处理器上的空闲时间的最佳重用和使用任务图的关键路径来构建初始群体来改善所提出的算法。该技术使GA能够比以前的算法更好地安排任务图。进行的实验结果表明，LAGA优于PARSA，CPGA，TDGA，CGL，BCGA，DSC，MCP，LC和最后算法。

本文的贡献总结如下:（1）提出一种由行为的新学习模式，这是一种基于行为的基于本地搜索的算法，即爬山爬升算法和学习自动机;（2）利用新的学习模式改进遗传算法的进化过程;（3）提出最佳再利用空闲时间启发式，旨在重用处理器上的空闲时间;（4）针对任务图调度问题，提出了基于最早开始时间的奖罚函数。

本论文的其余部分结构如下。在部分2，我们提供相关工作的概述。在部分3.，提出了一种用于调度任务图形的新算法。在部分4，评估所提出的算法的结果。最后，部分5总结了纸。

2.背景和以前的作品

研究界得到了准确的任务图调度的需求。在文献中，有许多关于任务图调度算法的作品。调度技术通常分为两个类;第一类是同质的[12第二个是异质的[13，14］.在同构系统中，所有处理器的处理能力被认为是相似的。在异构类型中，处理器具有不同的处理能力;因此，对于每个任务，每个处理器上的时间应该分别给出。本文假设调度是齐次的。

一般来说，所有的任务图调度算法可以分为静态和动态两类。静态调度离线执行;换句话说，需要的并行程序特性，如计算成本、通信成本和数据依赖关系，在执行之前就知道了[11］.动态调度算法可进一步分为两类:快速完成模式算法和批处理模式算法。在快速完成模式中，任务一到达就被映射。在批处理模式下，任务到达时不会映射;相反，它们被收集到一个列表中用于调度和映射[12］.本文的工作完全涉及静态调度。

静态任务图调度算法分为两类:基于启发式算法和基于引导随机搜索算法[14］.基于启发式的算法具有较低的复杂性性能。这些算法进一步分为三类：基于列出的算法，基于群集的算法和任务复制算法。

基于列表的调度方法，如HEFT [15]和cpop [14]，由两个阶段的任务优先级和处理器选择组成（将任务分配给处理器）。任务复制方法AIM，如STD [16], HCNF [17]，是在多个处理器上运行任务，以减少依赖任务的等待时间。这种方法背后的主要思想是使用处理器时间差距。

在文献中，有几种基于启发式（非RODEARY）调度算法，如PEFT [13]，ETF [18)、DSC (19], DLS [20.]，HLFET [20.]， 最后的 [21),(左右)22], MCP [23]，LC [24]，EZ [25]和MTSB [26］.大多数这些算法考虑了关于任务图结构的几个简单假设[2，12］.例如，忽略任务通信成本，或考虑所有任务相同的计算成本[2，或者假设任务图为树形结构[8]是其中一些简单的假设。通常，现在许多近期算法旨在处理任何图表。此外，在有限数量的处理器上调度，称为有界数量的处理器（BNP）或无限数量的处理器的可用性，称为无限数量的群集（UNC），是调度算法的另一假设。

由于任务图调度问题是NP-Hard问题[2，12];甚至简化的任务调度问题的版本是NP-Hard。让P和T分别表示处理器的数量和任务数量，因此，对处理器分配的可能数量的任务是P^T可能的任务排序数是T!;然后，整体搜索空间为 ．考虑到庞大的搜索空间，综合搜索所有可能的调度是不可能得到最优调度的;因此，遗传算法等进化方法可以有效地解决这类问题[8，27］.

利用遗传算法求解任务图调度问题一直受到人们的关注。遗传算法之间的主要区别在于表示调度的编码方案。编码结构显著影响遗传过程的复杂性，从而影响最优调度的收敛性。例如，Wang和Korfhage [10[呈现了一个计划的矩阵表示，其记录每个处理器上任务的执行顺序。在此编码中，交叉和突变运算符不会阻止生产无效的解决方案。虽然存在修复操作来纠正这些解决方案。但是，操作消耗额外的时间。Parsa等人。［8]提出了一种新的基于字符串表示的调度表示。在这种新的编码方案中，调度方案由一对数组表示( ， ），在哪里指示分配给处理器的任务号 ．使用该表示，在每个染色体中确定每个处理器上的任务的执行顺序和处理器上的任务执行的全局顺序。侯等人。［9]提出了一个可变长度表示，它在每个处理器上订购任务。他们提出的字符串表示可以防止生产无效的解决方案。然而，此表示不能跨越可能的时间表的完整空间，遗传算法可能不可能收敛到最佳解决方案。

Omara和Arafa [11]提出了具有新的编码方案的基于遗传基算法，即临界路径遗传算法（CPGA）和任务 - 复制遗传算法（TDGA）。CPGA算法试图调度放置在同一处理器上的关键路径上的任务，旨在减少完成时间。第二算法TDGA基于任务复制的原理，以最小化通信开销。该方法的一个弱点是产生无效的染色体。这两个算法的运行时间非常高，用于查找调度，因为它使用一些内部算法来调度，例如关键路径和任务复制。此外，算法的性能在基准测试中尚不清楚。

Daovod等人。［28]提出了一种新的调度算法，即最长动态关键路径(LDCP)，以支持异构计算系统的调度。LDCP是一种基于列表的调度算法，在异构计算系统中有效地选择任务进行调度。LDCP对任务的精确和更好的选择，使其能够在异构系统调度中提供高质量的调度。本文将该算法的功能与HEFT和DLS两种知名算法进行了比较。该算法的缺点之一是贪心，在大规模dag的情况下响应不佳。

bahnasawy等。［29]提出了一种新的基于可扩展任务复制的调度算法，用于异构多处理器计算系统的静态调度。该算法考虑到任务之间的优先级，将图划分为各级，每一级的任务根据其大小排列在一个列表中。基于优先级的任务被分配给列表中的第一个处理器。该算法的缺点之一是贪心问题，在求解大规模dag时，贪心问题难以解决。

Naser等人。［30.]提出了一种异构多处理器系统的调度算法，称为具有复制的通信层次DAG (CLDD)。该算法由三个阶段组成:水平安排，任务优先级，和处理器选择。

温(31]提出了一种遗传和可变邻域搜索（VNS）的混合算法[32]最小化异构多处理器系统中调度的任务。该算法来自GA和VNS的各种特征。

NSGA-II [33]是一种基于遗传的任务图调度算法。在该算法中，任务之间的依赖性不存在，并且精才操作者用于保护遗传算法的进化过程中的良好解决方案。为了提供解决方案的多样性，该算法使用拥挤距离技术。

TSB算法[34]属于一类名为BNP的调度算法。TSB利用两个队列，即，就绪任务队列，而不是就绪的任务队列执行调度。然后，它使用呼气第一搜索遍历算法来选择任务。MTSB算法[26]，也属于BNP类，不同于TSB算法，它不考虑任务与处理器之间的通信时间。

阿克巴里等人[35]提出了一种基于遗传的异构计算系统静态任务图调度算法。他们提出的算法提出了一种新的启发式算法来生成初始种群，并提出了新的算子来保证种群的多样性和收敛性。Akbari和Rashidi [36[异构计算系统中的静态任务图调度，采用了Cuckoo优化算法。因为该算法在连续空间上工作，因此，他们提出了该算法的离散化来解决任务图调度问题。

Moti Ghader等。［37]提出了一种用于静态任务图调度的基于自动机的算法。该算法使用学习自动机代表不同可能的调度。由于该算法是基于本地的搜索算法，因此它在本地Optima中陷入困境。

对所述算法进行性能评估和比较是一项复杂的任务，需要考虑一些问题。首先，有几种基于不同假设的调度算法。其次，大多数现有算法的性能是在小型任务图上评估的，因此，不清楚它们在大规模问题规模上的性能[38］.由于任务图调度的NP硬度，在寻找全局Optima时的收敛速率仍然不够。因此，需要一种可以提高收敛速度的方法，以实现良好的调度。

3.新算法

在本节中，呈现了一种基于学习的任务图调度问题的新的遗传算法。在该算法中，每个溶液由染色体表示。每种染色体的细胞被称为基因。基因的数量取决于任务的数量。我们在我们的算法中使用两种不同的染色体结构，命名为经典和扩展染色体结构。在经典染色体中，每个染色体的结构包括两行，第一行为任务编号，第二行是分配给任务的处理器编号（参见表1）.

扩展染色体结构用于学习过程。该表示具有四行，其中第一行是任务编号，第二行是分配给任务的处理器号，第三行是每个基因的深度，第四行是执行学习所需的每个任务的选择概率。最初是相等的它们的总概率（表2）.

在扩展染色体中，染色体结构被定义为一个元组 如下：（一世） ：是一组基因(r是任务的数量)。(2) ：是染色体中的一组处理器。(3) ：这是考虑与随机环境相互作用的基因评价的结果，并表明必须罚款或奖励基因。（iv） ：让N和R分别表示分配给基因的深度和基因的数量，这显示了一组基因的内部状态。(v) ：这是一个映射函数。基于评估基因的该功能决定了基因的下一个作用。（vi） ：是一种染色体的基因概率。这个矢量图（表中的第四行2）显示每个基因的选择概率，以执行奖励或惩罚操作。根据惩罚或奖励的事实，这些概率更新。如果没有先前的信息，则不存在不同基因的基础可以区分。在这种情况下，所有基因概率都会相等 - “纯机会”情况。为r- 乙烯染色体，基因概率由： (七) 表示学习所需的参数。

在算法中1，给出了我们所提出的任务图调度算法的步骤。以下部分进一步描述了该算法的不同部分。

新的任务调度算法的目标是最小化完成时间。使用了一些术语;提出的算法定义如下。

定义1。在任务图中，节点的T级我是从条目节点到的最长路径的长度我（不包括我）.其中，路径的长度为该路径上所有节点和边的权值之和[39］.

定义2。节点的B级是从节点到退出节点的最长路径的长度[39］.

定义3。任务图的关键路径（CP）是从条目节点到退出节点的路径，因为执行时间和通信成本的总和是最大值。位于CP上的节点可以用它们的值（T级+ B级）识别;即，该节点的T级+ B级应最大化[39］.

定义4。 - - - - - -最早的开始时间任务i和处理器j: EST为节点最早的执行开始时间n_我在处理器p_j．

3．1.初始种群

初始群体如算法所示构建2．

初始种群的生成方式使总体通信时间最小化。该算法识别出关键路径上的所有任务，然后将关键路径上的任务分配到同一个处理器中，从而缩短DAG中的关键路径。通过缩短关键路径的长度，减少了调度的最小完成时间。

3.2。计算染色体的适应性

每条染色体的质量取决于调度的完成时间。一个调度的完成时间代表了它的适应性。目标是最小化完成时间。该算法首先计算所有任务的EST;条目的值 ，参考任务我和处理器j，将由 在哪里FT._j是那种机器的时间j完成任务的所有先前任务的执行我和贝_IJ.表示运行任务所需的所有数据的时间我在处理器j已经准备好了。要计算这个时间，需要完成时间和在任务的所有直接前身的处理器之间传输数据所需的时间我在任务图中被考虑。

用于指导用于查找调度的遗传算法的进化过程的健身功能基于所得时间的总完成时间 在哪里和表示处理器的数量和最后一项任务在处理器中完成的时间 ，分别。 在我们的方法中，所获得的计划和MakEspan的长度被计算为算法3.．

在LAGA中，我们使用轮盘赌轮选择操作员为再现过程选择可能有用的染色体。适应性值用于将每个染色体的选择概率相关联。让n表示染色体I的适应值（由（4)和群体中染色体的数量。这条染色体的选择概率， ，计算如下： 使用 （5)，一个轮的比例分配给每个染色体。染色体的适应度值越高，它被选入繁殖过程的机会就越高。

3.3。重用空闲时间

重用空闲时间标准可以提高时间表的质量[40］.在本节中，我们提出了一种可重用的空闲时间贪婪算法来控制原始系统并提高返回结果的质量。对于种群中随机选择的染色体，在每一代中，我们将一些任务分配到空闲时间。例如,图3.显示与图相关的甘特调度图表的样本1．根据图3.（左），P1处理器中的时间间隙与10个单元一样大，处理器P1的完成时间等于148.此外，任务T10的重量相当于10。通过应用变化，T10可以从时间73开始，完成时间从148到138个单位减少了这种重用，如图所示3.(左)。

这种启发式的算法以算法显示4；虽然没有解决所有任务和所有插槽，但将重复该算法。让闲置开始时间和空格的时隙我表示和 ，分别。也假设dat（ ， ）和w（ ）表示任务的数据到达时间在处理器和执行时间的执行时间 ，分别。任务分配给槽什么时候

例如，假设处理器p₁有空闲槽;和坐₁= 73和EIT₁= 83。另一方面w(t₁₀= 10 and DAT (t .₁₀，P.₁）= 59。在我们的算法t₁₀计划启动时间93.通过应用重用空闲算法，t₁₀可以重新安排在83时开始。

我们需要一个列表来维护每个插槽的所有SIT和EIT。算法试图尽可能地填满插槽。我们的目标是选择满足上述要求的最大任务。为了完成这个任务，首先，我们根据任务的执行时间对任务进行升序排序，即: ；然后，使用算法4在美国，我们把任务分配在插槽中。

重用空闲时间启发式算法更能最小化最大完工时间;然而，对于大规模任务图，该算法在时间方面存在开销。因此，我们将重用空闲时间启发式限制在最佳染色体的30%。这意味着，在一个世代的染色体中，选择完成时间最短的30%采用可重用空闲时间启发式算法。

3.4。学习运营商

利用奖惩算子增强了LAGA的演化过程。这些运算符用于学习。在LAGA中，除了对染色体进行评估外，对染色体的基因进行评估的基础是它们对染色体适应度的结果。因此，在遗传算法的进化过程中，经常会发现染色体内最适合的基因位置和种群内最合适的染色体。该算法直观地选择染色体上的一个基因，并根据一定的标准对其进行评估。如果评价结果是好的，这个基因就会得到奖励。这意味着染色体中的基因处于正确的位置，应该受到保护，以防未来发生变化。但如果评价结果不好，基因就必须受到惩罚。在这种情况下，如果该基因尚未获得奖励，或者惩罚和奖励的数量相同，则会搜索该基因的所有可能邻居(待定义)以寻找惩罚行为。具有最高品质的邻居将会是这个基因的替换者。 But if the number of rewards received by the gene is greater than the number of received penalties, one of the numbers of rewards is reduced.

形式上，LAGA采用的奖惩操作符如下。

在调度过程中，LAGA选择基因在染色体中并评估它，如果它得到有希望的反馈，概率， ，该基因的增加，其他基因的概率降低。如果它有不合适的反馈，概率， ，该基因的降低和其他基因的概率增加。在本文中，我们利用了线性学习方案来学习。该方案首先在数学心理学中被认为是[41]但后来被夏皮罗和Narendra独立构思和引入工程文学中[41］.让和是两个函数，对于多基因的线性学习方案，我们有 在(6)和(7），米， ，和分别是染色体的基因数量、奖励参数和惩罚参数。的参数和用来控制染色体的收敛速度。根据(6)和(7),如果和等于，学习算法将被称为线性奖励罚款。如果 ，学习算法将被称为线性奖励-惩罚，如果b=0，学习算法将是线性奖励不作为。根据是否进行了惩罚或奖励，基因的概率更新如下。

对基因I有前途的反馈 但 所以 和 基因i的不适当反馈 但 所以 和 这些概率导致良好的基因随着时间的推移在染色体中找到它们的位置。这些概率的主要目的是利用系统的先前行为，以便为未来做出决定，因此发生学习。为了进行学习，必须确定每个基因的内部状态的数量。每个基因的这些内部态度维持失败的数量和成功。如何从染色体中选择基因是基于计算每个基因的累积概率，如下（是基因概率）： 在0到1之间产生一个随机数。如果生成的随机数大于和较低的比 ，相应的基因被选来评估奖励和惩罚。显然，概率高的基因更倾向于奖励或惩罚。

在算法的每个迭代步骤中，根据每条染色体的概率选择一个基因(8), (11), (12)和(15)，该基因的评估使用算法5．

一般来说，一个基因受到的惩罚或奖励如下。

假设一条染色体包含R基因( ）并已rn.内部状态( ）.内部状态的 与之相关 ， 与之相关 ，和 与之相关 ．所以， 所以G是一个映射函数。

如果基因处于内部状态吗 这个基因就会受到惩罚 然后内部状态更改如下： 如果基因获得奖励 然后内部状态更改如下： 如果基因处于内部状态 它会受到惩罚然后内部状态会发生如下变化 如果基因获得奖励，则转移状态执行如下： 在图中4，每个基因的内部状态被认为是N.在该图中，N和2N分别表示第一基因和第二基因的边界状态。在评估基因之后，如果它得到正反馈，它将移动到内部状态，如果采取不适当的反馈，则会移动到边界状态。如果基因达到边界状态并获得不希望的反馈，则它在染色体中与另一个基因移位，使得染色体的整体质量得到改善。为了执行这一点，产生基因的邻居，然后从这些邻居中搜索校准器中的处理器以进行位移，使得该染色体中的Makespan值低于其他染色体。如果产生的新染色体的Mapspana价值超过初始染色体，则它仍然是相同的初始染色体。实际上，算法继续直到没有获得更好的解决方案。邻居调度的概念如图所示5．在该图中，示出了电流调度和B，C和D是三个邻居调度。例如，考虑任务一个因此，在B中，它进入处理器4，在C中，它进入处理器2，在C中，它进入处理器3。

在学习过程中，选择来自选定染色体的几个基因，并且通过该算法定期改善了各种染色体（算法）6）.所提出的算法考虑了阈值确定用于搜索的邻居数量。这些阈值可能是范围内的任何百分比 ．使用低值减少了算法收敛前的步骤，并使用了较高的值增加算法收敛前的步长。然而，高阈值通常可以产生好的结果，这是合理的。基于价值，我们建议参加最陡峭的上升学习标准（SALC）和下一个上升学习标准（NALC）的学习模式的类型。在下一个学习标准等于零。这意味着当使用较低的MakeSpan（即，高质量解决方案）找到第一个调度时，算法停止搜索调度;在最陡峭的上升学习标准中，等于100％。这导致算法生成调度所有邻居并检查所有邻居，并选择具有最低MakEspan的邻居。

定理5。LAGA算法的时间复杂性是O（maxgen×popsize×n×v）。

证明。要计算算法的时间复杂性，首先，我们考虑以下假设：PopSize:种群中的个体数量MaxGen:代的数量I:奖励和惩罚操作符的迭代次数V:任务图中的任务数N:一个被选择基因的邻居数目#P:处理器的数量#s：处理器中的空闲插槽数v'：分配到处理器中的任务数为了计算染色体的时间复杂性，有必要计算所有处理器的完成时间，并在染色体的时间完成时选择它们的最大时间。因此，计算染色体的完成时间的时间复杂度是O（v）。有益的操作时间复杂性是o ，因为只有基因的内部状态会改变。但是，惩罚操作时间复杂度为O(N×V)，因为需要找到它的邻居，计算它们的完成时间，然后选择一个完成时间最短的邻居。
初始种群的创建可以在线性时间内完成，因此，主要的计算代价在步骤2(算法1）.学习模式的计算复杂性是O（n×v）。将染色体延伸至经典染色体的计算复杂性是O（粉扑×V）。学习的计算复杂性是O（弹出×n×v）。选择操作员的计算复杂性是O（v）。交叉的计算复杂性是O（POPSIZE×V），突变是O（POPSIZE×V）。重用空闲时间启发式的计算复杂性是O（粉扑×#p×#s×v'logv'）。Thus, the overall time complexity is O(V) + O(N×V) + O(N×V) + O(PopSize × #P × #S × v’logv’) + O(V) + O(PopSize×V) + O(PopSize× N×V) + O(PopSize×V) + O(PopSize×V). Therefore, considering the number of generations, the time complexity of LAGA can be simplified as O(MaxGen×PopSize× N×V).

4.实验结果

用于支持本研究结果的任务图载于[8，21] 和http://www.kasahara.cs.waseda.ac.jp/schedule/optim_pe.html.．在下文中，我们将所提出的算法与这些任务图中的许多其他算法进行比较。

首先，将LAGA算法与标准遗传算法(SGA)进行比较。在SGA中，没有深度，任务是根据每个染色体的拓扑顺序排列的。将LAGA应用于[8，21，图中重新绘制了这张图6．结果表明，LAGA与SGA相比有很大的改善。实验参数设置如下:（一世）群体大小:30条染色体，(2)代数:500，(3)处理器数量：3，（iv）交叉概率：80％，(v)突变概率：5％，（vi）深度:3,(七) （viii）奖励和惩罚概率：50％。

桌子3.显示如图所示任务图所获得的调度和完成时间6对于LAGA和SGA算法。而且，评估所提出的算法的稳定性。稳定性是进化和启发式算法中的一个关键问题。这意味着该算法在不同的运行中提供了相同或相同的解决方案。为了证明LAGA的稳定性，通过二十次算法获得的结果来安排图中所示的任务图7．

采用LAGA和SGA算法时，染色体的级数如图所示8．

与其他算法的提议算法的比较．现有的遗传算法和其他启发式算法都是在随机生成且没有通信开销的图上进行评估的。因此，我们选择在已知结果的特定图上进行比较的算法。因此，本节将LAGA与9种不同的算法在各自使用的图上进行比较。

在图中9将LAGA算法与Parsa算法和其他六种调度算法进行了比较。将LAGA应用于图中所示的任务图进行比较6［8，21]，并被Parsa和其他六种算法所使用。结果表明，LAGA算法的调度性能优于3-7算法，与Parsa算法和LC算法相同。然而，LAGA得到的结果非常迅速和稳定。此外，当任务数量增加时，LAGA运行得更快。此外，Parsa算法是用小问题规模来评估的，目前还不清楚它们在大规模问题规模上的性能。在图中10，将LAGA的稳定性与PARSA算法进行比较。

快速傅里叶变换任务图(FFT)，如图所示11，是评估调度算法的性能的好的基准。桌子4显示了这些图的三个版本(即FFT1、FFT2和FFT4)。每一种情况的第一列显示每个任务的计算时间，第二列显示每个任务与其他任务的通信时间。

根据表5和6，已经发现了LAGA与 始终优于基于遗传和环境的算法。因为，考虑到高速LAGA，同时与其他算法相同，它可以搜索更多的问题，结果可以找到具有更高质量的答案。

通常，针对任务图调度问题所提出的算法大都是在规模小、通信少的图上研究效率，而在实际应用中规模大、通信多的图上研究结果并不明确。的LAGA（ ）是否适用于特定的基准应用程序，哪些是从标准任务图(STG)档案 （http://www.kasahara.cs.waseda.ac.jp/schedule/optim_pe.html）（见表7）.该STG集的第一程序任务图1是随机生成的任务图，第二程序是一个机器人控制程序（任务图2），它是实际应用程序，最后程序是稀疏矩阵求解器（任务图3）。此外，我们考虑了随机通信成本的任务图。这些通信成本均匀地分布在1和指定的最大通信延迟之间。

桌子8表中列出的程序在4个处理器上比较SGA和LAGA(深度3和5)、Parsa、CPGA和TDGA算法的结果7．根据表格8，具有深度= 3的所提出的算法（LAGA）产生比其他算法低的调度长度。

桌子9在一些随机生成的图上，比较了三种基于遗传的算法和LAGA算法。任务执行时间和处理器之间的通信时间被认为是随机的。任务执行时间和通信时间分别均匀分布在(10,50)和(1,10)秒内。为了评估算法的效率，我们将算法的运行时间设置为相同的值。从这张表中可以看出，LAGA在所有情况下，以及与它们同时发生的情况下，都比其他情况表现得更好。这说明LAGA可以同时搜索更多的空间，因此它是有效的。

5.结论

任务图调度问题是NP难题。因此，为了解决这个问题，进化方法非常有效。但是，他们在寻找全局最优的收敛速度仍然不够。因此，需要一种能够提高收敛速度的方法来实现良好的调度。在本文中，我们将遗传算法与加速收敛速度策略组合，旨在在并行环境中实现更高的性能。我们提出了一种基于学习的遗传算法，用于解决更好地利用处理器的问题。考虑到所提出的方法的高速，所提出的方法可以在其他算法同时搜索更多的问题，因此它可以找到具有更高质量的解决方案。

5.1。未来的作品

为进一步拓展和完善这一工作，可以探索若干方向。（1）寻找有用且有效的奖励和惩罚功能;（2）在任务图的调度中使用聚类而不是使用关键路径;（3）找到所提出的算法的有用且有效的负载平衡启发式。（4）参数调谐是遗传算法的主要缺点之一。最近，为了解决NP难题，使用没有参数调整的优化算法，例如甲虫天线搜索算法[42，引起了广泛关注。在今后的工作中，我们希望将该算法应用于任务图调度问题。

该方法可推广到网格计算、云计算和异构环境下的调度问题;也可以用我们的方法来解决其他NP-Hard问题。

数据可用性

用于支持本研究发现的数据可由通讯作者要求提供。

利益冲突

作者声称他们没有利益冲突。

参考文献

1. M. Hall, D. Padua, K. Pingali，《编译器研究:未来50年》ACM的通信号，第52卷。2，第60-67页，2009。视图:谷歌学术
2. Y.-k.kwok和i. ahmad，“在多处理器任务调度上使用有效的状态空间搜索方法，”并行和分布式计算学报，第65卷，第5期12, pp. 1515-1532, 2005。视图:谷歌学术
3. 吴淑珍，“一种基于遗传算法的多处理器调度方法”，清华大学学报(自然科学版)IEEE并行和分布式系统汇刊，第15卷，第5期。9，页824-834,2004。视图:出版商的网站|谷歌学术
4. X. Lin，Y. Wang，Q..Xie和M. Pedram，“Task调度与移动云计算环境中能量最小化的动态电压和频率缩放，”Services Computing上的IEEE交易，第8卷，第2期2, pp. 175-186, 2014。视图:出版商的网站|谷歌学术
5. Tang Z.， Qi L.， Cheng Z.， K. Li, S. U. Khan, and K. Li，“一种基于分布式云环境的节能任务调度算法”，网格计算第14卷第2期1, pp. 55-74, 2016。视图:出版商的网站|谷歌学术
6. S. K. Panda和P. K. Jana，“异构多云环境下的高效任务调度算法”，超级计算杂志，卷。71，没有。4，pp。1505-1533,2015。视图:出版商的网站|谷歌学术
7. B. Keshanchi, A. Souri，和n.j. Navimipour，“一种用于云环境中使用优先级队列的任务调度的改进遗传算法:形式化验证、模拟和统计测试，”系统与软件杂志， 2017, vol. 124, pp. 1-21。视图:出版商的网站|谷歌学术
8. S. Parsa, S. Lotfi, N. Lotfi，“任务图调度的进化方法”，LNCS -施普林格链接日志, 2007年。视图:谷歌学术
9. E. S.H.Hou，N.Ansari和H. Ren，“一种多处理器调度的遗传算法”IEEE并行和分布式系统汇刊，卷。5，不。2，pp。113-120,1994。视图:出版商的网站|谷歌学术
10. M. Rinehart, V. Kianzad，和S. Bhattacharyya，“用于调度任务图的模块化遗传算法”，技术代表，2003。视图:谷歌学术
11. F. A. Omara和M. M. Arafa，《任务调度问题的遗传算法》，并行和分布式计算学报，第70卷，第2期1，页13-22,2010。视图:出版商的网站|谷歌学术
12. Y.-k.Kwok和I. Ahmad，“任务图调度算法的基准和比较”，“并行和分布式计算学报，第59卷，第59期3，第381-422页，1999。视图:出版商的网站|谷歌学术
13. H. Arabnejad和J.G.Barbosa，“通过乐观成本表列出异构系统的调度算法”IEEE并行和分布式系统汇刊，卷。25，不。3，pp。682-694,2014。视图:出版商的网站|谷歌学术
14. H. Topcuoglu, S. Hariri, M. Wu，“异构计算的高性能和低复杂度任务调度”，IEEE并行和分布式系统汇刊，第13卷，第2期3，pp。260-274,2002。视图:出版商的网站|谷歌学术
15. H. Topcuoglu, S. Hariri, M. Y. Wu，“异构处理器的任务调度算法”，刊于第八届异构计算研讨会论文集(HCW'99)，页3-14,IEEE, 1999。视图:谷歌学术
16. S. Ranaweera和D. P. Agrawal，“一种可扩展的基于任务重复的异构系统调度算法”2000年并行处理国际会议的诉讼程序，IEEE，2000。视图:谷歌学术
17. S. Baskiyar和P. C. Sairanga，“调度在工作站的异构网络上的定向A-循环任务图以最大限度地减少日程长度”2003年度并行处理研讨会国际会议的诉讼程序，ICPPW 2003，pp.97-103，IEEE，台湾，2003年10月。视图:谷歌学术
18. J. J. Hwang, Y. C. Chow, F. D. Anger, and C. Y. Lee，“基于处理器间通信时间的系统优先图调度”，计算机学报，卷。18，不。2，pp。244-257,1989。视图:出版商的网站|谷歌学术
19. T. Yang和A. Gerasoulis，“DSC:在无限数量的处理器上调度并行任务”，IEEE并行和分布式系统汇刊，卷。5，不。9，pp。951-967，1994。视图:出版商的网站|谷歌学术
20. G. C. SIH和E. A. Lee，“互连受限的异构处理器架构的编译时调度启发式，”IEEE并行和分布式系统汇刊，第4卷，第4期。2，页175-187,1993。视图:出版商的网站|谷歌学术
21. J. Baxter和J. H. Patel，“最后一次算法：基于启发式的静态任务分配算法，”1989年平行处理国际会议论文集，卷。2，pp。1989年8月217-222。视图:谷歌学术
22. B. Kruatrachue和T. G. Lewis，“复制调度启发式（DSH）：一个新的Persionoply Processor Systems的优先任务调度程序，”Tech。俄勒冈州州立大学，科瓦里斯，或者，美国，1987年。视图:谷歌学术
23. M. WU和D. Gajski，“超措施：用于消息传递系统的编程辅助工具”IEEE并行和分布式系统汇刊， vol. 1, no. 13，页330-343,1990。视图:出版商的网站|谷歌学术
24. V. Sarkar，分区和调度多处理器的并行程序，MIT新闻，剑桥，马，美国，1989年。
25. S. J. Kim和J. C.Browne，“绘制了对多处理器架构的并行计算的一般方法，”平行处理国际会议论文集，卷。2，pp。1-8,1988。视图:谷歌学术
26. R.Rajak，C.P.Katti和N.Rajak，“没有通信时间的任务图的修改任务调度算法”国际新型计算机架构及其应用（IJNCAA），第3卷，第2期。4，pp。88-93,2013。视图:谷歌学术
27. A. Radulescu和A. J. C. Van Gemund，《分布式内存机器的低成本任务调度》，IEEE并行和分布式系统汇刊，第13卷，第2期6，页648-658,2002。视图:出版商的网站|谷歌学术
28. M. I. Daoud和N.Kharma，“异构分布式计算系统中的静态任务调度高性能算法”并行和分布式计算学报，卷。68，没有。4，pp。399-409，2008。视图:出版商的网站|谷歌学术
29. N.A.A.Bahnasawy，M.A.Koutb，M. MOSA和F.Omara，一种用于异构分布式计算系统的静态任务调度算法，“非洲数学与计算机科学研究，第3卷，第2期。6，页221-234,2011。视图:谷歌学术
30. A. A. NASR，N.A.El-Bahnasawy和A. El-Sayed，“高性能异构分布式计算系统的任务调度算法”，国际计算机应用杂志，卷。110，没有。16，pp。23-29,2015。视图:谷歌学术
31. Y. Wen，H.Xu和J. Yang，“基于启发式的混合遗传 - 可变邻域搜索算法，用于异构多​​处理器系统的任务调度”，信息科学，卷。181年，没有。3，pp。567-581，2011。视图:出版商的网站|谷歌学术
32. P. Hansen和N.Mladenović，“可变邻居搜索：原则和应用程序”欧洲运筹学研究杂志，卷。130，否。3，第449-467,2001。视图:出版商的网站|谷歌学术|Mathscinet.
33. P. Chitra，R.Rajaram和P.Venkatesh，“混合进化多目标优化算法的应用与比较解决异构系统任务调度问题”应用软计算，卷。11，不。2，pp。2725-2734，2011。视图:出版商的网站|谷歌学术
34. R.Rajak，“多处理器系统中的任务调度新方法”，国际计算机应用杂志，卷。44，不。11，pp。12-16,2012。视图:出版商的网站|谷歌学术
35. M.Akbari，H.Rashidi和S. H. Alizadeh，“一种增强的遗传算法，具有新的运营商，用于异构计算系统中的任务调度，”人工智能的工程应用，第61卷，第35-46页，2017。视图:出版商的网站|谷歌学术
36. M.Akbari和H.Rashidi，“基于Cuckoo优化在异构系统中编译时的基于Cuckoo优化的多目标调度算法”具有应用的专家系统，卷。60，pp。234-248,2016。视图:出版商的网站|谷歌学术
37. H. M. Ghader，D. Keykhosravi和A. Hosseinalipour，“DAG调度在异构分布式系统上使用学习自动机构”亚洲智能信息和数据库系统会议的程序，PP。247-257，Springer，Berlin，Heidelberg，2010年。视图:谷歌学术
38. T.Davidović和T. G. Crainic，“具有同类多处理器系统上的通信延迟的任务图表的静态调度基准问题实例”计算机与运营研究，卷。33，不。8，pp。2155-2177,2006。视图:出版商的网站|谷歌学术
39. K. S. Shin, M. J. Cha, M. S. Jang, J. Jung, W. Yoon, S. Choi，“在同质系统中使用最小化重复的任务调度算法”，并行和分布式计算学报，卷。68，没有。8，pp。1146-1156，2008。视图:出版商的网站|谷歌学术
40. Z. Jovanovic和S. MariC，“高度并行计算系统中动态任务调度的启发式算法”下一代计算机系统，第十七卷，第二期6，页721-732,2001。视图:出版商的网站|谷歌学术
41. I. J. Shapiro，随机自动机在自适应控制中的应用[博士论文]。论文)Dep。eng。并应用了SCI。，耶鲁大学，纽黑文，康涅狄格州，美国，1969年。
42. X.江和李，“基础：甲壳虫天线搜索算法，”优化问题“，”2017，https：//arxiv.org/abs/1710.10724。视图:谷歌学术

版权

版权所有©2019 Habib Izadkhah。这是一篇发布在知识共享署名许可协议如果正确引用了原始工作，则允许在任何媒体中的不受限制使用，分发和再现。