To fully utilize multi-processors, new tools are required to manage software complexity. We present a novel technique that enables automating hierarchical process network transformations to derive optimized parallel applications. Designers leverage a library of process constructors and data-parallel algorithmic skeletons, utilizing the well-defined semantics of a restricted set of operators. This carefully chosen set addresses both temporal and spatial aspects of computation, enabling the automated identification of various parallel patterns. We utilize an augmented version of a meta-modeling framework grounded in system graphs and trait hierarchies to generate an intermediate representation (IR) of the system model to simplify automatic transformations and evaluations. Our augmentation allows for capturing skeletons and hierarchical networks. By meticulously selecting the underlying framework, we alleviate the need for tool integration in our design flow. We validate our approach through a proof-of-concept implementation, where our automated tool applied 193 transformations to fully parallelize an image processing application.

Embedded systems are ubiquitous and control many critical functions in society. A fairly new type of embedded system has emerged with the advent of partial reconfiguration, i.e. runtime reconfigurable systems. They are attracting interest in many different applications. Such a system is capable of reconfiguring itself at the hardware level and without the need to halt the application's execution. While modeling and implementing these systems is far from a trivial task, there is currently a lack of systematic approaches to tackle this issue. In other words, there is no unanimously agreed upon modeling paradigm that can capture adaptive behaviors at the highest level of abstraction, especially when regarding the design entry, namely, the initial high-level application and platform models. Given this, our paper proposes two domain ontologies for application and virtual platform models used to derive a classification system and to provide a set of rules on how the different model elements are allowed to be composed together. The application behavior is captured through a formal model of computation which dictates the semantics of execution, concurrency, and synchronization. The main contribution of this paper is to combine suitable formal models of computation, a functional modeling language, and two domain ontologies to create a systematic design flow from an abstract executable application model into a virtual implementation model based on a runtime reconfigurable architecture (virtual platform model) using well-defined mapping rules. We demonstrate the applicability, generality, and potential of the proposed model element classification system and mapping rules by applying them to representative and complete examples: an encoder/decoder system and an avionics attitude estimation system. Both cases yield a virtual implementation model from an abstract application model.

The design of embedded systems is inherently complex for two main reasons. Firstly, it entails the combined knowledge and results from a vast set of mature, well-established, yet separate disciplines, such as electrical engineering, computer science, mechanical engineering, etc. Secondly, it needs to account for the collective behavior of computing elements, infrastructure and physical environment. This behavior cannot be derived from the sum of its constituent components, rather it emerges from the manifold feedback interactions between them. One of the main tools that have enabled engineers to guide the development of systems with unprecedented complexity is abstraction, that is, capturing essential properties of phenomena into mathematical, well-behaved analyzable models.  Yet combining models from different disciplines is largely limited due to the fact that these models, although well-acknowledged, are most often incompatible.  In a system design process, this leads to  the discovery and understanding of unwanted or hazardous behaviors during later stages such as prototyping or deployment phases, when design reiterations are extremely costly.

This thesis introduces ForSyDe-Atom, a formal framework intended as an entry point for the disciplined design of embedded systems. This framework provides a set of rules for combining several domain specific languages as structured, enclosing layers in order to orthogonalize the many aspects of system behavior, yet study their interaction in tandem. It enables systematic exploitation of design properties in a system design flow by facilitating the step-wise projection of certain layers of interest, the isolated analysis and refinement on projections and the  seamless reconstruction of a system model from (possibly refined)  projections. As examples of languages hosted by this framework, five layers are presented: one for capturing timed interactions in heterogeneous systems, one for extending behaviors with controlled effects, one for structured parallelism, one for modeling uncertainty and one for describing component properties. The modeling capabilities are demonstrated through numerous didactic examples and four large case studies from the application domains of digital signal processing and avionics. A set of strategies for parallelizing timed simulation models, together with a preliminary component-based synthesis flow towards embedded platforms further highlight the potential of this framework as an entry point to system design. 

Design av inbyggda system är en komplex process av två skäl. För det första krävs det en kombination av kunskap och resultat från flera väletablerade discipliner. För det andra måste denna process ta ansvar för de ingående delarnas gemensamma beteende, deras infrastruktur samt fysiska miljö. Beteendet härrör inte från summan av beståndsdelarna, utan uppstår ur de talrika feedbackinteraktionerna mellan dem. Ett av de viktigaste verktygen som har gjort det möjligt att styra utvecklingen av komplexa system är abstraktion, dvs. att fånga fenomenens väsentliga egenskaper i analyserbara matematiska modeller. Kombinationen av modeller från separata väletablerade discipliner är dock starkt begränsad eftersom dessa modeller oftast är oförenliga, särskilt när det gäller inbyggda system. Oönskade eller farliga beteenden upptäcks sent i systemutvecklingsprocessen, under prototyp- eller distributionsfasen, när designändringar blir mycket kostsamma.

Denna avhandling introducerar ForSyDe-Atom, ett formellt ramverk avsett som utgångspunkt för rigorös design av inbyggda system. Detta ramverk ger en uppsättning regler för att kombinera flera domänspecifika språk som strukturerade, täckande lager, vilka ortogonaliserar de många aspekterna av systembeteende, samtidigt som de gör det möjligt att studera deras interaktion i tandem. Det möjliggör ett systematiskt utnyttjande av designens egenskaper i ett systemdesignflöde, genom att underlätta den stegvisa projektionen av vissa intressanta lager, den isolerade analysen och förfiningen av projektioner samt den sammanhängande rekonstruktionen av en systemmodell från (möjligen förfinade) projektioner. Som exempel på språk som ryms i detta ramverk presenteras fem lager: ett för att fånga tidsinteraktioner i heterogena system, ett för att utvidga beteenden med kontrollerade effekter, ett för strukturerad parallellitet, ett för modelleringsosäkerhet och ett för att beskriva komponentegenskaper. Modelleringsfunktionerna demonstreras genom ett antal didaktiska exempel samt fyra stora fallstudier från applikationsområdena digital signalbehandling och avioniksystem. Potentialen som utgångspunkt för systemdesign framhävs genom en uppsättning strategier för parallellisering av tidsbestämda simuleringsmodeller och ett preliminärt komponentbaserat syntesflöde.

We present ForSyDe-Atom, a formal framework intended as an entry point for disciplined design of complex cyber-physical systems. This framework provides a set of rules for combining several domain-specific languages as structured, enclosing layers to orthogonalize the many aspects of system behavior, yet study their interaction in tandem. We define four layers: one for capturing timed interactions in heterogeneous systems, one for structured parallelism, one for modeling uncertainty, and one for describing component properties. This framework enables a systematic exploitation of design properties in a design flow by facilitating the stepwise projection of certain layers of interest, the isolated analysis and refinement on projections, and the seamless reconstruction of a system model by virtue of orthogonalization. We demonstrate the capabilities of this approach by providing a compact yet expressive model of an active electronically scanned array antenna and signal processing chain, simulate it, validate its conformity with the design specifications, refine it, synthesize a sub-system to VHDL and sequential code, and co-simulate the generated artifacts.

The shift towards parallel computing witnessed since the turn of this century has forced us to rethink traditional software design paradigms to better utilize resources. Yet, the simulation of time-aware systems remains a challenging topic due to the inherent semantics of time and causality whose consistency needs to be controlled, traditionally in form of a global event queue, limiting the potential for parallel exploitation. We propose a rehash of this problem by tackling it from a different modeling perspective, one which is able to express concurrency more naturally, i.e. dataflow (DF) models of computation (MoCs). By abstracting time aspects as an algebra hosted on a pure DF MoC, we are able to apply recent results from MoC theory not only for the purpose of describing deterministic behaviors for distributed timed systems, but also to overcome the existing limitations of timed execution in order to increase a simulation model's performance. We use a well-known example of a deadlock-prone distributed discrete event system as a driver to introduce the modeling concepts and show their potential for parallelism.

With the ever increasing complexity in safety-critical and performance-demanding application domains such as automotive and avionics, the costs of designing, producing and especially testing systems does not scale well for the next generation of applications. One example is the active electronically scanned array (AESA) antenna signal processing chain, which is currently out-of-reach from consumer products but rather part of a few exclusive hi-tech appliances. To cope with the associated complexity of such systems, we propose a design flow starting from a high-level formal modeling language which captures and exposes important design properties to enable their systematic exploitation for the purpose of simulation, analysis and synthesis towards cost-efficient implementations. We demonstrate the capabilities of this approach by providing a compact yet expressive description of the AESA signal processing chain, generate automatic test-cases to verify the conformity of model with design specifications, synthesize a part of it to VHDL and co-simulate the generated artifact to validate its correctness.

The tradeoff between analyzability and expressiveness is a key factor when choosing a suitable dataflow model of computation (MoC) for designing, modeling, and simulating applications considering a formal base. A large number of techniques and analysis tools exist for static dataflow models, such as synchronous dataflow. However, they cannot express the dynamic behavior required for more dynamic applications in signal streaming or to model runtime reconfigurable systems. On the other hand, dynamic dataflow models like Kahn process networks sacrifice analyzability for expressiveness. Scenario-aware dataflow (SADF) is an excellent tradeoff providing sufficient expressiveness for dynamic systems, while still giving access to powerful analysis methods. In spite of an increasing interest in SADF methods, there is a lack of formally-defined functional models for describing and simulating SADF systems. This article overcomes the current situation by introducing a functional model for the SADF MoC, as well as a set of abstract operations for simulating it. We present the first modeling and simulation tool for SADF so far, implemented as an open source library in the functional framework ForSyDe. We demonstrate the capabilities of the functional model through a comprehensive tutorial-style example of a RISC processor described as an SADF application, and a traditional streaming application where we model an MPEG-4 simple profile decoder. We also present a couple of alternative approaches for functionally modeling SADF on different languages and paradigms. One of such approaches is used in a performance comparison with our functional model using the MPEG-4 simple profile decoder as a test case. As a result, our proposed model presented a good tradeoff between execution time and implementation succinctness. Finally, we discuss the potential of our formal model as a frontend for formal system design flows regarding dynamic applications.

Advancements on analog integrated design have led to new possibilities for complex systems combining both continuous and discrete time modules on a signal processing chain. However, this also increases the complexity any design flow needs to address in order to describe a synergy between the two domains, as the interactions between them should be better understood. We believe that a common language for describing continuous and discrete time computations is beneficial for such a goal and a step towards it is to gain insight and describe more fundamental building blocks. In this work we present an algebra based on the General Purpose Analog Computer, a theoretical model of computation recently updated as a continuous time equivalent of the Turing Machine.

Recent trends in replacing traditionally digital components with analog counterparts in order to overcome physical limitations have led to an increasing need for rigorous modeling and simulation of hybrid systems. Combining the two domains under the same set of semantics is not straightforward and often leads to chaotic and non-deterministic behavior due to the lack of a common understanding of aspects concerning time. We propose an algebra of primitive interactions between continuous and discrete aspects of systems which enables their description within two orthogonal layers of computation. We show its benefits from the perspective of modeling and simulation, through the example of an RC oscillator modeled in a formal framework implementing this algebra.