Models of computation and languages for embeddedsystem designA. Jantsch and I. SanderAbstract: Models of computation (MoC) are reviewed and organised with respect to the timeabstraction they use. Continuous time, discrete time, synchronous and untimed MoCs aredistinguished. System level models serve a variety of objectives with partially contradictingrequirements. Consequently, it is argued that different MoCs are necessary for the various tasks andphases in the design of an embedded system. Moreover, different MoCs have to be integrated toprovide a coherent system modelling and analysis environment. The relation between some popularlanguages and the reviewed MoCs is discussed to find that a given MoC is offered by manylanguages and a single language can support multiple MoCs. It is contended that it is of importancefor the quality of tools and overall design productivity, which abstraction levels and whichprimitive operators are provided in a language. However, it is observed that there are variousflexible ways to do this, e.g. by way of heterogeneous frameworks, coordination languages andembedding of different MoCs in the same language.1 IntroductionA system on a chip (SoC) can integrate microcontrollers,digital signal processors (DSPs), memories, custom hard-ware and reconfigurable hardware, in the form of fieldprogrammable gate arrays (FPGAs) together with acommunication structure and analogue-to-digital (A=D)and digital-to-analogue (D=A) converters on a single chip(Fig. 1). In total there may be dozens or hundreds of suchcomponents on a single SoC. These architectures offer anenormous potential. However, they are also tremendouslycomplex and heterogeneous. This does not only apply forthe hardware, but also for the software. Moreover, theoverall system complexity grows much faster than systemsize due to the component interaction. In fact, intra-systemcommunication is becoming the dominant factor for design,validation and performance analysis. Consequently, issuesof communication, synchronisation and parallelism mustplay a prominent role in all system design languages.1.1 Hardware and softwareIn order to manage the complexity and heterogeneity of SoCapplications Edwards et al. [1] believe that the designapproach should be based on the use of one or more formalmethods to describe the behaviour of the system at a highlevel of abstraction, before a decision on its decompositioninto hardware and software is taken. The final implemen-tation of the system should be made by using automaticsynthesis from this high level of abstraction toensure implementations that are ‘correct by construction’.Validation through simulation or verification should bedone at the higher levels of abstraction.This is in contrast to current design practice, whichtypically leads to an early definition of the interfacesbetween hardware and software. After these interfaceshave been specified and fixed by system designers, thehardware and software is developed in separate sub-projects by different teams. Each of them only validatestheir design against the specified interfaces, but there islittle opportunity to re-evaluate these interfaces or theoverall hardware–software partitioning. This is unfortu-nate because only when more details of the different partsare explicitly modelled, analysed and understood, willcertain requirements, constraints and needs becomeapparent.Example: In a mixed hardware=software design projecta task scheduler shall be implemented in software. Duringthe system specification it has been determined that thehardware timer sets a flag every 50 ms; which is the basictime unit for the scheduler. Even though the used timer hasa much higher resolution, during system design andhardware=software interface specification it is decided thatthe only information passed from the hardware timer tothe software scheduler is the flag, which is set by the timerand reset by the scheduler. There is no apparent reason whythe interface should be more complicated than this, asprevious product generations have successfully used thismechanism. Also, simplicity is a major design goal sinceexperience has shown that over-dimensioned designs havecaused increased hardware cost, delayed development andresulted in performance bottlenecks.It becomes apparent only much later that the new productrequires a more sophisticated scheduler. Due to challengingreal-time requirements, it sometimes happens that thescheduler is invoked up to 5 ms after the interrupt from thehardware timer. It turns out that it would still be possible forthe scheduler to properly schedule all tasks without timingviolations, because this situation never happens severaltimes in a row and one specific task can be delayed in thatcase. For this to work properly the scheduler has to knowq IEE, 2005IEE Proceedings online no. 20045098doi: 10.1049/ip-cdt:20045098The authors are with the Department for Microelectronics & InformationTechnology, Royal Institute of Technology, Electrum 229, Kista 16440,SwedenE-mail: [email protected] first received 28th July and in revised form 3rd November 2004IEE Proc.-Comput. Digit. Tech., Vol. 152, No. 2, March 2005114how many ms have elapsed since the last timer tick. Eventhough the timer has this information readily available, thehardware=software interface has no means to convey it.More often than not it is very difficult or impossible tochange the interface specification. Several design teamswork with the given specification, and too much hardwareand software had to be changed and revalidated. Thus, ifpossible, a more local solution to this kind of problem issought. For instance, in our case the software engineersmight be tempted to infer the elapsed time by countingexecuted instructions. This kind of ad-hoc solution causesa set of problems, such as undocumented dependency ona particular processor type and clock frequency with anightmare of potential validation problems.To avoid ending up in ad-hoc problem fixes and localoptimisations, Edwards et al. [1] argue for a systemspecification that is detailed enough to identify this kindof problem early on, but which does not commit to specificimplementations and detailed interface definitions. Essen-tially, they want to delay this commitment to a later phase,when the problem and the design are better understood, tomake more informed and better decisions. As a consequencethe mapping and implementation of the specification mustbe more automatic, faster and less