A hybrid heuristic–genetic algorithm for task scheduling in heterogeneous processor networks

Efficient task scheduling on heterogeneous distributed computing systems (HeDCSs) requires the consideration of the heterogeneity of processors and the inter-processor communication. This paper presents a two-phase algorithm, called H2GS, for task scheduling on HeDCSs. The first phase implements a heuristic list-based algorithm, called LDCP, to generate a high quality schedule. In the second phase, the LDCP-generated schedule is injected into the initial population of a customized genetic algorithm, called GAS, which proceeds to evolve shorter schedules. GAS employs a simple genome composed of a two-dimensional chromosome. A mapping procedure is developed which maps every possible genome to a valid schedule. Moreover, GAS uses customized operators that are designed for the scheduling problem to enable an efficient stochastic search. The performance of each phase of H2GS is compared to two leading scheduling algorithms, and H2GS outperforms both algorithms. The improvement in performance obtained by H2GS increases as the inter-task communication cost increases.     

A high performance algorithm for static task scheduling in heterogeneous distributed computing systems

Effective task scheduling is essential for obtaining high performance in heterogeneous distributed computing systems (HeDCSs). However, finding an effective task schedule in HeDCSs requires the consideration of both the heterogeneity of processors and high interprocessor communication overhead, which results from non-trivial data movement between tasks scheduled on different processors. In this paper, we present a new high-performance scheduling algorithm, called the longest dynamic critical path (LDCP) algorithm, for HeDCSs with a bounded number of processors. The LDCP algorithm is a list-based scheduling algorithm that uses a new attribute to efficiently select tasks for scheduling in HeDCSs. The efficient selection of tasks enables the LDCP algorithm to generate high-quality task schedules in a heterogeneous computing environment. The performance of the LDCP algorithm is compared to two of the best existing scheduling algorithms for HeDCSs: the HEFT and DLS algorithms. The comparison study shows that the LDCP algorithm outperforms the HEFT and DLS algorithms in terms of schedule length and speedup. Moreover, the improvement in performance obtained by the LDCP algorithm over the HEFT and DLS algorithms increases as the inter-task communication cost increases. Therefore, the LDCP algorithm provides a practical solution for scheduling parallel applications with high communication costs in HeDCSs.     

基于融合进化计算的网格任务调度算法

在网格计算中,任务调度是一个重要的组成部分。针对网格环境异构、分布等特点,该文结合遗传算法与蚂蚁算法的优点,在双层进化结构基础上,提出了一种基于融合进化计算的网格任务调度算法。模拟实验结果表明：在网格环境下,调度算法具有明显的优势。     

Cooperative scheduling mechanism for large-scale peer-to-peer computing systems

Over recent years, peer-to-peer (P2P) systems have become an important part of Internet. Millions of users have been attracted to their structures and services. P2P computing is a distributed computing paradigm that uses Internet to connect thousands, or even millions, of users into a single large virtual computer based on the sharing of computational resources. One of the most critical aspects to the design of P2P computing systems is the development of scheduling techniques to manage the computational resources efficiently and in a scalable way. This paper proposes a cooperative scheduling mechanism with a two-level topology designed to work on large-scale distributed computing P2P systems. Our main contribution is proposing three criteria that only use local information to schedule tasks thus providing scalability to the overall scheduling system. By setting up these three criteria, the system can be easily adapted to work efficiently with very different kinds of distributed applications. The extensive experimentation carried out justifies the importance of good scheduling in such heterogeneous systems, but also emphasizes the importance of having a scheduling algorithm capable of being adapted to the requirements of different kinds of application.     

基于异构分布式系统的实时容错调度算法

目前文献中研究的实时容错调度算法都是基于同构分布式系统，系统中的所有处理机完全相同。该文首先建立了一个基于异构分布式系统实时容错调度模型，异构分布式系统中的各个处理机均不相同。基于该异构分布式系统模型，该文引入了可靠性代价（reliability cost）概念，并提出两种静态实时容错调度算法（RTFTNO和RTFTRC）用于调度周期性实时容错任务。算法RTFTRC在调度任务时，尽量使系统的可靠性代价最小；而算法RTFTNO在调度实时任务时，没有考虑系统的可靠性代价。该文详细讨论了两种调度算法的性能。性能模拟实验分别比较了两个算法的可靠性代价，超时比率和可调度性；并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系。实验结果表明，算法RTFTRC的性能优于算法RTFTNO。     

网格计算中基于并行克隆遗传算法的任务分配与调度

实现网格计算的一个重要目的在于实现地理分布、异构资源的统一描述方法,提供用户虚拟的统一资源界面,并将用户提出的服务要求透明、动态地分配给最适应的资源上执行。针对目前任务调度的应用现状,提出了一种既能使资源负载均衡又能充分利用系统资源的并行克隆遗传算法,该启发式算法能显著地降低资源最优分配中的计算复杂度,使其能满足实时调度的需要。实验结果表明这种算法优于其他调度算法。     

Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud computing systems

As the cost-driven public cloud services emerge, budget constraint is one of the primary design issues in large-scale scientific applications executed on heterogeneous cloud computing systems. Minimizing the schedule length while satisfying the budget constraint of an application is one of the most important quality of service requirements for cloud providers. A directed acyclic graph (DAG) can be used to describe an application consisted of multiple tasks with precedence constrains. Previous DAG scheduling methods tried to presuppose the minimum cost assignment for each task to minimize the schedule length of budget constrained applications on heterogeneous cloud computing systems. However, our analysis revealed that the preassignment of tasks with the minimum cost does not necessarily lead to the minimization of the schedule length. In this study, we propose an efficient algorithm of minimizing the schedule length using the budget level (MSLBL) to select processors for satisfying the budget constraint and minimizing the schedule length of an application. Such problem is decomposed into two sub-problems, namely, satisfying the budget constraint and minimizing the schedule length. The first sub-problem is solved by transferring the budget constraint of the application to that of each task, and the second sub-problem is solved by heuristically scheduling each task with low-time complexity. Experimental results on several real parallel applications validate that the proposed MSLBL algorithm can obtain shorter schedule lengths while satisfying the budget constraint of an application than existing methods in various situations.     

异构集群下的任务调度算法研究

针对异构集群下高效节能的任务调度算法进行了研究, 提出了一种基于复制的任务调度算法, 在任务初始分配的基础上, 分别从能源感知和性能—能源平衡两个角度考虑任务的复制。建立了由计算和通信造成的能源消耗的数学模型, 并进行了大量的实验。实验结果表明, 与已有的BEATA算法相比, 该算法能明显地减少异构集群处理并行应用的调度长度和能耗。分析结果发现, 任务复制的方法在减少调度长度的同时会增加相应的能耗, 能同比优化调度长度和能耗的任务调度方法是今后的研究方向。     

一种实时异构系统的集成动态调度算法

提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(quality of service)降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.     

Task scheduling for heterogeneous systems using an incremental approach

Effective scheduling of the tasks of a distributed application is one of the key factors in achieving improved performance. It results in an adequate utilization of the underlying resources and also reduces the total execution time of the application. Generating an optimal schedule for a distributed application is not a trivial task as it exists in the class of NP-complete problems. In this paper, a novel strategy called incremental subgraph earliest finish time (INCSEFT) is proposed. It is aimed at scheduling tasks on heterogeneous systems. It incorporates the use of a subgraph that grows incrementally by adding critical paths. At each step, the scheduling strategy attempts to minimize the schedule length. Considering a large set of nodes at an instance makes this approach perform better than other scheduling strategies used for heterogeneous systems. The experiments performed with several graphs show that the INCSEFT strategy produces significant improvement over the well-known HEFT, LOOKAHEAD and CEFT strategies used for scheduling heterogeneous systems.     

DAG Scheduling in Heterogeneous Computing and Grid Environments Using Variable Neighborhood Search Algorithm

DAG scheduling is a process that plans and supervises the execution of interdependent tasks on heterogeneous computing resources. Efficient task scheduling is one of the important factors to improve the performance of heterogeneous computing systems. In this paper, an investigation on implementing Variable Neighborhood Search (VNS) algorithm for scheduling dependent jobs on heterogeneous computing and grid environments is carried out. Hybrid Two PHase VNS (HTPHVNS) DAG scheduling algorithm has been proposed. The performance of the VNS and HTPHVNS algorithm has been evaluated with Genetic Algorithm and Heterogeneous Earliest Finish Time algorithm. Simulation results show that VNS and HTPHVNS algorithm generally perform better than other meta-heuristics methods.     

一种基于双层进化结构的网格任务调度算法

在网格计算中,任务调度是一个重要的组成部分,并被证明为NP完全问题,以启发式方法求解较为适合。针对网格环境异构、分布等特点,本文运用遗传算法原理,结合高度分层排序,提出了一种基于双层进化结构的网格任务调度算法。模拟实验结果表明,在网格异构环境下,本算法优于其它几种算法。     

异构分布式系统混合型实时容错调度算法

基/副版本技术是实现实时分布式系统容错的一个重要手段。提出了一种异构分布式混合型容错模型,该模型与传统的异构分布式实时调度模型相比同时考虑了周期和非周期调度任务。在此基础上给出3种容错调度算法:以可调度性为目的SSA算法、以可靠性为目的RSA算法、以负载均衡性为目的BSA算法。算法能够在异构系统中同时调度具有周期和非周期容错需求的实时任务,且能够保证在异构系统中某节点机失效情况下,实时任务仍然能在截止时间内完成。最后从可调度性、可靠性代价、负载均衡性、周期与非周期任务数及任务周期与粒度J个方面对算法进行了分析。模拟实验结果显示算法各有优缺点,所以在选择调度算法时应该根据异构系统的特点来选择。     

一种无抖动的分布式多媒体任务调度算法

在分布式多媒体系统中,资源的管理和分配算法是保证应用的服务质量（ＱｏＳ）的关键问题,而资源管理中,ＱｏＳ协商和确认都和多媒体任务调芳算法有关,任务调度算法是资源管理的重要内容。现有的调度算法ＥＤＦ,ＲＭ,ＤＳｒ适用在分布式多媒体系统中,有局限性。本文基于风车调度模型,提出了一种无抖动调度的逐步消除候选项的并行算法ＤＭＳｒ,能达到分布系统中多媒体任务周期调度的无抖动特点,并讨论了算法的计算复杂度,证     

List scheduling with duplication for heterogeneous computing systems

Effective task scheduling is essential for obtaining high performance in heterogeneous computing systems (HCS). However, finding an effective task schedule in HCS, requires the consideration of the heterogeneity of computation and communication. To solve this problem, we present a list scheduling algorithm, called Heterogeneous Earliest Finish with Duplicator (HEFD). As task priority is a key attribute for list scheduling algorithm, this paper presents a new approach for computing their priority which considers the performance difference in target HCS using variance. Another novel idea proposed in this paper is to try to duplicate all parent tasks and get an optimal scheduling solution. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithm HEFD significantly surpasses other three well-known algorithms.     

Multi-objective energy-efficient workflow scheduling using list-based heuristics

Workflow applications are a popular paradigm used by scientists for modelling applications to be run on heterogeneous high-performance parallel and distributed computing systems. Today, the increase in the number and heterogeneity of multi-core parallel systems facilitates the access to high-performance computing to almost every scientist, yet entailing additional challenges to be addressed. One of the critical problems today is the power required for operating these systems for both environmental and financial reasons. To decrease the energy consumption in heterogeneous systems, different methods such as energy-efficient scheduling are receiving increasing attention. Current schedulers are, however, based on simplistic energy models not matching the reality, use techniques like DVFS not available on all types of systems, or do not approach the problem as a multi-objective optimisation considering both performance and energy as simultaneous objectives. In this paper, we present a new Pareto-based multi-objective workflow scheduling algorithm as an extension to an existing state-of-the-art heuristic capable of computing a set of tradeoff optimal solutions in terms of makespan and energy efficiency. Our approach is based on empirical models which capture the real behaviour of energy consumption in heterogeneous parallel systems. We compare our new approach with a classical mono-objective scheduling heuristic and state-of-the-art multi-objective optimisation algorithm and demonstrate that it computes better or similar results in different scenarios. We analyse the different tradeoff solutions computed by our algorithm under different experimental configurations and we observe that in some cases it finds solutions which reduce the energy consumption by up to 34.5% with a slight increase of 2% in the makespan.     

Scalable,low complexity,and fast greedy scheduling heuristics for highly heterogeneous distributed computing systems

For heterogeneous distributed computing systems, important design issues are scalability and system optimization. Given such systems, it is crucial to develop low computational complexity algorithms to schedule tasks in a manner that exploits the heterogeneity of the resources and applications. In this paper, we report and evaluate three scalable, and fast scheduling heuristics for highly heterogeneous distributed computing systems. We conduct a comprehensive performance evaluation study using simulation. The benchmarking outlines the performance of the schedulers, representing scalability, makespan, flowtime, computational complexity, and memory utilization. The set of experimental results shows that our heuristics perform as good as the traditional approaches, for makespan and flowtime, while featuring lower complexity, lower running time, and lower used memory. The experimental results also detail the various scenarios under which certain algorithms excel and fail.     

实时异构系统的动态调度算法研究

实时多处理器系统是解决复杂时应用的有效手段,目前对实时多处理器调度算法的研究却大多集中在同构系统上,对实时异构系统的调度则研究得比较少,提出了一种新的实时异构系统的动态调度算法,该算法采用了集中式的调度方案,同时,引入了一个新的任务分配策略,从而通过提高任务可行性而提高了算的调度成功率,此外,为了评估该算法的性能,还进行了大量的模拟研究,由于近视算法经简单修改便可以应用到实时异构系统的动态调度中,因此,在模拟研究中,以近视算法作为基准,将其应用于实时异构系统动态调度时的性能与新算法进行了比较,模拟结果显示,在多种任务参数的取值下,新算法的调度成功率均高于近视算法。     

Supporting schedules of resource co-allocation for distributed computing in scalable systems

This paper proposes a model of scheduling and validates methods of resource co-allocation for distributed computations in scalable systems. Solution of the problem of allocating heterogeneous computing resources for performing complex sets of tasks (jobs) is related to the formation of strategies (families of admissible supporting schedules). The choice of a specific schedule depends on the nature of events occurring in the distributed environment and related primarily to the load and accessibility of computing nodes.     

一个调度Out-Tree任务图的启发式算法

任务调度问题是并行分布式计算中的挑战性问题之一。大多数实际的调度算法是启发式的因而常常具有改进的余地。针对Out-Tree任务图这一基本结构提出一个基于任务复制的启发式调度算法,该算法在确保最短调度长度的同时,注重处理器的负载平衡,以达到节约处理器的目的。比较性实验的结果表明,该算法确保了最短调度长度且使用的处理器最少。因而,该算法提高了系统的利用率,避免消耗过多的资源,实际应用性更好。