网格计算环境下资源联合分配的映射策略与机制

提出用于网格环境的资源协同调度框架及网格环境下多任务的资源映射策略,用图论中有向无环图解决资源调度过程中任务的优先级限制问题,并在有向无环图上构造兼容图,通过寻找图中最大独立任务集的方法,解决多任务对多资源请求的资源共享问题。给出了网格计算环境下动态资源联合分配的资源管理机制。     

A dominant predecessor duplication scheduling algorithm for heterogeneous systems

This paper proposes a new duplication-based task scheduling algorithm for distributed heterogeneous computing (DHC) systems. For such systems, many researchers have focused on solving the NP-complete problem of scheduling directed acyclic task graphs to minimize the makespan. However, the heterogeneity of computational resources and communication mechanisms poses some major obstacles to achieving high parallel efficiency. This paper proposes a heuristic strategy called the Dominant Predecessor Duplication (DPD) scheduling algorithm, which allows for system heterogeneities and communication bandwidth to exploit the potential of parallel processing. This algorithm can improve system utilization and avoid redundant resource consumption, resulting in better schedules. Experimental results show that the system heterogeneities and program structures of applications affect scheduling performance, and that our presented algorithm is better able to avoid these problems than those presented in previous literature. Here, we show that our algorithm can be applied to design efficient distributed systems to overcome performance bottlenecks caused by system heterogeneities.

On the design of communication-aware fault-tolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication devices

Fault-tolerant scheduling is an imperative step for large-scale computational Grid systems, as often geographically distributed nodes co-operate to execute a task. By and large, primary-backup approach is a common methodology used for fault tolerance wherein each task has a primary and a backup on two different processors. In this paper, we address the problem of how to schedule DAGs in Grids with communication delays so that service failures can be avoided in the presence of processors faults. The challenge is, that as tasks in a DAG have dependence on each other, a task must be scheduled to make sure that it will succeed when any of its predecessors fails due to a processor failure. We first propose a communication model and determine when communications between a backup and backups of its successors are necessary. Then we determine when a backup can start and its eligible processors so as to guarantee that every DAG can complete upon any processor failure. We develop two algorithms to schedule backups, which minimize response time and replication cost, respectively. We also develop a suboptimal algorithm which targets minimizing replication cost while not affecting response time. We conduct extensive simulation experiments to quantify the performance of the proposed algorithms.     

An innovative workflow mapping mechanism for Grids in the frame of Quality of Service

The advent of Grid environments made feasible the solution of computational intensive problems in a reliable and cost-effective way. As workflow systems carry out more complex and mission-critical applications, Quality of Service (QoS) analysis serves to ensure that each application meets user requirements. In that frame, we present a novel algorithm which allows the mapping of workflow processes to Grid provided services assuring at the same time end-to-end provision of QoS based on user-defined parameters and preferences. We also demonstrate the operation of the implemented algorithm and evaluate its effectiveness using a Grid scenario, based on a 3D image rendering application.     

QoS guided Min-Min heuristic for grid task scheduling

Task scheduling is an integrated component of computing.With the emergence of Grid and ubiquitous computing,new challenges appear in task scheduling based on properties such as security,quality of service,and lack of central control within distributed administrative domains.A Grid task scheduling framework must be able to deal with these issues.One of the goals of Grid task scheduling is to achivev high system throughput while matching applications with the available computing resources.This matching of resources in a non-deterministically shared heterogeneous environment leads to concerns over Quality of Service (QoS).In this paper a novel QoS guided task scheduling algorithm for Grid computing is introduced.The proposed novel algorithm is based on a general adaptive scheduling heuristics that includes QoS guidance.The algorithm is evaluated within a simulated Grid environment.The experimental results show that the nwe QoS guided Min-Min heuristic can lead to significant performance gain for a variety of applications.The approach is compared with others based on the quality of the prediction formulated by inaccurate information.     

云计算环境下基于路径优先级的任务调度算法

为了最小化云计算系统的任务调度长度,结合表启发式调度技术和任务复制的思想提出基于路径优先权的任务调度算法.采用一种新方法计算DAG图中任务节点及边的权值,从最高优先权的路径开始依次选择任务进行调度,并通过有选择性地复制任务节点的父任务来减少任务间信息传送的时间花费,最后将任务安排到使其执行完成时间最早的虚拟机上.通过随机产生的DAG图与HEFT算法进行对比分析,实验结果表明了该算法能获得较短的调度长度.     

云中多媒体应用中基于混合DAG的最优任务调度研究

云计算的平台优势使得它在多媒体应用中得到广泛使用。由于多媒体服务的多样性和异构性,如何将多媒体任务有效地调度至虚拟机进行处理成为当前多媒体应用的研究重点。对此,研究了云中多媒体最优任务调度问题,首先引入有向无环图来模拟任务中的优先级及任务之间的依赖性,分别对串行、并行、混合结构任务调度模型进行任务调度研究,根据有限资源成本将关键路径中任务节点融合,提出一种实用的启发式近似最优调度方法。实验结果表明,所提调度方法能够以最短的执行时间在有限的资源成本下完成最优的任务分配。     

An SCP-based heuristic approach for scheduling distributed data-intensive applications on global grids

Data-intensive Grid applications need access to large data sets that may each be replicated on different resources. Minimizing the overhead of transferring these data sets to the resources where the applications are executed requires that appropriate computational and data resources be selected. In this paper, we consider the problem of scheduling an application composed of a set of independent tasks, each of which requires multiple data sets that are each replicated on multiple resources. We break this problem into two parts: one, to match each task (or job) to one compute resource for executing the job and one storage resource each for accessing each data set required by the job and two, to assign the set of tasks to the selected resources. We model the first part as an instance of the well-known Set Covering Problem (SCP) and apply a known heuristic for SCP to match jobs to resources. The second part is tackled by extending existing MinMin and Sufferage algorithms to schedule the set of distributed data-intensive tasks. Through simulation, we experimentally compare the SCP-based matching heuristic to others in conjunction with the task scheduling algorithms and present the results.     

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.     

On-demand minimum cost benchmarking for intermediate dataset storage in scientific cloud workflow systems

Many scientific workflows are data intensive: large volumes of intermediate datasets are generated during their execution. Some valuable intermediate datasets need to be stored for sharing or reuse. Traditionally, they are selectively stored according to the system storage capacity, determined manually. As doing science on clouds has become popular nowadays, more intermediate datasets in scientific cloud workflows can be stored by different storage strategies based on a pay-as-you-go model. In this paper, we build an intermediate data dependency graph (IDG) from the data provenances in scientific workflows. With the IDG, deleted intermediate datasets can be regenerated, and as such we develop a novel algorithm that can find a minimum cost storage strategy for the intermediate datasets in scientific cloud workflow systems. The strategy achieves the best trade-off of computation cost and storage cost by automatically storing the most appropriate intermediate datasets in the cloud storage. This strategy can be utilised on demand as a minimum cost benchmark for all other intermediate dataset storage strategies in the cloud. We utilise Amazon clouds’ cost model and apply the algorithm to general random as well as specific astrophysics pulsar searching scientific workflows for evaluation. The results show that benchmarking effectively demonstrates the cost effectiveness over other representative storage strategies.     

An improved heuristic to minimize total flow time for scheduling in the m-machine no-wait flow shop

In this paper, we present a constructive heuristic to minimize total flow time criterion for the well-known NP-hard no-wait flow shop scheduling problem. It is based on the assumption that the priority of a job in the initial sequence is given by the sum of its processing times on the bottleneck machines. The initial sequence of jobs thus generated is further improved using a new job insertion technique. We show, through computational experimentation, that the proposed method significantly outperforms the best-known heuristics while retaining its time complexity of O(n²). Statistical tests of significance are used to confirm the improvement in solution quality.     

动态服务组合构造与最优组合服务算法研究

服务组合是将已有服务组合为一个新服务的过程,以增加服务的功能或／和性能。本文将组合方案表示为一个有向无环图,节。占、表示服务,边表示服务交互,以目标服务的输入为指标集,给出候选组合方案的构造算法。以服务费用为测度,并计入服务的计算、存储和通信费用。通过费用转移,提出了基于经典Dijkstra算法的最优组合服务算法。     

网格环境下工作流的费用-时间调度算法

开放网格服务架构（OGSA）和计算经济模型的提出,使得动态的、不同QoS的服务支持下的资源调度成为一个复杂且具有挑战性的问题。该文提出了网格环境下基于费用-时间的工作流调度算法,该算法采用动态资源选择策略适应网格计算环境下的动态性和自治性。在追求较小的工作流完成时间的同时,对费用进行了优化。模拟结果显示该调度算法符合计算网格的复杂环境,能够更好地满足不同用户的实际需要。     

云中截止时间动态分配的工作流调度成本优化算法

现如今,如何在满足截止时间约束的前提下降低工作流的执行成本,是云中工作流调度的主要问题之一。三步列表调度算法可以有效解决这一问题。但该算法在截止时间分配阶段只能形成静态的子截止时间。为方便用户部署工作流任务,云服务商为用户提供了的三种实例类型,其中竞价实例具有非常大的价格优势。为解决上述问题,提出了截止时间动态分配的工作流调度成本优化算法(S-DTDA)。该算法利用粒子群算法对截止时间进行动态分配,弥补了三步列表调度算法的缺陷。在虚拟机选择阶段,该算法在候选资源中增加了竞价实例,大大降低了执行成本。实验结果表明,相较于其他经典算法,该算法在实验成功率和执行成本上具有明显优势。综上所述,S-DTDA算法可以有效解决工作流调度中截止时间约束的成本优化问题。     

Joint optimization method for task scheduling time and energy consumption in mobile cloud computing environment

An unheard of growth in mobile data traffic has drawn attention from academia and industry. Mobile cloud computing is an emerging computing paradigm combining cloud computing and mobile networks to alleviate resource-constrained limitations of mobile devices, which can greatly improve network quality of service and efficiency to make good use of available network resource. Mobile cloud computing not only inherits the advantages of strong computing capacity and massive storage of cloud computing, but also overcomes the time and geographical restrictions, bringing benefits for mobile users to offload complex computation to powerful cloud servers for execution anytime and anywhere. To this end, an optimal task workflow scheduling scheme is proposed for the mobile devices, based on the dynamic voltage and frequency scaling technique and the whale optimization algorithm. Through considering three factors: task execution position, task execution sequence, and operating voltage and frequency of mobile devices, this study makes a tradeoff between performance and energy consumption by solving the joint optimization for task completion time and energy consumption simultaneously. Finally, a series of extensive simulation results has demonstrated and verified the scheme has distinguished performance in terms of efficiency and operational cost, providing feasible solutions to similar optimization problems of mobile cloud computing.     

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.     

New Heuristic Distributed Parallel Algorithms for Searching and Planning

This paper proposes new heuristic distributed parallel algorithms for searching and planning,which are based on the concepts of wave concurrent propagations and competitive activation mechanisms.These algorithms are characterized by simplicity and clearness of control strategies for earching,and distinguished abilities in many aspects,such as high speed processing,wide suitability for searching AND/OR implicit graphs,and ease in hardware implementation.     

An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time

We address the two-stage multi-machine assembly scheduling problem. The first stage consists of m independently working machines where each machine produces its own component. The second stage consists of two independent and identical assembly machines. The objective is to come up with a schedule that minimizes total or mean completion time for all jobs. The problem has been addressed in the scheduling literature and several heuristics have been proposed. In this paper, we propose a new heuristic called artificial immune system (AIS). We conduct experimental analysis for comparing the newly proposed heuristic AIS with the best known heuristic in the literature. Experimental results show that our proposed heuristic AIS performs better than the best known existing heuristic. More specifically, our new heuristic AIS reduces the error of the best known heuristic by 60% while the computational times of both AIS and the best known heuristic are almost the same.     

Definition, modelling and simulation of a grid computing scheduling system for high throughput computing

In this paper, we study and compare grid and global computing systems and outline the benefits of having a hybrid system called DIRAC. To evaluate the DIRAC scheduling for high throughput computing, a new model is presented and a simulator was developed for many clusters of heterogeneous nodes belonging to a local network. These clusters are assumed to be connected to each other through a global network and each cluster is managed via a local scheduler which is shared by many users. We validate our simulator by comparing the experimental and analytical results of a M/M/4 queuing system. Next, we do the comparison with a real batch system and we obtain an average error of 10.5% for the response time and 12% for the makespan. We conclude that the simulator is realistic and well describes the behaviour of a large-scale system. Thus we can study the scheduling of our system called DIRAC in a high throughput context. We justify our decentralized, adaptive and opportunistic approach in comparison to a centralized approach in such a context.     

An efficient list-based task scheduling algorithm for heterogeneous distributed computing environment

The task scheduling in heterogeneous distributed computing systems plays a crucial role in reducing the makespan and maximizing resource utilization. The diverse nature of the devices in heterogeneous distributed computing systems intensifies the complexity of scheduling the tasks. To overcome this problem, a new list-based static task scheduling algorithm namely Deadline-Aware-Longest-Path-of-all-Predecessors (DA-LPP) is being proposed in this article. In the prioritization phase of the DA-LPP algorithm, the path length of the current task from all its predecessors at each level is computed and among them, the longest path length value is assigned as the rank of the task. This strategy emphasizes the tasks in the critical path. This well-optimized prioritization phase leads to an observable minimization in the makespan of the applications. In the processor selection phase, the DA-LPP algorithm implements the improved insertion-based policy which effectively utilizes the unoccupied leftover free time slots of the processors which improve resource utilization, further least computation cost allocation approach is followed to minimize the overall computation cost of the processors and parental prioritization policy is incorporated to further reduce the scheduling length. To demonstrate the robustness of the proposed algorithm, a synthetic graph generator is used in this experiment to generate a huge variety of graphs. Apart from the synthetic graphs, real-world application graphs like Montage, LIGO, Cybershake, and Epigenomic are also considered to grade the performance of the DA-LPP algorithm. Experimental results of the DA-LPP algorithm show improvement in performance in terms of scheduling length ratio, makespan reduction rate , and resource reduction rate when compared with other algorithms like DQWS, DUCO, DCO and EPRD. The results reveal that for 1000 task set with deadline equals to two times of the critical path, the scheduling length ratio of the DA-LPP algorithm is better than DQWS by 35%, DUCO by 23%, DCO by 26 %, and EPRD by 17%.