This section covers:
- Control of Real-Time Computing Systems
- Real-Time Techniques in Control System Implementation
- Design Tools for Embedded Control Systems

For a more detailed state-of-the-art overview we refer to the roadmap developed by the cluster during Year 1, see


Control of Real-Time Computing Systems

Feedback-based approaches have always been used in engineering systems. One example is the flow and congestion control mechanisms in the TCP transport protocol. Typical of many applications of this type is that feedback control is used in a more or less ad hoc way without any connections to control theory. During the last few years this situation has changed. Today control theory is beginning to be applied to real-time computing and communication systems in a more structured way. Dynamic models are used to describe how the performance or Quality of Service (QoS) depends on the resources at hand. The models are then analyzed to determine the fundamental performance limitations of the system. Based on the model and the specifications, control design is performed. In some cases the analysis and design is based on optimization. The areas where currently most work is being performed are control of server systems, control of CPU scheduling, and control of communication networks.

The main example from the first area is large multi-tier eCommerce servers, of the type used by companies like Amazon and Google. Another example is servers in web-hotels. Servers of these types are complex dynamic systems with high levels of uncertainty. The need for control arises at several levels, e.g., admission control, delay control, and utilization control. This type of application imposes several new challenges for the control field. Since the servers are engineering artefacts, first principles do not apply, at least not on the macroscopic level. Several competing modelling formalisms need to be combined, e.g., continuous-time flow models, queuing models, and various types of event-based models. System stability has an unclear meaning, and the whole issue of how to write controllable and observable software systems is still largely unexplored.
In real-time systems with hard timing constraints, e.g., deadlines, it is paramount that all timing constraints are fulfilled. If sufficient information is available about worst-case resource requirements, e.g., worst-case execution times (WCET), then the results from classical schedulability theory can be applied to decide if this is the case or not. Using, e.g., priority-based or deadline-based scheduling strategies, it is then possible to provide a system implementation that guarantees that the timing constraints are fulfilled at all times.

However, in many situations the hard real-time scheduling approach is unpractical. Worst-case numbers are notoriously difficult to derive. In order to be on the safe side, a heuristically chosen safety margin is often added to measurements of “worst-case values”. This may lead to under-utilization of resources. In other cases resource requirements vary greatly over time. The reason for this may be changes in the external load on the system, e.g., large variations in the number of requests to a web server, or mode changes in application tasks. Again, designing the system for the worst case may lead to under-utilization. The above situations are both caused by uncertainty. A major strength of control theory is its ability to manage uncertainty.

In feedback scheduling of CPU resources the allocation of resources is based on a comparison of the actual resource consumption by, e.g., a set of tasks, with the desired resource consumption. The difference is then used for deciding how the resources should be allocated to the different users. The decision mechanism constitutes the actual controller in the feedback scheduling scheme. A key observation here is that feedback scheduling is not suitable for applications that are truly hard in nature. The reason for this is that feedback acts on errors. In the CPU utilization case above this would mean that some tasks temporarily might receive less resources than required, i.e., they could miss deadlines. Feedback scheduling is therefore primarily suited for applications that are soft, i.e., tolerate occasional deadline misses without any catastrophic effects, or that are said to be adaptive. The latter means that missing one or more deadline does not jeopardize correct system behaviour, but only causes performance degradation.

For this type of systems, the goal is typically to meet some QoS requirements. The adaptive class of real-time systems is a suitable description for many practical applications. This includes different types of multimedia applications, and web server systems. It also includes a large class of control applications. Most control systems can tolerate occasional deadline misses. The control performance or Quality of Control (QoC) is also dependent on to which degree the timing requirements are fulfilled. It is only in safety critical control applications, e.g., automotive steer-by-wire applications, that the hard real-time model really is motivated.

Traffic control of communication networks involves issues such as congestion control, routing and admission control. Of particular interest is congestion control and how to control heterogeneous networks consisting of a blend of wired and wireless links.

The research on control of computing systems has increased immensely and gained a large interest during the last years. A large number of applications have been proposed in different areas, e.g., high-performance web, multimedia streaming, real-time databases], web storage systems, network routers, active queue management schemes, processor architectures, and control systems. However, so far most of the work presented in literature has been conducted by scientists working either in the real-time computing or telecommunication fields or in the automatic control field. Unfortunately, this has sometimes led to erroneous models and strange results.

The development within this area during the last year can be described by a steady development rather any revolutionary breakthroughs. An important event was the establishment of the workshop series Workshop on Feedback Control Implementation and Design in Computing Systems and Networks (FeBID) that was held this year in Vancouver and will be held next year in Munich. Generally, the research is currently more aimed at studying larger applications, e.g., large multi-tier server systems. Experimental results are also something that is very important.

Real-Time Techniques in Control System Implementation

By tradition, the design of embedded control systems is based on the principle of separation of concerns. This separation is based on the assumption that feedback controllers can be modeled and implemented as periodic tasks that have a fixed period, a known worst-case bound on the execution time (WCET), and a hard deadline. The latter implies that it is imperative that the tasks always meet their deadlines, i.e., that the actual execution time (response time) is always less or equal to the deadline, for each invocation of the task. This is in contrast to a soft deadline, which may occasionally be violated. The fixed-period assumption of the simple task model has also been widely adopted by the control community and has resulted in the development of the sampled computer-control theory with its assumption of deterministic, equidistant sampling. The separation of concerns has allowed the control community to focus on the pure control design without having to worry about how the control system eventually is implemented. At the same time, it has allowed the real-time computing community to focus on development of scheduling theory and computational models that guarantee that hard deadlines are met, without any need to understand what impact scheduling has on the stability and performance of the plant under control.

Historically, the separated development of control and scheduling theories for computer-based control systems has produced many useful results and served its purpose well. However, the separation has also had negative effects. The two communities have partly become alienated. This has led to a lack of mutual understanding between the fields. The assumptions of the simple model are also overly restrictive with respect to the characteristics of many control loops. Many control loops are not periodic, or they may switch between a number of different fixed sampling periods. Control loop deadlines are not always hard. On the contrary, many controllers are quite robust to variations in sampling period and response time. Hence, it is arguable whether it is necessary to model them as hard-deadline tasks or not.
From an industrial point of view it can in many cases also be expensive or difficult to pursue a separation-based design approach. Guaranteeing hard deadlines and providing tight bounds on input output latency is costly. It may require the use of computational models which do not match the current state of practice. It requires good worst-case execution time estimates. It often implies that the resource utilization is quite low. Hence, in many industrial application, although the intention is to separate the concerns between control and computing, a complete separation will not be achieved. The effect of this is undesired interactions between the computing system and control system, e.g., jitter and delays, having a negative effect on control performance.

The relationship between computer system design parameters and control performance is quite complex. Scheduling and networking related parameters such as thread periods, deadlines, priorities, protocols, etc., influence the controller task parameters (latencies, jitter, etc) in a complex way. Similarly the controller task parameters influence the control performance parameters (e.g., rise time, overshoot, signal variances, etc) in an equally complex way. Hence, also in applications where a separation of concerns-based design approach is followed, the need is large for analysis tools that help the designer to quantify the relationships above.

The main drawbacks with the separations of concerns are that it does not always utilize the available computing resources in an optimal way, and that it sometimes gives rise to worse control performance than what can be achieved if the design of the control and real-time computing parts are integrated. This is particularly important for embedded control applications with limited computing and communication resources, with demanding performance specifications and high requirements on flexibility. For these types of applications, better performance can be achieved if a codesign approach is adopted where the control system is designed taking the resource constraints into account and where the real-time computing and scheduling is designed with the control performance in mind. The resulting implementation-aware control systems are better suited to meet the requirements of embedded and networked applications.

Of special interest for the work in this activity is temporal robustness in control systems, i.e., robustness towards implementation-level timing uncertainties and implementation-level functional robustness, i.e., tolerance towards implementation platform faults. Increased understanding of which types of temporal guarantees that really are required by a given control application in order to meet desired specifications is needed. Different computational models are more or less well suited for control system implementation. Software component technology and domain-specific languages for control systems are important ingredients in control systems implementation as well as model-based development tools.

Also in this field there has been a steady progress during the year. The push towards using sensor network technology in control applications has increased the need for control system implementation techniques that are temporally robust and resource-efficient.

Design Tools for Embedded Control Systems

Control systems design has traditionally been treated separately from the design of its software and hardware implementation. The increasing use of embedded control in for example distributed, safety critical and mass-produced systems has caused an increasing need for the simultaneous consideration of the control system and its implementation platform during development. To this end, there is a need for both theoretical contributions and supporting tools that assist designers in understanding and analyzing the intricate relationships between the qualities, such as control performance, robustness and cost, and design parameters related to control system and platform design.

There exist numerous types of tools that support co-design, at least partially. One such example is multi-domain modelling languages such as Ptolemy II and Metropolis. In these systems it is possible to model heterogeneous systems consisting of several different models of computation simultaneously. However, the tools are typically weak at representing continuous-time plant dynamics. Another tool category is scheduling simulators that have been extended with support for simulation of continuous dynamics. One such example is RTSIM. These tools typically do not support simulation of networks. A similar category of tools are network simulators, such as ns-2, that have been extended with support for continuos-time dynamics. These can be used to simulate networked control loops, but are not well suited for simulation of real-time kernels. Software emulators such as, e.g. Simics, emulate the behaviour of a real-time kernel on the machine instruction level. It is also possible to extend these with support for simple network models. However, again these types of tools are not intended for simulation of the continuous plant dynamics. Hence, there exists a variety of tools from different categories, but few of them can handle all the aspects that are of interest for networked embedded control systems.

The approach taken in the cluster is to focus on Matlab/Simulink as the basic platform. This is the standard analysis, design, and simulation environment for control engineers today. In our Matlab/Simulink tools we have then added support for scheduling, simulation of real-time kernels and networks and control performance analysis.
Model integration and management constitute key challenges in the design of embedded systems. At the workshop on “Tool Integration in System Development” (at the ESEC 2003 conference), one central outcome from the discussions was that available classical results such as the ECMA reference model for case environments (European Computer Manufacturer’s Association. A Reference Model for Frameworks of Computer Assisted Software Engineering Environments) and basic tool-integration mechanisms/middleware services such as CORBA do not really address the essence of the problem. New technologies and frameworks such as ECLIPSE or the OMG’s MDA activities in the area of “model-driven application development” promise to really address the problem in form of (meta-) model-based tool integration but their applicability remains to be proven especially for non standard domains with rather heterogeneous tool landscapes such as embedded systems. Many efforts in the area of tool integration focus on specific inter-relations and on ad-hoc integration of a few views, e.g. integrating safety analysis with architecture design. Another example of this is various co-design efforts. While such efforts can be very useful in a specific setting they provide no solution to the more general problem of model integration. A framework supporting systematic integration, catering for different types of models, relations and integration needs is needed for embedded control systems. An important industrial requirement on solutions is tailorability to suit different needs.

(c) Artist Consortium, All Rights Reserved - 2006, 2007, 2008, 2009

Réalisation Axome - Création de sites Internet