Design and Analysis of Distributed Embedded Systems

The main purpose of this paper is to discuss if the Unified Modeling Language (UML) can be used as a system-level language (SLL) for specifying embedded systems, in co-design environments. The requirements that a language has to fulfil to be considered as an SLL are presented and the advantages and disadvantages of using UML as an SLL are also indicated. The contribution of this paper consists on the explicit discussion of the key issues that must be taken into account when deciding if UML is to be used in a project as an SLL for embedded software.

This article is meant to highlight Specification PEARL in an object-oriented perspective. Specification PEARL is a specification and description language, which originates from Multiprocessor PEARL (DIN 66253, Part 3), also named PEARL for distributed systems. It extends the standard by allowing the description of asymmetrical distributed architectures as well as by additional parameters for the parameterisation of the RTOS and later feasibility analysis.

PEARL itself in its latest implementation still is a procedural language although it supports features like tasking and synchronisation, being supported only by some object oriented languages. Due to the nature of its applications, transferring PEARL into an object-oriented language was not an easy nor straightforward process; hence, there are several implementations of object-oriented PEARL. For Multiprocessor PEARL there was no attempt in this direction so far. In Specification PEARL HW/SW co-design methodology we are striving to use the Specification PEARL language as a specification language with the current release of PEARL (PEARL90).

The aim of this article is to give Specification PEARL and its components an object oriented perspective — to structure them in a way, which would lead to natural generalisation-specialisation and whole-part relationships and define their interfaces. It will also show why it would be convenient for Specification PEARL to support classes of objects.

We present a high-level executable specification for the Universal Plug and Play (UPnP) standard illustrating the use of Abstract State Machine (ASM) technology as a practical tool for applied systems engineering. The concept of distributed real-time ASM allows us to combine both synchronous and asynchronous execution models in one uniform model of computation.

The growing complexity of modern real-time embedded systems makes it imperative to apply formal analysis techniques at early stages of system development. This paper considers formal modelling of event-driven real-time systems with Time Petri Nets, and subsequent analysis via model-checking by a simple, fully automatable translation into Timed Automata. The proposed approach is applied to a small application scenario taken from Avionics Mission Computing.

During the last years we have developed a methodology for the design of complex embedded real-time systems. The methodology supports the complete design flow reaching from modeling of embedded systems on a high level of abstraction over simulation and analysis down to the implementation on target platforms. In this paper, we describe our current work, which aims at opening the methodology for dynamically reconfigurable systems. We describe the main ideas for extending our formal model of High-Level Petri Nets in order to capture these systems. Furthermore, we describe our approach for timing analysis of these systems.

Many standards mandating verification of requirements correctness do not comprehensively state what information should be captured and used for verification and quality assurance activities. Therefore, a wide range of methods, from simplistic checklists to comprehensive formal methods, is used to verify correctness of system and software requirements. In this paper, a semi-formal method to verify functional requirements using a graphical logic-based structured architecture referred to as Graphical Requirement Analysis is proposed and illustrated with a case study. Its architecture allows to trace functional system requirements and to show correctness (non-ambiguity, consistency, completeness) of specifications. The support of graphical system engineering descriptions greatly facilitates to simulate requirement specifications and designs. Such capability is believed by many to be an essential aspect of developing and assuring the quality of highly complex systems requiring high integrity.

The specification of software for distributed production control systems is an error prone task. The ISILEIT project aims at the development of a seamless methodology for the integrated design, analysis and validation of such embedded systems. Suitable subsets of UML and SDL for the design of such systems are therefore identified in a first step. The paper then focuses on how we use a series of formal semantics of our design language to enable the effective evaluation of software designs by means of validation and verification. We will further explain how the use of multiple Abstract State Machine meta-models permits simulation and model checking at different levels of abstraction

Embedded systems present a tremendous opportunity to customize designs by exploiting the application behavior. Due to increasing design complexity deeply pipelined high performance embedded processors are common today. In the presence of hazards and exceptions the validation of pipelined embedded processors is a major challenge. We extend a Finite State Machine (FSM) based modeling of pipelined processors to verify the pipeline specification in the presence of hazards and multiple exceptions. Our approach leverages the system architect’s knowledge about the behavior of the pipelined processor, through Architecture Description Language (ADL) constructs, and thus allows a powerful top-down approach to pipeline verification. We applied this methodology to the DLX processor to demonstrate the usefulness of our approach

Replication is a technique commonly used to provide high-availability and fault tolerance in distributed systems. With multiple copies of the entities, a service can keep operation even when some copies are inaccessible because of a crash of the computer where a copy was stored, for instance. There are two main classes of replication techniques: passive and active replication. Passive replication suffers from a high reconfiguration cost in case of failure on the primary, and active replication has permanent processing redundancy.

The hybrid replication technique presented in this paper has the same advantages of the passive replication in good runs, and has much less processing overhead than the active replication. In this paper, we demonstrate the efficiency of our replication model by the comparison among the response time (for the client) of the passive, active and hybrid replication scenarios using statistical analysis.

An increasing range of industries have a growing dependence on embedded software systems, many of which are safety-critical, real-time applications that require extremely high dependability. Two fundamental approaches — fault avoidance and fault tolerance — have been proposed to increase the overall dependability of such systems. However, the increased cost of using the fault tolerance approach may mean that this increase in dependability is not worth the extra expense involved. We describe an experiment undertaken in order to establish whether or not software redundancy (or the multi-version design method) can offer increased dependability over the traditional single-version development approach when given the same level of resources. The results of this and a subsequent follow-up study are then given. The analytic results from these experiments show that despite the poor quality of individual versions, the multi-version method results in a safer system than the single-version solution. It is evident that regarding the single-version method as a “seem-to-be” safer design decision for critical applications is not generally justifiable.

In the paper, a proposition for a systematic approach to fault detection in building a dependable and fault-tolerant control system is presented. A network of simple monitoring cells that monitor and evaluate functioning of critical sub-processes of the system is proposed. Further, different approaches for the implementation of the monitoring cells are observed.

Integrators of CORBA-based dependable systems require information on the robustness of candidate middleware implementations, in order to select the implementation that is best suited to their requirements. We illustrate an approach for characterizing the dependability of middleware service implementations, with respect to corrupt method invocations arriving over the network. Preliminary results from experiments targeting the CORBA Event Service are presented.

Rapid growth in inexpensive, short range, and low-power wireless communication hardware and network standards are now enabling the construction of ubiquitous computing and communication environments. Devices in ubicomp environments form short range and low power mobile ad hoc networks whose topologies are usually dynamic due to arbitrary node mobility. Typical applications in ubicomp environments are context-sensitive, adaptive, and often engage in impromptu, and volatile communication. These properties require both programming and runtime support in the application and system levels. A middleware approach can be very effective to provide these support to reduce the effort required to develop ubicomp software, in addition to providing the commonly known middleware services, such as interoperability, location transparency, naming service, etc. In contrast to middleware architectures for fixed networks, a middleware for ubicomp environments should be adaptive to various contexts, be reconfigurable, and should be of high-performance to facilitate ad hoc communication among objects. In this paper, an adaptive middleware, which is reconfigurable and context sensitive, is presented for applications in ubiquitous computing environments.

The paper describes techniques, which have been developed to simplify the customization of the PURE operating system family for embedded systems and can be applied to almost any embedded software intended for reuse. The approach is based on feature modeling and the use of aspect-oriented programming and supported by a complete tool chain.

An independent test facility is described, which simulates the environments of distributed and parallel embedded real time systems with special emphasis on the exact modeling of the prevailing time conditions. Its main application areas are software verification and safety licensing. Following the black box approach, just by providing worst case oriented input patterns to integrated hardware/software systems and monitoring the corresponding outputs, the time behaviour of such systems can precisely be determined. High accuracy time information is provided by employing a hardware supported timer synchronised with legal time, viz., Universal Time Co-ordinated, as received via GPS satellites.

Traditional Worst-Case Execution-Time (WCET) analysis is very complex. It has to deal with path analysis, to identify and describe the possible execution paths through the code to be analyzed, and it has to model the worst-case timing of the possible paths on the target hardware. The latter is again nontrivial due to interference of modern hardware features like instruction pipelines, caches, and parallel instruction-execution units on the processor.

To simplify WCET analysis we have proposed a new programming paradigm, single-path programming. Every program following this paradigm has only a single possible execution path, which makes path analysis and thus WCET analysis almost trivial. In this work we show how any real-time program code that is WCET-analyzable can be transformed into single-path code. This demonstrates that the single-path paradigm provides a universal solution to simplify WCET analysis.

Today’s complex embedded systems integrate multiple hardware and software components, many of them provided as IP from different vendors. Performance analysis is crucial for such heterogeneous systems. There already exists a variety of formal timing analysis techniques for small sub-problems, e. g. task performance, scheduling strategies, etc.. In this paper, we analyze these individual approaches in the context of performance analysis of heterogeneous platforms at different levels of abstraction, and present a three-level bottom-up analysis procedure.

This paper describes a new method to integrate low power analysis into high-level synthesis. We addressed especially a specific analysis technique within the scheduling task of high-level synthesis. The analysis technique allows the determination of dedicated turn-on and turn-off mechanism. Therefore, the optimisation of power consumption is simultaneously improved with the design delay.

In real-time computing systems, timing-requirement specifications coming from the application designer are the obvious primary driver for resource allocation. Deadline-driven scheduling of computation-segments has been studied as an advanced mode of scheduling devised to meet the timing requirement specifications. However, it does not reflect additional concerns of the application designer, the damaging impacts of various timing violations on the application. The notion of risk-incursion function (RIF) as a framework for specification of such damaging impacts has been established by the first co-author. In this paper, a concrete implementation approach of the RIFdriven resource allocation scheme is discussed first. Then two RIF-based scheduling algorithms are discussed. The results of the experiment conducted to compare the performance of RIF-based scheduling algorithms against that of deadline-driven scheduling algorithms are also provided.

With its high-speed deterministic communication, its low cost and its guaranteed bandwidth, the IEEE-1394 high-performance serial bus (also known as FireWire®) is ideal for interconnecting the components of modular distributed systems such as computers and I/Os. Mindready’s paper will cover the following points: design of a typical industrial control system, heterogeneous computer systems and their limitations, isochronous data transmission, node synchronization, IEEE-1394 parameters and IEEE-1394 within the transport of digital data.

The complexity of mechatronic elements has grown along with the customer requirements in automotive and public transportation. The mechatronic systems can not be designed as a stand-alone unit, but as a part of an interacting network. To attend safety and synchronisation between processing elements we present in this paper the use of IEEE1394a for a deterministic communication system. As a case study we use the Novel Railway System Paderborn, which will be implemented using the hardware platform RABBIT.

In the embedded systems domain predictability, fault tolerance and high-speed data transmission rates are key challenges for the interface design. Multiple tasks and channels communicate through different protocols with each other. In this paper we present a consistent design approach for configurable real-time interfaces. An interface design methodology therefore should regard the relationship between distributed tasks, channels and supported protocols within a HW/SW Codesign scenario. The model dependent parameters are important information for this process and are represented in a formal UML-based way. As result of the design process an interface-block (IFB) is generated which considers all these parameters. A complex embedded system in the context of a case study implements a collision avoidance algorithm for two interacting robots. It demonstrates the usability of this concept for an implementation of HW/SW-interfaces with respect to the real-time restrictions..

This paper presents a color segmentation algorithm for embedded real-time systems with a special focus on latencies. The algorithm is part of a Hardware-Software-System that realizes fast reactions on visual stimuli in highly dynamic environments. There is furthermore the constraint to use low-cost hardware to build the system. Our system is implemented on a RoboCup middle size league prototype robot.

We discuss the application of the metaprogramming techniques for soft IP design. Two metaprogramming paradigms are considered: the internal (using capabilities of the single language) and external (based on the usage of the target language and external metalanguage simultaneously) ones. The novelty of our approach is that we apply the concept of the multi-dimensional separation of concerns implemented via metaprogramming for the design of parameterized soft IPs for embedded systems in order to achieve higher flexibility, reusability and customizability.

The structure of Internet applications and scenarios is evolving rapidly. New software architectures and formats for transfer of data and site-spanning interoperability are emerging and reshaping the realm of web-centered computing. These changes are having repercussions that will change the established methodologies of design processes and business-to-business applications. Therefore, these effects on the domain of the electronic design automation (EDA) have to be considered and their validity shown.. In this paper we present an approach to exploit webservices technology in the field of embedded system design.

Developing distributed embedded control systems increases the need for a consistent design approach. Our example is taken from the mechatronic design in the automotive industry and illustrates our structuring concept for a modular realization of real-time-critical controllers. In our consistent design approach we employ the structured modelling of mechatronic systems, a modular integration platform for real-time software implementation and a modular hardware platform based on FPGAs and microcontrollers.