Model Predictive Control for Stochastic Resource Allocation

In this paper, we consider a class of stochastic resource allocation problems where resources assigned to a task may fail probabilistically to complete assigned tasks. Failures to complete a task are observed before new resource allocations are selected. The resulting temporal resource allocation problem is a stochastic control problem, with a discrete state space and control space that grow in cardinality exponentially with the number of tasks. We modify this optimal control problem by expanding the admissible control space, and show that the resulting control problem can be solved exactly by efficient algorithms in time that grows nearly linear with the number of tasks. The approximate control problem also provides a bound on the achievable performance for the original control problem. The approximation is used as part of a model predictive control (MPC) algorithm to generate resource allocations over time in response to information on task completion status. We show in computational experiments that, for single resource class problems, the resulting MPC algorithm achieves nearly the same performance as the optimal dynamic programming algorithm while reducing computation time by over four orders of magnitude. In multiple resource class experiments involving 1000 tasks, the model predictive control performance is within 4% of the performance bound obtained by the solution of the expanded control space problem.     

实时控制任务的模糊反馈调度系统研究

分析了实时控制任务的控制性能在不同控制阶段与处理器利用率需求间的关系,提出一种实时控制任务的模糊反馈调度系统.模糊控制器通过监测实时控制任务的误差及其变化率,查询模糊决策表,动态决定任务的优先级,反馈调度器根据优先级分配任务的利用率.仿真结果表明，在计算资源有限时，该方法能有效改善实时控制任务的控制性能.     

Increasing processor utilization in hard-real-time systems with checkpoints

Often hard real-time systems require results that are produced on time despite the occurrence of processor failures. This paper considers a distributed system where tasks are periodic and each task occurs in multiple copies which are periodically synchronized in order to handle failures. The problem of preemptively scheduling a set of such tasks is discussed where every occurrence of a task has to be completely executed before the next occurrence of the same task. First, a static scheduling algorithm is proposed which uses periodic checkpoints to tolerate processor failures. Then, the performance of the algorithm is substancially improved employing a mixed strategy which constructs a schedule where high frequency tasks are duplicated, and low frequency tasks are periodically checkpointed. The performance of the solution proposed is evaluated in terms of the minimum achievable processor utilization due to the useful computation of the tasks. Moreover, analytical and simulation studies are used to reveal interesting trade-offs associated with the scheduling algorithm. In particular, if high frequency tasks are less than 70 percent of the total number of tasks then the mixed strategy yields a higher processor utilization than the task duplication scheme.     

实时多处理器系统的动态分批优化调度算法

提出了一种实时多处理器系统的新的高效动态调度算法--动态分批优化调度算法,该算法突破了以往算法中一次只安排一项任务的做法,采用在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上运行构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都安排一个处理器或为每个处理器安排一项任务,使得这种安排具有最好的"合适性",以增大未安排任务的可行性.这种方法极大地提高了算法的调度成功率.同时,为了研究该算法的有效性,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与节约算法的调度成功率进行了比较.模拟结果显示,在节约算法的调度成功率小于10%的约束条件下,该算法的调度成功率大于90%,说明新算法的优势是非常明显的.     

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

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

Connection of nonlinear model predictive controllers for smooth task switching in autonomous driving

Motion planning, decision making, and control are vital functions in autonomous driving for accomplishing the desired driving task while considering passenger comfort, road infrastructure, and surrounding traffic participants. Model predictive control (MPC) is a promising method for simultaneously realizing these functions. However, formulating a single MPC that can run through all driving scenarios is difficult, and previous research has often been conducted to design an MPC for a specific driving task. To extend the availability of MPC for all driving tasks, smooth switching between different MPCs designed for each driving task must be addressed. One of the difficulties in switching between MPCs is guiding the state to a feasible set of optimization problems after switching. In this paper, we present a new framework to realize the smooth connection of MPCs, that is, to reduce the optimization infeasibility at the time of MPC switching. In our proposed method, two general nonlinear MPCs with different state spaces, cost functions, constraints, and formulations can be systematically switched via automatically generated intermediate-MPCs without requiring any particular alterations. This can help reduce the system complexity of the hybrid MPC system.     

面向同构多核处理器的节能任务调度方法

对于运行在同构多核处理器上的周期性硬实时任务,设计了一个基于动态电压调节的节能调度方法。该方法首先将计算任务按照周期数降序排序并基于计算任务调度长度最短的原则安排任务映射。然后将各个处理核上具有最小通讯时间的计算任务设置为最后执行的计算任务而其它计算任务顺序保持不变。在初始映射中所有计算任务都被分配最高频率的情况下,每个处理核上的计算任务在执行时间扩展过程中确定最佳的计算任务顺序。基于 Intel PXA270的功耗模型,以几个随机任务集作实验。结果表明提出的方法能够有效地降低多核处理器的能量。     

Experimental quadrotor flight performance using computationally efficient and recursively feasible linear model predictive control

A new linear model predictive control (MPC) algorithm in a state-space framework is presented based on the fusion of two past MPC control laws: steady-state optimal MPC (SSOMPC) and Laguerre optimal MPC (LOMPC). The new controller, SSLOMPC, is demonstrated to have improved feasibility, tracking performance and computation time than its predecessors. This is verified in both simulation and practical experimentation on a quadrotor unmanned air vehicle in an indoor motion-capture testbed. The performance of the control law is experimentally compared with proportional-integral-derivative (PID) and linear quadratic regulator (LQR) controllers in an unconstrained square manoeuvre. The use of soft control output and hard control input constraints is also examined in single and dual constrained manoeuvres.     

云环境下基于模板遗传算法的任务调度方法

云任务调度是云计算研究的一个热点。云任务调度方法的好坏直接影响云平台的整体性能。提出一种基于模板遗传算法(TBGA)的任务调度方法。首先,根据处理机的运算速度和带宽等条件,计算出每个处理机应分配的任务量模板大小;然后,根据模板大小将任务集合中的任务划分为多个子集合;最后,利用遗传算法将集合中的任务分配到对应的处理机。实验证明通过此方法能得到总任务完成时间较短的调度结果。通过仿真实验将TBGA算法与Min-Min算法和遗传算法(GA)进行比较,实验结果表明,TBGA算法与Min-Min算法相比任务集合完成时间降低了20%左右,与遗传算法相比任务集合完成时间降低了30%左右,是一种有效的任务调度算法。     

Guaranteed Response Times in a Hard-Real-Time Environment

This paper describes a scheduling algorithm for a set of tasks that guarantees the time within which a task, once started, will complete. A task is started upon receipt of an external signal or the completion of other tasks. Each task has a rxed set of requirements in processor time, resources, and device operations needed for completion of its various segments. A worst case analysis of task performance is carried out. An algorithm is developed for determining the response times that can be guaranteed for a set of tasks. Operating system overhead is also accounted for.     

A design fix to supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

In the article ‘Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks’, Park and Cho presented a systematic way of computing a largest fault-tolerant and schedulable language that provides information on whether the scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. The computation of such a language is mainly dependent on the task execution model presented in their paper. However, the task execution model is unable to capture the situation when the fault of a processor occurs even before the task has arrived. Consequently, a task execution model that does not capture this fact may possibly be assigned for execution on a faulty processor. This problem has been illustrated with an appropriate example. Then, the task execution model of Park and Cho has been modified to strengthen the requirement that none of the tasks are assigned for execution on a faulty processor.     

Machine Learning Accelerated Real-Time Model Predictive Control for Power Systems

This paper presents a machine-learning-based speed-up strategy for real-time implementation of model-predictive-control (MPC) in emergency voltage stabilization of power systems. Despite success in various applications, real-time implementation of MPC in power systems has not been successful due to the online control computation time required for large-sized complex systems, and in power systems, the computation time exceeds the available decision time used in practice by a large extent. This long-standing problem is addressed here by developing a novel MPC-based framework that i) computes an optimal strategy for nominal loads in an offline setting and adapts it for real-time scenarios by successive online control corrections at each control instant utilizing the latest measurements, and ii) employs a machine-learning based approach for the prediction of voltage trajectory and its sensitivity to control inputs, thereby accelerating the overall control computation by multiple times. Additionally, a realistic control coordination scheme among static var compensators (SVC), load-shedding (LS), and load tap-changers (LTC) is presented that incorporates the practical delayed actions of the LTCs. The performance of the proposed scheme is validated for IEEE 9-bus and 39-bus systems, with ±20% variations in nominal loading conditions together with contingencies. We show that our proposed methodology speeds up the online computation by 20-fold, bringing it down to a practically feasible value (fraction of a second), making the MPC real-time and feasible for power system control for the first time.      

基于多步控制集的鲁棒预测控制器设计

针对有约束多胞不确定系统, 本文提出多步控制集的概念, 并将其作为终端集进而设计鲁棒预测控制器. 由于设计了一系列可变的反馈律, 鲁棒预测控制器可以得到更好的控制性能和更大的初始可行域. 另外, 利用多步控制集的特性, 本文提出了一种将预测控制器的在线计算量转移到离线完成的算法. 通过该算法, 可以有效地平衡鲁棒预测控制器的控制性能、在线计算量和初始可行域. 仿真算例验证了这些算法的有效性.     

Maximizing the stability radius of a set of systems under real-time scheduling constraints

We address the problem of synthesising real-time embedded controllers taking into account constraints deriving from the implementation platform, thus exploring the relation between the processor's time (or "attention") devoted to different control tasks and the overall robustness of the resulting design. Assuming a time-triggered model of computation for tasks controlling a set of independent systems and a real-time preemptive scheduling policy managing a single CPU processor board, we deal with two problems: 1) deciding whether a performance specification can be attained on a candidate platform, 2) optimising performance on a platform. The considered performance metric is the minimum stability radius attained over the different feedback loops.     

一种新的分布式控制系统容错调度算法

目前多数容错调度算法在调度非周期任务时采用预留时间的方法,非周期任务无法得到充分响应。针对该问题,提出一种新的分布式控制系统容错调度算法,采用任务集划分的方法在不同处理机上运行不同的周期任务子集,使每个处理机具有不同的非周期任务预留时间,当非周期任务发生时,即可得到有效响应。结果表明,该方法能提高容错调度的效率。     

云环境下周期和非周期混合实时任务双容错调度算法

云环境中的处理机故障已成为云计算不可忽视的问题,容错成为设计和发展云计算系统的关键需求。针对一些容错调度算法在任务调度过程中调度效率低下以及任务类型单一的问题,提出一种处理机和任务主副版本分组的容错调度方法;并给出了副版本可重叠执行的判定方法,以及任务最坏响应时间的计算公式。通过实验和分析表明,和以前算法相比,将处理机分成两组分别执行任务主版本和任务副版本,减少了任务调度所需进行可调度测试的时间,增加了副版本重叠执行的机会,减少了所需的处理机个数,对提高系统处理机的利用率和容错调度的效率具有重要的意义。     

A New Approach for Scheduling of Parallelizable Tasks in Real-Time Multiprocessor Systems

In a parallelizable task model, a task can be parallelized and the component tasks can be executed concurrently on multiple processors. We use this parallelism in tasks to meet their deadlines and also obtain better processor utilisation compared to non-parallelized tasks. Non-preemptive parallelizable task scheduling combines the advantages of higher schedulability and lower scheduling overhead offered by the preemptive and non-preemptive task scheduling models, respectively. We propose a new approach to maximize the benefits from task parallelization. It involves checking the schedulability of periodic tasks (if necessary, by parallelizing them) off-line and run-time scheduling of the schedulable periodic tasks together with dynamically arriving aperiodic tasks. To avoid the run-time anomaly that may occur when the actual computation time of a task is less than its worst case computation time, we propose efficient run-time mechanisms.We have carried out extensive simulation to study the effectiveness of the proposed approach by comparing the schedulability offered by it with that of dynamic scheduling using Earliest Deadline First (EDF), and by comparing its storage efficiency with that of the static table-driven approach. We found that the schedulability offered by parallelizable task scheduling is always higher than that of the EDF algorithm for a wide variety of task parameters and the storage overhead incurred by it is less than 3.6% of the static table-driven approach even under heavy task loads.     

Renaming and Dispersing: Techniques for Fast Load Balancing

Consider the following situation: n processors of a PRAM are given n independent tasks. Each task can be executed in constant time by a single processor. The distribution of tasks among the processors is unknown; each processor has information only about its set of tasks. The batch execution problem is to reschedule the tasks so that the quickest execution of all tasks is achieved. This problem captures some basic cooperation obstacles of the PRAM model since, without rescheduling overhead, all the tasks can be completed in O(1) time. The solution presented in this paper is an O(lg lg n) time load balancing algorithm which achieves, with overwhelming probability, an almost flat distribution, i.e., O(1) tasks for each processor. We introduce two novel techniques which are of an independent interest: renaming-a randomized scheme for an approximate compaction, and dispersing-a gather-scatter paradigm for distribution smoothing. The model of computation used in the CRCW PRAM. The concurrent-write submodel is ROBUST; i.e., if two or more processors write into the same cell at the same time then no prediction can be made about the cell contents.     

基于杂交遗传算法的多处理器硬实时容错调度算法

传统的硬实时容错调度算法获得了较好的容错性能,但其任务拒绝率、处理器分配偏差比例以及最早完成时间等性能参数不佳,对此提出一种基于杂交遗传算法的优化方案,并对传统的硬实时容错算法进行优化。采用了中心型调度模型,并采用了任务备份方案来实现容错能力。将任务拒绝率、处理器分配偏差比例以及最早完成时间三个优化参数作为遗传算法适应度目标函数的三个带权分量,对其进行优化,通过遗传算法的杂交与迭代计算获得了优化的结果。最终使用不同的任务数量与处理器数量的组合对本算法与传统算法进行对比试验,结果可看出本算法的3个优化参数明显优于传统算法,且总适应度值亦比传统算法有明显改进。     

Partitioned EDF scheduling for multiprocessors using a C=D task splitting scheme

An EDF-based task-splitting scheme for scheduling multiprocessor systems is presented in this paper. For m processors at most m?1 tasks are split. The first part of a split task is constrained to have a deadline equal to its computation time. The second part of the task then has the maximum time available to complete its execution on a different processor. The advantage of this scheme is that no special run-time mechanisms are required and the overheads are kept to a minimum. Analysis is developed that allows the parameters of the split tasks to be derived. This analysis is integrated into the QPA algorithm for testing the schedulability of any task set executing on a single processor under EDF. Evaluation of the C=D scheme is provided via a comparison with a fully partitioned scheme. Different heuristics for choosing the task to split are derived and evaluated. Issues pertaining to the implementation of the C=D scheme on Linux or via the Ada programming language are also discussed.