A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems

Mixed-machine heterogeneous computing (HC) environments utilize a distributed suite of different high-performance machines, interconnected with high-speed links, to perform groups of computing-intensive applications that have diverse computational requirements and constraints. The problem of optimally mapping a class of independent tasks onto the machines of an HC environment has been proved, in general, to be NP-complete, thus requiring the development of heuristic techniques for practical usage. If the mapping has real-time requirements such that the mapping process is performed during task execution, fast greedy heuristics must be adopted. This paper investigates fast greedy heuristics for this problem and identifies the importance of the concept of task consistency in designing this mapping heuristic. We further propose task priority graph based fast greedy heuristics, which consider the factors of both task consistency and machine consistency (the same concept of consistency as in previous studies). A collection of 20 greedy heuristics, including 17 newly proposed ones, are implemented, analyzed, and systematically compared within a uniform model of task execution time. This model is implemented by the coefficient-of-variation based method. The experimental results illuminate the circumstances when a specific greedy heuristic would outperform the other 19 greedy heuristics.     

Scheduling algorithms for heterogeneous batch processors with incompatible job-families

We consider the problem of scheduling heterogeneous batch processors (i.e., batch processors with different capacity) with incompatible job-families and non-identical job sizes to maximize the utilization of the batch processors. We analyzed the computational complexity of this problem and showed that it is NP-hard and proposed eight variants of a fast greedy heuristic. A series of computational experiments were carried out to compare the performance of the heuristics and showed that the heuristics are capable of consistently obtaining near (estimated) optimal solutions with very low-computational burden for large-scale problems. We also carried out a study to find the effect of family processing time changes on the performance of the heuristics. This sensitivity analysis indicated that the processing time set of job-families influences the performance of the heuristic algorithms.     

Assignment of independent tasks to minimize completion time

The task of scheduling dynamic applications that consist of single process tasks on a non-shared memory multicomputer is examined in this paper. Each task of the application is assumed to (1) require execution on a single processor, (2) have an estimate of its maximum execution time, and (3) not wait on communications with other tasks. The objective of the studied schedulers is to map an application's tasks onto the underlying hardware in such a way that the application's completion time is minimized. Experimental evaluation of the schedulers indicate that in many situations, a more sophisticated scheduler fails to outperform simpler schedulers.     

Assigning real-time tasks to heterogeneous processors by applying ant colony optimization

The problem of determining whether a set of periodic tasks can be assigned to a set of heterogeneous processors without deadline violations has been shown, in general, to be NP-hard. This paper presents a new algorithm based on ant colony optimization (ACO) metaheuristic for solving this problem. A local search heuristic that can be used by various metaheuristics to improve the assignment solution is proposed and its time and space complexity is analyzed. In addition to being able to search for a feasible assignment solution, our extended ACO algorithm can optimize the solution by lowering its energy consumption. Experimental results show that both the prototype and the extended version of our ACO algorithm outperform major existing methods; furthermore, the extended version achieves an average of 15.8% energy saving over its prototype.     

Scheduling imprecise computation tasks on uniform processors

We consider the problem of preemptively scheduling n imprecise computation tasks on m?1 uniform processors, with each task Ti having two weights wi and . Three objectives are considered: (1) minimizing the maximum w^′-weighted error; (2) minimizing the total w-weighted error subject to the constraint that the maximum w^′-weighted error is minimized; (3) minimizing the maximum w^′-weighted error subject to the constraint that the total w-weighted error is minimized. For these objectives, we give polynomial time algorithms with time complexity O(mn⁴), O(mn⁴) and O(kmn⁴), respectively, where k is the number of distinct w-weights. We also present alternative algorithms for the three objectives, with time complexity O(cmn³), O(cmn³+mn⁴) and O(kcmn³), respectively, where c is a parameter-dependent number.     

Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system

The scheduling problem for real-time tasks on multiprocessor is one of the NP-hard problems. This paper proposes a new scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm (mohGA) on heterogeneous multiprocessor environment. In solution algorithms, the genetic algorithm (GA) and the simulated annealing (SA) are cooperatively used. In this method, the convergence of GA is improved by introducing the probability of SA as the criterion for acceptance of new trial solution.     

Scheduling online mixed-parallel workflows of rigid tasks in heterogeneous multi-cluster environments

Workflow scheduling on parallel systems has long been known to be a NP-complete problem. As modern grid and cloud computing platforms emerge, it becomes indispensable to schedule mixed-parallel workflows in an online manner in a speed-heterogeneous multi-cluster environment. However, most existing scheduling algorithms were not developed for online mixed-parallel workflows of rigid data-parallel tasks and multi-cluster environments, therefore they cannot handle the problem efficiently. In this paper, we propose a scheduling framework, named Mixed-Parallel Online Workflow Scheduling (MOWS), which divides the entire scheduling process into four phases: task prioritizing, waiting queue scheduling, task rearrangement, and task allocation. Based on this framework, we developed four new methods: shortest-workflow-first, priority-based backfilling, preemptive task execution and All-EFT task allocation, for scheduling online mixed-parallel workflows of rigid tasks in speed-heterogeneous multi-cluster environments. To evaluate the proposed scheduling methods, we conducted a series of simulation studies and made comparisons with previously proposed approaches in the literature. The experimental results indicate that each of the four proposed methods outperforms existing approaches significantly and all these approaches in MOWS together can achieve more than 20% performance improvement in terms of average turnaround time.     

分布式训练异构任务调度算法研究

分布式机器学习中的工作结点在训练过程中经常需要处理异构任务,但任务发布者可能无法根据有效的先验知识确定边缘服务器集群中哪些是处于训练状态的工作结点.针对边缘服务器集群无法同时满足训练性能与服务质量最大化的问题,对异构任务调度算法进行了研究.首先在集群资源约束下分析了分布式训练收敛性能的影响因素;其次建立了最大化训练性能...     

A decentralized model for scheduling independent tasks in Federated Grids

In this paper we present a decentralized model for scheduling independent tasks in Federated Grids. This model consists of a set of meta-schedulers on each of the grid infrastructures of the Federated Grid. Each meta-scheduler has to implement a mapping strategy in order to improve two of the most common objective functions of task scheduling problems: makespan and resource performance. We consider four possible algorithms that have to provide a simple, decoupled, and coarse-grained solution that could be deployed in any Grid. The main axis of the algorithms is that they consider the performance of the infrastructures forming the Federated Grid, not only their state.     

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.     

Scheduling trees with large communication delays on two identical processors

We consider the problem of scheduling trees on two identical processors in order to minimize the makespan. We assume that tasks have unit execution times, and arcs are associated with large identical integer communication delays. We prove that the problem is NP-hard in the strong sense even when restricted to the class of binary trees, and we provide a polynomial-time algorithm for complete binary trees.This work has been partially supported by the French-Greek bilateral exchange program PLATON and the GDR-PRS Ordonnancement pour le parallélisme program of the French government.     

A performance study of general-purpose applications on graphics processors using CUDA

Graphics processors (GPUs) provide a vast number of simple, data-parallel, deeply multithreaded cores and high memory bandwidths. GPU architectures are becoming increasingly programmable, offering the potential for dramatic speedups for a variety of general-purpose applications compared to contemporary general-purpose processors (CPUs). This paper uses NVIDIA’s C-like CUDA language and an engineering sample of their recently introduced GTX 260 GPU to explore the effectiveness of GPUs for a variety of application types, and describes some specific coding idioms that improve their performance on the GPU. GPU performance is compared to both single-core and multicore CPU performance, with multicore CPU implementations written using OpenMP. The paper also discusses advantages and inefficiencies of the CUDA programming model and some desirable features that might allow for greater ease of use and also more readily support a larger body of applications.     

Energy efficient scheduling of real-time tasks on multi-core processors with voltage islands

This paper studies energy efficient scheduling of periodic real-time tasks on multi-core processors with voltage islands, in which cores are partitioned into multiple blocks (termed voltage islands) and each block has its own power source to supply voltage. Cores in the same block always operate at the same voltage level, but can be adjusted by using Dynamic Voltage and Frequency Scaling (DVFS). We propose a Voltage Island Largest Capacity First (VILCF) algorithm for energy efficient scheduling of periodic real-time tasks on multi-core processors. It achieves better energy efficiency by fully utilizing the remaining capacity of an island before turning on more islands or increasing the voltage level of the current active islands. We provide detailed theoretical analysis of the approximation ratio of the proposed VILCF algorithm in terms of energy efficiency. In addition, our experimental results show that VILCF significantly outperforms the existing algorithms when there are multiple cores in a voltage island.     

基于负载执行紧迫度的实时补偿任务调度策略TSCTTL

针对支持补偿性的实时任务模型,分析实时任务的系统负载执行紧迫度,进而提出基于负载执行紧迫度的实时补偿任务调度策略TSCTTL;通过实验仿真表明,依据实时任务的负载执行紧迫度来调度补偿任务,降低了系统任务的截止期错失率,并提高了系统收益。     

Scheduling unit-time tasks with integer release times and deadlines

The problem of scheduling n unit-time tasks with integer release times and deadlines is shown to be solvable in o(n log n) time if a sufficient amount of uninitialized space is available. Specifically, the tasks may be scheduled in O(f(n)) time, using O(M + n) space, where f(n) is the time to solve an off-line minimum problem, and M is the size of the largest deadline. By a recent result of Gabow and Tarjan (1983), f(n) is O(n).     

一种基于代价抢占的混合可重构任务调度算法*

针对同时存在独立任务和相依性任务的混合可重构任务调度,提出了基于代价抢占的混合可重构任务实时调度算法。提出了相依性任务等价运行截止时刻的计算方法,使混合可重构任务按照配置截止时刻排队配置。针对相依性任务调度特点,分析得到了相依性任务集合调度失败的充分条件,提前判定和丢弃无法调度成功的相依性任务集合;通过有限预配置防止相依性任务无效占用可重构资源;通过基于代价抢占减少调度失败任务个数。仿真结果表明,该调度算法提高了任务调度成功率。     

基于人工鱼群遗传算法的异构多核系统任务调度研究

异构多核系统的任务调度问题已经被证明是一个NP完全问题。人工鱼群算法在算法初期具有较快的收敛速度,后期收敛较慢,而遗传算法的种群初始化具有较强的鲁棒性,初始化种群的质量直接影响着遗传算法的性能。本文提出了一种将人工鱼群算法与遗传算法相结合的任务调度算法,首先分析了异构多核系统的任务调度问题的本质,使用改进的人工鱼群算法来构建遗传算法的初始化种群,并使用改进的遗传算法进行迭代进化,从而提高了算法的收敛速度。     

Leveraging workload diversity through OS scheduling to maximize performance on single-ISA heterogeneous multicore systems

Recent research has highlighted the potential benefits of single-ISA heterogeneous multicore processors over cost-equivalent homogeneous ones, and it is likely that future processors will integrate cores that have the same instruction set architecture (ISA) but offer different performance and power characteristics. To fully tap into the potential of these processors, the operating system must be aware of the hardware asymmetry when making scheduling decisions and map applications to cores in consideration of their performance characteristics. We propose a Heterogeneity-Aware Signature-Supported (HASS) scheduling algorithm that performs this mapping using per-thread architectural signatures, which are compact summaries of threads’ architectural properties. We implemented HASS in OpenSolaris, and demonstrated that it always outperforms a heterogeneity-agnostic scheduler (by as much as 12.5%) for workloads exhibiting sufficient diversity. Our evaluation also includes an extensive comparison with other heterogeneity-aware schedulers to provide a more clear understanding of the pros and cons behind HASS.