Power and performance management for parallel computations in clouds and data centers

We address scheduling independent and precedence constrained parallel tasks on multiple homogeneous processors in a data center with dynamically variable voltage and speed as combinatorial optimization problems. We consider the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint on multiple processors. Our approach is to use level-by-level scheduling algorithms to deal with precedence constraints. We use a simple system partitioning and processor allocation scheme, which always schedules as many parallel tasks as possible for simultaneous execution. We use two heuristic algorithms for scheduling independent parallel tasks in the same level, i.e., SIMPLE and GREEDY. We adopt a two-level energy/time/power allocation scheme, namely, optimal energy/time allocation among levels of tasks and equal power supply to tasks in the same level. Our approach results in significant performance improvement compared with previous algorithms in scheduling independent and precedence constrained parallel tasks.     

软件容错模型中的容错实时调度算法

在软件容错模型的容错实时调度算法中,主部分可执行性的预测精度是影响调度算法性能的关键.针对此问题提出了DPA(deep-prediction based algorithm)和EDPA(EDF-based DPA)算法.算法考虑当前时间至替代部分通知时间之间的任务执行情况,通过构建预测表对待执行主部分的可执行性进行精确预测.当主部分不发生错误时算法根据预测表调度任务. DPA依照预测表中通知时间的先后顺序调度主部分,而EDPA则按照EDF算法调度预测表中的主部分.模拟结果表明,DPA和EDPA较目前同类算法可获得更多的主部分执行时间,降低CPU的消耗.当软件错误率较低、任务周期较短时,算法能够以较小的调度开销获得较高的调度性能.     

A software tool for human-robot shared-workspace collaboration with task precedence constraints

A key challenge in human-robot shared workspace is defining the decision criterion to select the next task for a fluent, efficient and safe collaboration. While working with robots in an industrial environment, tasks may comply with precedence constraints to be executed. A typical example of precedence constraint in industry occurs at an assembly station when the human cannot perform a task before the robot ends on its own. This paper presents a methodology based on the Maximum Entropy Inverse Optimal Control for the identification of a probability distribution over the human goals, packed into a software tool for human-robot shared-workspace collaboration. The software analyzes the human goal and the goal precedence constraints, and it is able to identify the best robot goal along with the relative motion plan. The approach used is, an algorithm for the management of goal precedence constraints and the Partially Observable Markov Decision Process (POMDP) for the selection of the next robot action. A comparison study with 15 participants was carried out in a real world assembly station. The experiment focused on evaluating the task fluency, the task efficiency and the human satisfaction. The presented model displayed reduction in robot idle time and increased human satisfaction.     

Average-case performance analysis of scheduling random parallel tasks with precedence constraints on mesh connected multicomputer systems

We investigate the problem of scheduling parallel tasks with precedence constraints on mesh connected multicomputer systems. It is still an open problem on whether there exists an approximation algorithm with finite asymptotic worst-case and/or average-case performance bound for this scheduling problem. As an early attempt to solve our problem, we propose and analyze the performance of a level-by-level scheduling algorithm LL. In fact, we solve a special case of the problem when all tasks request for square submeshes and run on a square mesh system whose size is a power of 2. There are three basic techniques in algorithm LL, i.e., the level-by-level scheduling strategy for handling precedence constraints, the largest-task-first algorithm for scheduling tasks in the same level, and the two-dimensional buddy system for system partitioning and processor allocation. Algorithm LL does not have a finite worst-case performance bound; however, it has quite acceptable average-case performance. The main contribution of the paper is to show that under the assumptions that task sizes are independent and identically distributed (i.i.d.) random variables with a common probability distribution, and that task execution times are i.i.d. random variables with finite mean and variance, and that the probability distributions of task sizes and execution times are independent of each other, for wide task graphs and typical task size distributions, algorithm LL has an asymptotic average-case performance bound about two for all probability distributions of task execution times.     

Enforcement of entailment constraints in distributed service-based business processes

ContextA distributed business process is executed in a distributed computing environment. The service-oriented architecture (SOA) paradigm is a popular option for the integration of software services and execution of distributed business processes. Entailment constraints, such as mutual exclusion and binding constraints, are important means to control process execution. Mutually exclusive tasks result from the division of powerful rights and responsibilities to prevent fraud and abuse. In contrast, binding constraints define that a subject who performed one task must also perform the corresponding bound task(s).ObjectiveWe aim to provide a model-driven approach for the specification and enforcement of task-based entailment constraints in distributed service-based business processes.MethodBased on a generic metamodel, we define a domain-specific language (DSL) that maps the different modeling-level artifacts to the implementation-level. The DSL integrates elements from role-based access control (RBAC) with the tasks that are performed in a business process. Process definitions are annotated using the DSL, and our software platform uses automated model transformations to produce executable WS-BPEL specifications which enforce the entailment constraints. We evaluate the impact of constraint enforcement on runtime performance for five selected service-based processes from existing literature.ResultsOur evaluation demonstrates that the approach correctly enforces task-based entailment constraints at runtime. The performance experiments illustrate that the runtime enforcement operates with an overhead that scales well up to the order of several ten thousand logged invocations. Using our DSL annotations, the user-defined process definition remains declarative and clean of security enforcement code.ConclusionOur approach decouples the concerns of (non-technical) domain experts from technical details of entailment constraint enforcement. The developed framework integrates seamlessly with WS-BPEL and the Web services technology stack. Our prototype implementation shows the feasibility of the approach, and the evaluation points to future work and further performance optimizations.     

Decentralized multi-robot allocation of tasks with temporal and precedence constraints

Abstract

We present an auction-based method for a team of robots to allocate and execute tasks that have temporal and precedence constraints. Temporal constraints are expressed as time windows, within which a task must be executed. The robots use our priority-based iterated sequential single-item auction algorithm to allocate tasks among themselves and keep track of their individual schedules. A key innovation is in decoupling precedence constraints from temporal constraints and dealing with them separately. We demonstrate the performance of the allocation method and show how it can be extended to handle failures and delays during task execution. We leverage the power of simulation as a tool to analyze the robustness of schedules. Data collected during simulations are used to compute well-known indexes that measure the risk of delay and failure in the robots’ schedules. We demonstrate the effectiveness of our method in simulation and with real robot experiments.     

Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times

This paper addresses scheduling problems for tasks with release and execution times. We present a number of efficient and easy to implement algorithms for constructing schedules of minimum makespan when the number of distinct task execution times is fixed. For a set of independent tasks, our algorithm in the single processor case runs in time linear in the number of tasks; with precedence constraints, our algorithm runs in time linear in the sum of the number of tasks and the size of the precedence constraints. In the multi-processor case, our algorithm constructs minimum makespan schedules for independent tasks with uniform execution times. The algorithm runs in O(n log m) time where n is the number of tasks and m is the number of processors. Received September 25, 1997; revised June 11, 1998.     

满足偏序约束的在线调度

具备偏序关系的实时调度要求调度算法产生的执行序列既要满足任务的实时约束,又要满足任务间执行的偏序约束。基于并行拓扑排序,提出一种新的在线调度算法,该算法通过同时考察任务间执行的串行性和并行性来进行优先级设置,能够处理释放时间任意的任务集。给出该算法的原理和设计,并通过示例分析和比较对算法进行验证。     

基于软件容错的动态实时调度算法

在硬实时系统中，由于任务超时完成将会导致灾难性后果，因而硬实时系统具有严格的时间及可靠性限制条件．目前实时容错调度算法大多针对硬件的容错，很少考虑软件运行的故障．提出了一种类似EDF的软件容错的动态实时调度算法PKSA(Probng-step Algorithm)，本算法在任务执行过程中，通过若干试探性检测步骤，提高了任务可执行性的预测，尽可能地避免了任务早期的失败对后续任务的影响，因此提高了任务的完成率，并同时有效地减少了浪费的CPU时间片．通过实验测试．同目前所知的同类算法相比，具有更佳的调度性能-调度成本比.     

Task scheduling with precedence constraints to minimize the total completion time

The authors study the problem of scheduling a set of tasks with known execution times and arbitrary precedence constraints to computing systems. The objective function used to measure the performance of a schedule in this paper is the sum of completion times of all tasks, which is called total completion time. Finding the minimum total completion time of tasks with precedence constraints on the uniprocessor system is known to be NP-complete, let alone on the multiprocessor system (Garey and Johnson 1979) Based on the well-known A? algorithm proposed in the field of artificial intelligence (Nilson 1980) two algorithms are developed to solve efficiently the scheduling problems on the uniprocessor system and multiprocessor system. Some evaluation functions are proposed to accelerate the search of an optimal schedule. A table named the backwards range-limited table is used to assist the computation of the evaluation function. Experimental results show that the proposed approaches can achieve the optimal schedule with greatly reduced search tree size, especially when bounding rules are applied.     

基于CPU／GPU异构平台并行优化的研究

CPU／GPU异构系统具有很大的发展潜力,深入研究CPU／GPU异构平台的并行优化,可实现系统整体计算能力的最大化。通过对CPU／GPU任务划分的优化来平衡CPU和GPU的负载,可提高计算资源的利用率,缩短计算任务的执行时间;通过对GPU线程划分的优化,可使GPU获得更高的速度。从而提高系统整体性能。     

Comparative study of task duplication static scheduling versus clustering and non-clustering techniques

One of the major issues that needs to be addressed in distributed memory multiprocessor (DMM) systems is the program task partitioning and scheduling problems, i.e. mapping of an application program's precedence related task threads among the processing elements of a DMM system. The optimal task partitioning and scheduling problem, with the goal of minimizing the program execution time and interprocessor communication overhead, is known to be an NP-complete problem. The paper addresses the design, development and performance evaluation of a novel static task partitioning and scheduling method called linear clustering with task duplication (LCTD). LCTD employs the linear (sequential) execution of tasks and task duplication heuristics in achieving minimized computation and interprocessor communication delays in DMMs. The superiority of the proposed LCTD algorithm is demonstrated through simulation studies and comparison against several of the existing static scheduling schemes, such as heavy node first (HNF) and linear clustering. We show that the proposed method can obtain an average of 33% improvement in program execution time and 21% improvement in processor utilization compared to linear clustering and HNF methods.     

Sensitivity bounds for machine scheduling with uncertain communication delays

The paper deals with the scheduling of tasks on a set of parallel machines subject to precedence constraints and communication delays, that are not fully known before the execution. This is usual in parallel computing (message passing) and in production workshops (part transportation). The goal is to give a priori informations on the behavior of different schedules computed before the execution. This sensitivity analysis helps to choose among different available algorithms. It also provides tools to decide whether it is justified to change the schedule structure at execution time (run-time scheduling).By hypothesis, the communication delays are within a given interval. Worst case sensitivity bounds are proposed that give the maximum loss of performance. These bounds hold for algorithms which are optimal in the deterministic case, but can be easily adapted to arbitrary algorithms. Some applications to specific problems are presented, namely two identical machines, and unbounded number of machines, for tree-like precedence constraints.     

PGMA: An algorithmic approach for multi-objective hardware software partitioning

Designing embedded systems efficiently has always been of significant interest. This has been tremendously scaled-up for contemporary and high-end applications with their increasing complexity and the need to satisfy multiple conflicting constraints. This paper presents a high-speed Hardware Software Partitioning technique for the design of such systems. The partitioning problem has been modeled as a multi-dimensional optimization problem with the aim of minimizing the area utilization, power dissipation, time of execution and system memory requirement of the implementation. A two-phased algorithm (Phased Greedy Metaheuristic Algorithm or PGMA) has been proposed which also takes into consideration the communication costs between hardware and software Processing-Engines (PEs) while partitioning. Subsequently, a detailed empirical analysis of the proposed algorithm is presented to ascertain its efficiency, quality and speed. The execution time is as low as 18 ms for partitioning an algorithm consisting of 1000 blocks. Thereafter, the proposed algorithm is applied to a real-life embedded system, the Joint Photographic Expert-Group (JPEG) Encoder, to demonstrate its effectiveness. For a power constraint of 600 mW, an area utilization of 58.28% has been achieved, which is the maximum amongst all the reported works till date, to the best of our knowledge. This allowed for a decreased offloading of tasks to software, resulting in a memory usage of only 14 KB and execution time of 20 ms.     

A capacity sharing and stealing strategy for open real-time systems

This paper focuses on the scheduling of tasks with hard and soft real-time constraints in open and dynamic real-time systems. It starts by presenting a capacity sharing and stealing (CSS) strategy that supports the coexistence of guaranteed and non-guaranteed bandwidth servers to efficiently handle soft tasks’ overloads by making additional capacity available from two sources: (i) reclaiming unused reserved capacity when jobs complete in less than their budgeted execution time and (ii) stealing reserved capacity from inactive non-isolated servers used to schedule best-effort jobs.CSS is then combined with the concept of bandwidth inheritance to efficiently exchange reserved bandwidth among sets of inter-dependent tasks which share resources and exhibit precedence constraints, assuming no previous information on critical sections and computation times is available. The proposed Capacity Exchange Protocol (CXP) has a better performance and a lower overhead when compared against other available solutions and introduces a novel approach to integrate precedence constraints among tasks of open real-time systems.     

Deadline and activation time assignment for partitioned real-time application on multiprocessor reservations

Providing temporal isolation between critical activities has been an important design criterion in real-time open systems, which can be achieved using resource reservation techniques. As an abstraction of reservation servers, virtual processor is often used to represent a portion of computing power available on a physical platform while hiding the implementation details. In this paper, we present a general framework of partitioning an application comprised of hard real-time tasks with precedence constraints onto multiple virtual processors in consideration of communication latencies between tasks. A novel method is proposed for assigning deadlines and activation times to tasks such that tasks partitioned onto different virtual processors can be analyzed separately using well-established theories for uniprocessor. Extensive simulations have been performed and the results have shown that, compared to existing algorithms, the proposed method achieves better performance in terms of minimizing both total bandwidth and the maximum individual bandwidth.     

Algorithmic aspects of area-efficient hardware/software partitioning

Area efficiency is one of the major considerations in constraint aware hardware/software partitioning process. This paper focuses on the algorithmic aspects for hardware/software partitioning with the objective of minimizing area utilization under the constraints of execution time and power consumption. An efficient heuristic algorithm running in O(n log n) is proposed by extending the method devised for solving the 0-1 knapsack problem. Also, an exact algorithm based on dynamic programming is proposed to produce the optimal solution for small-sized problems. Simulation results show that the proposed heuristic algorithm yields very good approximate solutions while dramatically reducing the execution time.     

一种面向部分可重构FPGA的混合实时调度算法

在CPU/FPGA平台上运行的实时任务通常由软/硬件子任务组成并存在优先约束关系。提出了一种软/硬件混合实时任务调度算法。在截止期限错失时刻,通过分析系统的运行情况,推导出实时任务可调度的充分条件。每个实时任务的硬件子任务分成多组,每组硬件子任务重叠配置到FPGA上。通过手工布局硬件子任务端口和总线端口,使得硬件子任务可动态的连接到系统总线上。实验表明,该算法能够满足任务的实时性,充分利用FPGA资源。     

异构分布式系统中一种新型主副版本调度算法

针对异构分布式系统中处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，提出一种新型高可靠性主副版本调度算法（HRPB）。任务模型以有向无环图（DAG）表示，该算法共计调度主、副两个版本的任务。在任务优先级排序阶段，根据任务执行时间及截止时限来制定新指标平均最晚开始时间（ALST）进行排序；在任务处理器分配阶段，采取多一重备份策略以解决处理器数量相对较少时优先级约束条件带来的副版本调度易失败问题，并且改进了副版本调度时的可靠性指标计算方法。通过随机生成DAG图进行算法仿真测试，实验结果表明，HRPB比eFRD具有更优的副版本调度成功率、更高的系统可靠性。     

Framework for automated partitioning and execution of scientific workflows in the cloud

Scientific workflows have become a standardized way for scientists to represent a set of tasks to overcome/solve a certain scientific problem. Usually these workflows consist of numerous CPU and I/O-intensive jobs that are executed using workflow management systems (WfMS), on clouds, grids, supercomputers, etc. Previously, it was shown that using k-way partitioning to distribute a workflow’s tasks between multiple machines in the cloud reduces the overall data communication and therefore lowers the cost of the bandwidth usage. A framework was built to automate this process of partitioning and execution of any workflow submitted by a scientist that is meant to be run on Pegasus WfMS, in the cloud, with ease. The framework provisions the instances in the cloud using CloudML, configures and installs all the software needed for the execution, partitions and runs the provided scientific workflow, also showing the estimated makespan and cost.