Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

Supervisory control theory is a well-established theoretical framework for feedback control of discrete event systems whose behaviours are described by automata and formal languages. In this article, we propose a formal constructive method for optimal fault-tolerant scheduling of real-time multiprocessor systems based on supervisory control theory. In particular, we consider a fault-tolerant and schedulable language which is an achievable set of event sequences meeting given deadlines of accepted aperiodic tasks in the presence of processor faults. Such a language eventually provides information on whether a scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. Moreover, we present a systematic way of computing a largest fault-tolerant and schedulable language which is optimal in that it contains all achievable deadline-meeting sequences.     

Long-range predictive control of a rapid thermal processor

Long-range predictive control of a quartz chamber furnace used in microelectronic technology is discussed. It is based on a technique called rapid thermal processing (short thermal cycles, reaching high temperatures for a short time). The furnace temperature and the electric power supplied to the furnace are selected as controlled and control variables, respectively. The control algorithm is based on the minimization of a quadratic criterion involving the input and output traektng errors- it is derived in the receding-horizon sense. To represent the complex dynamics of the furnace, a single input/output controlled autoregressive integrating moving average model (CARIMA) was adopted. The model parameters are estimated on-line using a robust identification scheme which includes data normalization, covariance matrix factorization, adjustable forgetting factor, etc. Experimental results are included which demonstrate the capability of the adaptive control algorithm considered with rapid thermal processes.     

RPM: a rapid prototyping engine for multiprocessor systems

RPM enables rapid prototyping of different multiprocessor architectures. It uses hardware emulation for reliable design verification and performance evaluation. The major objective of the RPM project is to develop a common, configurable hardware platform to accurately emulate different MIMD systems with up to eight execution processors. Because emulation is orders of magnitude faster than simulation, an emulator can run problems with large data sets more representative of the workloads for which the target machine is designed. Because an emulation is closer to the target implementation than an abstracted simulation, it can accomplish more reliable performance evaluation and design verification. Finally, an emulator is a real computer with its own I/O; the code running on the emulator is not instrumented. As a result, the emulator looks exactly like the target machine (to the programmer) and can run several different workloads, including code from production compilers, operating systems, databases, and software utilities     

Optimal control of rapid thermal annealing in a semiconductor process

This study focuses on the optimal control of rapid thermal annealing (RTA) used in the formation of ultrashallow junctions needed in next-generation microelectronic devices. Comparison of different parameterizations of the optimal trajectories shows that linear profiles give the best combination of minimizing junction depth and sheet resistance. Worst-case robustness analysis of the optimal control trajectory motivates improvements in feedback control implementations for these processes. This is the first time that the effects of model uncertainties and control implementation inaccuracies are rigorously quantified for RTA.     

Real-time concurrency control in a multiprocessor environment

Although many high-performance computer systems are now multiprocessor-based, little work has been done in real-time concurrency control of transaction executions in a multiprocessor environment. Real-time concurrency control protocols designed for uniprocessor or distributed environments may not fit the needs of multiprocessor-based real-time database systems because of a lower concurrency degree of transaction executions and a larger number of priority inversions. This paper proposes the concept of a priority cap to bound the maximum number of priority inversions in multiprocessor-based real-time database systems to meet transaction deadlines. We also explore the concept of two-version data to increase the system concurrency level and to explore the abundant computing resources of multiprocessor computer systems. The capability of the proposed methodology is evaluated in a multiprocessor real-time database system under different workloads, database sizes and processor configurations. It is shown that the benefits of the priority cap in reducing the blocking time of urgent transactions are far greater than the losses involved in committing less urgent transactions. The idea of two-version data also greatly improves the system performance because of a much higher concurrency degree in the system     

Optimal control of a resource-sharing multiprocessor with periodic maintenance

Shared resources and the processes that control them play a critical role in the functioning of concurrent systems. The article analyzes the production control of a workstation producing a number of products concurrently. The workstation is periodically stopped for maintenance. The objective of the production control is to minimize inventory and backlog costs over an infinite time horizon. Using the maximum principle and under the so-called agreeable cost structure, we derive the optimal production control. We prove that under this cost structure, the problem can be solved in polynomial time.     

Learning control of mobile robots using a multiprocessor system

A real-time multiprocessor system is proposed for the solution of the tracking problem of mobile robots operating in a real context with environmental disturbances and parameter uncertainties. The proposed control scheme utilizes multiple models of the robot for its identification in an adaptive and learning control framework. Radial Basis Function Networks (RBFNs) are considered for the multiple models in order to exploit the net non-linear approximation capabilities for modeling the kinematic behavior of the vehicle and for reducing unmodeled contributions to tracking errors. The training of the nets and the tests of the achieved control performance have been done in a real experimental setup. The proposed control architecture improves the robot tracking performance achieving fast and accurate control actions in presence of large and time-varying uncertainties in dynamical environments. The experimental results are satisfactory in terms of tracking errors and computational efforts.     

Supervisory control using a new control-relevant switching

This paper presents a new supervisory control scheme, which is based on a control-relevant switching logic. Unlike most of the existing switching methods considering only estimator performance, the proposed scheme takes both estimator and controller performance into account. As an index to the controller performance, an iISS (integral-input-to-state stability) Lyapunov function is employed; it is ensured that the Lyapunov function satisfies a certain inequality. This Lyapunov-based switching is then coupled to the state-dependent dwell-time switching developed recently, and the state of the uncertain plant is shown to converge asymptotically. The proposed supervisory control scheme is applied to an input-constrained neurally stable linear plant.     

Supervisory control of switching control systems

In this paper, the problem of designing a switching policy for an adaptive switching control system is formulated as a problem of supervisory control of a discrete-event system (DES). Two important problems in switching control are then addressed using the DES formulation and the theory of supervisory control under partial observation. First, it is verified whether for a given set of controllers, a switching policy satisfying a given set of constraints on the transitions among controllers exists. If so, then a minimally restrictive switching policy is designed. Next, an iterative algorithm is introduced for finding a minimal set of controllers for which a switching policy satisfying the switching constraints exists. It is shown that in the supervisory control problem considered in this paper, limitations on event observation are the factors that essentially restrict supervisory control. In other words, once observation limitations are respected, limitations on control will be automatically satisfied. This result is used to simplify the proposed iterative algorithm for finding minimal controller sets.     

Supervisory multiple regime control

The objective of this work is to identify a control algorithm that is capable of handling nonlinear behaviour (operating point dependent) witnessed in most industrial processes. To this end, the proposed solution is that of a supervisory multiple model control scheme, SMMC. This work demonstrates that the multiple model methodology can be recast into a Supervisory approach, whereby the supervisor is employed as a selector. This selector (supervisor) identifies the appropriate local-controller from a fixed family set. Unlike other supervisory techniques a multiple model observer (MMO) is proposed for the selection mechanism. Switching between local-controllers is accomplished bumplessly through a multiple model bumpless transfer scheme. Consequently, producing a continuous control signal as the process transverses between different operating regimes. The key issue in this application is the unique interaction between the local-controllers and the supervisor. This interaction is necessary to ensure global stability is maintained at all times, especially during switching. In short, the SMMC scheme enables the implementation of linear control theory, which is well accepted in industry, to standard nonlinear processes. The SMMC approach warrants the control design to extend beyond normal operating conditions that breakdown when standard linear control techniques are applied. The above notion is applied to a pilot-scale binary distillation column. In this example the column's distinct operating points describe the nonlinear behaviour. The results illustrate that as the distillation column shifted between different operating points the SMMC self-regulates accordingly. This self-regulation ensures that global stability and performance are maintained at an optimum. The entire SMMC design was implemented within a PC Windows-NT environment that was interfaced to an industrial DCS system.     

Supervisory control of hybrid systems within a behavioural framework

This contribution addresses the synthesis of supervisory control for hybrid systems Σ with discrete external signals. Such systems are in general neither l-complete nor can they be represented by finite state machines. We find an l-complete approximation (abstraction) Σ_l for Σ, represent it by a finite state machine, and investigate the control problem for the approximation. If a solution exists, we synthesize the maximally permissive supervisor for Σ_l. We show that it also solves the control problem for the hybrid system Σ. If no solution exists, approximation accuracy can be increased by computing a k-complete abstraction Σ_k, k>l. This paper is entirely set within the framework on Willems’ behavioural systems theory.     

Multiprogramming a distributed-memory multiprocessor

The development of computing systems with large numbers of processors has been motivated primarily by the need to solve large, complex problems more quickly than is possible with uniprocessor systems. Traditionally, multiprocessor systems have been uniprogrammed, i.e., dedicated to the execution of a single set of related processes, since this approach provides the fastest response for an individual program once it begins execution. However, if the goal of a multiprocessor system is to minimize average response time or to maximize throughput, then multiprogramming must be considered. In this paper, a model of a simple multiprocessor system with a two-program workload is reviewed; the model is then applied to an Intel iPSC/2 hypercube multiprocessor with a workload consisting of parallel wavefront algorithms for solving triangular systems of linear equations. Throughputs predicted by the model are compared with throughputs obtained experimentally from an actual system. The results provide validation for the model and indicate that significant performance improvements for multiprocessor systems are possible through multiprogramming.     

Supervisory control and reactive synthesis: a comparative introduction

This paper presents an introduction to and a formal connection between synthesis problems for discrete event systems that have been considered, largely separately, in the two research communities of supervisory control in control engineering and reactive synthesis in computer science. By making this connection mathematically precise in a paper that attempts to be as self-contained as possible, we wish to introduce these two research areas to non-expert readers and at the same time to highlight how they can be bridged in the context of classical synthesis problems. After presenting general introductions to supervisory control theory and reactive synthesis, we provide a novel reduction of the basic supervisory control problem, non-blocking case, to a problem of reactive synthesis with plants and with a maximal permissiveness requirement. The reduction is for fully-observed systems that are controlled by a single supervisor/controller. It complements prior work that has explored problems at the interface of supervisory control and reactive synthesis. The formal bridge constructed in this paper should be a source of inspiration for new lines of investigation that will leverage the power of the synthesis techniques that have been developed in these two areas.     

Supervisory control synthesis of discrete-event systems using a coordination scheme

Supervisory control of distributed DES with a global specification and local supervisors is a difficult problem. For global specifications, the equivalent conditions for local control synthesis to equal global control synthesis may not be met. This paper formulates and solves a control synthesis problem for a generator with a global specification and with a combination of a coordinator and local controllers. Conditional controllability is proven to be an equivalent condition for the existence of such a coordinated controller. A procedure to compute the least restrictive solution within our coordination control architecture is provided and conditions under which the result coincides with the supremal controllable sublanguage are stated.     

Supervisory control of timed discrete-event systems

The Ramadge-Wonham framework for control of discrete event systems is augmented with timing features by use of Ostroff's semantics for timed transition models. It is shown that the RW concept of controllability and the existence of maximally permissive supervisory controls can be suitably generalized. The enhanced setting admits subsystem composition and the concept of forcible event as an event that preempts the tick of a global clock. An example of a simple manufacturing cell illustrates how the new framework can be used to solve synthesis problems which may include logic-based, temporal and quantitative optimality specifications     

Supervisory control of automatic pouring machine

This paper presents supervisory control of a total molten-metal pouring system to improve the productivity of the factory, the safety of workers, and the quality of the product. Through the pouring processes model, a forward tilting control input was calculated by an adaptive feedforward control system to hold the liquid in the sprue cup at a constant level considering the change effected by the accumulating slag in the ladle. A backward tilting input was obtained by means of the hybrid shape approach applied to suppress the slosh. The supervisory control system reasonably switches from the forward tilting motion to the backward tilting motion by using model predictive control to achieve the accurate poured quantity. The validity of the proposed total control system was demonstrated through experiments.     

Supervisory control of concurrent discrete-event systems

When a discrele-event system P consists of several subsystems P₁,...,P_n which operate concurrently, a natural approach to the supervisory control problem is to synthesize a ‘local’ controller S_i , for each subsystem P_i , and operate the individually controlled subsystems S_i/P_i concurrently. Such an approach is called concurrent supervisory control and is closely related to decentralized supervisory control as studied by Cieslak et al. (1988) and Lin and Wonham (1988). In the present paper simple and easily computable conditions are developed which guarantee that concurrent supervisory control can achieve the optimal behaviour achievable by a global supervisor. To achieve this, two specific concurrent control strategies are introduced.     

多处理机并行计算自动测控系统

介绍了多处理机系统的并行计算,在此基础上,给出了采用十刻度策略解决任务排序,采用满射策略解决任务映射的算法。最后,给出了一个自动测控系统示例,该系统不仅可以使多台处理机同时进行多种不同仪器仪表、设备的测控工作,而且处理机间的通信成本较低,加快了被测对象的测试速度,节省了测试时间。     

The optimal control approach to generalized multiprocessor scheduling

In this paper we present several new results in the theory of homogeneous multiprocessor scheduling. We start with some assumptions about the behavior of tasks, with associated precedence constraints, as processor power is applied. We assume that as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization, and task scheduling overhead, this speedup increases less than linearly with the number of processors applied. We also assume that the number of processors which can be assigned to a task is a continuous variable, with a view to exploiting continuous mathematics. The optimal scheduling problem is to determine the number of processors assigned to each task, and task sequencing, to minimize the finishing time.These assumptions allow us to recast the optimal scheduling problem in a form which can be addressed by optimal control theory. Various theorems can be proven which characterize the optimal scheduling solution. Most importantly, for the special case where the speedup function of each task isp , wherep is the amount of processing power applied to the task, we can directly solve our equations for the optimal solution. In this case, for task graphs formed from parallel and series connections, the solution can be derived by inspection. The solution can also be shown to be shortest path from the initial to the final state, as measured by anl _1/ distance metric, subject to obstacle constraints imposed by the precedence constraints.This research has been funded in part by the Advanced Research Project Agency monitored by ONR under Grant No. N00014-89-J-1489, in part by Draper Laboratory, in part by DARPA Contract No. N00014-87-K-0825, and in part by NSF Grant No. MIP-9012773. The first author is now with AT&T Bell Laboratories and the second author is with BBN Incorporated.     

Supervisory control strategies evaluated on a pilot Jameson flotation cell

An L-150 pilot Jameson flotation cell was instrumented and a distributed control system was developed. The parameters of a metallurgic phenomenological model were estimated from industrial data. A steady state simulator was built based on this nonlinear model.This hybrid system combines on-line measured operating variables with virtual variables, characterizing the feed. All these variables are fed on-line to a simulator to predict the characteristics of the concentrate and tailings.The expert system modifies the set points of the distributed control system, including two routines: expert feedback and feed forward control. Several cases for different feed conditions are discussed.