Slot selection algorithms in distributed computing

In this work, we introduce slot selection and co-allocation algorithms for parallel jobs in distributed computing with non-dedicated and heterogeneous resources. A single slot is a time span that can be assigned to a task, which is a part of a job. The job launch requires a co-allocation of a specified number of slots starting synchronously. The challenge is that slots associated with different resources of distributed computational environments may have arbitrary start and finish points that do not match. Some existing algorithms assign a job to the first set of slots matching the resource request without any optimization (the first fit type), while other algorithms are based on an exhaustive search. In this paper, algorithms for effective slot selection of linear complexity on an available slots number are studied and compared with known approaches. The novelty of the proposed approach consists of allocating alternative sets of slots. It provides possibilities to optimize job scheduling.     

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.     

A PTS-PGATS based approach for data-intensive scheduling in data grids

Grid computing is the combination of computer resources in a loosely coupled, heterogeneous, and geographically dispersed environment. Grid data are the data used in grid computing, which consists of large-scale data-intensive applications, producing and consuming huge amounts of data, distributed across a large number of machines. Data grid computing composes sets of independent tasks each of which require massive distributed data sets that may each be replicated on different resources. To reduce the completion time of the application and improve the performance of the grid, appropriate computing resources should be selected to execute the tasks and appropriate storage resources selected to serve the files required by the tasks. So the problem can be broken into two sub-problems: selection of storage resources and assignment of tasks to computing resources. This paper proposes a scheduler, which is broken into three parts that can run in parallel and uses both parallel tabu search and a parallel genetic algorithm. Finally, the proposed algorithm is evaluated by comparing it with other related algorithms, which target minimizing makespan. Simulation results show that the proposed approach can be a good choice for scheduling large data grid applications.     

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

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

A decomposition approach to non-preemptive real-time scheduling

Consider the problem of scheduling a set ofn tasks on a uniprocessor such that a feasible schedule that satisfies each task's time constraints is generated. Traditionally, researchers have looked at all the tasks as a group and applied heuristic or enumeration search to it. We propose a new approach called thedecomposition scheduling where tasks are decomposed into a sequence of subsets. The subsets are scheduled independently, in the order of the sequence. It is proved that a feasible schedule can be generated as long as one exists for the tasks. In addition, the overall scheduling cost is reduced to the sum of the scheduling costs of the tasks in each subset.Simulation experiments were conducted to analyze the performance of decomposition scheduling approach. The results show that in many cases decomposition scheduling performs better than the traditional branch-and-bound algorithms in terms of scheduling cost, and heuristic algorithms in terms of percentage of finding feasible schedules over randomly-generated task sets.     

Multi-cost job routing and scheduling in Grid networks

A key problem in Grid networks is how to efficiently manage the available infrastructure, in order to satisfy user requirements and maximize resource utilization. This is in large part influenced by the algorithms responsible for the routing of data and the scheduling of tasks. In this paper, we present several multi-cost algorithms for the joint scheduling of the communication and computation resources that will be used by a Grid task. We propose a multi-cost scheme of polynomial complexity that performs immediate reservations and selects the computation resource to execute the task and determines the path to route the input data. Furthermore, we introduce multi-cost algorithms that perform advance reservations and thus also find the starting times for the data transmission and the task execution. We initially present an optimal scheme of non-polynomial complexity and by appropriately pruning the set of candidate paths we also give a heuristic algorithm of polynomial complexity. Our performance results indicate that in a Grid network in which tasks are either CPU- or data-intensive (or both), it is beneficial for the scheduling algorithm to jointly consider the computational and communication problems. A comparison between immediate and advance reservation schemes shows the trade-offs with respect to task blocking probability, end-to-end delay and the complexity of the algorithms.     

实时异构系统的动态分批优化调度算法

提出了一种实时异构系统的动态分批优化调度算法,该算法采用的是在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上的运行综合各种因素构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都分配一个处理器或为每个处理器分配一项任务,使得这种分配具有最好的“合适性”,以增大未被调度任务的可行性.这种方法有效地提高了算法调度成功率.同时,为了评估该算法的性能,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与老算法的调度成功率进行了比较.模拟结果显示,新算法优于老算法.     

Scheduling image processing tasks in a multilayer system

Multilayer multiprocessor systems are generally employed in real-time applications such as robotics and computer vision. This paper introduces three heuristic algorithms for multiprocessor task scheduling in such systems. In our model, tasks with arbitrary processing times and arbitrary processor requirements are considered. The scheduling aims at minimising completion time of processes in a two-layer system. We employed an effective lower bound (LB) for the problem. Then, we analysed the average performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the LB on a set of randomly generated problems. We have also applied these algorithms for scheduling computer vision tasks running on prototype multilayer architecture. Our computational and empirical results showed that the proposed heuristic algorithms perform well.     

多MapReduce作业协同下的大数据挖掘类算法资源效率优化

由于任意的MapReduce作业都需要独立地进行任务调度、资源分配等一系列复杂的操作,这使得同一算法协同的多个MapReduce作业之间,存在着大量的冗余磁盘I/O及资源重复申请操作,导致计算过程中资源利用效率低下。大数据挖掘类算法通常被切分成多个MapReduce job协作完成。以ItemBased算法为例,对多MapReduce作业协同下的大数据挖掘算法存在的资源效率问题进行了分析,提出基于DistributedCache的ItemBased算法,利用DistributedCache将多个MapReduce job之间的I/O数据进行缓存处理,打破作业之间独立性的缺陷,减少map与reduce任务之间的等待时延。实验结果表明,DistributedCache能够提高MapReduce作业的数据读取速度,利用DistributedCache重构后的算法极大地减少了map与reduce任务之间的等待时延,资源效率提高3倍以上。     

Cluster-based multicore real-time mixed-criticality scheduling

Cluster-based scheduling is recently gaining importance to be applied to mixed-criticality real-time systems on multicore processors platform. In this approach, the cores are grouped into clusters, and tasks that are partitioned among different clusters are scheduled by global scheduler in each cluster. This research work introduces a new cluster-based task allocation scheme for the mixed-criticality real-time task sets on multicore processors. For task allocation, smaller clusters sizes (sub-clusters) are used for mixed-criticality tasks in low criticality mode, while relatively larger cluster sizes are used for high criticality tasks in high criticality mode. In this research paper, the mixed-criticality task set is allocated to clusters using worst-fit heuristic. The tasks from each cluster are also allocated to its sub-clusters, using the same worst-fit heuristic. A fixed-priority response time analysis approach based on Audsley’s approach is used for the schedulability analysis of tasks in each cluster and sub-cluster. If the high criticality job is not completed after its worst case execution time in low mode, then the system is switched to high criticality mode. After mode switch, all the low criticalities tasks are discarded and only high criticality tasks are further executed in high criticality mode. Simulation results indicate that the percentage of schedulable task sets significantly increases under cluster scheduling as compared to partitioned and global mixed-criticality scheduling schemes.     

Minimizing mean flow-time with parallel processors and resource constraints

Summary The problem to be considered is one of scheduling nonpreemptable tasks in multiprocessor systems when tasks need for their processing processors and other limited resources, and when mean flow time is the system performance measure. For each task the time required for its processing and the amount of each resource which it requires, are given. Special attention is paid to the computational complexity of algorithms for determining the optimal schedules for different assumptions concerning the environment. For the case of scheduling independent, arbitrary length tasks when each task may require a unit of an additional resource of one type, an O(n ³) algorithm is given. For more complicated resource requirements, however, it is proved that the problem under consideration is NP-hard in the strong sense, even for the case of two processors.     

A Load Balanced Task Scheduling Heuristic for Large-Scale Computing Systems

Optimal task allocation in Large-Scale Computing Systems (LSCSs) that endeavors to balance the load across limited computing resources is considered an NP-hard problem. MinMin algorithm is one of the most widely used heuristic for scheduling tasks on limited computing resources. The MinMin minimizes makespan compared to other algorithms, such as Heterogeneous Earliest Finish Time (HEFT), duplication based algorithms, and clustering algorithms. However, MinMin results in unbalanced utilization of resources especially when majority of tasks have lower computational requirements. In this work we consider a computational model where each machine has certain bounded capacity to execute a predefined number of tasks simultaneously. Based on aforementioned model, a task scheduling heuristic Extended High to Low Load (ExH2LL) is proposed that attempts to balance the workload across the available computing resources while improving the resource utilization and reducing the makespan. ExH2LL dynamically identifies task-to-machine assignment considering the existing load on all machines. We compare ExH2LL with MinMin, H2LL, Improved MinMin Task Scheduling (IMMTS), Load Balanced MaxMin (LBM), and M-Level Suffrage-Based Scheduling Algorithm (MSSA). Simulation results show that ExH2LL outperforms the compared heuristics with respect to makespan and resource utilization. Moreover, we formally model and verify the working of ExH2LL using High Level Petri Nets, Satisfiability Modulo Theories Library, and Z3 Solver.     

移动云计算中的任务调度与计算迁移算法

随着互联网的发展,许多应用程序对计算机的计算能力和资源的需求越来越大,而移动设备具有有限的资源和计算能力,云计算迁移技术是解决计算密集型任务在移动端上顺利运行的主流方法。针对无线网络中联合调度和迁移的问题,提出了一个快速高效的启发式算法。算法将能够迁移的任务全部迁移到云端作为初始解,然后逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端。每迁移一个任务,该算法都会依据任务间的通信时间,及时更新各个任务的能耗节省量。为了进一步优化启发式算法得到的解,还构造了适用于此问题并以启发解为初始解的模拟退火算法,给出了相应的编码方法、目标函数、邻域解、温度参数以及算法终止准则。与无迁移、饱和迁移、随机迁移三类算法的对比实验结果表明,由启发式算法得出的解具有高效性,能给出使移动端能耗更小的解。     

Static scheduling of multiple workflows with soft deadlines in non-dedicated heterogeneous environments

Typical patterns of using scientific workflows include their periodical executions using a fixed set of computational resources. Using the statistics from multiple runs, one can accurately estimate task execution and communication times to apply static scheduling algorithms. Several workflows with known estimates could be combined into a set to improve the resulting schedule. In this paper, we consider the mapping of multiple workflows to partially available heterogeneous resources. The problem is how to fill free time windows with tasks from different workflows, taking into account users’ requirements of the urgency of the results of calculations. To estimate quality of schedules for several workflows with various soft deadlines, we introduce the unified metric incorporating levels of meeting constraints and fairness of resource distribution.The main goal of the work was to develop a set of algorithms implementing different scheduling strategies for multiple workflows with soft deadlines in a non-dedicated environment, and to perform a comparative analysis of these strategies. We study how time restrictions (given by resource providers and users) influence the quality of schedules, and which scheme of grouping and ordering the tasks is the most effective for the batched scheduling of non-urgent workflows. Experiments with several types of synthetic and domain-specific sets of multiple workflows show that: (i) the use of information about time windows and deadlines leads to the significant increase of the quality of static schedules, (ii) the clustering-based scheduling scheme outperforms task-based and workflow-based schemes. This was confirmed by an evaluation of studied algorithms on a basis of the CLAVIRE workflow management platform.     

Efficient scheduling algorithms for real-time multiprocessorsystems

Efficient scheduling algorithms based on heuristic functions are developed for scheduling a set of tasks on a multiprocessor system. The tasks are characterized by worst-case computation times, deadlines, and resources requirements. Starting with an empty partial schedule, each step of the search extends the current partial schedule by including one of the tasks yet to be scheduled. The heuristic functions used in the algorithm actively direct the search for a feasible schedule, i.e. they help choose the task that extends the current partial schedule. Two scheduling algorithms are evaluated by simulation. To extend the current partial schedule, one of the algorithms considers, at each step of the search, all the tasks that are yet to be scheduled as candidates. The second focuses its attention on a small subset of tasks with the shortest deadlines. The second algorithm is shown to be very effective when the maximum allowable scheduling overhead is fixed. This algorithm is hence appropriate for dynamic scheduling in real-time systems     

Adaptive checkpointing strategy to tolerate faults in economy based grid

In this paper, we develop a fault tolerant job scheduling strategy in order to tolerate faults gracefully in an economy based grid environment. We propose a novel adaptive task checkpointing based fault tolerant job scheduling strategy for an economy based grid. The proposed strategy maintains a fault index of grid resources. It dynamically updates the fault index based on successful or unsuccessful completion of an assigned task. Whenever a grid resource broker has tasks to schedule on grid resources, it makes use of the fault index from the fault tolerant schedule manager in addition to using a time optimization heuristic. While scheduling a grid job on a grid resource, the resource broker uses fault index to apply different intensity of task checkpointing (inserting checkpoints in a task at different intervals). To simulate and evaluate the performance of the proposed strategy, this paper enhances the GridSim Toolkit-4.0 to exhibit fault tolerance related behavior. We also compare “checkpointing fault tolerant job scheduling strategy” with the well-known time optimization heuristic in an economy based grid environment. From the measured results, we conclude that even in the presence of faults, the proposed strategy effectively schedules grid jobs tolerating faults gracefully and executes more jobs successfully within the specified deadline and allotted budget. It also improves the overall execution time and minimizes the execution cost of grid jobs.     

数据密集作业在GPU集群上的调度算法研究

数据密集型作业包含大量的任务,使用GPU设备来提高任务的性能是目前的主要手段.但是,在解决数据密集型作业之间的GPU资源公平共享以及降低任务所需数据在网络间的传输代价方面,现有的研究方法没有综合考虑资源公平与数据传输代价的矛盾.分析了GPU集群资源调度的特点,提出了一种基于最小代价最大任务数的GPU集群资源调度算法,解决了GPU资源的公平分配与数据传输代价较高的矛盾.将调度过程分为两个阶段：第1阶段为各个作业按照数据传输代价给出自己的最优方案;第2阶段为资源分配器合并各个作业的方案,按照公平性给出全局的最优方案.首先,给出了GPU集群资源调度框架的总体结构,各个作业给出自己的最优方案,资源分配进行全局优化;第二,给出了网络带宽估计策略以及计算任务的数据传输代价的方法;第三,给出了基于GPU数量的资源公平分配的基本算法;第四,提出了最小代价最大任务数的资源调度算法,描述了资源非抢夺、抢夺以及不考虑资源公平策略的实现策略;最后,设计了6种数据密集型计算作业,对所提出的算法进行了实验.通过实验验证,最小代价最大任务数的资源调度算法对于资源公平性能够达到90%左右,同时亦能保证作业并行运行时间最小.     

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

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

树型网格计算环境下的独立任务调度

任务调度是实现高性能网格计算的一个基本问题,然而,设计和实现高效的调度算法是非常具有挑战性的.讨论了在网格资源计算能力和网络通信速度异构的树型计算网格环境下,独立任务的调度问题.与实现最小化任务总的执行时间不同(该问题已被证明是NP难题),为该任务调度问题建立了整数线性规划模型,并从该线性规划模型中得到最优任务分配方案??各计算节点最优任务分配数.然后,基于最优任务分配方案,构造了两种动态的需求驱动的任务分配启发式算法:OPCHATA(optimization-based priority-computation heuristic algorithm for task allocation)和OPBHATA(optimization-basedpriority-bandwidth heuristic algorithm for task allocation).实验结果表明:在异构的树型计算网格环境下实现大量独立任务调度时,该算法的性能明显优于其他算法.     

DAGMap: efficient and dependable scheduling of DAG workflow job in Grid

DAG has been extensively used in Grid workflow modeling. Since Grid resources tend to be heterogeneous and dynamic, efficient and dependable workflow job scheduling becomes essential. It poses great challenges to achieve minimum job accomplishing time and high resource utilization efficiency, while providing fault tolerance. Based on list scheduling and group scheduling, in this paper, we propose a novel scheduling heuristic called DAGMap. DAGMap consists of two phases, namely Static Mapping and Dependable Execution. Four salient features of DAGMap are: (1) Task grouping is based on dependency relationships and task upward priority; (2) Critical tasks are scheduled first; (3) Min-Min and Max-Min selective scheduling are used for independent tasks; and (4) Checkpoint server with cooperative checkpointing is designed for dependable execution. The experimental results show that DAGMap can achieve better performance than other previous algorithms in terms of speedup, efficiency, and dependability.