Converging to periodic schedules for cyclic scheduling problems with resources and deadlines

Cyclic scheduling has been widely studied because of the importance of applications in manufacturing systems and in computer science. For this class of problems, a finite set of tasks with precedence relations and resource constraints must be executed repetitively while maximizing the throughput. Many applications also require that execution schedules be periodic i.e. the execution of each task is repeated with a fixed global period w.The present paper develops a new method to build periodic schedules with cumulative resource constraints, periodic release dates and deadlines. The main idea is to fix the period w, to unwind the cyclic scheduling problem for some number of iterations, and to add precedence relations so that the minimum time lag between two successive executions of any task equals w. Then, using any usual (not cyclic) scheduling algorithm to compute task starting times for the unwound problem, we prove that either the method converges to a periodic schedule of period w or it fails to compute a schedule. A non-polynomial upper bound on the number of iterations to unwind in order to guarantee that cyclic precedence relations and resource constraints are fulfilled is also provided. This method is successfully applied to a real-life problem, namely the software pipelining of inner loops on an embedded VLIW processor core by using a Graham list scheduling algorithm.     

Optimal traffic flow schedules in a semi-parallel tree network

Scheduling of traffic through a tree-structured model under a semi-parallel constraint is considered. The problem of finding the optimal root without resort to exhaustive search is studied. Several sufficient conditions to exclude a node as a optimal root candidate are presented.     

Supporting Timing Analysis by Automatic Bounding of Loop Iterations

Static timing analyzers, which are used to analyze real-time systems, need to know the minimum and maximum number of iterations associated with each loop in a real-time program so accurate timing predictions can be obtained. This paper describes three complementary methods to support timing analysis by bounding the number of loop iterations. First, an algorithm is presented that determines the minimum and maximum number of iterations of loops with multiple exits. Even when the number of iterations cannot be exactly determined, it is desirable to know the lower and upper iteration bounds. Second, when the number of iterations is dependent on unknown values of variables, the user is asked to provide bounds for these variables. These bounds are used to determine the minimum and maximum number of iterations. Specifying the values of variables is less error prone than specifying the number of loop iterations directly. Finally, a method is given to tightly predict the execution time of inner loops whose number of iterations is dependent on counter variables of outer level loops. This is accomplished by formulating the total number of iterations of a loop in terms of summations and solving the resulting equation. These three methods have been successfully integrated in an existing timing analyzer that predicts the performance for optimized code on a machine that exploits caching and pipelining. The result is tighter timing analysis predictions and less work for the user.     

支持替代/补偿的实时调度策略

提出了支持替代／补偿的实时事务模型，该模型上的实时事务具备较强的适应能力和自我纠错能力，适合于嵌入式实时数据库系统．在分析补偿任务的实时性和价值特征的基础上，研究了补偿任务的调度时机，给出了相应的调度策略和实现算法．     

Making schedules in multiprocessing systems with several additional resources

The problem of making a feasible schedule in a preemptive multiprocessing system with identical processors and several types of additional recourses is considered in the case when the task execution intervals are given and the durations of task execution linearly depend on the amount of the additional resource allocated to them. Algorithms based on reducing this problem to a network flow problem and a system of linear constraints are developed.     

Energy-efficient scheduling of real-time tasks with shared resources

This paper explores the energy-efficient scheduling of real-time tasks on a non-ideal DVS processor in the presence of resource sharing. We assume that tasks are periodic, preemptive and may access to shared resources. When dynamic-priority and fixed-priority scheduling are considered, we use the earliest deadline first (EDF) algorithm and the rate monotonic (RM) algorithm to schedule the given set of tasks. Based on the stack resource policy (SRP), we propose an approach, called blocking-aware two-speed (BATS) algorithm, to synchronize the tasks with shared resources and to calculate appropriate execution speeds so that the shared resources can be accessed in a mutual exclusive manner and the energy consumption can be reduced. Particularly, BATS uses a static low speed to execute tasks initially, and then it switches to a high speed dynamically whenever a task blocks a higher priority task. More specifically, the processor runs at the high speed from the beginning of the blocking until the deadline of the blocked task or the processor becomes idle. In order to guarantee that the deadlines of tasks are met, the static low speed and the dynamic high speeds are derived based on the theoretical analysis of the schedulability of tasks. Compared with existing work, BATS achieves more energy saving because its dynamic high speeds are lower than that of existing work and the processor has less chance to execute tasks at the high speeds. The schedulability analysis and the properties of our proposed BATS are provided in this paper. We also evaluated the capabilities of BATS by a series of experiments, for which we have some encouraging results.     

A self-organized model for the control,planning and learning of nonlinear multi-dimensional systems using a sensory feedback

A new approach is presented to deal with the problem of modelling and simulating the control mechanisms underlying planned-arm-movements. We adopt a synergetic view in which we assume that the movement patterns are not explicitly programmed but rather are emergent properties of a dynamic system constrained by physical laws in space and time. The model automatically translates a high-level command specification into a complete movement trajectory. This is an inverse problem, since the dynamic variables controlling the current state of the system have to be calculated from movement outcomes such as the position of the arm endpoint. The proposed method is based on an optimization strategy: the dynamic system evolves towards a stable equilibrium position according to the minimization of a potential function. This system, which could well be described as a feedback control loop, obeys a set of non-linear differential equations. The gradient descent provides a solution to the problem which proves to be both numerically stable and computationally efficient. Moreover, the addition into the control loop of elements whose structure and parameters have a pertinent biological meaning allows for the synthesis of gestural signals whose global patterns keep the main invariants of human gestures. The model can be exploited to handle more complex gestures involving planning strategies of movement. Finally, the extension of the approach to the learning and control of non-linear biological systems is discussed.     

Supporting soft real-time parallel applications on multiprocessors

The prevalence of multicore processors has resulted in the wider applicability of parallel programming models such as OpenMP and MapReduce. A common goal of running parallel applications implemented under such models is to guarantee bounded response times while maximizing system utilization. Unfortunately, little previous work has been done that can provide such performance guarantees. In this paper, this problem is addressed by applying soft real-time scheduling analysis techniques. Analysis and conditions are presented for guaranteeing bounded response times for parallel applications under global EDF multiprocessor scheduling.     

求解网络广告资源优化模型的改进微粒群算法

针对网络广告的特点，提出一个最大化广告效果函数的广告资源分配模型．在Langheinrich线性模型的基础上，加入分散广告显示的二次惩罚项，使所得到的最优解更能发挥网络广告的作用，结合微粒群(PSO)算法和模型的特点，设计出能有效处理约束的改进PSO算法，数值仿真证明了算法的有效性。     

Migration-aware adaptive MPSoC static schedules with dynamic reconfigurability

Technology scalings in semiconductors have enabled the integration of dozens of processing elements (PEs) onto a single chip (MPSoC). Scheduling application tasks onto the target MPSoC has been widely reported in the literature. Both technology scalings and resource competitions among applications have led to the variations of availability resources at runtime. While adaptive static schedules with predictable responses to runtime resource variations have consequently been proposed, a large number of task migrations upon PE failures in this reconfigurable schedule scheme will lead to excessive migration cost among processors and performance degradation. In this paper, we present an algorithm to reduce the number of task migrations while retaining the benefits of the fore techniques. Through embedding several soft constraints into the baseline heuristic scheduling algorithm, the proposed algorithm can decrease the number of task migrations significantly on the basis of holding the advantages of the initial dynamic reconfigurable schedule scheme. The performance evaluation of the proposed technique is carried out by incorporation into a well known heuristic scheduling algorithm. The simulation results confirm its effectiveness in minimizing the number of task migrations during dynamic reconfiguration.     

Symbolic execution of floating‐point computations

Symbolic execution is a classical program testing technique which evaluates a selected control flow path with symbolic input data. A constraint solver can be used to enforce the satisfiability of the extracted path conditions as well as to derive test data. Whenever path conditions contain floating‐point computations, a common strategy consists of using a constraint solver over the rationals or the reals. Unfortunately, even in a fully IEEE‐754‐compliant environment, this leads not only to approximations but also can compromise correctness: a path can be labelled as infeasible although there exists floating‐point input data that satisfy it. In this paper, the peculiarities of symbolic execution of programs with floating‐point numbers are addressed. Issues in the symbolic execution of this kind of program are carefully examined and a constraint solver is described that supports constraints over floating‐point numbers. Preliminary experimental results demonstrate the value of the approach proposed. Copyright © 2005 John Wiley & Sons, Ltd.     

Time-constrained project scheduling with adjacent resources

We develop a decomposition method for the Time-Constrained Project Scheduling Problem (TCPSP) with adjacent resources. For adjacent resources the resource units are ordered and the units assigned to a job have to be adjacent. On top of that, adjacent resources are not required by single jobs, but by job groups. As soon as a job of such a group starts, the adjacent resource units are occupied, and they are not released before all jobs of that group are completed. The developed decomposition method separates the adjacent resource assignment from the rest of the scheduling problem. Test results demonstrate the applicability of the decomposition method. The presented decomposition forms a first promising approach for the TCPSP with adjacent resources and may form a good basis to develop more elaborated methods.     

Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling

This paperdescribes an algorithm designed to minimally reconfigure schedulesin response to a changing environment. External factors havecaused an existing schedule to become invalid, perhaps due tothe withdrawal of resources, or because of changes to the setof scheduled activities. The total shift in the start and endtimes of already scheduled activities should be kept to a minimum.This optimization requirement may be captured using a linearoptimization function over linear constraints. However, the disjunctivenature of the resource constraints impairs traditional mathematicalprogramming approaches. The unimodular probing algorithm interleavesconstraint programming and linear programming. The linear programmingsolver handles only a controlled subset of the problem constraints,to guarantee that the values returned are discrete. Using probebacktracking, a complete, repair-based method for search, thesevalues are simply integrated into constraint programming. Unimodularprobing is compared with alternatives on a set of dynamic schedulingbenchmarks, demonstrating its effectiveness.In the final discussion, we conjecture that analogous probebacktracking strategies may obtain performance improvements overconventional backtrack algorithms for a broad range of constraintsatisfaction and optimization problems.     

多核嵌入式系统总线冲突避免的节能调度综述

在多核嵌入式系统中,避免总线冲突并在时间限制下调度通信任务和计算任务来降低能量消耗是非常重要的,有效节能调度可以避免总线冲突并在时间限制下实现有效节能。由于任务的粒度、优先级、通信任务和计算任务的协同调度对此类算法的节能有着重要影响,概述了这三个方面的研究现状,指出总线冲突避免的节能调度算法设计中有待解决的问题,并给出了多核嵌入式系统总线冲突避免的节能调度算法的发展方向。     

一种嵌入式终端多应用网络资源分配协议

为了在嵌入式终端多应用之间合理分配有限的网络带宽资源,提出一种嵌入式终端多应用网络资源分配协议。根据应用特性对网络数据包进行分类,结合实时探测的可用带宽,为每种类型数据包分别添加不同的延迟时间,依据延迟大小调度数据包。将该协议应用于实际IP机顶盒中,在同时运行HTTP流媒体应用和FTP下载应用的环境中,能够优先保证前台流媒体应用的流畅播放。实验结果表明,该协议在多应用运行环境下,能够优先满足用户关注度高的应用网络带宽需求,实现了网络资源在嵌入式终端上的合理分配。     

同构Hadoop环境作业执行时间计算方法

执行时间是作业调度的重要参考因素之一。通过分析Hadoop MapReduce环境作业的执行特征,提出了以map任务和reduce任务执行时间为输入,估算作业执行时间的方法。该方法在一定假设条件下,借助作业预执行来获取map任务和reduce任务的执行时间。实验结果表明,该方法估算作业执行时间的误差率小于7%。     

Scheduling with flexible resources in parallel workcenters to minimize maximum completion time

In this paper we consider the parallel machine scheduling problem with dual resource constraints with the objective of minimizing the maximum completion time. We develop heuristics that combine list-scheduling and bin-packing approaches with rules to iteratively modify the flexible resource allocation. A lower bound is presented and the previous and proposed solution approaches to the problem are analyzed under a variety of experimental conditions, demonstrating that there are advantages to the proposed heuristics.     

Agent-based modeling and simulation of an autonomic manufacturing execution system

Production management systems must constantly deal with unplanned disruptive events and disturbances such as arrivals of rush orders, raw material shortage/delays or equipment breakdowns along with a multitude of interactions in the supply chain which constantly demand on-line task rescheduling and order execution control. For responsiveness and agility at the shop-floor, a distributed design for manufacturing execution systems is proposed based on autonomic units that fill the gap between production planning and shop-floor control. An interaction mechanism designed around the concept of order and resource agents implementing the monitor-analyze-plan-execution loop is described. Generative simulation modeling of an autonomic manufacturing execution system (@MES) is proposed in order to evaluate emerging behaviors and macroscopic dynamics in a multiproduct batch plant. Results obtained for an industrial case study using a simulation model of the proposed @MES are presented. The usefulness of agent-based modeling and simulation as a tool for distributed MESs design and to verify performance, stability and disturbance rejection capability of an interaction mechanism is highlighted.     

多用户视频流分布式最小失真调度算法

为了提高视频流数据的传输质量,减小视频流数据的失真率,从而提高网络中视频流数据的利用效率,提出了一种多用户视频流分布式最小失真调度方案.该方案采用相加模型来捕捉总的视频失真,建立起视频流失真模型,并通过M/G/1排队模型来进一步建模,得到视频流失真与视频流传输的延迟分布相关性函数,通过优化网络拥塞来进行系统的延迟约束,从而减小视频流失真率;通过同时考虑路由和速率分配问题来得到路由拥塞的最小化最优解,最大限度地减少网络的传输延迟.实验数据结果及对比分析表明,该方案在减小视频流失真比率、缩短视频流传输的延迟时间和控制网络丢包率上均取得了较好的效果.     

Feasibility Analysis of Real-Time Periodic Tasks with Offsets

The problem of feasibility analysis of asynchronous periodic task sets, where tasks can have an initial offset, is known to be co-NP-complete in the strong sense. A sufficient pseudo-polynomial test has been proposed by Baruah, Howell and Rosier, which consists in analyzing the feasibility of the corresponding synchronous task set (i.e. all offsets are set equal to 0). If the test gives a positive result, then the original asynchronous task set is feasible; else, no definitive answer can be given. In many cases, this sufficient test is too pessimistic, i.e. it gives no response for many feasible task sets.In this paper, we present a new sufficient pseudo-polynomial test for asynchronous periodic task sets. Our test reduces the pessimism by explicitely considering the offsets in deriving a small set of critical arrival patterns. We show, trough a set of extensive simulations, that our test outperforms the previous sufficient test.Rodolfo Pellizzoni received the Laurea degree in Computer Engineering from the Università di Pisa and the Diploma degree from the Scuola Superiore SantAnna, in 2004. He is presently a Ph.D. student in the Department of Computer Science at the University of Illinois at Urbana-Champaign. His main research interests are in real-time operating systems, scheduling theory and resource-allocation in distributed and multiprocessor systems.Giuseppe Lipari graduated in Computer Engineering at the University of Pisa in 1996, and received the Ph.D. degree in Computer Engineering from Scuola Superiore SantAnna in 2000. During 1999, he was a visiting student at University of North Carolina at Chapel Hill, collaborating with professor S.K. Baruah and professor K. Jeffay on real-time scheduling. Currently, he is assistant professor of Operating Systems with Scuola Superiore SantAnna. His main research activities are in real-time scheduling theory and its application to real-time operating systems, soft real-time systems for multimedia applications and component-based real-time systems.