Embedded Systems Design Based on Formal Models of Computation

An embedded computing system represents a set of processing elements embedded inside a larger system and usually communicates with the physical world. Although embedded systems are already widespread, the number of applications is expanding both in traditional areas such as communications, consumer electronics, aerospace, automotive, and in new ones such as biomedical.

This chapter looks at several important models of computation and languages for embedded systems design. We do not attempt to draw sharp distinctions between models and languages. Thus, the topics in this section are not divided strictly to either models of computation or languages. A model of computation is commonly used for defining the semantics of a language. However, when a model of computation is expressed with a simple syntax, it can also be called a language. For example, synchronous dataflow (SDF) is usually thought of as a model of computation. But as soon as it is expressed with a simple graphical syntax consisting of a network of blocks connected with arrows, it is not incorrect to call it a language.

This chapter describes how embedded systems are specified in DFCharts. Section 3.1 presents an introduction to specification in DFCharts. Section 3.2 illustrates the application of DFCharts on a practical heterogeneous embedded system called frequency relay. Section 3.3 discusses languages and models related to DFCharts. Section 3.4 presents an extension of DFCharts called DDFCharts, which gives another dimension to DFCharts of being suitable to formally model class of distributed embedded systems.

In this chapter we present the formal semantics of DFCharts. Section 4.1 discusses the automata semantics, introduced first in [88], where the behaviour of a complete specification is expressed as an FSM. This section is divided into seven sub-sections Section 4.1.1 introduces multiclock FSMs that are used as inputs to DFCharts operators. Sections 4.1.2–4.1.5 define the semantics of four DFCharts operators: synchronous parallel, asynchronous parallel, localization\hiding and refinement. DFCharts operators are defined in a similar style as Argos [24] operators. However, because of the use of multiclock FSMs, their operation is quite different. Section 4.1.6 defines with a simple language how the operators may be applied on multiclock FSMs. As seen in Chap. 3, an SDFG and an FSM are connected with the asynchronous parallel operator. According to the semantics of the asynchronous parallel operator in Sect. 4.1.3, it operates only on FSMs like all other operators. For this reason, an SDFG is represented as an FSM so that it can be combined with “real FSMs”. This is the topic of Sect. 4.1.7. Since an SDFG proceeds at its own speeds, an FSM that represents an SDFG (“SDF FSM”) is triggered by a clock that is different from the clock of real FSMs. Thus, when a “real FSM” and “SDF FSM” are combined, a multiclock FSM results. In the definitions of operators, which comprise DFCharts automata semantics, rendezvous is treated simply as an event that triggers a transition. What exactly happens on the channel is irrelevant. This is the topic of Sect. 4.2. It examines in detail the ordering of events on a channel within the Tagged Signal Model (TSM) framework. The analysis leads to understanding of how an array variable produces multiple SDF tokens and vice versa. Data transfer from SDF to FSM is the topic of Sect. 4.2.1, while Sect. 4.2.2. deals with data transfer from FSM to SDF. The TSM semantics of DFCharts was previously described in [89]. Finally, Sect. 4.3 examines the effect of clock speeds on DFCharts behaviour.

With graphical syntax presented in Chap. 1 and Java-based textual syntax given in Chap. 6, DFCharts can be used as a language for specification of embedded systems. In this chapter we use DFCharts as a model of computation to assess the effectiveness of two popular system level languages, SystemC and Esterel, in capturing behaviour of heterogeneous embedded systems. While SystemC is being proposed by an industry consortium and has no formal semantics, Esterel has a formal semantics and formal verification capabilities. Hence, both these languages represent differing perspectives on system-level modelling. The frequency relay case study was specified in both languages, following the DFCharts model as closely as possible. Using this analysis, we can identify what needs to be improved in each language in order to increase their ability to handle heterogeneous embedded systems. The relation between the two languages and DFCharts was previously described in [105].

This chapter presents a Java environment for DFCharts based design. The specification of finite state machines, synchronous dataflow graphs and communication mechanisms used in DFCharts is supported by a Java class library. Besides the DFCharts library, Ptolemy is needed for simulation of SDF graphs.

Long-term trend in semiconductor development has been integration of larger and larger systems on a single chip. It has been governed by Moore’s law in terms of integration capabilities and double increase of the number of transistors on a chip every 12–24 months. At the same time this has also led to the increasing raw computation power on a single chip. However, all those transistors can’t be used to achieve faster and more powerful processors due to architectural and power limitations. Rather, the development has taken another direction towards systems on chip which consists of many processors or processing elements, sometimes tens or hundreds of such elements, with a clear trend towards chips which will have thousands of processors. One of the main reasons for this trend is that those processors are simpler, easier to implement and work at lower frequencies than high performance processors, thus they are less power and energy demanding. However, the new approach, which is often referred to as multiple processor (or multiprocessor) systems on chip (MPSoC) faces many challenges. Among them most notable are related to the selection of the type of processing elements (e.g. general purpose vs. application-specific, uniform vs. heterogeneous), selection of interconnect structures and system architecture (e.g. networks on chip vs. circuit interconnect vs. buses), life-time of the processing elements (static or dynamic or reconfigurable), run-time support (operating systems or customized), design flow and tools support (e.g. traditional programming languages vs. concurrent languages). Many new architectures have emerged with a claim of their advantages over others in at least specific application domains. The new approaches are mostly based on concentration on certain features (e.g. architecture, run-time support or languages) but not many of them look at the big picture and design flow that will ensure more consistency and better linkages between those features.

Previous chapters deal with system level by exploring issues such as specification, simulation and formal semantics of DFCharts without any reference to implementation. The focus of this chapter is implementation of DFCharts specifications. The target architecture for implementation is HiDRA, which was described in Chap. 7. HiDRA is capable of implementing both control-dominated and data-dominated types of behaviour that are found in DFCharts. It has special features supporting reactivity while data-dominated operations are supported using traditional solutions. In principle, any multiprocessor architecture may be used for implementation of DFCharts. However, because of special features that support reactivity, HiDRA is likely to provide more efficient implementations. This is the main reason for selecting HiDRA. In Sect. 8.1, we present a design methodology for implementing DFCharts on HiDRA. It consists of five steps: specification, FSM compositions, allocation and partitioning, synthesis and performance evaluation. We are mainly concerned with the synthesis step, which is separately treated in Sect. 8.2 where details regarding the execution of DFCharts on HiDRA are presented. In Sect. 8.3 we show how the methodology is applied on the frequency relay case study.

Design of embedded systems based on formal models of computation has been gaining acceptance as a sound method for dealing with increasing system complexities. While models of computation have been successfully used individually for control-dominated systems and data-dominated systems, modelling of heterogeneous systems still poses a challenge. We presented DFCharts, a model of computation for heterogeneous embedded systems that combine control-dominated and data-dominated parts. We demonstrated how DFCharts could be used in embedded systems design by linking it to system level design languages and implementation architecture. We used a realistic heterogeneous embedded system called frequency relay, in order to illustrate the concepts.