Worst-case execution-time analysis for embedded real-time systems

In this article we give an overview of the worst-case execution time (WCET) analysis research performed by the WCET group of the ASTEC Competence Centre at Uppsala University. Knowing the WCET of a program is necessary when designing and verifying real-time systems. The WCET depends both on the program flow, such as loop iterations and function calls, and on hardware factors, such as caches and pipelines. WCET estimates should be both safe (no underestimation allowed) and tight (as little overestimation as possible). We have defined a modular architecture for a WCET tool, used both to identify the components of the overall WCET analysis problem, and as a starting point for the development of a WCET tool prototype. Within this framework we have proposed solutions to several key problems in WCET analysis, including representation and analysis of the control flow of programs, modeling of the behavior and timing of pipelines and other low-level timing aspects, integration of control flow information and low-level timing to obtain a safe and tight WCET estimate, and validation of our tools and methods. We have focussed on the needs of embedded real-time systems in designing our tools and directing our research. Our long-term goal is to provide WCET analysis as a part of the standard tool chain for embedded development (together with compilers, debuggers, and simulators). This is facilitated by our cooperation with the embedded systems programming-tools vendor IAR Systems.     

A compiler-hardware approach to software protection for embedded systems

Because of their rapid growth in recent years, embedded systems present a new front in vulnerability and an attractive target for attackers. Their pervasive use, including sensors and mobile devices, makes it easier for an adversary to gain physical access to facilitate both attacks and reverse engineering of the system. This paper describes a system - CODESSEAL - for software protection and evaluates its overhead. CODESSEAL aims to protect embedded systems from attackers with enough expertise and resources to capture the device and attempt to manipulate not only software, but also hardware. The protection mechanism involves both a compiler-based software tool that instruments executables and an on-chip FPGA-based hardware component that provides run-time integrity and control flow checking on the executable code. The use of reconfigurable hardware allows CODESSEAL to provide such security services as confidentiality, integrity and program-flow protection in a platform-independent manner without requiring a redesign of the processor. Similarly, the compiler instrumentation hides the security details from software developers. Software and data protection techniques are presented for our system and a performance analysis is provided using cycle accurate simulation. Our experimental results show that protecting instructions and data with a high level of security can be achieved with low performance penalty, in most cases less than 10%.     

A software integration approach for designing and assessing dependable embedded systems

Embedded systems increasingly entail complex issues of hardware-software (HW-SW) co-design. As the number and range of SW functional components typically exceed the finite HW resources, a common approach is that of resource sharing (i.e., the deployment of diverse SW functionalities onto the same HW resources). Consequently, to result in a meaningful co-design solution, one needs to factor the issues of processing capability, power, communication bandwidth, precedence relations, real-time deadlines, space, and cost. As SW functions of diverse criticality (e.g. brake control and infotainment functions) get integrated, an explicit integration requirement need is to carefully plan resource sharing such that faults in low-criticality functions do not affect higher-criticality functions.On this background, the main contribution of this paper is a dependability-driven framework that helps to conduct the integration of SW components onto HW resources such that the maintenance of system dependability over integration of diverse criticality components is assured by design.We first develop a clustering strategy for SW components into Fault Containment Modules (FCMs) such that error propagation via interaction is minimized. Subsequently, the rules of composition for FCMs with respect to error propagation are developed. To allocate the resulting FCMs to the existing HW resources we provide several heuristics, each optimizing particular attributes thereof. Further, a framework for assessing the goodness of the achieved HW-SW composition as a dependable embedded system is presented. Two new techniques for quantifying the goodness of the proposed mappings are introduced by examples, both based on a multi-criteria decision theoretic approach.     

Software performance tuning of software product family architectures: Two case studies in the real-time embedded systems domain

Software performance is an important non-functional quality attribute and software performance evaluation is an essential activity in the software development process. Especially in embedded real-time systems, software design and evaluation are driven by the needs to optimize the limited resources, to respect time deadlines and, at the same time, to produce the best experience for end-users. Software product family architectures add additional requirements to the evaluation process. In this case, the evaluation includes the analysis of the optimizations and tradeoffs for the whole products in the family. Performance evaluation of software product family architectures requires knowledge and a clear understanding of different domains: software architecture assessments, software performance and software product family architecture. We have used a scenario-driven approach to evaluate performance and dynamic memory management efficiency in one Nokia software product family architecture. In this paper we present two case studies. Furthermore, we discuss the implications and tradeoffs of software performance against evolvability and maintenability in software product family architectures.     

Requirements-driven database systems benchmark method

Benchmarks are the vital tools in the performance measurement, evaluation, and comparison of relational database management systems (RDBMS). Standard benchmarks such as the TP1, TPC-A, TPC-B, TPC-C, TPC-D, TPC-H, TPC-R, TPC-W, Wisconsin, and AS³AP benchmarks have been used to assess the performance of relational database management systems. These benchmarks are synthetic and domain-specific. Test results from these benchmarks are estimates of possible system performance for certain pre-determined application types. Database system performance on actual database domain may vary significantly from those in the standard benchmarks. In this paper, we describe a new benchmark method that is computer-assisted and developed from the perspective of the user's requirements.     

Reliability-driven deployment optimization for embedded systems

One of the crucial aspects that influence reliability of embedded systems is the deployment of software components to hardware nodes. If the hardware architecture is designed prior to the customized software architecture, which is often the case in product-line manufacturing (e.g. in the automotive domain), the system architect needs to resolve a nontrivial task of finding a (near-)optimal deployment balancing the reliabilities of individual services implemented on the software level.In this paper, we introduce an approach to automate this task. As distinct to related approaches, which typically stay with quantification of reliability for a specific deployment, we target multi-criteria optimization and provide the architect with near-optimal (non-dominated) deployment alternatives with respect to service reliabilities. Toward this goal, we annotate the software and hardware architecture with necessary reliability-relevant attributes, design a method to quantify the quality of individual deployment alternatives, and implement the approach employing an evolutionary algorithm.     

Continuity aspects of embedded reconfigurable computing

In embedded systems, dynamically reconfigurable computing can be partially modified at runtime without stopping the operation of the whole system. In this paper, we consider a reorganization mechanism for dynamically reconfigurable computing in embedded systems to guarantee that invariants of the design are respected. This reorganization is considered as a visual transformation of the logical configuration by the formulated rules. The invariant is recognized under the restructuring of the configuration using reconfiguration rules.     

Prototype of fault adaptive embedded software for large-scale real-time systems

This paper describes a comprehensive prototype of large-scale fault adaptive embedded software developed for the proposed Fermilab BTeV high energy physics experiment. Lightweight self-optimizing agents embedded within Level 1 of the prototype are responsible for proactive and reactive monitoring and mitigation based on specified layers of competence. The agents are self-protecting, detecting cascading failures using a distributed approach. Adaptive, reconfigurable, and mobile objects for reliablility are designed to be self-configuring to adapt automatically to dynamically changing environments. These objects provide a self-healing layer with the ability to discover, diagnose, and react to discontinuities in real-time processing. A generic modeling environment was developed to facilitate design and implementation of hardware resource specifications, application data flow, and failure mitigation strategies. Level 1 of the planned BTeV trigger system alone will consist of 2500 DSPs, so the number of components and intractable fault scenarios involved make it impossible to design an ‘expert system’ that applies traditional centralized mitigative strategies based on rules capturing every possible system state. Instead, a distributed reactive approach is implemented using the tools and methodologies developed by the Real-Time Embedded Systems group.     

Towards a homogeneous architecture for high-energy physics data acquisition systems

Data acquisition systems are mission-critical components in high-energy physics experiments. They are embedded in an environment of custom electronics, and are frequently characterized by high performance requirements. With the advent of powerful mainstream computing platforms and affordable high-speed networking equipment, system cost and time to completion can be significantly reduced. There still exists a considerable effort in custom software developments to build these systems and make them running efficiently. Therefore we strive for a software architecture flexible and robust enough to be usable in different system configurations and deployment cases. The software should cover the largest possible application domain and provide a practical balance between efficiency and flexibility. This article pinpoints the requirements imposed on such an on-line software infrastructure and sheds light on a viable design approach. As such, this article aims at laying out the foundations for a broader understanding of the importance for fostering a homogeneous architecture for high-energy physics data acquisition.     

A configurable cryptography subsystem in a middleware framework for embedded systems

Computer and network security is becoming increasingly important as both large systems and, increasingly small, embedded systems are networked. Middleware frameworks aid the system developer who must interconnect individual systems into larger interconnected, distributed systems. However, there exist very few middleware frameworks that have been designed for use with embedded systems, which constitute the vast majority of CPUs produced each year, and none offer the range of security mechanisms required by the wide range of embedded system applications. This paper describes MicroQoSCORBA, a highly configurable middleware framework for embedded systems, and its security subsystem. It first presents an analysis of security requirements for embedded applications and what can and should be done in middleware. It then presents the design of MicroQoSCORBA’s security subsystem and the wide range of mechanisms it supports. Experimental results for these mechanisms are presented for two different embedded systems and one desktop computer that collectively represent a wide range of computational capabilities.     

A distributed development environment for embedded software

The HAGAR project is building a high-performance disk controller. It is an embedded system for which many hundreds of thousands of lines of embedded software will have to be developed concurrently with the development of the hardware. We found existing methods for embedded software development, such as simulation and remote cross development, to be inadequate for us. To meet our special needs, we developed a distributed development environment that combines and extends the capabilities of existing methods while fixing their drawbacks. Our environment is based on a processor-pool architecture, in which multiple hardware sets are pooled and managed systematically. It supports embedded software development for many programmers at different sites. It allows for the emulation of non-existing hardware adaptor cards and for the integration of embedded software testing with hardware simulation. The environment provides a single system image, hiding many hardware and configuration details from its users. From the perspective of the programmers, our environment makes developing embedded software for special hardware systems as easy as developing application programs for a UNIX workstation.     

An architectural approach with separation of concerns to address extra-functional requirements in the development of embedded real-time software systems

A large proportion of the requirements on embedded real-time systems stems from the extra-functional dimensions of time and space determinism, dependability, safety and security, and it is addressed at the software level. The adoption of a sound software architecture provides crucial aid in conveniently apportioning the relevant development concerns. This paper takes a software-centered interpretation of the ISO 42010 notion of architecture, enhancing it with a component model that attributes separate concerns to distinct design views. The component boundary becomes the border between functional and extra-functional concerns. The latter are treated as decorations placed on the outside of components, satisfied by implementation artifacts separate from and composable with the implementation of the component internals. The approach was evaluated by industrial users from several domains, with remarkably positive results.     

Specification and performance analysis of embedded systems with coloured petri nets

To analyze synchronization, concurrency, communication protocols and system performance, a system level specification is modelled in a coloured Petri net. A toolbox collects information for the implementation, e.g., processing times, waiting times, idle times, data accesses, processing requests. This is illustrated with a data-link protocol system, where the disturbance on the communication channels is modelled, too.     

LyraNET: A zero-copy TCP/IP protocol stack for embedded systems

Embedded systems are usually resource limited in terms of processing power, memory, and power consumption, thus embedded TCP/IP should be designed to make the best use of limited resources. Applying zero-copy mechanism can reduce memory usage and CPU processing time for data transmission. Power consumption can be reduced as well. In this paper, we present the design and implementation of zero-copy mechanism in the target embedded TCP/IP component, LyraNET, which is derived from Linux TCP/IP codes and remodeled as a reusable software component that is independent from operating systems and hardware. Performance evaluation shows that TCP/IP protocol processing overhead can be significantly decreased by 23–63%. Besides, object code size of this network component is only 77.64% of the size of the original Linux TCP/IP stack. The experience of this study can serve as the reference for embedding Linux TCP/IP stack into a target system that requires network connectivity and improving the transmission efficiency of Linux TCP/IP by zero-copy implementation. This paper is an extended version of the paper “LyraNET: A Zero-Copy TCP/IP Protocol Stack for Embedded Operating Systems” that appeared in the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Mei-Ling Chiang received the B.S. degree in Management Information Science from National Chengchi University, Taipei, Taiwan, in 1989. She received the M.S. degree in 1993 and her Ph.D degree in 1999 in Computer and Information Science from National Chiao Tung University, Hsinchu, Taiwan. Now she is an Assistant Professor in the Department of Information Management at National Chi-Nan University, Puli, Taiwan. Her current research interests include operating systems, embedded systems, and clustered systems. Yun-Chen Lee received the B.S degree in 2002 and the M.S. degree in 2005 in Information Management from National Chi-Nan University, Puli, Taiwan. He is currently a software engineer in InterVideo Digital Tech., responsible for software development of multimedia-related products.     

Supporting UML-based development of embedded systems by formal techniques

We describe an approach to support UML-based development of embedded systems by formal techniques. A subset of UML is extended with timing annotations and given a formal semantics. UML models are translated, via XMI, to the input format of formal tools, to allow timed and non-timed model checking and interactive theorem proving. Moreover, the Play-Engine tool is used to execute and analyze requirements by means of live sequence charts. We apply the approach to a part of an industrial case study, the MARS system, and report about the experiences, results and conclusions. This work has been supported by EU-project IST 33522 – OMEGA “Correct Development of Real-Time Embedded Systems in UML”. For more information, see . During this project, the second author was at theWeizmann Institute of Science, the third author at VERIMAG, the fourth author at OFFIS, and the fifth author at NLR.     

Optimizing CAM-based instruction cache designs for low-power embedded systems

Energy consumption and power dissipation are important concerns in the design of embedded systems and they will become even more crucial with finer process geometry, higher frequencies, deeper pipelines and wider issue designs. In particular, the instruction cache consumes more energy than any other processor module, especially with commonly used highly associative CAM-based implementations.Two energy-efficient approaches for highly associative CAM-based instruction cache designs are presented by means of using a segmented wordline and a predictor-based instruction fetch mechanism. The latter is based on the fact that not all instructions in a given I-cache fetch are used due to taken branches. The proposed Fetch Mask Predictor unit determines which instructions in a cache access will actually be used to avoid fetching any of the other instructions. Both proposed approaches are evaluated for an embedded 4-wide issue processor in 100 nm technology. Experimental results show average I-cache energy savings of 48% and overall processor energy savings of 19%.     

Distributed real-time embedded systems: Recent advances, future trends and their impact on manufacturing plant control

Real-time and embedded systems have historically been small scale. However, advances in microelectronics and software now allow embedded systems to be composed of a large set of processing elements, and the trend is towards significant enhanced functionality, complexity, and scalability, since those systems are increasingly being connected by wired and wireless networks to create large-scale distributed real-time embedded systems (DRES). Such embedded computing and information technologies have become at the same time an enabler for future manufacturing enterprises as well as a transformer of organizations and markets. This paper discusses opportunities for using recent advances in the DRES area in the deployment of intelligent, adaptive, and reconfigurable manufacturing plant control architectures.     

A CASE-tool oriented approach for embedded systems design

The process of successfully creating an embedded system is highly challenging and complex; engineers typically operate under tight financial, technical and time-to-market constraints. To achieve the desired objective, the design team need to utilise effectively the most advanced software tools available, in order that the task may be completed to specification in a timely and cost-effective manner. This paper discusses the use of a CASE-tool in an embedded systems design, and reviews issues pertaining to the integration of such a tool into an embedded systems development environment. The paper focuses on the application of this high level approach in embedded systems design and concludes by describing the use of the CASE-tool in the design of a simple demonstrator.