基于DAG图解-重构的机群系统静态调度算法

机群系统静态任务调度是NP-完全问题,通常的算法是通过一些启发式算法得到多项式次优 解.该文提出的图解-子图重构算法实现了对分布在有向无环图(directed acyclic graph, 简称DAG)上的并行任务的快速有效调度.该算法的复杂性为O(log^|V|×(|V|+| E|)),采用递归方法实现了对任务图的有效分解和子图重构,生成任务群,完成任务调度,并 且初步实现了对处理机的优化.通过实例分析以及与其他启发式调度算法的性能比较,证明该 算法是一种快速、有效、可     

Bi-level fuzzy based advanced reservation of Cloud workflow applications on distributed Grid resources

The increasing demand on execution of large-scale Cloud workflow applications which need a robust and elastic computing infrastructure usually lead to the use of high-performance Grid computing clusters. As the owners of Cloud applications expect to fulfill the requested Quality of Services (QoS) by the Grid environment, an adaptive scheduling mechanism is needed which enables to distribute a large number of related tasks with different computational and communication demands on multi-cluster Grid computing environments. Addressing the problem of scheduling large-scale Cloud workflow applications onto multi-cluster Grid environment regarding the QoS constraints declared by application’s owner is the main contribution of this paper. Heterogeneity of resource types (service type) is one of the most important issues which significantly affect workflow scheduling in Grid environment. On the other hand, a Cloud application workflow is usually consisting of different tasks with the need for different resource types to complete which we call it heterogeneity in workflow. The main idea which forms the soul of all the algorithms and techniques introduced in this paper is to match the heterogeneity in Cloud application’s workflow to the heterogeneity in Grid clusters. To obtain this objective a new bi-level advanced reservation strategy is introduced, which is based upon the idea of first performing global scheduling and then conducting local scheduling. Global-scheduling is responsible to dynamically partition the received DAG into multiple sub-workflows that is realized by two collaborating algorithms: (1) The Critical Path Extraction algorithm (CPE) which proposes a new dynamic task overall critically value strategy based on DAG’s specification and requested resource type QoS status to determine the criticality of each task; and (2) The DAG Partitioning algorithm (DAGP) which introduces a novel dynamic score-based approach to extract sub-workflows based on critical paths by using a new Fuzzy Qualitative Value Calculation System to evaluate the environment. Local-scheduling is responsible for scheduling tasks on suitable resources by utilizing a new Multi-Criteria Advance Reservation algorithm (MCAR) which simultaneously meets high reliability and QoS expectations for scheduling distributed Cloud-base applications. We used the simulation to evaluate the performance of the proposed mechanism in comparison with four well-known approaches. The results show that the proposed algorithm outperforms other approaches in different QoS related terms.     

网络流量的有效测量方法分析

把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|²).     

A note on the two machine job shop with the weighted late work criterion

The paper presents a dynamic programming approach for the two-machine nonpreemptive job-shop scheduling problem with the total weighted late work criterion and a common due date (J2 | n_i ￡ 2,d_i = d | Y_w )(J2\,|\,n_i \le 2,d_i = d\,|\,Y_w ), which is known to be NP-hard. The late work performance measure estimates the quality of an obtained solution with regard to the duration of late parts of tasks not taking into account the quantity of this delay. Providing a pseudopolynomial time method for the problem mentioned we can classify it as binary NP-hard.     

FGFS: Feature Guided Frontier Scheduling for SIMT DAGs

In the past decade, heterogeneous multicore architectures with support for Single Instruction Multiple Thread (SIMT) style computing have become the standard platform of choice for scheduling HPC applications. Here, applications are typically modelled as a set of data-parallel tasks with dependencies represented in the form of a directed acyclic graph (DAG). The relevant execution time information for each constituent task in the DAG is known beforehand and is leveraged by scheduling algorithms (List or Cluster based) to ascertain near-optimal schedules at runtime. However, given an online setting, where applications are submitted by multiple users and the types of applications are not restrictive, the chances of knowing execution time information for every program are highly unlikely. In this context, we propose a class of intelligent algorithms for heterogeneous CPU-GPU platforms that leverage static analysis-assisted machine learning techniques for deciding how device assignments should be made at runtime, thus bypassing the requirement for expensive offline profiling passes. We formalize relevant task-level ranking metrics and discuss how existing scheduling techniques can be adapted for our proposed class of algorithms. We also devise an online cluster scheduling algorithm that supports dynamic task arrival by determining in any given scheduling epoch, mapping decisions for a subset of tasks in a DAG. We perform a detailed comparative analysis between our proposed cluster and list scheduling heuristics via extensive simulation experiments using a variety of heterogeneous multicore platform configurations and observe performance speedups in the range of 1.1–1.5× for cluster scheduling over that of list scheduling.

     

A branch, bound, and remember algorithm for the 1|r i |∑t i scheduling problem

This paper presents a modified Branch and Bound (B&B) algorithm called, the Branch, Bound, and Remember (BB&R) algorithm, which uses the Distributed Best First Search (DBFS) exploration strategy for solving the 1|r _i |∑t _i scheduling problem, a single machine scheduling problem where the objective is to find a schedule with the minimum total tardiness. Memory-based dominance strategies are incorporated into the BB&R algorithm. In addition, a modified memory-based dynamic programming algorithm is also introduced to efficiently compute lower bounds for the 1|r _i |∑t _i scheduling problem. Computational results are reported, which shows that the BB&R algorithm with the DBFS exploration strategy outperforms the best known algorithms reported in the literature.     

A general and fast distributed system for large-scale dynamic programming applications

Dynamic programming is an important technique widely used in many scientific applications. Due to the massive volume of applications’ data in practice, parallel and distributed DP is a must. However, writing a parallel and distributed DP program is difficult and error-prone because of its intrinsically strong data dependency. In this paper, we present DPX10, a DAG-based distributed X10 framework aiming at simplifying the parallel programming for DP applications. DPX10 enables users to write highly efficient parallel DP programs without much effort. For DPX10 programming, users only need to do two things: 1) Instantiating a DAG pattern by indicating the dependency between vertices of the DAG; 2) Implementing the DP application’s logic in the compute method of the vertices. DPX10 provides eight commonly used DAG patterns and a simple API to allow users to customize their own DAG patterns. All the tiresome work of DP parallelization including DAG distribution, tasks scheduling, and tasks communication are hidden from users and covered by DPX10. Moreover, DPX10 is fault-tolerant and has a mechanism to handle the problem of straggler tasks, which run much slower than other tasks due to unexpected resource contention. Finally, we use four DP applications with up to 2 billion vertices running on 240 cores to demonstrate the simplicity, efficiency, and scalability of our proposed framework.     

Performance analysis of available bandwidth estimation tools for grid networks

Modern large-scale grid computing systems for processing advanced science and engineering applications rely on geographically distributed clusters. In such highly distributed environments, estimating the available bandwidth between clusters is a key issue for efficient task scheduling. We analyze the performance of two well known available bandwidth estimation tools, pathload and abget, with the aim of using them in grid environments. Differently than previous investigations (Jain et al., ; Shriram et al., in Passive and active network measurement: 6th international workshop, PAM 2005. Springer, Berlin, 2005), our experiments consider a series of relevant metrics such as accuracy of the estimation, convergence time, degree of intrusion in the grid links, and ability to handle multiple simultaneous estimations. No previous work has analyzed the use of available bandwidth tools for the derivation of efficient grid scheduling.     

分布式系统下的DAG任务调度研究综述

近年来随着网格、云计算工作流等分布式计算技术的发展,关于DAG(有向无环图)模型任务在分布式系统环境下的调度问题逐渐成为备受关注的研究热点。根据最新研究进展,对分布式系统下的DAG任务调度问题和有关技术进行了研究与讨论,主要包括四个方面:系统地描述了分布式系统和异构分布式系统的有关概念,异构分布式系统下的DAG任务调度问题、调度模型及其典型应用;对现有分布式系统下DAG任务调度的研究按照不同的方式进行了分类;探讨了多DAG共享异构分布式资源调度的研究现状;讨论了目前多DAG共享异构分布式资源调度研究存在的问题和未来可能的研究方向。     

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.     

Algorithms for (0, 1, d)-graphs with d constrains

Let G be a graph with vertex set V(G). Let n, k, d be non-negative integers such that n+2k+d≤|V(G)|?2 and |V(G)|?n?d are even. A matching which saturates exactly |V(G)|?d vertices is called a defect-d matching of G. If when deleting any n vertices the remaining subgraph contains a matching of k edges and every k-matching can be extended to a defect-d matching, then G is said to be an (n, k, d)-graph. We present an algorithm to determine (0, 1, d)-graphs with d constraints. Moreover, we solve the problem of augmenting a bipartite graph G=(B, W) to be a (0, 1, d)-graph by adding fewest edges, where d=∥B|?|W∥. The latter problem is applicable to the job assignment problem, where the number of jobs does not equal the number of persons.     

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.     

A note on scheduling multiprocessor tasks with identical processing times

We study the scheduling situation where n tasks with identical processing times have to be scheduled on m parallel processors. Each task is subjected to a release date and requires simultaneously a fixed number of processors. We show that, for each fixed value of m, the problem of minimizing total completion time can be solved in polynomial time. The complexity status of the corresponding problem Pm|r_i,p_i=p,size_i|∑C_i was unknown before.Scope and purposeThere has been increasing interest in multiprocessor scheduling, i.e., in scheduling models where tasks require several processors (machines) simultaneously. Many scheduling problems fit in this model and a large amount of research has been carried on theoretical multiprocessor scheduling. In this paper we study the situation where tasks, subjected to release dates, have identical processing time and we introduce a dynamic programming algorithm that can compute the minimum total completion time. Although this scheduling problem has been open in the literature for several years, our algorithm is simple and easy to understand.     

A Class of Composite Codes with Minimum Distance 8

We consider linear composite codes based on the |a+x|b+x|a+b+x| construction. For m 3 and r 4m + 3, we propose a class of linear composite [3 · 2 ^m , 3 · 2 ^m – r, 8] codes, which includes the [24,12,8] extended Golay code. We describe an algebraic decoding algorithm, which is valid for any odd m, and a simplified version of this algorithm, which can be applied for decoding the Golay code. We give an estimate for the combinational-circuit decoding complexity of the Golay code. We show that, along with correction of triple independent errors, composite codes with minimum distance 8 can also correct single cyclic error bursts and two-dimensional error bytes.     

Parallel batch scheduling of equal-length jobs with release and due dates

In this paper we study parallel batch scheduling problems with bounded batch capacity and equal-length jobs in a single and parallel machine environment. It is shown that the feasibility problem 1|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− can be solved in O(n ²) time and that the problem of minimizing the maximum lateness can be solved in O(n ²log n) time. For the parallel machine problem P|p-batch,b<n,r _j ,p _j =p,C _j ≤d _j |− an O(n ³log n)-time algorithm is provided, which can also be used to solve the problem of minimizing the maximum lateness in O(n ³log ² n) time.     

Generalization of EDF and LLF: Identifying All Optimal Online Algorithms for Minimizing Maximum Lateness

It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to minimize the maximum lateness (1|r _j ,pmtn|L _max). It was not previously known what other online algorithms are optimal for this problem. As this problem is fundamental in machine scheduling, it deserves a thorough investigation. In this paper, the concept of compound laxity is introduced, and a complete characterization of all optimal online algorithms for this problem is derived.     

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

We present polylogarithmic approximations for the R|prec|C _max and R|prec|∑ _j w _j C _j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind. We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994). The first step in our algorithm for the R|prec|C _max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function. A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005. V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683. Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636.     

An Analysis of Fixed-Priority Schedulability on a Multiprocessor

A new feasibility test for preemptive scheduling of periodic or sporadic real-time tasks on a single-queue m-server system allows for arbitrary fixed task priorities and arbitrary deadlines. For the special case when deadline equals period and priorities are rate monotonic, any set of tasks with maximum individual task utilization u_max and minimum individual task utilization u_min is feasible if the total utilization does not exceed . Ted Baker received the Ph.D. in Computer Science from Cornell University in 1973. He is a Professor in the Department of Computer Science at the Florida State University, which he chaired from 1998 to 2005. After spending several years doing research in computational complexity theory, he moved on to more practical aspects of computing and has worked in the area of both Ada compilation and real-time systems for the last two decades. A group he organized at FSU in 1979 produced one of the first validated Ada cross-compilers for embedded systems. Since then, he has done research, development, and consulting related to real-time embedded computing, from basic research on scheduling and concurrency control through development of kernels and run-time system support for real-time programming languages. He has also been active in IEEE (POSIX) and ISO standards work related to real-time systems. Dr. Baker was a member of the SEI Rate Monotonic Analysis group, served as real-time area expert for the Ada 9X language mapping and revision team. He directed the FSU teams that developed several software products, including the FSU POSIX threads library, the Florist implementation of IEEE Std 1003.5b-c (the POSIX/Ada API), a set of validation tests for the 1003.5b standards, and the multitasking run-time system for the Gnu Ada (GNAT) compiler. He directed the porting of the latter to several environments, including the Java Virtual Machine and RT Linux. His current research interests are real-time multiprocessor scheduling and real-time device driver architecture.     

Cluster scheduling for real-time systems: utilization bounds and run-time overhead

Cluster scheduling, where processors are grouped into clusters and the tasks that are allocated to one cluster are scheduled by a global scheduler, has attracted attention in multiprocessor real-time systems research recently. In this paper, assuming that an optimal global scheduler is adopted within each cluster, we investigate the worst-case utilization bounds for cluster scheduling with different task allocation/partitioning heuristics. First, we develop a lower limit on the utilization bounds for cluster scheduling with any reasonable task allocation scheme. Then, the lower limit is shown to be the exact utilization bound for cluster scheduling with the worst-fit task allocation scheme. For other task allocation heuristics (such as first-fit, best-fit, first-fit decreasing, best-fit decreasing and worst-fit decreasing), higher utilization bounds are derived for systems with both homogeneous clusters (where each cluster has the same number of processors) and heterogeneous clusters (where clusters have different number of processors). In addition, focusing on an efficient optimal global scheduler, namely the boundary-fair (Bfair) algorithm, we propose a period-aware task allocation heuristic with the goal of reducing the scheduling overhead (e.g., the number of scheduling points, context switches and task migrations). Simulation results indicate that the percentage of task sets that can be scheduled is significantly improved under cluster scheduling even for small-size clusters, compared to that of the partitioned scheduling. Moreover, when comparing to the simple generic task allocation scheme (e.g., first-fit), the proposed period-aware task allocation heuristic markedly reduces the scheduling overhead of cluster scheduling with the Bfair scheduler.     

A probabilistic algorithm for vertex connectivity of graphs

A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time $\text{O((-log ε|V|}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{|E|)}$ with error probability at most e provided that |E|<frcase|1/2d|V|² for some universal constant d<1.