Energy‐efficient scheduling algorithms for batch‐of‐tasks (BoT) applications on heterogeneous computing systems

One of the major design constraints of a heterogeneous computing system is optimal scheduling, that is, mapping of tasks on the processing nodes in order to optimize the QoS parameters. Because of the huge energy consumption by computing resources, negative environmental effects and reduced system reliability, energy has unavoidably been added as a new parameter to the list of QoS parameters. Energy optimization in scheduling strategies along with makespan makes it an even more challenging combinatorial optimization problem. This work proposes two energy‐aware scheduling algorithms G1 and G2 to schedule a batch‐of‐tasks, made of a collection of independent tasks, on heterogeneous processors in order to minimize the makespan and the energy consumption. The proposed algorithms schedule tasks based on weighted aggregation cost function to the appropriate processors followed by task migration phase designed to further minimize the makespan and the energy consumption. The study evaluates the performance of the proposed algorithms with some of the peers, that is, MinMin, MINSuff on account of makespan, energy consumption, flowtime, and utilization. An experimental study reveals that the proposed algorithm (G2) consistently performs better under various test conditions. Copyright © 2015 John Wiley & Sons, Ltd.     

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.     

Improved Chameleon Swarm Optimization-Based Load Scheduling for IoT-Enabled Cloud Environment

Internet of things (IoT) and cloud computing (CC) becomes widespread in different application domains such as business, e-commerce, healthcare, etc. The recent developments of IoT technology have led to an increase in large amounts of data from various sources. In IoT enabled cloud environment, load scheduling remains a challenging process which is applied for ensuring network stability with maximum resource utilization. The load scheduling problem was regarded as an optimization problem that is solved by metaheuristics. In this view, this study develops a new Circle Chaotic Chameleon Swarm Optimization based Load Scheduling (C3SOA-LS) technique for IoT enabled cloud environment. The proposed C3SOA-LS technique intends to effectually schedule the tasks and balance the load uniformly in such a way that maximum resource utilization can be accomplished. Besides, the presented C3SOA-LS model involves the design of circle chaotic mapping (CCM) with the traditional chameleon swarm optimization (CSO) algorithm for improving the exploration process, shows the novelty of the work. The proposed C3SOA-LS model computes an objective with the minimization of energy consumption and makespan. The experimental outcome implied that the C3SOA-LS model has showcased improved performance and uniformly balances the load over other approaches.     

一种负载均衡的网格在线调度算法

任务调度是网格领域的一个核心问题。针对网格资源及任务高度异构环境下的负载失衡问题,设计一种负载均衡的在线任务调度算法BOS。BOS算法在进行任务调度时,综合考虑任务到达频率、任务计算量、任务的完成时刻以及任务开始执行时刻等因素。任务周转时间由执行时间和等待时间2个部分组成。对于长任务,执行时间占更大比重。而对于短任务,等待时间的影响更大。算法根据长任务和短任务的各自特点,引入适应度的概念来指导调度。实验结果表明,与MCT算法相比,BOS算法的调度跨度、任务周转时间、响应比更小,资源利用率更高,负载也更加均衡。     

Task scheduling using NSGA II with fuzzy adaptive operators for computational grids

Scheduling algorithms have an essential role in computational grids for managing jobs, and assigning them to appropriate resources. An efficient task scheduling algorithm can achieve minimum execution time and maximum resource utilization by providing the load balance between resources in the grid. The superiority of genetic algorithm in the scheduling of tasks has been proven in the literature. In this paper, we improve the famous multi-objective genetic algorithm known as NSGA-II using fuzzy operators to improve quality and performance of task scheduling in the market-based grid environment. Load balancing, Makespan and Price are three important objectives for multi-objective optimization in the task scheduling problem in the grid. Grid users do not attend load balancing in making decision, so it is desirable that all solutions have good load balancing. Thus to decrease computation and ease decision making through the users, we should consider and improve the load balancing problem in the task scheduling indirectly using the fuzzy system without implementing the third objective function. We have used fuzzy operators for this purpose and more quality and variety in Pareto-optimal solutions. Three functions are defined to generate inputs for fuzzy systems. Variance of costs, variance of frequency of involved resources in scheduling and variance of genes values are used to determine probabilities of crossover and mutation intelligently. Variance of frequency of involved resources with cooperation of Makespan objective satisfies load balancing objective indirectly. Variance of genes values and variance of costs are used in the mutation fuzzy system to improve diversity and quality of Pareto optimal front. Our method conducts the algorithm towards best and most appropriate solutions with load balancing in less iteration. The obtained results have proved that our innovative algorithm converges to Pareto-optimal solutions faster and with more quality.     

基于任务复制的网格任务调度算法

网格中资源之间存在着通信延迟,通过任务复制的冗余,可以减少任务之间的通信开销,缩短整个计算程序的计算时间。目前网格中的任务调度算法基本上是没有考虑任务复制的;而基于任务复制调度算法往往会产生过多的复制任务,增大系统开销,甚至有可能延迟计算时间。由于基于任务复制的任务调度是一个NP问题,因此本文提出了一种基于任务复制的网格资源调度算法,以减少调度长度为主要目标、减少任务复制量和资源占用量为次要目标。该算法在调度长度和任务复制数量以及占用资源数量方面都等于或优于其它算法。     

一种改进的启发式网格任务调度算法

网格任务调度算法是影响网格成功与否的关键技术之一。网格计算中,一个好的任务调度算法不但要考虑所有任务的makespan,使其值尽量小,同样要考虑到整个系统机器间的负载平衡问题。文章对异构计算环境下的元任务调度算法进行了分析,针对Min-min算法可能引发的负载不平衡问题,结合网格计算环境的特点,提出了一种适用于网格计算环境中的任务调度算法。     

信任驱动的网格调度算法

针对目前网格资源管理中任务与资源匹配问题的不足,基于信任效益函数与匹配概念,提出了信任驱动的网格调度匹配算法。在调度中同时还考虑了任务和资源效益值,对已经提出的两种信任驱动的网格调度算法进行改进。结果证明:该算法较传统基于的信任驱动调度算法而言,信任效益值,资源效益值,负载平衡和失效服务数等方面有较好的综合性能。     

Honey bee behavior inspired load balancing of tasks in cloud computing environments

Scheduling of tasks in cloud computing is an NP-hard optimization problem. Load balancing of non-preemptive independent tasks on virtual machines (VMs) is an important aspect of task scheduling in clouds. Whenever certain VMs are overloaded and remaining VMs are under loaded with tasks for processing, the load has to be balanced to achieve optimal machine utilization. In this paper, we propose an algorithm named honey bee behavior inspired load balancing (HBB-LB), which aims to achieve well balanced load across virtual machines for maximizing the throughput. The proposed algorithm also balances the priorities of tasks on the machines in such a way that the amount of waiting time of the tasks in the queue is minimal. We have compared the proposed algorithm with existing load balancing and scheduling algorithms. The experimental results show that the algorithm is effective when compared with existing algorithms. Our approach illustrates that there is a significant improvement in average execution time and reduction in waiting time of tasks on queue.     

Fitness rate-based rider optimization enabled for optimal task scheduling in cloud

ABSTRACT

Not long ago, there has been a dramatic augment in the attractiveness of cloud computing systems that depends computing resources on-demand, bill on a pay-as-you-go basis, and multiplex many users on the same physical infrastructure. It is considered as an essential pool of resources, which are offered to users through Internet. Without troubling the fundamental infrastructure, pay-per-use computing resources are provided to the users by the cloud computing technology. Scheduling is a significant dilemma in cloud computing as a cloud provider has to serve multiple users in cloud environment. This proposal plans to implement an optimal task scheduling model in cloud sector as a challenge over the existing technologies. The proposed model solves the task scheduling problem using an improved meta-heuristic algorithm called Fitness Rate-based Rider Optimization Algorithm (FR-ROA), which is the advanced form of conventional Rider Optimization Algorithm (ROA). The objective constraints considered for optimal task scheduling are the maximum makespan or completion time, and the sum of the completion times of entire tasks. Since the proposed FR-ROA has attained the advantageous part of reaching the convergence in a small duration, the proposed model will outperform the other conventional algorithms for accomplishing the optimal task scheduling in cloud environment.     

虚拟计算环境中的多机群协同调度算法

基于虚拟计算环境的核心机理,提出由自主调度单元、域调度共同体、元调度执行体为核心的多机群协同系统框架.剖析多机群任务并发运行性能模型,设计了多机群协同调度算法框架,提出最大空闲节点优先、最小网络拥塞优先、最小异构因子优先与最小异构空闲节点优先4种启发式资源选择策略.实验验证了协同调度模型与算法在任务集完成时间与系统平均利用率的测度上的有效性.     

基于动态能量感知的云计算任务调度模型

针对传统云计算任务调度模型出现的计算量大、能耗高、效率低、调配精度差等问题,基于动态能量感知设计了一种新的云计算任务调度模型;以动态能量感知为基础,选取资源分配服务器的中央处理器的使用率、存储器的占用率、控制器的负载率等3个参数,构建三维云计算任务节点投影空间,将上述参数向量投影到空间中;引入动态能量感知建立云计算任务调度模型,采用虚拟技术将多个服务器合并成一台服务器,对调度任务进行需求分析和分类,采用能量感知算法将待调度任务分配给满足调度需求的虚拟资源,将任务调度到服务器资源上,实现任务调度;实验结果表明,基于动态能量感知的云计算任务调度模型在从小任务集和大任务集两个角度都能给有效缩短调度时间,降低调度能耗。     

物联网环境下具有顺序约束关系的静态任务表调度算法

针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。     

网格计算中任务调度算法的研究和改进

任务调度一直是网格计算中的热点问题,任务调度的目的是最优地分配任务,实现最佳的调度策略,以高效地完成计算任务。在网格环境中,资源的合理有效利用是实现任务调度的关键问题之一。本文首先论述静态任务调度算法和动态任务算法的原理和优缺点等,然后结合Min-min、Max-min算法的优点设计一种新的调度算法SA-MM,根据资源的使用情况自适应调度相应算法进行任务到资源的映射。最后,用GridSim模拟工具对网格计算中Min-min、Max-min和SA-MM任务调度算法进行仿真实验,分析和比较它们的调度长度(MakeSpan)和资源负载情况等影响任务调度效率的指标。     

Security‐aware scheduling model for computational grid

Grid applications with stringent security requirements introduce challenging concerns because the schedule devised by nonsecurity‐aware scheduling algorithms may suffer in scheduling security constraints tasks. To make security‐aware scheduling, estimation and quantification of security overhead is necessary. The proposed model quantifies security, in the form of security levels, on the basis of the negotiated cipher suite between task and the grid‐node and incorporates it into existing heuristics MinMin and MaxMin to make it security‐aware MinMin(SA) and MaxMin(SA). It also proposes SPMaxMin (Security Prioritized MinMin) and its comparison with three heuristics MinMin(SA), MaxMin(SA), and SPMinMin on heterogeneous grid/task environment. Extensive computer simulation results reveal that the performance of the various heuristics varies with the variation in computational and security heterogeneity. Its analysis over nine heterogeneous grid/task workload situations indicates that an algorithm that performs better for one workload degrades in another. It is conspicuous that for a particular workload one algorithm gives better makespan while another gives better response time. Finally, a security‐aware scheduling model is proposed, which adapts itself to the dynamic nature of the grid and picks the best suited algorithm among the four analyzed heuristics on the basis of job characteristics, grid characteristics, and desired performance metric. Copyright © 2011 John Wiley & Sons, Ltd.     

云计算环境下对资源聚类的工作流任务调度算法

针对云计算环境中资源具有规模庞大、异构性、多样性等特点,提出了一种对资源进行模糊聚类的工作流任务调度算法。经过对网络资源属性进行量化、规范化,以预先构建的任务模型和资源模型为基础,结合模糊数学理论划分资源,使得在任务调度时能够较准确地优先选择综合性能较好的资源类簇,缩短了任务资源相匹配的时间,提高了调度性能。通过仿真实验将此算法与HEFT、DLS进行比较,实验结果表明,当任务在[0,100]范围增加时,该算法平均SLR比HEFT小34%,比DLS小99%,其平均Speedup比HEFT大59%,比DLS大102%;当资源在[0,100]范围增加时,该算法平均SLR比HEFT小36%,比DLS小97%,其平均Speedup比HEFT大45%,比DLS大108%。所提算法实现了对资源的合理划分,且在执行跨度方面具有优越性。     

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.     

Security Driven Scheduling Model for Computational Grid Using NSGA-II

Number of software applications demands various levels of security at the time of scheduling in Computational Grid. Grid may offer these securities but may result in the performance degradation due to overhead in offering the desired security. Scheduling performance in a Grid is affected by the heterogeneities of security and computational power of resources. Customized Genetic Algorithms have been effectively used for solving complex optimization problems (NP Hard) and various heuristics have been suggested for solving Multi-objective optimization problems. In this paper a security driven, elitist non-dominated sorting genetic algorithm, Optimal Security with Optimal Overhead Scheduling (OSO₂S), based on NSGA-II, is proposed. The model considers dual objectives of minimizing the security overhead and maximizing the total security achieved. Simulation results exhibit that the proposed algorithm delivers improved makespan and lesser security overhead in comparison to other such algorithms viz. MinMin, MaxMin, SPMinMin, SPMaxMin and SDSG.     

Research on the collaboration of service selection and resource scheduling for IoT simulation workflows

Cloud resources provide a promising way to efficiently perform the needed simulation tasks for a complex manufacturing process. Most of the existing work focuses only on how to effectively schedule computing resources to execute computing requirements of simulation workflows in Internet of Things (IoT) applications. Research on the scheduling of simulation workflows in consideration of task ordering, service selection, and resource allocation altogether has not been lacking. To fill in this void, this paper proposes a cloud-based 3-stage workflow scheduling model. Before scheduling computing resources to complete task requirements, the order of the tasks is determined and the services that can meet the task requirements are selected. In this model, the workload to satisfy task requirements is not fixed and takes on a different value depending upon the service selected with its unique complexity and accuracy. An optimization function that transforms and integrates makespan, cost, and accuracy in a unique way is proposed. For its solution, the relatively new symbiotic organisms search (SOS) algorithm is modified and two SOS-based optimization strategies are developed, i.e., joint optimization-based SOS (JOSOS) and split optimization-based SOS (SOSOS). The simulation results reveal that SOS-based algorithms, especially the SOSOS method, outperform all compared algorithms. Based on the proposed method, simulation services and computing resources can be rationally selected and scheduled to ensure the requirements of IoT applications.     

一种用于异构环境中任务调度的高效算法

在异构计算环境中,有效的任务调度对于获得高性能是十分重要的。现在虽然已经有许多异构处理器调度算法,但它们或者不具有良好的效果,或者算法代价太高。提出了一种新的基于表的调度算法APS。APS利用有向无环图来计算任务优先级,并采用基于调度的策略分配任务到不同处理器,以获得任务最少完工时间。将APS和LMT,HEFT,CPOP算法做比较之后得出：在大多数情况下APS算法都能获得更好性能。