Lower bound algorithms for multiprocessor task scheduling with ready times

In this paper, we deal with multiprocessor task scheduling with ready times and prespecified processor allocation. We consider an on‐line scenario where tasks arrive over time, and, at any point in time, the scheduler only has knowledge of the released tasks. An application of this problem arises in wavelength division multiplexing broadcasting where the main future will be in the so‐called one‐to‐many transmission. We propose algorithms to find lower bounds of the minimum makespan, and present experiments on various scenarios.     

多处理器系统可靠性约束下的节能调度算法

针对多处理器系统中随机到达的任务,设计了可靠性约束下的节能调度算法(ESACR)。该算法在满足任务截止期限的前提下选择一个预计产生能耗最小的处理器以节能,在单个处理器上运用最早截止期限优先策略进行调度并尽量使各个任务的执行电压/频率均衡,当新到任务在处理器上不能满足截止期限要求时则逐个调高前面未执行任务的电压/频率。同时,为保证系统的可靠性,ESACR给正在执行的任务预留错误恢复时间以保证当发生瞬时错误时该任务能被恢复。实验结果表明,与最高电压节能调度(HVEA)、最小能耗最小完成时间调度(ME-MC)、最早完成时间优先调度(EFF)相比,ESACR在保证系统可靠性的前提下节能效果最好。     

Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems

An algorithm is proposed for scheduling dependent tasks in time-varying heterogeneous multiprocessor systems, in which computational power and links between processors are allowed to change over time. Link contention is considered in the multiprocessor scheduling problem. A linear switching-state space-modeling paradigm is introduced to enable theoretical analysis from a system engineering perspective. Theoretical analysis of this model shows its robustness against changes in processing power and link failure. The proposed algorithm uses a fuzzy decision-making procedure to handle changes in the multiprocessor system. The efficiency of the proposed algorithm is illustrated by several random experiments and comparison against a recent benchmark approach. The results show up to 18% average improvement in makespan, especially for larger scale systems.     

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

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

A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system

Effective task scheduling, which is essential for achieving high performance in a heterogeneous multiprocessor system, remains a challenging problem despite extensive studies. In this article, a heuristic-based hybrid genetic-variable neighborhood search algorithm is proposed for the minimization of makespan in the heterogeneous multiprocessor scheduling problem. The proposed algorithm distinguishes itself from many existing genetic algorithm (GA) approaches in three aspects. First, it incorporates GA with the variable neighborhood search (VNS) algorithm, a local search metaheuristic, to exploit the intrinsic structure of the solutions for guiding the exploration process of GA. Second, two novel neighborhood structures are proposed, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized respectively, to improve both the search quality and efficiency of VNS. Third, the proposed algorithm restricts the use of GA to evolve the task-processor mapping solutions, while taking advantage of an upward-ranking heuristic mostly used by traditional list scheduling approaches to determine the task sequence assignment in each processor. Empirical results on benchmark task graphs of several well-known parallel applications, which have been validated by the use of non-parametric statistical tests, show that the proposed algorithm significantly outperforms several related algorithms in terms of the schedule quality. Further experiments are carried out to reveal that the proposed algorithm is able to maintain high performance within a wide range of parameter settings.     

数据仓库系统中任务调度策略研究

针对数据仓库系统中存在众多的数据处理任务,提出了数据仓库系统中任务调度框架.通过自动分析任务文本生成任务流图,并提出了3种任务调度策略.模拟实验结果显示,该框架可以很好地完成数据仓库系统中的任务调度和管理,同时发现影响系统性能的因素还应包括磁盘I/O性能.     

Bandwidth‐aware divisible task scheduling for cloud computing

Task scheduling is a fundamental issue in achieving high efficiency in cloud computing. However, it is a big challenge for efficient scheduling algorithm design and implementation (as general scheduling problem is NP‐complete). Most existing task‐scheduling methods of cloud computing only consider task resource requirements for CPU and memory, without considering bandwidth requirements. In order to obtain better performance, in this paper, we propose a bandwidth‐aware algorithm for divisible task scheduling in cloud‐computing environments. A nonlinear programming model for the divisible task‐scheduling problem under the bounded multi‐port model is presented. By solving this model, the optimized allocation scheme that determines proper number of tasks assigned to each virtual resource node is obtained. On the basis of the optimized allocation scheme, a heuristic algorithm for divisible load scheduling, called bandwidth‐aware task‐scheduling (BATS) algorithm, is proposed. The performance of algorithm is evaluated using CloudSim toolkit. Experimental result shows that, compared with the fair‐based task‐scheduling algorithm, the bandwidth‐only task‐scheduling algorithm, and the computation‐only task‐scheduling algorithm, the proposed algorithm (BATS) has better performance. Copyright © 2012 John Wiley & Sons, Ltd.     

异构多核系统任务调度算法研究

为解决异构多核系统任务调度问题,提出一种混合静态调度算法——HSCGS (hybrid successor concerned genetic scheduling),该算法分为启发式算法和遗传算法2个阶段.第1阶段采用所提出的考虑后继节点的列表启发式调度算法(SCLS)产生一个近似最优的调度结果;第2阶段采用针对调度问题改进的遗传算法IGA (improved genetic algorithm),对第1阶段产生的调度结果进行优化.将SCLS与StarPU相结合,实现一种动态调度算法——DSCLS(dynamic successor concerned list scheduling),通过与StarPU上已有调度算法的对比实验表明了DSCLS算法在运行时间和系统吞吐量两方面的优势.     

On-line scheduling of scalable real-time tasks on multiprocessor systems

The computation time of scalable tasks depends on the number of processors allocated to them in multiprocessor systems. As more processors are allocated to a scalable task, the overall computation time of the task decreases but the total amount of processors’ time devoted to the execution of the task, called workload, increases due to parallel execution overhead. In this paper, we propose a task scheduling algorithm that utilizes the property of scalable tasks for on-line and real-time scheduling. In the proposed algorithm, the total workload of all scheduled tasks is reduced by managing processors allocated to the tasks as few as possible without missing their deadlines. As a result, the processors in the system have less load to execute the scheduled tasks and can execute more newly arriving tasks before their deadlines. Simulation results show that the proposed algorithm performs significantly better than the conventional algorithm based on a fixed number of processors to execute each task.     

Context‐aware scheduling in MapReduce: a compact review

It is a fact that the attention of research community in computer science, business executives, and decision makers is drastically drawn by big data. As the volume of data becomes bigger, it needs performance‐oriented data‐intensive processing frameworks such as MapReduce, which can scale computation on large commodity clusters. Hadoop MapReduce processes data in Hadoop Distributed File System as jobs scheduled according to YARN fair scheduler and capacity scheduler. However, with advancement and dynamic changes in hardware and operating environments, the performance of clusters is greatly affected. Various efforts in literature have been made to address the issues of heterogeneity (i.e., clusters consisting of virtual machines and machines with different hardware), network communication, data locality, better resource utilization, and run‐time scheduling. In this paper, we present a survey to discuss various research efforts made so far to improve Hadoop MapReduce scheduling. We classify scheduling algorithms and techniques proposed in the literature so far based on their addressing areas and present a taxonomy. Furthermore, we also discuss various aspects of open issues and challenges in the scheduling of MapReduce to improve its performance. Copyright © 2015 John Wiley & Sons, Ltd.     

云计算中基于任务分层和时间约束的关联任务调度算法

针对云计算中对关联任务进行调度时出现任务执行延迟的问题,提出了一种基于任务分层和时间约束的关联任务调度(RTS-THTC)算法。该算法采用构建有向无环图(DAG)的方式表示关联任务的执行次序,通过使用对DAG进行分层的方法提高任务的并行性,计算每一层任务的完成时间约束,将每一层中的任务同时调度至具有最小完成时间的资源上。与基于异构环境的最小完成时间(HEFT)算法的对比实验〖BP(〗原文“试验”〖BP)〗结果表明,RTS-THTC算法在完成时间上比HEFT算法短,并且能够有效地减缓关联任务出现延迟的情况。     

Approximation algorithms and heuristics for task scheduling in data‐intensive distributed systems

In this work, we are interested in the problem of task scheduling on large‐scale data‐intensive computing systems. In order to achieve good performance, one must construct not only good task schedules but also good data allocation across nodes on the system, since before a task can be executed, it must have access to data distributed on the system. In this article, we present a general formulation of a static problem that combines both scheduling and replication problems in data‐intensive distributed systems. We show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem that considers some practical constraints, an approximation algorithm can be designed. From a practical perspective, we introduce a novel heuristic for the problem that is based on nodes clustering. We compare the heuristic with two adapted approaches from other works in the literature by computational simulations using an extensive set of instances based on real computer grids. We show that our heuristic often obtains the best solutions and also runs faster than other approaches.     

云环境下绿色任务调度策略

针对云计算数据中心的能耗问题,提出了绿色云计算体系理论,设计了绿色云系统架构;基于该架构,将能量作为一种系统资源进行分配,提出了三种绿色任务调度算法分别是STF-OS、LTF-OS和RT-OS算法;对三种绿色任务调度算法可行性做了相关的理论分析,三种算法可以有效地减少能源消耗;通过扩展云计算仿真平台CloudSim实现了模拟实验,结果表明STF-OS算法降低数据中心能耗的能力最优。     

基于粒子群优化的异构多处理器任务调度算法

为提高异构多处理器任务调度的执行效率,充分发挥多处理器并行性能,提出一种基于粒子群优化的异构多处理器任务调度算法——FPSOTTS算法。该算法以求得任务最短完成时间为目标,首先通过建立新的编码方式和粒子更新公式实现粒子搜索空间到离散空间的映射,使连续的粒子群优化算法适用于离散的异构多处理器任务调度问题;同时通过引入禁忌算法进行局部搜索,克服粒子群算法的早熟收敛现象,避免陷入局部最优。实验结果表明,FPSOTTS算法的执行效率优于Min-min算法和遗传算法,有效地降低任务的执行时间。FP-SOTTS算法很好地解决了异构多处理器任务调度问题,并且适合于大规模并行任务调度。     

异构多核下兼顾应用公平性和能耗的调度方法研究

异构多核处理器通常由高性能的大核和低能耗的小核组成,在其上进行合理的线程调度可以有效地提高资源利用率,节省能耗。之前论文提出的大小核上的公平性调度并没有考虑核上有不同频率/电压状态的情况,而现在支持DVFS调节的处理器越来越普遍,因此很有必要将线程间公平度的计算进行扩展和改进。提出在每个核有若干种不同的DVFS状态时异构多核处理器上线程公平度的计算方法,对已有的性能预测模型进行改进,采用自适应算法调整模型中的系数,并在此基础上提出了一种调度策略,维持各线程之间的公平度和处理器功率满足提前设定的阈值,同时选取能效最优化的配置,实现减小应用运行能耗的目的。实验结果表明,与所提出的调度策略相比,采用static、DVFS-only、swap-only三种调度方法时,在总的运行时间几乎相同的情况下,平均要多产生20%以上能耗,对于有些应用甚至达到了50%。     

CGSA scheduler: A multi-objective-based hybrid approach for task scheduling in cloud environment

In cloud computing task scheduling is one of the important processes. The key problem of scheduling is how to allocate the entire task to a corresponding virtual machine while maximizing profit. The main objective of this paper is to execute the entire task with low cost, less resource use, and less energy consumption. To obtain the multi-objective function for scheduling, in this paper we propose a hybridization of cuckoo search and gravitational search algorithm (CGSA). The vital design of our approach is to exploit the merits of both cuckoo search (CS) and gravitational search algorithms (GSA) while avoiding their drawbacks. The performance of the algorithm is analyzed based on the different evaluation measures. The algorithms like GSA, CS, Particle swarm optimization (PSO), and genetic algorithm (GA) are used as a comparative analysis. The experimental results show that our proposed algorithm achieves the better result compare to the existing approaches.     

基于禁忌搜索的多处理器任务调度算法

为合理利用多处理器资源,对任务调度算法进行研究,针对现有任务调度算法在任务规模较大的情况下全局寻优能力方面的不足,提出基于禁忌搜索的多处理器任务调度算法。对任务图不设任何约束条件,利用基于任务复制的TDS算法产生高质量的初始调度以降低算法复杂度,利用禁忌搜索算法全局寻优得到最优调度。实验结果表明,该算法可以有效降低任务调度长度,减少所需处理器数目。     

可重构混合任务调度算法

隐藏和减少配置时间是可重构任务调度的关键问题。针对同时存在相关联的软、硬件任务的可重构混合任务,提出一种可重构混合任务调度算法。通过预配置策略和优先级算法确定需要预先配置的任务及其预配置顺序,将后继任务的配置过程隐藏在前驱任务的运行时间中,并采用配置重用策略,减少相同任务的配置次数。实验仿真结果表明,同已有的算法相比,该调度算法调度效果明显,减少了可重构任务调度的整体开销。     

Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters

This paper addresses the problem of minimizing the scheduling length (make-span) of a batch of jobs with different arrival times. A job is described by a direct acyclic graph (DAG) of parallel tasks. The paper proposes a dynamic scheduling method that adapts the schedule when new jobs are submitted and that may change the processors assigned to a job during its execution. The scheduling method is divided into a scheduling strategy and a scheduling algorithm. We also propose an adaptation of the Heterogeneous Earliest-Finish-Time (HEFT) algorithm, called here P-HEFT, to handle parallel tasks in heterogeneous clusters with good efficiency without compromising the makespan. The results of a comparison of this algorithm with another DAG scheduler using a simulation of several machine configurations and job types shows that P-HEFT gives a shorter makespan for a single DAG but scores worse for multiple DAGs. Finally, the results of the dynamic scheduling of a batch of jobs using the proposed scheduler method showed significant improvements for more heavily loaded machines when compared to the alternative resource reservation approach.     

分布式控制系统中多种混合任务的容错调度

分布式控制系统中存在有强实时、软实时和非实时等多种实时性的任务,其中强实时任务必须在其时限前完成,否则会出现灾难性后果,因此必须为分布式控制系统提供一定的容错能力。首先给出了用于调度多种实时性任务的单处理器调度算法——双优先级队列调度算法,并分析算法的可调度性条件。针对分布式控制系统,考虑基版本与副版本的执行时间不同时,结合版本复制技术和单处理器调度算法提出了一种新的容错调度算法。分析了算法的可调度行,给出了可任务集的可调度条件判断方法和基版本任务时限的设置方法。在此基础上,采用启发式静态任务分配算法,保证各处理器的负载均衡。本算法在保证任务容错可调度的条件下,可提高系统中各处理器的利用率,仿真结果表明该算法是有效的。