Integrating best effort and fixed priority scheduling

Adaptive and dynamic behaviour is seen as one of the key characteristics of next generation hard real-time systems. Whilst fixed priority pre-emptive scheduling is becoming a de facto standard in real-time system implementation, it remains inflexible in its purest form. One approach to countering this criticism is to allow optional components, not guaranteed offline, to be executed at run-time. Optional components may be guaranteed a minimum set of resources at run-time, with competing resource requests scheduled according to the best-effort approach. This allows increased dynamic behaviour and improves the utility of the system. In this paper, we discuss this integration of fixed priority and best-effort scheduling.     

Reliability-aware scheduling for reducing system-wide energy consumption for weakly hard real-time systems

While energy consumption is the primary concern for the design of real-time embedded systems, reliability and Quality of Service (QoS) are becoming increasingly important in the development of today’s pervasive computing systems. In this paper, we present a reliability-aware energy management (RAEM) scheme for reducing the energy consumption for weakly hard real-time systems with (m, k)-constraints, which requires that at least m out of any k consecutive jobs of a task meet their deadlines. In order to ensure the (m, k)-constraints while preserving the system reliability, we propose to partition the real-time jobs into mandatory and optional ones as well as to reserve recovery space for mandatory ones in an adaptive way. Moreover, efficient on-line scheduling techniques are proposed to reduce the system-wide energy, which is consumed not only by the processor but also by other peripheral devices at run-time. Through extensive simulations, our experiment results demonstrate that the proposed techniques can significantly outperform the previous research in reducing system-wide energy consumption for weakly hard real-time systems while preserving the system reliability.     

Formal approach to agent-based dynamic reconfiguration in Networks-On-Chip

A Network-On-Chip (NoC) platform is an emerging topology for large-scale applications. It provides a required number of resources for critical and excessive computations. However, the computations may be interrupted by faults occurring at run-time. Hence, reliability of computations as well as efficient resource management at run-time are crucial for such many-core NoC systems. To achieve this, we utilize an agent-based management system where agents are organized in a three-level hierarchy. We propose to incorporate reallocation and reconfiguration procedures into agents hierarchy such that fault-tolerance mechanisms can be executed at run-time. Task reallocation enables local reconfiguration of a core allowing it to be eventually reused in order to restore the original performance of communication and computations. The contributions of this paper are: (i) an algorithm for initial application mapping with spare cores, (ii) a multi-objective algorithm for efficient utilization of spare cores at run-time in order to enhance fault-tolerance while maintaining efficiency of communication and computations at an adequate level, (iii) an algorithm integrating the local reconfiguration procedure and (iv) formal modeling and verification of the dynamic agent-based NoC management architecture incorporating these algorithms within the Event-B framework.     

Correspondence: Criticality and utility in the next generation

Conclusion One of the issues raised by the editorial of Stankovic and Ramamritham is that of using unbounded software components within the context of real-time systems. We have attempted to give a different perspective to this issue; specifically how can we increase at run-time, the utility of 100% guaranteed tasks. We believe that many future systems will contain predominantly crucial computations. The need to have full predictability remains. Indeed, there is a need to develop platforms that have realistic worst case performance to probability levels compatible with the overall failure hypothesis.     

基于软实时多处理器系统的动态低功耗算法

结合DVS技术和(m,k)-firm模型，提出一个保证完成率、适用于软实时多电压多处理器系统中有依赖关系任务集的动态低功耗算法VAP_DY。该算法权衡应用的性能需求、执行时间的不确定性和系统对合理执行失败的容忍来动态调整每个处理器运行时的供电电压,以降低多处理器系统的总功耗。分析和实验结果表明，VAP_DY能够在保证时间和完成率约束的条件下有效降低系统功耗。     

Event-based run-time adaptation in communication-centric systems

Communication-centric systems are software systems built as assemblies of distributed artifacts that interact following predefined communication protocols. Session-based concurrency is a type-based approach to ensure the conformance of communication-centric systems to such protocols. This paper presents a model of session-based concurrency with mechanisms for run-time adaptation. Our model allows us to specify communication-centric systems whose session behavior can be dynamically updated at run-time. We improve on previous work by proposing an event-based approach: adaptation requests, issued by the system itself or by its context, are assimilated to events which may trigger adaptation routines. These routines exploit type-directed checks to enable the reconfiguration of processes with active protocols. We equip our model with a type system that ensures communication safety and consistency properties: while safety guarantees absence of run-time communication errors, consistency ensures that update actions do not disrupt already established session protocols. We provide soundness results for binary and multiparty protocols.     

A network level channel abstraction for multimedia communication inreal-time networks

The design of communication protocols to support guaranteed real-time communication for distributed multimedia systems is examined. A network level abstraction called φ-channel that supports the requirements of real-time applications is proposed. A φ-channel represents a fractional, simplex, end-to-end communication channel between a source and a destination. The channel is characterized by a set of specific performance parameters associated with its traffic. The required performance characteristics of a φ-channel are specified in terms of the packet maximum end-to-end delay and the maximum number of packets that can be sent over that delay. The primary attribute supported by the φ-channel is the on-time reliability. Based on the specified parameters, the underlying delivery system verifies the feasibility of supporting such a channel. The performance of an accepted φ-channel is guaranteed under any conditions, barring hardware failures. The basic scheme that the model uses to verify the feasibility of accepting a φ-channel and the run-time support used to guarantee its performance are described. The results of a simulation experiment implementing the basic functionalities of the proposed scheme are also presented     

Task behavior monitoring for adaptive real-time communication

Real-time distributed systems include communicating tasks that interact via message-passing. In such systems the timely delivery of messages is essential for meeting task timing constraints. Consequently, in addition to task execution times, message delivery times must also be constrained. In order to minimize the number of failures to meet timing constraints message communication protocols, in addition to task scheduling algorithms, play a crucial role. A legitimate question to ask is whether making such protocols adaptive to run-time system and environment status can significantly improve system performance. Consequently, a rum-time monitoring approach to adaptive real-time distributed systems is proposed; the work focuses on an investigation of adaptive message communication protocols and corresponding run-time support mechanisms. Simulation is used to obtain performance results. It is concluded that although improvement is obtained it ,ay not be significant enough to offset the increased overhead and requirement for task information.     

Reflection and time-dependent computing: Experiences with the R2 architecture

In this paper we present an application of computational reflection in the programming oftime-dependent systems. A time-dependent system performs its tasks according to timing specifications specified within the system or imposed from outside the system. Reflective techniques can be applied to programming time-dependent systems because (1) some application programs require the introduction of a new language construct for specifying timing requirements and (2) different applications may require domain-specific scheduling algorithms. To allow a programmer to add or modify language constructs or scheduling algorithms, however, a clear reflective architecture and program interfaces must be provided. This paper proposes a concurrent object-based reflective architecture (R ² architecture) for time-dependent computing. This architecture is based on anindividual reflection scheme and introduces new meta-level objects (real-time meta objects) that are responsible for time-dependent capabilities. An alarm-clock object and a scheduler object are introduced, and message protocols between them and real-time meta objects are defined. We implemented this architecture on ABCL/R2 and created the Sampled Sound Player program as an application. With this application we provided three different scheduler objects and measured the impact of different scheduling algorithms on sound playback. The measured results show that a scheduler with more complex computations at the meta level exhibited less scheduling overhead, thus was capable of better sound playback. The other example, Time-dependent Graceful Degradation Scheme, demonstrates the programming of functionality degradation triggered by failure to satisfy timing specifications.     

A dynamic execution time estimation model to save energy in heterogeneous multicores running periodic tasks

Nowadays, real-time embedded applications have to cope with an increasing demand of functionalities, which require increasing processing capabilities. With this aim real-time systems are being implemented on top of high-performance multicore processors that run multithreaded periodic workloads by allocating threads to individual cores. In addition, to improve both performance and energy savings, the industry is introducing new multicore designs such as ARM’s big.LITTLE that include heterogeneous cores in the same package.A key issue to improve energy savings in multicore embedded real-time systems and reduce the number of deadline misses is to accurately estimate the execution time of the tasks considering the supported processor frequencies. Two main aspects make this estimation difficult. First, the running threads compete among them for shared resources. Second, almost all current microprocessors implement Dynamic Voltage and Frequency Scaling (DVFS) regulators to dynamically adjust the voltage/frequency at run-time according to the workload behavior. Existing execution time estimation models rely on off-line analysis or on the assumption that the task execution time scales linearly with the processor frequency, which can bring important deviations since the memory system uses a different power supply.In contrast, this paper proposes the Processor–Memory (Proc–Mem) model, which dynamically predicts the distinct task execution times depending on the implemented processor frequencies. A power-aware EDF (Earliest Deadline First)-based scheduler using the Proc–Mem approach has been evaluated and compared against the same scheduler using a typical Constant Memory Access Time model, namely CMAT. Results on a heterogeneous multicore processor show that the average deviation of Proc–Mem is only by 5.55% with respect to the actual measured execution time, while the average deviation of the CMAT model is 36.42%. These results turn in important energy savings, by 18% on average and up to 31% in some mixes, in comparison to CMAT for a similar number of deadline misses.     

Flexible hard real-time scheduling for deliberative AI systems

Constructing deliberative real-time AI systems is challenging due to the high execution-time variance in AI algorithms and the requirement of worst-case bounds for hard real-time guarantees, often resulting in poor use of system resources. Using a motivating case study, the general problem of resource usage maximization is addressed. We approach the issues by employing a hybrid task model for anytime algorithms, which is supported by recent advances in fixed priority scheduling for imprecise computation. In particular, with a novel scheduling scheme based on Dual Priority Scheduling, hard tasks are guaranteed by schedulability analysis and scheduled in favor of optional and anytime components which are executed whenever possible for enhancing system utility. Simulation studies show satisfactory performance on the case study with the application of the scheduling scheme. We also suggest how aperiodic tasks can be scheduled effectively within the framework and how tasks can be prioritized based on their utilities by an efficient algorithm. These works form a comprehensive package of scheduling model, analysis, and algorithms based on fixed priority scheduling, providing a versatile platform where real-time AI applications can be suitably facilitated.

Dispatching stream operators in parallel execution of continuous queries

Data stream is a continuous, rapid, time-varying sequence of data elements which should be processed in an online manner. These matters are under research in Data Stream Management Systems (DSMSs). Single processor DSMSs cannot satisfy data stream applications?? requirements properly. Main shortcomings are tuple latency, tuple loss, and throughput. In our previous publications, we introduced parallel execution of continuous queries to overcome these problems via performance improvement, especially in terms of tuple latency. We scheduled operators in an event-driven manner which caused system performance reduction in periods between consecutive scheduling instances. In this paper, a continuous scheduling method (dispatching) is presented to be more compatible with the continuous nature of data streams as well as queries to improve system adaptivity and performance. In a multiprocessing environment, the dispatching method forces processing nodes (logical machines) to send partially-processed tuples to next machines with minimum workload to execute the next operator on them. So, operator scheduling is done continuously and dynamically for each tuple processed by each operator. The dispatching method is described, formally presented, and its correctness is proved. Also, it is modeled in PetriNets and is evaluated via simulation. Results show that the dispatching method significantly improves system performance in terms of tuple latency, throughput, and tuple loss. Furthermore, the fluctuation of system performance parameters (against variation of system and stream characteristics) diminishes considerably and leads to high adaptivity with the underlying system.     

Building Web Knowledge Flows based on Interactive Computing with Semantics

Web personalized services alleviate the burden of information overload by providing right information which meets individual user’s needs. How to obtain and represent knowledge needed by users is a key issue. This paper presents Web Knowledge Flow (WKF) to represent the specific knowledge on Web pages and a model of Interactive Computing with Semantics (ICS) to provide a feasible means of generating WKF. Objective WKF (OWKF) and Real-time WKF (RWKF) are firstly proposed to satisfy staged and real-time user interests. Secondly, the generation algorithm of WKF is proposed based on Semantics Link Network. Thirdly, “interactive point” is introduced to detect the moment of user interests change to ensures the dynamics of WKF. Experimental results demonstrate that ICS can effectively capture the change of user interests and the generated WKF can satisfy user requirements accurately.     

Exact Acceleration of Real-Time Model Checking

Different time scales do often occur in real-time systems, e.g., a polling real-time system samples the environment many times per second, whereas the environment may only change a few times per second. When these systems are modeled as (networks of) timed automata, the validation using symbolic model checking techniques can significantly be slowed down by unnecessary fragmentation of the symbolic state space. This paper introduces a syntactical adjustment to a subset of timed automata that addresses this fragmentation problem and that can speed-up forward symbolic reachability analysis in a significant way. We prove that this syntactical adjustment does not alter reachability properties and that it indeed is effective. We illustrate our exact acceleration technique with run-time data obtained with the model checkers Uppaal and Kronos. Moreover, we demonstrate that automated application of our exact acceleration technique can significantly speed-up the verification of the run-time behavior of LEGO Mindstorms programs.     

Problems with expert systems in real-time control

There is increasing use of knowledge-based or expert systems in the process and manufacturing industries, with currently in excess of 2000 installations. The advantage offered by such systems is their ability to deal with complex and possibly incorrect or incomplete data. A new generation of expert-system tools, designed specifically for real-time control applications, has been developed. This paper examines the requirements of an expert system for real-time control, and shows how current approaches attempt to meet them. It is argued that none of the currently available tools fully satisfy the needs of a real-time expert control system, particularly in terms of reliability and guaranteed real-time response.     

Expressing embedded systems configurations at high abstraction levels with UML MARTE profile: Advantages,limitations and alternatives

Embedded systems have become an essential aspect of our professional and personal lives. From avionics, transport and telecommunication systems to general commercial appliances such as smart phones, high definition TVs and gaming consoles; it is difficult to find a domain where these systems have not made their mark. Moreover, Systems-on-Chips (SoCs) which are considered as an integral solution for designing embedded systems, offer advantages such as run-time reconfiguration that can change system configurations during execution, depending upon Quality-of-Service (QoS) criteria such as performance and energy levels. This article deals with aspects related to modeling of these configurations, useful for describing various states of an embedded system, from both structural and operational viewpoints. Our proposal adapts a high abstraction level approach based on the principles of Model-Driven Engineering (MDE) and takes into account the UML MARTE profile for modeling of real-time and embedded systems. Elevating the design abstraction levels help to increase design productivity and achieve execution platform independence, among other advantages. The article details the current proposition of configurations in MARTE via some examples, and points out the advantages as well as some limitations, mainly concerning the semantic aspects of the defined concepts. Finally, we report our experiences on the modeling of an alternate notion of configurations and execution modes within the MARTE compliant Gaspard2 SoC Co-Design framework that has been successful for the design as well as implementation of FPGA based SoCs.     

An efficient algorithm for optimal control of PWA systems with polyhedral performance indices

We present an algorithm for the computation of explicit optimal control laws for piecewise affine (PWA) systems with polyhedral performance indices. The algorithm is based on dynamic programming (DP) and represents an extension of ideas initially proposed in Kerrigan and Mayne [(2003). Optimal control of constrained, piecewise affine systems with bounded disturbances. In Proceedings of the 41st IEEE conference on decision and control, Las Vegas, Nevada, USA, December], and Baoti? et al. [(2003). A new algorithm for constrained finite time optimal control of hybrid systems with a linear performance index. In Proceedings of European control conference, Cambridge, UK, September]. Specifically, we show how to exploit the underlying geometric structure of the optimization problem in order to significantly improve the efficiency of the off-line computations. An extensive case study is provided, which clearly indicates that the algorithm proposed in this paper may be preferable to other schemes published in the literature.     

Hardware-Efficient and Highly Reconfigurable 4- and 2-Track Fault-Tolerant Designs for Mesh-Connected Arrays

We consider m-track models for constructing fault-tolerant (FT) mesh systems which have one primary and m spare tracks per row and column, switches at the intersection of these tracks, and spare processors at the boundaries. A faulty system is reconfigured by finding for each fault u a reconfiguration path from the fault to a spare in which, starting from the fault u, a processor is replaced or “covered” by the nearest “available” succeeding processor on the path—a processor on the path is not available if it is faulty or is used as a “cover” on some other reconfiguration path. In previous work, a 1-track design that can support any set of node-disjoint straight reconfiguration paths, and a more reliable 3-track design that can support any set of node-disjoint rectilinear reconfiguration paths have been proposed. In this research note, we present: (1) A fundamental result regarding the universality of simple “one-to-one switches” in m-track 2-D mesh designs in terms of their reconfigurabilities. (2) A 4-track mesh design that can support any set of edge-disjoint (a much less restrictive criterion than node-disjointness) rectilinear reconfiguration paths, and that has 34% less switching overhead and significantly higher, actually close-to-optimal, reconfigurability compared to the previously proposed 3-track design. (3) A new 2-track design derived from the above 4-track design that we show can support the same set of reconfiguration paths as the previous 3-track design but with 33% less wiring overhead. (4) Results on the deterministic fault tolerance capabilities (the number of faults guaranteed reconfigurable) of our 4- and 2-track designs, and the previously proposed 1- and 3-track designs.     

Issues in the Design and Control of Parallel Rule-Firing Production Systems

The parallel execution of rules in a production system provides the potential for faster execution, but increases the complexity of control and design issues. We address two issues: controlling the execution of productions without introducing serial bottlenecks and maintaining correctness during the course of simultaneous rule executions. Two novel rule-firing policies are described: an asynchronous rule-firing policy that causes rules to be executed as soon as they become enabled and a task-based scheduler that allows multiple independent tasks to run asynchronously with respect to each other while allowing rules to execute either synchronously or asynchronously within the context of each task. Previous research in parallel rule-firing systems has indicated that a serializable result cannot be guaranteed without a run-time mechanism for detecting potentially harmful rule interactions. Our analysis of such mechanisms indicates that their overhead is prohibitive for asynchronous rule-firing systems. In exchange for improved performance, we trade the guarantee of serializability for the somewhat weaker claim that correct parallel rule-firing programs may be designed, given the appropriate language mechanisms. We present a simple locking scheme for working memory, which, when coupled with the appropriate language idioms, allows serializable programs to be developed without incurring the expense of run-time interference detection. The experimental results of this research are presented in the context of UMass Parallel OPS5, a rule-based language that incorporates parallelism at the rule, action, and match levels, and provides language constructs for supporting the design of parallel rule-based programs. Results are presented for a number of programs illustrating common AI paradigms including search, inference, and constraint satisfaction problems.