A minimized makespan scheduler with multiple factors for Grid computing systems

Most scheduling heuristics applied to Heterogeneous Computing (HC) focus on the search of a minimum makespan, instead of the reduction of cost. However, relevant studies presume that HC is based on high-speed bandwidth and communication time has ignored. Furthermore, in response to the appeal for a user-pay policy, when a user submits a job to a Grid environment for computation each implementation of a job would be charged. Therefore, the Apparent Tardiness Cost Setups-Minimum Completion Time (ATCS-MCT) scheduling heuristic considers both makespan and cost, and it composes of execution time, communication time, weight and deadline factors. This study simulates experiments in a dynamic environment, due to the nature of Grid computing being dynamic. The ATCS-MCT is compared to frequent solutions by five scheduling heuristics. This study indicates that the ATCS-MCT achieves a similarly smaller makespan, and lower cost than Minimum Completion Time (MCT) scheduling heuristic, which is the benchmark of on-line mapping.     

一种基于虚拟截止时间制导的改进的Min-Min元任务调度算法

在网格环境下,资源状况和用户行为相当复杂,是一个异构计算环境,元任务（meta—task）调度比传统并行调度更为复杂。如何映射一组任务到一组机器上被证明是NP问题,其目的一般是最小化任务完成时间（makespan）。为解决这一问题,已经提出一些启发式任务调度算法,例如具有代表性的MinMin元任务调度算法。本文在Min-Min元任务调度算法的基础上,通过虚拟截止时间制导的方法来改进Min-Min算法。实验结果表明,本文提出的算法具有更短的任务完成时间。     

Robust static allocation of resources for independent tasks under makespan and dollar cost constraints

Heterogeneous computing (HC) systems composed of interconnected machines with varied computational capabilities often operate in environments where there may be inaccuracies in the estimation of task execution times. Makespan (defined as the completion time for an entire set of tasks) is often the performance feature that needs to be optimized in such systems. Resource allocation is typically performed based on estimates of the computation time of each task on each class of machines. Hence, it is important that makespan be robust against errors in computation time estimates. In this research, the problem of finding a static mapping of tasks to maximize the robustness of makespan against the errors in task execution time estimates given an overall makespan constraint is studied. Two variations of this basic problem are considered: (1) where there is a given, fixed set of machines, (2) where an HC system is to be constructed from a set of machines within a dollar cost constraint. Six heuristic techniques for each of these variations of the problem are presented and evaluated.     

Queue Waiting Time Aware Dynamic Workflow Scheduling in Multicluster Environments

Workflows are prevailing in scientific computation. Multicluster environments emerge and provide more resources, benefiting workflows but also challenging the traditional workflow scheduling heuristics. In a multicluster environment, each cluster has its own independent workload management system. Jobs are queued up before getting executed, they experience different resource availability and wait time if dispatched to different clusters. However, existing scheduling heuristics neither consider the queue wait time nor balance the performance gain with data movement cost. The proposed algorithm leverages the advancement of queue wait time prediction techniques and empirically studies if the tunability of resource requirements helps scheduling. The extensive experiment with both real workload traces and test bench shows that the queue wait time aware algorithm improves workflow performance by 3 to 10 times in terms of average makespan with relatively very low cost of data movement.     

Dependable Grid Workflow Scheduling Based on Resource Availability

Due to the highly dynamic feature, dependable workflow scheduling is critical in the Grid environment. Various scheduling algorithms have been proposed, but seldom consider the resource reliability. Current Grid systems mainly exploit fault tolerance mechanism to guarantee the dependable workflow execution, which, however, wastes system resources. The paper proposes a dependable Grid workflow scheduling system (called DGWS). It introduces a Markov Chain-based resource availability prediction model. Based on the model, a reliability cost driven workflow scheduling algorithm is presented. The performance evaluation results, including the simulation on both parametric randomly generated DAGs and two real scientific workflow applications, demonstrate that compared to present workflow scheduling algorithms, DGWS improves the success ratio of tasks and diminishes the makespan of workflow, so improves the dependability of workflow execution in the dynamic Grid environments.     

基于Petri网的网格调度模型研究

网格环境具有异构性、动态性和不可靠性,为了合理而经济地利用资源,本文提出一个基于QoS且具有容错性的任务调度算法,以时间和费用的预算以及时间和费用的权重比值作为QoS参数。使计算过程和通信过程重叠,以隐藏网络时延。本文用随机Petri网模型描述网格环境中的任务调度模型;定义了随机Petfi肉的可达图,用来分析任务调度模型的性能。通过分析和模拟,反映此算法能够在满足用户的时间和费用的限制,具有容错性,任务完成时间短,以及综合花费少等优点。     

Meeting security and user behavior requirements in Grid scheduling

Most of current research in Grid computing is still focused on the improvement of the performance of Grid schedulers. However, unlike traditional scheduling, in Grid systems there are other important requirements to be taken into account. One such a requirement is the secure scheduling, namely achieving an efficient allocation of tasks to reasonable trustful resources. In this paper we formalize the Grid scheduling problem as a non-cooperative non-zero sum game of the Grid users in order to address the security requirements. The premise of this model is that in a large-scale Grid, the cooperation among all users in the system is unlikely to happen. The users’ cost of playing the game is interpreted as a total cost of the secure job execution in Grid. The game cost function is minimized, at global (Grid) and local (users) levels, by using four genetic-based hybrid meta-heuristics. We have evaluated the proposed model under the heterogeneity, the large-scale and dynamics conditions using a Grid simulator. The relative performance of four hybrid schedulers is measured by the makespan and flowtime metrics. The obtained results suggested that it is more resilient for the Grid users to pay some additional scheduling cost, due to verification of the security conditions, instead of taking the risk of assigning their tasks to unreliable resources.     

Scheduling jobs under decreasing linear deterioration

This paper considers the scheduling problems under decreasing linear deterioration. Deterioration of a job means that its processing time is a function of its execution start time. Optimal algorithms are presented respectively for single machine scheduling of minimizing the makespan, maximum lateness, maximum cost and number of late jobs. For two-machine flow shop scheduling problem to minimize the makespan, it is proved that the optimal schedule can be obtained by Johnson's rule. If the processing times of operations are equal for each job, flow shop scheduling problems can be transformed into single machine scheduling problems.     

Ant colony optimization for multi-objective flow shop scheduling problem

Flow shop scheduling problem consists of scheduling given jobs with same order at all machines. The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, multi-objective approach for scheduling to reduce the total scheduling cost is important. Hence, in this study, we consider the flow shop scheduling problem with multi-objectives of makespan, total flow time and total machine idle time. Ant colony optimization (ACO) algorithm is proposed to solve this problem which is known as NP-hard type. The proposed algorithm is compared with solution performance obtained by the existing multi-objective heuristics. As a result, computational results show that proposed algorithm is more effective and better than other methods compared.     

Enhancing list scheduling heuristics for dependent job scheduling in grid computing environments

Job scheduling plays a critical role in resource utilisation in a grid computing environment. The heterogeneity of grid resources adds some challenges to the work of job scheduling especially when jobs have dependencies which can be represented as Direct Acyclic Graphs (DAGs). Heuristics have been developed for job scheduling optimisation. This paper presents six heuristic enhancements—MMSTFT for minimising both makespan and task finish time, levelU for upward DAG levelling, TMWD for matching tasks with data, Slack for prioritising task scheduling based on slack time, LSlack for levelling the Slack heuristic, and NLPETS for non-levelling of performance effective task scheduling (PETS). The performance of LSlack is amongst the best heuristics evaluated (with BL and LMT). Additionally, heuristic enhancements MMSTS and TMWD can significantly improve the makespan of generated schedules. To facilitate performance evaluation, a DAG simulator is implemented which provides a set of tools for DAG job configuration, execution and monitoring. The components of the DAG simulator are also presented in this paper.     

Data Intensive and Network Aware (DIANA) Grid Scheduling

In Grids scheduling decisions are often made on the basis of jobs being either data or computation intensive: in data intensive situations jobs may be pushed to the data and in computation intensive situations data may be pulled to the jobs. This kind of scheduling, in which there is no consideration of network characteristics, can lead to performance degradation in a Grid environment and may result in large processing queues and job execution delays due to site overloads. In this paper we describe a Data Intensive and Network Aware (DIANA) meta-scheduling approach, which takes into account data, processing power and network characteristics when making scheduling decisions across multiple sites. Through a practical implementation on a Grid testbed, we demonstrate that queue and execution times of data-intensive jobs can be significantly improved when we introduce our proposed DIANA scheduler. The basic scheduling decisions are dictated by a weighting factor for each potential target location which is a calculated function of network characteristics, processing cycles and data location and size. The job scheduler provides a global ranking of the computing resources and then selects an optimal one on the basis of this overall access and execution cost. The DIANA approach considers the Grid as a combination of active network elements and takes network characteristics as a first class criterion in the scheduling decision matrix along with computations and data. The scheduler can then make informed decisions by taking into account the changing state of the network, locality and size of the data and the pool of available processing cycles.     

A stochastic model for heterogeneous computing and its applicationin data relocation scheme development

In a dedicated, mixed-machine, heterogeneous computing (HC) system, an application program may be decomposed into subtasks, then each subtask assigned to the machine where it is best suited for execution. Data relocation is defined as selecting the sources for needed data items. It is assumed that multiple independent subtasks of an application program can be executed concurrently on different machines whenever possible. A theoretical stochastic model for HC Is proposed, in which the computation times of subtasks and communication times for intermachine data transfers can be random variables. The optimization problem for finding the optimal matching, scheduling, and data relocation schemes to minimize the total execution time of an application program is defined based on this stochastic HC model. The global optimization criterion and search space for the above optimization problem are described. It is validated that a greedy algorithm-based approach can establish a local optimization criterion for developing data relocation heuristics. The validation is provided by a theoretical proof based on a set of common assumptions about the underlying HC system and application program. The local optimization criterion established by the greedy approach, coupled with the search space defined for choosing valid data relocation schemes, can help developers of future practical data relocation heuristics     

Minimizing the application execution time through scheduling ofsubtasks and communication traffic in a heterogeneous computing system

In a heterogeneous computing (HC) environment consisting of different types of machines, an application program is decomposed into subtasks, each of which is computationally homogeneous. The goal is to execute subtasks on the machines in such a way that the total program execution time is minimized. A mathematical framework is presented that models the matching of subtasks to machines, scheduling of subtasks' computation, scheduling of intermachine communication steps, and selection of sources of shared data items for intermachine communication (data relocation). The goal of this work is to generate a provably optimal scheme for communicating shared data among subtasks as an enhancement to any given matching and scheduling. Initially, it is assumed that at any instant in time, only one machine is being used for program execution and only one subtask is being executed. Based on this assumption, a polynomial algorithm is introduced to optimize scheduling and data relocation with respect to any given matching of subtasks to machines. The data relocation scheme is then extended to reduce intermachine data communication time in an HC environment with a given matching and scheduling of subtasks' computation where: multiple subtasks' computations can be performed concurrently on different machines; subtask computation steps can be overlapped with other subtasks' communication steps for intermachine data transfers; and machines in the HC suite are interconnected by a shared-bus type of network     

Multi-objective list scheduling of workflow applications in distributed computing infrastructures

Executing large-scale applications in distributed computing infrastructures (DCI), for example modern Cloud environments, involves optimization of several conflicting objectives such as makespan, reliability, energy, or economic cost. Despite this trend, scheduling in heterogeneous DCIs has been traditionally approached as a single or bi-criteria optimization problem. In this paper, we propose a generic multi-objective optimization framework supported by a list scheduling heuristic for scientific workflows in heterogeneous DCIs. The algorithm approximates the optimal solution by considering user-specified constraints on objectives in a dual strategy: maximizing the distance to the user’s constraints for dominant solutions and minimizing it otherwise. We instantiate the framework and algorithm for a four-objective case study comprising makespan, economic cost, energy consumption, and reliability as optimization goals. We implemented our method as part of the ASKALON environment (Fahringer et al., 2007) for Grid and Cloud computing and demonstrate through extensive real and synthetic simulation experiments that our algorithm outperforms related bi-criteria heuristics while meeting the user constraints most of the time.     

Reputation-based dependable scheduling of workflow applications in Peer-to-Peer Grids

Grids facilitate creation of wide-area collaborative environment for sharing computing or storage resources and various applications. Inter-connecting distributed Grid sites through peer-to-peer routing and information dissemination structure (also known as Peer-to-Peer Grids) is essential to avoid the problems of scheduling efficiency bottleneck and single point of failure in the centralized or hierarchical scheduling approaches. On the other hand, uncertainty and unreliability are facts in distributed infrastructures such as Peer-to-Peer Grids, which are triggered by multiple factors including scale, dynamism, failures, and incomplete global knowledge.In this paper, a reputation-based Grid workflow scheduling technique is proposed to counter the effect of inherent unreliability and temporal characteristics of computing resources in large scale, decentralized Peer-to-Peer Grid environments. The proposed approach builds upon structured peer-to-peer indexing and networking techniques to create a scalable wide-area overlay of Grid sites for supporting dependable scheduling of applications. The scheduling algorithm considers reliability of a Grid resource as a statistical property, which is globally computed in the decentralized Grid overlay based on dynamic feedbacks or reputation scores assigned by individual service consumers mediated via Grid resource brokers. The proposed algorithm dynamically adapts to changing resource conditions and offers significant performance gains as compared to traditional approaches in the event of unsuccessful job execution or resource failure. The results evaluated through an extensive trace driven simulation show that our scheduling technique can reduce the makespan up to 50% and successfully isolate the failure-prone resources from the system.     

Iterative-Improvement-Based Heuristics for Adaptive Scheduling of Tasks Sharing Files on Heterogeneous Master-Slave Environments

The scheduling of independent but file-sharing tasks on heterogeneous master-slave platforms has recently found important applications in Grid environments. The scheduling heuristics recently proposed for this problem are all constructive in nature and based on a common greedy criterion which depends on the momentary completion time values of the tasks. We show that this greedy decision criterion has shortcomings in exploiting the file-sharing interaction among tasks since completion time values are inadequate to extract the global view of this interaction. We propose a three-phase scheduling approach which involves initial task assignment, refinement, and execution ordering phases. For the refinement phase, we model the target application as a hypergraph and, with an elegant hypergraph-partitioning-like formulation, we propose using iterative-improvement-based heuristics for refining the task assignments according to two novel objective functions. Unlike the turnaround time, which is the actual schedule cost, the smoothness of proposed objective functions enables the use of iterative-improvement-based heuristics successfully since their effectiveness and efficiency depend on the smoothness of the objective function. Experimental results on a wide range of synthetically generated heterogeneous master-slave frameworks show that the proposed three-phase scheduling approach performs much better than the greedy constructive approach.     

Dynamic Load Balancing and Pricing in Grid Computing with Communication Delay

Due to the emergence of Grid computing over the Internet, there is presently a need for dynamic load balancing algorithms which take into account the characteristics of Grid computing environments. In this paper, we consider a Grid architecture where computers belong to dispersed administrative domains or groups which are connected with heterogeneous communication bandwidths. We address the problem of determining which group an arriving job should be allocated to and how its load can be distributed among computers in the group to optimize the performance. We propose algorithms which guarantee finding a load distribution over computers in a group that leads to the minimum response time or computational cost. We then study the effect of pricing on load distribution by considering a simple pricing function. We develop three fully distributed algorithms to decide which group the load should be allocated to, taking into account the communication cost among groups. These algorithms use different information exchange methods and a resource estimation technique to improve the accuracy of load balancing. We conducted extensive simulations to evaluate the performance of the proposed algorithms and strategies.     

Autonomic Clouds on the Grid

Computational clouds constructed on top of existing Grid infrastructure have the capability to provide different entities with customized execution environments and private scheduling overlays. By designing these clouds to be autonomically self-provisioned and adaptable to changing user demands, user-transparent resource flexibility can be achieved without substantially affecting average job sojourn time. In addition, the overlay environment and physical Grid sites represent disjoint administrative and policy domains, permitting cloud systems to be deployed non-disruptively on an existing production Grid. Private overlay clouds administered by, and dedicated to the exclusive use of, individual Virtual Organizations are termed Virtual Organization Clusters. A prototype autonomic cloud adaptation mechanism for Virtual Organization Clusters demonstrates the feasibility of overlay scheduling in dynamically changing environments. Commodity Grid resources are autonomically leased in response to changing private scheduler loads, resulting in the creation of virtual private compute nodes. These nodes join a decentralized private overlay network system called IPOP (IP Over P2P), enabling the scheduling and execution of end user jobs in the private environment. Negligible overhead results from the addition of the overlay, although the use of virtualization technologies at the compute nodes adds modest service time overhead (under 10%) to computationally-bound Grid jobs. By leasing additional Grid resources, a substantial decrease (over 90%) in average job queuing time occurs, offsetting the service time overhead.     

Job scheduling and processor allocation for grid computing on metacomputers

Scheduling is a fundamental issue in achieving high performance on metacomputers and computational grids. For the first time, the job scheduling problem for grid computing on metacomputers is studied as a combinatorial optimization problem. A cost model is proposed for modeling communication heterogeneity on computational grids. A processor allocation algorithm is developed which always finds an optimal processor allocation that minimizes the effective execution time of a job when the job is being scheduled. It is proven that the list scheduling (LS) algorithm can achieve reasonable worst-case performance bound in grid environments supporting distributed supercomputing with large applications. We compare the performance of various job scheduling and processor allocation algorithms for grid computing on metacomputers. We evaluate the performance of 128 combinations of two job scheduling algorithms, four initial job ordering strategies, four processor allocation algorithms, and four metacomputers by extensive simulation. It is found that the combination of largest job first (LJF) initial job ordering and minimum effective execution time (MEET) or largest machine first (LMF) processor allocation algorithm yields the best average-case performance, and the choice of FCFS and LS depends on the range of job sizes. It is also observed that communication heterogeneity does have significant impact on schedule lengths.