任务复制

摘要： 关键路径的确定与优化在异构多核系统的任务调度算法中占据重要地位。为解决异构多核系统调度算法常因估算关键路径时的参数选择存在局限而导致的估算结果偏差过大,调度结果不佳的问题,文章提出一种在参数计算时考虑资源约束的异构多核任务复制调度算法(task-duplication scheduling algorithm with resource constraints,TDSA-RC)。该算法通过改进布局优化方式,扩大其适用范围;同时通过筛除冗余任务,减少任务复制过程中产生的不必要的计算。通过随机生成的任务图和3种实际应用的任务图调度对比实验表明,该算法能有效缩短并行任务的调度长度,与TDCA(task-duplication based clustering algorithm)算法相比,平均性能可提升12.08%,适合处理规模大、层级少且join节点占比多的并行任务。

摘要： 随着边缘计算的快速发展,边缘往往需要处理大量的任务,一些边缘集群超载,导致慢任务的产生.文章首次基于多臂赌博机的算法应用于边缘计算环境的任务复制问题.以往的工作通常是将任务从过载边缘复制到空闲边缘,以减少排队和计算时延来换取传输时延.在作出复制决策之前,无法预测被复制到不同边缘的任务的完成时延,这影响了任务复制机制的性能.因此,将多臂赌博机应用于任务复制问题,并对边缘计算性能和链路带宽的随机性进行了描述.文章提出了一种边缘计算环境中基于复制的任务加速机制,证明了该任务加速机制是次线性的.最后,对所提出的任务加速机制的时延性能和服务可靠性进行了仿真评估.与SINGLE和RANDOM相比,此任务加速机制将平均作业完成时间分别提高了56.4％和77.6％.

摘要： 在分布式计算中常把任务之间的协同和通信关系转换为任务图模型,而任务调度是决定分布式计算性能的关键因素之一.为解决OSA、TDCS、RECS等传统经典算法处理器个数消耗多且存在大量冗余任务等问题,提出一种改进的任务图调度算法.该算法基于贪心策略复制任务的前驱以及前驱的前驱,减少调度长度和处理器空闲时间,并在不增加调度长度的前提下,通过合并簇及减少冗余任务降低处理器个数和处理器的负载.实验结果表明,该算法在处理器个数、加速比以及冗余任务比率上都有一定程度的优化,能提升分布式计算性能.

摘要： In order to improve the execution efficiency and lower execution cost of the tasks in cloud,we propose a policy of parallel tasks scheduling based on correlation. The queues are divided according to the communication overhead between tasks before the tasks are scheduled. The finish time of the latest path can be shortened by the partition of the queues. Then,the task is replicated according to the correlation. Task replication algorithm can reduce the waiting time of tasks and improve the parallelism of tasks. After replication,the task queues on the processors are independent of each other,improving the execution efficiency of the tasks. Correlation is quantified by the communication overhead and computational overhead between tasks and set threshold value. If the correlation is greater than the threshold value,then task is replicated,otherwise not be replicated. This strategy can reduce the communication overhead between tasks and avoid the space consumption caused by all tasks replication. Experiment shows that the strategy can improve the parallelism of the tasks and it has a significant effect in improving the utilization ratio of processors and lowering the cost of tasks execution.%为了提高云环境下任务的执行效率、降低执行费用,提出了一种基于相关性的并行任务调度策略.该策略在任务调度之前根据任务间的通信开销进行队列划分,通过队列的划分可以缩短最晚路径的完成时间,然后根据相关性进行任务复制,任务复制算法降低了任务的等待时间,提高了任务的并行性.经过任务复制,每个处理机上的任务队列基本都是相互独立的,提高了任务的执行效率.相关性由任务间的通信开销和计算开销来量化并设定阈值,若相关性大于阈值则进行任务复制,否则不予复制.该策略既可以减少由任务间的通信带来的开销,也可以避免由所有任务复制带来的空间消耗.实验结果表明,该方法可以提高任务的并行度,在提高任务的执行效率及降低执行费用方面有很大的改进.

摘要： 针对当前云计算环境下DAG任务调度时存在的负载失衡、任务调度效率不高的问题,提出了一种负载均衡优先的改进优先级表调度算法(LS-IPLB).算法将云计算集群中虚拟机的状态参数变化抽象成空间中的参数向量变化,给出实时衡量云计算集群的负载均衡性方法,并作为虚拟机选择权值的重要参数.同时以任务执行代价、任务的出度和任务间的通信代价作为参数计算任务优先级,并在任务调度时采用任务复制策略进一步优化调度过程.结果表明,LS-IPLB算法能有效缩短DAG任务图的完成时间,并实现了良好的负载均衡性.%Aiming at such problems as the load imbalance and low efficiency of DAG task scheduling in the current cloud computing environment, a list scheduling algorithm of improved priority with considering load balance (LS-IPLB) was proposed.In the algorithm, the state parameter change of virtual machine in the cloud computing cluster was abstracted into the parameter vector variation in the space, and the real-time measurement method for the load balance of cloud computing cluster was given, which was taken as an important parameter to select the weight of virtual machine.At the same time, the task priority was calculated through taking the task execution cost, task output value and communication cost between the tasks as the parameters.In addition, the task duplication strategy was used in the task scheduling to further optimize the scheduling process.The results show that the LS-IPLB algorithm can effectively shorten the completion time of DAG task graph, and can achieve good load balance.

摘要： This paper proposes HCNPSV algorithm based on critical task and processor selection value to improve the performance of processing dependent tasks in heterogeneous and distributed environment. The algorithm combines list scheduling and task duplication scheduling, improves the method of calculating critical tasks, gives highest priority to crit-ical tasks and decrement of upword rank and increment of number of related tasks by the order of sort. Besides this paper establishes parameter based on earliest finish time and least distance exit time of the tasks to select processors, finally tasks assign to the value minimum resources to perform. Experiments show that HCNPSV scheduling enhances the performance.%为了提升异构分布式环境下处理具有依赖关系的任务的性能,提出一种基于关键任务和处理器选择参数的启发式任务调度算法(HCNPSV).该算法结合表调度和任务复制调度的思想,改进了关键任务的计算方法,并按照是否为关键任务、上行权重值递减、关联任务数递增的顺序获得调度序列,资源选择阶段综合考虑了任务的最早完成时间和到出口节点的最短距离,最后将任务调度到处理器选择参数最小的资源上执行.实验结果表明,HCNPSV有效地提高了系统的调度性能.

摘要： 在多核系统中，任务调度是决定系统性能的关键因素之一。为优化任务调度，基于一些典型的任务调度算法（如PPA，徐成提出的算法等），提出了一种新的任务调度算法。该算法一方面合理确定前驱任务复制的先后顺序，而且进行两个阶段的复制，从而可以复制更多的前驱任务以减少调度长度和处理器上空余时间；另一方面，通过去除不影响任务系统调度长度的冗余簇，然后进行簇之间的合并，以减少处理机的数目和调度长度。实验表明，改进后的算法在任务调度的性能上优于典型算法。%In the multi-processor system, task scheduling is one of the key factors which decide the performance of system. In order to optimize the task scheduling, this paper proposes a new task scheduling algorithm based on some typical algo-rithms(e.g., PPA, the algorithm which is put forward by XU Cheng etc.). On the one hand, the algorithm establishes reason-able order to duplicate precursor task, and two stages of replication, which can duplicate more precursor task to reduce scheduling length and spare time. On the other hand, the algorithm removes redundant clusters which don’t affect the sched-uling length of the task system, then carries on the merger between clusters to reduce the number of the processor and scheduling length. Simulation results show that the improved algorithm on the performance of task scheduling is superior to the above typical algorithms.

摘要： 基于云环境下的科学工作流,以提高处理机利用率、降低费用为目标,提出了一种基于聚簇的执行优化策略.该策略首先基于合理的任务复制和分簇,以实现关键任务的尽早调度;在此基础上,对任务簇再次进行聚集,以充分利用任务簇中任务间可能的空闲时间.实验表明,该策略能够提高任务的并行度,提前工作流的最早完成时间,并且在提高处理机的利用率和降低科学工作流的执行费用方面有显著效果.

摘要： 在模糊云计算环境下,需要对特定数据进行识别定位,实现目标数据信号的准确检测和访问。传统方法采用先分层后分支的数据目标资源识别定位算法,定位识别性能计算复杂度较大,准确度不高,提出一种基于通信开销缩减和冗余任务删除的特定数据目标资源识别定位技术。首先对DAG图中的任务进行任务归并,然后将DAG图分层,从整个任务图的全局出发考虑任务的优先级,构建模糊云计算模型,设计模糊云计算核函数,创建多个线程的信息流特征编码,考虑对整个任务图调度时间起决定作用的关键任务,设计通信开销缩减算子,将调度列表头结点分配到使其具有最小最早完成时间的处理器内核上,提高对特定数据的目标资源定位识别性能。仿真实验得出,该算法定位精度较高,对目标资源的冗余任务进行有效删除,明显提高了任务调度效率,收敛性能较好。

摘要： Aiming at the problem of current scheduling algorithm for multi-core which fails to consider that the nodes on the critical path have a major impact on the ending time of tasks,leading to the delay of the task completion time;a scheduling algorithm based on critical path and task duplication (CPTD)is proposed.Firstly,the fork-nodes were duplicated to change the task graph into products processing tree,then the critical path in the processing tree were found,and the father nodes of the nodes on critical path were made to work at the earliest time.These operations can advance the start time of nodes on critical path.The purpose of the above operation is to shorten the implementation of the mandate of the total time. Theoretical analysis shows that the algorithm can achieve a single task fully parallel processing on multi-core,and also can shorten the completion time of the tasks.%针对目前大多数多核处理器任务分配优化算法没有考虑关键路径上节点对任务完成时间的重要影响，导致任务完成总时间延迟的问题，提出了基于关键路径和任务复制（CPTD ）的单任务调度算法。CPTD算法通过复制任务图中fork节点的方式将任务图转化为与之相对应的产品加工树；再在生成的产品加工树中找到关键路径，并采取使关键路径上节点的紧前节点尽早调度的方式，使关键路径上节点尽早开始执行，进而使产品加工树中节点完成时间得以提前，达到缩短任务执行总时间的目的。理论分析表明，CPTD算法能够实现应用程序在多核上充分并行处理，并能缩短任务完成时间。

摘要： 任务调度就是根据一定的调度规则和调度策略,把组成并行程序的一组任务按照一定执行时序分配到并行分布系统的多个计算节点上,以最小化并行应用程序的完成时间.当前,基于任务复制的调度已成为研究热点.任务复制是指在不同处理机上执行相同的任务,从而可以减少任务间的通讯时间.一般来说,基于任务复制的调度绝对优于不是基于任务复制的调度.然而,无论任务是否复制,多处理机相关任务调度问题始终是一个NP完全问题.现已有许多基于任务复制的调度算法在任务满足某些条件时能产生最优调度.任务复制可以通过任务的冗余减少通信时间，现已成为一种新的研究方法。当通信开销较小时，现已有许多基于任务复制的调度算法能产生最优调度。但其最优条件要么比较苛刻，要么比较复杂。因此，本文提出一个简单有效的新调度算法，不仅其最优条件简单、宽松，而且算法具有更小的时间复杂度O（dVIOgd），其中，V和d分别表示任务集中任务的个数和最大入度。

摘要： 任务调度是实现高性能网格计算的一个基本问题。在网格环境中,任务调度的目标系统通常为任意连接的网络,应用程序常为复杂的计算密集型的并行分布式应用程序,本文提出了一个新的基于复制任务调度算法,该算法减少了任务在执行过程中重复查找最佳处理器的时间花费,并且可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载。仿真实验结果表明该算法更加符合网格的复杂环境,能够更好的满足不同用户的实际需要。

摘要： 任务调度是实现高性能网格计算的一个基本问题。在网格环境中,任务调度的目标系统通常为任意连接的网络,应用程序常为复杂的计算密集型的并行分布式应用程序,本文提出了一个新的基于复制任务调度算法,该算法减少了任务在执行过程中重复查找最佳处理器的时间花费,并且可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载。仿真实验结果表明该算法更加符合网格的复杂环境,能够更好的满足不同用户的实际需要。

摘要： 任务调度是实现高性能网格计算的一个基本问题。在网格环境中,任务调度的目标系统通常为任意连接的网络,应用程序常为复杂的计算密集型的并行分布式应用程序,本文提出了一个新的基于复制任务调度算法,该算法减少了任务在执行过程中重复查找最佳处理器的时间花费,并且可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载。仿真实验结果表明该算法更加符合网格的复杂环境,能够更好的满足不同用户的实际需要。

摘要： 任务调度是实现高性能网格计算的一个基本问题。在网格环境中,任务调度的目标系统通常为任意连接的网络,应用程序常为复杂的计算密集型的并行分布式应用程序,本文提出了一个新的基于复制任务调度算法,该算法减少了任务在执行过程中重复查找最佳处理器的时间花费,并且可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载。仿真实验结果表明该算法更加符合网格的复杂环境,能够更好的满足不同用户的实际需要。

摘要： 任务调度是实现高性能网格计算的一个基本问题。在网格环境中,任务调度的目标系统通常为任意连接的网络,应用程序常为复杂的计算密集型的并行分布式应用程序,本文提出了一个新的基于复制任务调度算法,该算法减少了任务在执行过程中重复查找最佳处理器的时间花费,并且可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载。仿真实验结果表明该算法更加符合网格的复杂环境,能够更好的满足不同用户的实际需要。

摘要： 针对网格环境中应用程序常为复杂的计算密集型的并行分布式应用程序,提出了一个新的基于复制和插入的启发式任务调度算法(duplication-and-insertion-based scheduling,DIBS),可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载.实验结果表明,该算法更加符合网格的复杂环境,能够更好地满足不同用户的实际需要.

摘要： 针对网格环境中应用程序常为复杂的计算密集型的并行分布式应用程序,提出了一个新的基于复制和插入的启发式任务调度算法(duplication-and-insertion-based scheduling,DIBS),可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载.实验结果表明,该算法更加符合网格的复杂环境,能够更好地满足不同用户的实际需要.

摘要： 针对网格环境中应用程序常为复杂的计算密集型的并行分布式应用程序,提出了一个新的基于复制和插入的启发式任务调度算法(duplication-and-insertion-based scheduling,DIBS),可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载.实验结果表明,该算法更加符合网格的复杂环境,能够更好地满足不同用户的实际需要.

摘要： 针对网格环境中应用程序常为复杂的计算密集型的并行分布式应用程序,提出了一个新的基于复制和插入的启发式任务调度算法(duplication-and-insertion-based scheduling,DIBS),可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载.实验结果表明,该算法更加符合网格的复杂环境,能够更好地满足不同用户的实际需要.

摘要： 本发明公开了一种基于节点复制的异构多核系统任务调度方法，包括：1根据有向无环图与异构计算消耗表，计算后续步骤需要的参数，并依据参数对任务进行排序，得到任务优先级列表；2按照任务优先级列表将任务依次取出，并把任务分配到不同的内核队列，生成初始布局；3遍历初始布局，对符合节点复制条件的任务节点进行相应的复制操作，生成复制后布局；4遍历复制后布局，在符合wait条件的join节点前补充冗余的wait节点，生成次优布局；5对次优布局进行冗余筛查，删除布局中的冗余任务，生成最优布局。本发明有利于估算并缩短异构环境下并行任务的关键路径，减少任务执行的整体时间，并通过冗余筛查避免无价值的冗余计算。

摘要： 本公开涉及对网络存储设备中的复制任务进行分配的方法和设备。例如，一种对网络存储设备中的复制任务进行分配的方法，包括：响应于接收到用于复制多个会话的请求，将用于复制多个会话中的配置会话的任务分配给网络存储设备的第一处理单元，该配置会话包含描述多个会话的配置信息；将用于复制多个会话中除配置会话之外的其他会话的多个任务分配给不同于第一处理单元的多个第二处理单元；以及响应于第一处理单元和多个第二处理单元完成各自的任务，汇总对多个会话的复制的结果。通过本公开的技术方案，可以提高处理效率，节约时间。

摘要： 本发明公开了一种基于节点复制的异构多核系统任务调度方法，包括：1根据有向无环图与异构计算消耗表，计算后续步骤需要的参数，并依据参数对任务进行排序，得到任务优先级列表；2按照任务优先级列表将任务依次取出，并把任务分配到不同的内核队列，生成初始布局；3遍历初始布局，对符合节点复制条件的任务节点进行相应的复制操作，生成复制后布局；4遍历复制后布局，在符合wait条件的join节点前补充冗余的wait节点，生成次优布局；5对次优布局进行冗余筛查，删除布局中的冗余任务，生成最优布局。本发明有利于估算并缩短异构环境下并行任务的关键路径，减少任务执行的整体时间，并通过冗余筛查避免无价值的冗余计算。

摘要： 一种用于在分布式数据处理系统中处理任务的方法包括处理任务集。该方法包括在第一处理节点处维护多个计数器，该多个计数器包括：工作计数器，该工作计数器在该分布式数据处理系统中指示该多个时间间隔中的当前时间间隔；以及复制计数器，该复制计数器指示该多个时间间隔中的某个时间间隔，在该时间间隔内，在该多个处理节点中的数个处理节点处复制以下中的至少一个：(1)与该时间间隔相关联的所有任务以及(2)与该时间间隔相关联的所有相应结果。该方法包括从该第一处理节点向该多个处理节点中的其他处理节点提供消息，该消息包括该工作计数器和该复制计数器。

摘要： 基于关键路径和任务复制的单任务多核调度方法。目前多核任务调度算法，在处理器内核不足时无法进行有效调度。本发明方法包括：DAG任务图处理模块，采用任务复制的方法，将DAG任务图中的fork节点复制给其后继任务节点，形成join结构任务图，再进一步将join图转换为产品加工树；任务节点调度分配模块，引入综合调度中关键路径思想，查找产品加工树的关键路径，并优先调度关键路径上节点，尽量提前关键路径上节点开始执行时间；调度序列调整优化模块，采用合并相似度最大的调度序列的方式，将调度序列合并以使调度序列数不大于处理器内核数，实现处理器内核充分并行处理。本发明用于基于片上互连的同构多核处理器单任务多核调度。

摘要： 本发明公开了一种基于任务复制的多复本容错并行任务调度方法，包括如下步骤：首先确定任务节点的优先级，然后考虑优先级最高的任务，最后将该任务分配到能使它最早执行的处理器上。本发明容错能力强，有更短的调度长度，能应对有限处理器环境。

摘要： 基于关键路径和任务复制的单任务多核调度方法。目前多核任务调度算法，在处理器内核不足时无法进行有效调度。 本发明方法包括： DAG 任务图处理模块，采用任务复制的方法，将 DAG 任务图中的 fork 节点复制给其后继任务节点，形成 join 结构任务图，再进一步将 join 图转换为产品加工树；任务节点调度分配模块，引入综合调度中关键路径思想，查找产品加工树的关键路径，并优先调度关键路径上节点，尽量提前关键路径上节点开始执行时间；调度序列调整优化模块，采用合并相似度最大的调度序列的方式，将调度序列合并以使调度序列数不大于处理器内核数，实现处理器内核充分并行处理。本发明用于基于片上互连的同构多核处理器单任务多核调度。

摘要： 本发明涉及一种基于任务复制与聚簇的并行任务分配方法，其特征在于：初始化并对子节点无约束类节点进行复制；应用DCPEZ过程,依据为聚簇的调度不增加原则，对任务进行聚簇，在聚簇关系的基础上对其余可复制节点进行复制；得到最终复制聚簇结果。本发明具有以下优点：PTDADC方法依据调度长度不增加原则，发展了子节点无约束复制的调度长度不增加定理、子结点带约束复制的调度长度不增加原则、动态关键路径聚簇的调度长度不增加原则，从而缩短了任务的执行时间。PTDADC方法遵循了最小化聚簇与复制的原则，减少了处理器的需求数量。

摘要： 本发明公开了一种基于任务复制的多复本容错并行任务调度方法，包括如下步骤：首先确定任务节点的优先级，然后考虑优先级最高的任务，最后将该任务分配到能使它最早执行的处理器上。本发明容错能力强，有更短的调度长度，能应对有限处理器环境。

摘要： 本发明公开了一种边缘计算环境下动态任务复制方法、设备和系统。方法包括：以边缘环境下作业的总完成时间与理想最优复制决策下的作业完成总时延之差regret最小为目标建立优化问题；利用基于多臂赌博机的任务复制决策算法对优化问题进行求解，包括：在第一个时隙开始时，根据任务的任务类型和输入数据的大小来估计任务计算量wt；对每一个任务t，计算将任务t从边缘集群i复制到边缘集群j的时延的置信下限根据确定所有可用的边缘集群，从中选择rt个较小的可用边缘集群作为目标边缘集群，将任务复制到所有目标边缘集群上进行执行。本发明首次将基于多臂赌博机的算法应用于边缘计算系统的任务复制问题，方法具有优秀的时延性能和服务可靠性。