Embedded Software

Effective design of embedded computer systems requires considering information from multiple domains in a model-centered approach. Using a model-centered approach, the system designer defines and composes models representing multiple system perspectives throughout the design, implementation and testing process. Rosetta is a heterogeneous systems-level modeling language designed to support specification and analysis of complex, computer-based systems. Rosetta provides a model-centered specification capability that allows specifiers to define and combine system models. Users define models, called facets, and assemble those models to define components and systems using facet composition. Each facet model is written with reference to a domain that defines a vocabulary and semantics for the model definition. To model interaction between specifications from different domains, Rosetta provides an interaction definition mechanism based on institution theory. The Rosetta model-centered specification approach allows systems designers to specify many domains of interest from many perspectives and supports predictive design analysis at the systems-level.

This paper describes the modeling language Charon for modular design of interacting hybrid systems. The language allows specification of architectural as well as behavioral hierarchy, and discrete as well as continuous activities. The modular structure of the language is not merely syntactic, but is exploited by analysis tools, and is supported by a formal semantics with an accompanying compositional theory of refinement. We illustrate the benefits of Charon in design of embedded control software using examples from automated highways concerning vehicle coordination.

This paper is sort of a confession. Issues of synchrony, asynchrony, and synchronization, arise frequently in designing embedded systems from components, like everyone I knew this for quite a long time. But it is only recently that it went aware of the diversity of such issues, depending on the context. The aim of this paper is to show and explain this diversity by looking at three areas where systems design is of interest, namely: 1/ building software or hardware architectures composed of components interacting asynchronously, 2/ synchronous hardware design from IP’s, and 3/ designing distributed real-time control systems. A large part of this paper relies on other people’s work, I indicate appropriate references in each case.

The synchronous programming methodology for reactive systems has been developed since the beginning of the 80’s and it is currently used in numerous critical embedded systems projetcs. The methodolody is based on a strong mathematical framework that rigorously established the semantics of synchronous formalisms. The main industrial tools are Scade (Telelogic), Esterel Studio (Esterel Technologies), and Sildex (TNI). Current applications concern avionics, transportation systems, energy, telecom and wireless systems, etc. We present the general synchronous framework and the formalisms tailored to data-flow or control-flow dominated applications. We discuss the main issues in efficient code generation and formal property verification (safety, timing, etc.). We discuss the strength and limits of the basic synchronous paradigms, and present new ways of designing globally asynchronous / locally synchronous (GALS) systems.

We outline a practical modular method for the development of embedded systems from requirements and its comprehensive support by a CASE tool. Our focal point is on model-oriented development, multiview modelling, and validation. We present a method with a comprehensive tool support to develop models systematically from requirements and discuss various validation techniques by means of a car seat example. The resulting method is industrial strength, but nevertheless based on a solid scientific foundation and mathematical theory.

This paper is meant to motivate tools and methods research in the field of model-based embedded software development. In particular, we include usage scenarios to describe how an automated model assembler called a model compiler could support automotive embedded control systems development. We describe some desired characteristics and features of the envisioned model compiler and place particular emphasis on support for model compatibility checking. Finally, we describe characteristics of model components that are commonly used in practice.

We propose in this paper a historical perspective of programming issues found in the implementation of control systems, based on the author’s observations for more than fifteen years, but especially during the Crisys Esprit project. We show that in contrast with the asynchronous tradition of computer scientists, control engineers were naturally led to a synchronous practice that was later formalised and generalised by computer people. But, we also show that, for the sake of robustness and distribution those practitioners had to incorporate some degree of asynchrony in this synchronous approach and we try to comment the resulting programming style.

Computer aided formal methods have been very successful for the verification or at least enhanced debugging of hardware. The cost of correction of a hardware bug is huge enough to justify high investments in alternatives to testing such as correctness verification. This is not the case for software for which bugs are a quite common situation which can be easily handled through online updates. However in the area of embedded software, errors are hardly tolerable. Such embedded software is often safety-critical, so that a software failure might create a safety hazard in the equipment and put human life in danger. Thus embedded software verification is a research area of growing importance. Present day software verification technology can certainly be useful but is yet too limited to cope with the formidable challenge of complete software verification. We highlight some of the problems to be solved and envision possible abstract interpretation based static analysis solutions.

The ability to incorporate low-power, wireless communication into embedded devices gives rise to a new genre of embedded software that is distributed, dynamic, and adaptive. This paper describes the network-centric approach to designing software for highly constrained devices embodied in TinyOS. It develops a tiny Active Message communication model and shows how it is used to build non-blocking applications and higher level networking capabilities, such as multihop ad hoc routing. It shows how the TinyOS event-driven approach is used to tackle challenges in implementing the communication model with very limited storage and the radio channel modulated directly in software in an energy efficient manner. The open, component-based design allows many novel relationships between system and application.1

Dynamic storage allocation and automatic garbage collection are among the most popular features that high-level languages can offer. However, time-critical applications cannot be written in such languages unless the time taken to allocate and deallocate storage can be reasonably bounded. In this paper, we present algorithms for automatic storage allocation that are appropriate for real-time and embedded systems. We have implemented these algorithms, and results are presented that validate the predictability and efficiency of our approach.

We classify component-based models of computation into component models and interface models. A component model specifies for each component howthe component behaves in an arbitrary environment; an interface model specifies for each component what the component expects from the environment. Component models support compositional abstraction, and therefore component-based verification. Interface models support compositional refinement, and therefore componentbased design. Many aspects of interface models, such as compatibility and refinement checking between interfaces, are properly viewed in a gametheoretic setting, where the input and output values of an interface are chosen by different players.

Giotto provides an abstract programmer’s model for the implementation of embedded control systems with hard real-time constraints. A typical control application consists of periodic software tasks together with a mode switching logic for enabling and disabling tasks. Giotto specifies time-triggered sensor readings, task invocations, and mode switches independent of any implementation platform. Giotto can be annotated with platform constraints such as task-to-host mappings, and task and communication schedules. The annotations are directives for the Giotto compiler, but they do not alter the functionality and timing of a Giotto program. By separating the platform-independent from the platform-dependent concerns, Giotto enables a great deal of flexibility in choosing control platforms as well as a great deal of automation in the validation and synthesis of control software. The time-triggered nature of Giotto achieves timing predictability, which makes Giotto particularly suitable for safety-critical applications.

We review the basics of functional programming, and give a brief introduction to emerging techniques and approaches relevant to buildingreal-time software. In doingso we attempt to explain the relevance of functional programming concepts to the real-time applications domain. In particular, we address the use of types to classify properties of real-time computations.

Run-time executives and operating system kernels for embedded systems have long relied exclusively on static priority scheduling of tasks to ensure timing constraints and other correctness conditions are met. Static priority scheduling is easy to understand and support but it suffers from a number of significant shortcomings such as the complexity of simultaneously mapping timing and importance constraints onto priority values. Rate-based resource allocation schemes offer an attractive alternative to traditional static priority scheduling as they offer flexibility in specifying and managing timing and criticality constraints. This paper presents a taxonomy of rate-based resource allocation and summarizes the results of some recent experiments evaluating the real-time performance of three allocation schemes for a suite of intra-kernel and application-level scheduling problems encountered is supporting a multimedia workload on FreeBSD UNIX.

The constructive design of dependable distributed real-time systems out of prevalidated components requires precise interface specifications of the components in the temporal domain and in the value domain. This paper focuses on the temporal specification of interfaces in composable distributed realtime systems. It establishes four principles of composability and gives examples of common composability violations in existing systems. It then classifies interfaces from the point of view of composability and presents, in the final section, as an example, the rational for the interface design in the time-triggered architecture. The time-triggered architecture is a distributed architecture for dependable embedded systems that supports the principles of composability.

We present a framework to extend the concept of type systems in programming languages to capture the dynamic interaction in component-based design, such as the communication protocols between components. In our system, the interaction types and the dynamic behavior of components are defined using interface automata - an automata-based formalism. Type checking, which checks the compatibility of a component with a certain interaction type, is conducted through automata composition. Our type system is polymorphic in that a component may be compatible with more than one interaction type. We show that a subtyping relation exists among various interaction types and this relation can be described using a partial order. This system-level type order can be used to facilitate the design of polymorphic components and simplify type checking. In addition to static type checking, we also propose to extend the use of interface automata to the on-line reflection of component states and to run-time type checking. We illustrate our framework using a component-based design environment, Ptolemy II, and discuss the trade-offs in the design of system-level type systems.

A variety of diverse pressures are shaping how we will design digital systems in the near future. Shrinking geometries into the deep submicron range raise electrical design challenges that make it impossible to use existing methodologies for application specific system design. In addition, the corresponding exponential increase in the number of devices per chip results in a complexity problem which by itself threatens to cripple existing design methodologies. Finally, increased non-recurring engineering costs for masks and design tools force designs to be limited to higher volume products. All of these point to a gradual reduction of designs done using conventional ASIC (application specific integrated circuits) design methodology.The above forces are resulting in an increase in systems that contain programmable components that are specialized for a specific application domain, while at the same time providing design flexibility that permits the same device to be used for a range of related products and also generations of a product. These systems need to satisfy one or more of high computation, low power, and real-time constraints. Architecturally, these constraints are met by exploiting concurrency at all levels - at the bit operation level through specialized functional units, at the instruction level through instruction level parallelism and at the coarse grain level through on-chip multiprocessing.This class of highly specialized embedded systems requires specialized software implementation tools to ensure an efficient mapping of the application onto the architecture. These tools - particularly the compiler and simulator - are needed for two distinct aspects of the design. During architectural evaluation, they are needed to provide feedback about the suitability of the architecture for the application. During system implementation, they are needed to ensure efficient mapping and validation of design constraints.

Advances in VLSI technology have lead to a tremendous increase in the density and number of devices that can be manufactured in a single microchip. One of the interesting ways in which this silicon may be used is to leave portions of it uncommitted and re-programmable depending on an applications needs. In an earlier paper, we proposed a machine architecture for achieving this reconfigurability and compilation issues that such an architecture will face. In this paper, we will elaborate on the compiler optimization issues involved. In particular, we will outline a framework for code partitioning, instruction synthesis, configuration selection, resource allocation, and instruction scheduling. Partitioning is the problem of identifying code sections that may benefit by mapping them on to the programmable logic resources. The instruction synthesis phase generates suitable implementations for the candidates partitions and updates the machine description database with the new instructions. Configuration selection is the problem of narrowing down the choices of which synthesized instruction (from the set generated by the instruction synthesis phase) to use for each of the code regions that will be mapped to programmable logic. Unlike traditional optimizing compilers, the adaptive EPIC compiler must deal with the existence of synthesized instructions. Compilation techniques addressing each of these problems will be presented.

Object-oriented frameworks are a software reuse technology that fosters reuse of entire architectures and which has made software reuse a reality in many domain areas. Like other advanced software techniques, however, framework technology has seldom been used in the embedded domain. This paper argues that its application to embedded (control) systems is technically feasible and liable to bring to them the same benefits it has already brought to other domains. The description of a prototype framework for satellite control systems corroborates the argument. It is then argued that software frameworks, when combined with other enabling technologies, have the potential to standardize various aspects of embedded software and to transform the embedded sytems market.

Embedded systems have been and will be deployed on a wide scale.Their applications range from bread toasters with 4-bit microcontrollers to large distributed systems on a large factory floor or a battleship.These systems also operate under a wide spectrum of constraints: size constraints, power consumption needs, processing power and communication bandwidth.Multiple domains of expertise in control systems, signal processing, communications, human-computing interfaces, fault-tolerance, testing and systems integration also come into play necessitating several system models, perspectives and sets of terms. As a result, solutions and techniques for building embedded systems have tended to be very specialized, piece-meal and fragmented in nature. Thanks to Moore’s Law and advances in software engineering, products and standards, future embedded systems can now be based on common frameworks and approaches.The IMAGES (Integrated Modeling for Analysis and Generation of Embedded Software) project at Carnegie Mellon University is developing an integrated framework and toolset that can capture, model and analyze all steps of an end-to-end methodology to design embedded systems ranging from cost-constrained automotive control systems to large-scale avionics applications.The integrated toolset will interface with both commercial tools such as Rational Rose, TimeWiz from TimeSys Corporation, Matlab from MathWorks as well as research prototypes developed at Carnegie Mellon University.The framework enables multiple capabilities that have been done in compartmentalized ways, if at all, in a single coherent inter-operable manner.These capabilities include analyses (timing analysis, fault management analysis, Quality of Service analysis), modeling (hybrid systems modeling, resource consumption, event dependencies, software architecture capture), software reusability (using customizable component libraries), run-time services (RTOS and middleware abstractions, code-generation, target-specific optimizations), and verification (model checking, test-vector generation).The integration of the various system models is enabled by the use of a consistent and well-understood run-time scheduling framework based on event-driven priority-based preemptive scheduling and resource reservations.System modeling, analysis and run-time data can be stored in a common data repository, which allows the interoperability of multiple tools operating on different models of the system.Mo del checking can be used to obtain the worst-case execution times of code segments, as well as to verify logical properties of the embedded application.Both design-time and run-time attributes of software components can be manipulated rendering embedded software components both customizable and reusable. Real-time UML and UML models can also be used to perform traditional modeling of the software components.Hybrid systems techniques are used to verify both the continuous and discrete dynamics of the physical plant being controlled.Application-sp ecific code generation can be automatically interfaced to work with communications glue code in a location-independent fashion by the use of run-time abstractions.The target environment can be rich, with real-time operating systems ranging from real-time versions of Linux to OSEK, and middleware ranging from none to Real-Time Java to Real-Time CORBA.

This paper presents our experience implementing the memory management extensions in the Real-Time Specification for Java. These extensions are designed to given real-time programmers the control they need to obtain predictable memory system behavior while preserving Java’s safe memory model.We describe our implementation of certain dynamic checks required by the Real-Time Java extensions. In particular, we describe how to perform these checks in a way that avoids harmful interactions between the garbage collector and the memory management system. We also found that extensive debugging support was necessary during the development of Real-Time Java programs. We therefore used a static analysis and a dynamic debugging package during the development of our benchmark applications.

Embedded systems for safety-critical applications often integrate multiple “functions” and must generally be fault-tolerant. These requirements lead to a need for mechanisms and services that provide protection against fault propagation and ease the construction of distributed fault-tolerant applications.A number of bus architectures have been developed to satisfy this need. This paper reviews the requirements on these architectures, the mechanisms employed, and the services provided. Four representative architectures (SAFEbusTM, SPIDER,TTA, and FlexRay) are briefly described.

The methodologies that are in use today for software development rely on representations and techniques appropriate for the applications (compilers, business applications, CAD, etc.) that have been traditionally implemented on programmable processors. Embedded software is different: by virtue of being embedded in a surrounding system, the software must be able to continuously react to stimula in the desired way. Verifying the correctness of the system requires that the model of the software be transformed to include (refine) or exclude (abstract) information to retain only what is relevant to the task at hand. In this paper, we outline a framework that we inted to use for studying the problems of abstraction and refinement in the context of embedded software for hybrid systems.

Embedded systems composed of hardware and software components are designed to interact with a physical environment in real-time in order to fulfill control objectives and system specifications. In this paper, we address the complex design challenges in embedded software by focusing on predictive and systematic hierarchical design methodologies which promote system verification and validation. First, we advocate a mix of top-down, hierarchical design and bottom-up, component-based design for complex control systems. Second, it is our point of view that at the level closest to the environment under control, the embedded software needs to be time-triggered for guaranteed safety; at the higher levels, we advocate an asynchronous hybrid controller design. We briefly illustrate our approach through an embedded software design for the control of a group of autonomous vehicles.

Software has become strategic to developing effective distributed real-time and embedded (DRE) systems. Next-generation DRE systems, such as total ship computing environments, coordinated unmanned air vehicle systems, and national missile defense, will use many geographically dispersed sensors, provide on-demand situational awareness and actuation capabilities for human operators, and respond flexibly to unanticipated run-time conditions. These DRE systems will also increasingly run unobtrusively and autonomously, shielding operators from unnecessary details, while communicating and responding to mission-critical information at an accelerated operational tempo. In such environments, it’s hard to predict system configurations or workloads in advance. This paper describes the need for adaptive and reflective middleware systems (ARMS) to bridge the gap between application programs and the underlying operating systems and network protocol stacks in order to provide reusable services whose qualities are critical to DRE systems. ARMS middleware can adapt in response to dynamically changing conditions for the purpose of utilizing the available computer and network infrastructure to the highest degree possible in support of mission needs.

The evolution of information sciences and technologies is characterized by the extensive integration of embedded components in systems used in various application areas, from telecommunications to automotive, manufacturing, medical applications, e-commerce etc. In most cases, embedded components are real-time systems that continuously interact with other systems and the physical world. Integration and continuous interaction of software and hardware components makes the assurance of global quality a major issue in system design. The failure of a component may have catastrophic consequences on systems performance, security, safety, availability etc.

Embedded systems are proliferating at an amazing rate. To be successful these systems must be tailoredto meet many cost, time to market, performance, and dependability constraints. Building and tailoring embedded systems by using domain specific components has promise. However, in composing components the most difficult issues are ensuring that non-functional properties such as real-time performance and dependability are being met. The VEST toolkit is aimed at providing a rich set of dependency checks based on aspects to support embedded system development via components.

This paper discusses challenges and opportunities in embedded system and software design. The key thesis of the paper is that embedded computing applications create fundamentally new challenges for software technology that require new ideas and approaches. The paper reviews two of the new challenges, physicality and its effects on change management. The discussion on the impacts of these challenges focuses on key components of integrated development environments, representation, synthesis and analysis, and generator technology.

We introduce a task model for embedded systems operating on packet streams, such as network processors. This model along with a calculus meant for reasoning about packet streams allows a unified treatment of several problems arising in the network packet processing domain such as packet scheduling, task scheduling and architecture/algorithm explorations in the design of network processors. The model can take into account quality of service constraints such as data throughput and deadlines associated with packets. To illustrate its potential, we provide two applications: (a)a new task scheduling algorithm for network processors to support a mix of real-time and non-real-time flows, (b)a scheme for design space exploration of network processors.

The paper describes an approach to organizing a collection of spatially distributed entities into a system capable of carrying out different complex missions. The entities are devices (artifacts like vehicles, sensors, actuators, computing and communications equipment) or agents or controllers, which control devices or other agents. The systemlevel capabilities concern complicated activities such as reconnaissance and logistics, requiring optimization, planning, and real-time control. The approach is to construct a system-level capability by appropriately organizing (composing) agents that can execute a small set of tasks. Agents are organized in a hierarchy: those at upper layers have authority over those at lower layers. The capability to conduct different missions is achieved by changing the agent architecture. The hybrid system specification and simulation language SHIFT is convenient for describing devices and agents, and their interaction. The paper gives two illustrative designs, one specified in SHIFT. To deploy systems organized in this way poses several research challenges, one of which is indicated here—the need for an exception-handling facility that provides a ‘fallback’ mechanism if an agent is unable to complete the task assigned to it.

This paper outlines an approach to embedded computer system development that is based on integrated use of multiple domainspecific languages; on increased use of mathematical analysis methods; and on increased integration between domain-specific specification and mathematical modeling and code generation. We first outline some general principles of this approach. We then present a bit more detail about the emerging SAE standard Avionics Architecture Description Language and our supporting MetaH toolset.We conclude with a summary of some research challenge problems, technical approaches, and preliminary results uncovered during our work.

The USES-groupat the Universität des Saarlandes follows an approach to compute reliable run-time guarantees which is both wellbased on theoretical foundations and practical from a software engineering and an efficiency point of view. Several aspects are essential to the USES approach: the resulting system is modular by structuring the task into a sequence of subtasks, which are tackled with appropriate methods. Generic and generative methods are used whenever possible. These principles lead to an understandable, maintainable, efficient, and provably correct system. This paper gives an overview of the methods used in the USES approach to WCET determination. A fully functional prototype system for the Motorola ColdFire MCF 5307 processor is presented, the implications of processor design on the predictability of behavior described, and experiences with analyzing applications running on this processor reported.

Although computers have been employed for decades to control machinery and entire laboratories, the term embedded system has received renewed attention and is about to establish itself as a discipline of its own. We therefore try to identify its characteristics and peculiarities. The most outstanding single item is the role of time. The addition of timing conditions to all other specifications of a system causes real-time programming to appear as a particularly difficult and challenging subject. We ask how the rapidly growing demands can be met, and emphasize that reliability must be guaranteed in view of the potentially disastrous consequences of failures upon the controlled equipment and its environment.

Systems-on-chips (SoCs) up the stakes in embedded software in several dimensions. Not only do they allow us to integrate more software on a single chip, they also allow us to implement new types of systems, such as multiprocessor algorithms and networked systems-on-chips. The software for these SoCs must not only meet the traditional requirements of software but must also meet more hardware-like properties such as timing, power consumption, and size. Video provides an excellent example of advanced embedded software for SoCs. This paper uses a smart camera being designed at Princeton University to illustrate how a hierarchy of abstractions can be used in embedded software system design.