Search

Software and systems modeling 20(3), 611-639 (2021). doi:10.1007/s10270-021-00876-z, Published by Springer, Berlin; Heidelberg; New York, NY

Radar system simulation usually needs to consider not only the modeling work of its static system structure but also the representation of dynamic behaviors. Traditionally, the standard Simulation Model Portability (SMP) published by European Space Agency is very suitable to build the structure of entities and their internal and external static relationships as well, but it shows pale to specify complex dynamic behaviors, such as that of radar system. To describe the behavioral aspect, we applied Synchronous data flow (SDF) and combined SMP with it. If so, one can benefit from a loose coupling way to design radar system in two different kinds of formalisms, and can simultaneously support structural modeling and behavioral modeling. For this purpose, the goal of this paper is to design a mechanism of how to combine and use these two formalisms together to form a novel simulation language. As a proof of concept, we built a set of functional models of a general radar system by using this new language and simulation results show its proper availability.

Various programming languages have been developed specifically for audio DSP in the last decades, yet only a handful of industrial and commercial applications are known to actually use them. We assume that this is due to some common deficiencies of such languages, namely the tight coupling between syntax and computational model, which limits modularity, and the adoption of programming paradigms that are conceptually distant from conventional DSP formalism. We propose a new audio DSP programming language, called Ciaramella, based on the synchronous data flow (SDF) computational model and featuring a fully declarative syntax to address these issues. A source-to-source compiler which translates Ciaramella code to C++ and MATLAB programs has been developed. We have verified that our solution allows to naturally represent and correctly schedule highly-interdependent DSP systems such as Wave Digital Filters (WDFs) which would be hard to handle in current audio DSP languages.

This thesis proposes the use of a synchronous data flow graph (SDFG) to model the computation of a non-iterative co-simulation. An SDFG is a determinate model of computation with a lot of scheduling research available. A method for creating an SDFG from a co-simulation network, initial tokens and simulator step sizes is described. A simulator in the proposed method is a synchronous data flow actor that is used to model the execution of a co-simulation slave. It is shown that such an SDFG has consistent rates and uniformly updates the states of all simulators. To analyze the behavior of numerical errors introduced in the co-simulation, it is assumed that coupled ordinary differential equations can represent the modeled system. This thesis uses the numerical defect analysis to formulate a co-simulation quality criterion. The numerical defect is divided into integration, output and connection defects. Such a defect distribution reflects the division of responsibility between the co-simulation master and the internal solvers of the slaves. This work proposes how connection defects can be calculated and output defects can be estimated. Integration defects are not analyzed as it is assumed that they are controlled by internal solvers of the slaves. The proposed quality criterion for the co-simulation is based on the aggregation of the output and connection defects. The simulator step sizes, the number and values of the initial tokens should be determined in order to configure the execution of a co-simulation network. A method for calculating the number of initial tokens based on the simulator step sizes is proposed. It is shown that an SDFG with such number of initial tokens does not deadlock. Furthermore, a method how to check whether it can run in real-time is shown. The quality criterion enables an optimization approach to find the values of the initial tokens. In the proposed approach, the quality criterion is assessed in a single iteration of the SDFG. The Nelder-Mead algorithm is used to solve the optimization problem of finding initial token values. To complete the automatic configuration of the co-simulation, the simulator step sizes must be determined. This is done by reducing the simulator step sizes until the requested tolerance is met. This thesis proves that connection and output defects can be controlled by reducing simulator step sizes. The automated configuration algorithm presented in the last chapter is the main goal of this thesis. The methods for determining the step sizes of the simulator, the number and the values of the initial tokens are building blocks of this algorithm. The validity and usefulness of the proposed algorithm is justified with theorems and examples presented throughout this thesis. Ovaj rad predlaže korištenje grafa sinkronog protoka podataka (SDFG) za modeliranje izračuna neiterativne kosimulacije. SDFG je jedinstveno definiran računski model s dostupnom literaturom u području planiranja izvedbe. Opisana je metoda za generiranje SDFG iz kosimulacijske mreže, početnih žetona i veličina koraka simulatora. Simulator u predloženoj metodi je agent sinkronog protoka podataka koji se koristi za modeliranje izvedbe kosimulacijske jedinice. Pokazalo se da takav SDFG ima konzistentne stope i jednoliko ažurira stanja svih simulatora. Pretpostavlja se da povezane obične diferencijalne jednadžbe mogu predstavljati modelirani sustav zbog analize ponašanja numeričkih pogrešaka unesenih u kosimulaciji. Ovaj rad koristi numeričku analizu defekata za formuliranje kriterija kvalitete kosimulacije. Numerički defekt dijeli se na integracijske, izlazne i spojne defekte. Takva raspodjela defekata odražava podjelu odgovornosti između algoritma upravljanja kosimulacijom i kosimulacijskih jedinica. Ovaj rad sugerira kako se mogu izračunati spojni defekti i procijeniti izlazni defekti. Izlazni defekti se ne analiziraju jer se pretpostavlja da ih kontroliraju algoritmi rješavanja običnih diferencijalnih jednadžbi. Predloženi kriterij kvalitete za kosimulaciju temelji se na spajanju izlaznih i spojnih defekata. Potrebno je odrediti veličinu koraka simulatora, broj i vrijednosti početnih žetona kako bi se oblikovalo izvođenje kosimulacijske mreže. Predložena je metoda za izračunavanje broja početnih žetona na temelju veličina koraka simulatora. Pokazano je da SDFG s takvim brojem početnih žetona ne dolazi u zastoj. Nadalje, prikazana je metoda kako provjeriti može li raditi u stvarnom vremenu. Kriterij kvalitete omogućuje optimizacijski pristup za pronalaženje vrijednosti početnih žetona. U predloženom pristupu, kriterij kvalitete ocjenjuje se u jednoj iteraciji SDFG-a. Nelder-Mead algoritam se koristi za rješavanje problema optimizacije pronalaženja početnih vrijednosti žetona. Da bi se dovršilo automatsko oblikovanje kosimulacije, mora se odrediti veličina koraka simulatora. To se postiže smanjenjem koraka simulatora sve dok se ne ispuni tražena tolerancija. Ovaj rad dokazuje da se spojni i izlazni defekti mogu kontrolirati smanjenjem koraka simulatora. Algoritam automatiziranog oblikovanja predstavljen u posljednjem poglavlju glavni je cilj ovog rada. Metode za određivanje veličine koraka simulatora, broja i vrijednosti početnih tokena osnovni su blokovi ovog algoritma. Valjanost i korisnost predloženog algoritma opravdane su teoremima i primjerima prikazanim u ovom radu.

The implementation of embedded software applications is a complex process. The complexity arises from the intense time-to-market pressures; power and memory constraints. To deal with this complexity, an idea is to automatically construct the applications based on the high-level abstraction model. Synchronous data flow (SDF) is a high-level model of computation, and is used to model the embedded applications. Formal System Design (ForSyDe), developed by ForSyDe group at KTH Royal Institute of Technology, is a methodology for modeling and designing heterogeneous systems-on-chip. The aim of Formal System Design (ForSyDe) is to automatically generate the detailed software implementation or hardware implementation according to the high-level system specification. Formal System Design (ForSyDe) starts from the high-level system specification and specifies the system model in Haskell language. Synchronous data flow is supported by ForSyDe. ForSyDe IO is an intermediate representation of the high-level system specification. This master thesis focuses on the software synthesis of synchronous data flow models specified in ForSyDe IO, and aims to produce an automatic code generator that can generate software applications in C code for different platforms based on ForSyDe IO. In this project, a software synthesis method for ForSyDe IO was proposed. Then, based on the software synthesis method, a code generator, written in Java and Xtend, was designed. The derived code generator was tested on two examples. The experiment results show that the synchronous data flow models specified in ForSyDe IO are successfully synthesized into C code. The code is in the Github repository https://github.com/Rojods/CInTSyDe.git with MIT license. Implementeringen av inbäddade mjukvaruapplikationer är en komplex process. Komplexiteten beror på det intensiva trycket på tid-till-marknad; kraft- och minnesbegränsningar. För att hantera denna komplexitet är en idé att applikationerna automatiskt kan konstrueras den högnivåabstraktionsmodellen. Synkront dataflöde (SDF) är en beräkningsmodell på hög nivå som används för att modellera inbäddade applikationer. Formell systemdesign (ForSyDe), utvecklad av ForSyDe-gruppen vid KTH, Kungliga Tekniska Högskolan , är en metodik för modellering och design av heterogena system på chipp. Syftet med formell systemdesign (ForSyDe) är att automatiskt generera den detaljerade mjuk- eller hårdvaruimplementationen enligt systemspecifikationen på hög nivå. Formell systemdesign (ForSyDe) utgår från systemspecifikationen på hög nivå och specificerar systemmodellen på Haskell-språket. Synkront dataflöde stöds av ForSyDe. ForSyDe IO är en mellanrepresentation av systemspecifikationen på hög nivå. Detta examensarbete fokuserar på mjukvarusyntesen av ForSyDe IO och synkront dataflöde, och syftar till att producera ett automatiskt verktyg som kan generera mjukvaruapplikation i C-kod för olika plattformar baserat på ForSyDe IO. I detta projekt föreslås en mjukvarusyntesmetod för ForSyDe IO. Sedan, baserat på mjukvarusyntesmetoden, designas en kodgenerator skriven i Java och Xtend. Den härledda kodgeneratorn testas på två exempel. Experimentresultaten visar att ForSyDe IO framgångsrikt har syntetiserats till C-kod.

Synchronous Data Flow (SDF) is a graphical computation model used for analyzing digital signal processing and real time multimedia applications. In general, these applications have two primary performance metrics - throughput and latency. Latency is important in multimedia processing applications such as video-conferencing, Internet telephony and games since latency surpassing a specific limit results in poor quality of service (QoS). Past work had focused on computing the latency of SDF graphs on homogeneous multiprocessor platforms. In this paper, we present an approach to compute the latency of a static schedule for a given unfolding factor with an optimal throughput for an SDF graph on a heterogeneous multiprocessor platform using timed automata. We use timed automata as a semantic model to represent the system model, which includes a synchronous data flow graph and an execution platform. We use the UPPAAL model-checker to specify the resulting network of timed automata and compute the latency.

International audience; Fast yet accurate performance and timing prediction of complexparallel data flow applications on multi-processor systems remainsa difficult discipline. The reason for it comes from the complexity ofthe data flow applications and the hardware platform with sharedresources, like buses and memories. This combination may lead tocomplex timing interferences that are difficult to express in pure analyticalor classical simulation-based approaches. In this work, wepropose a message-level communication model for timing and performanceprediction of Synchronous Data Flow (SDF) applicationson MPSoCs with shared memories. We compare our work againstmeasurement and TLM simulation-based performance predictionmodels on two case-studies from the computer vision domain. Weshow that the accuracy and execution time of our simulation outperformsexisting approaches and is suitable for a fast yet accuratedesign space exploration.

Combat system modeling generally includes two aspects: structure and behavior. Structural modeling is to build the structure of entities and their internal and external static relationships. Behavioral modeling aims at the typical working processes. The simulation modeling definition language (SMDL) of Simulation Modeling Platform (SMP2) can describe system structure well, but it is difficult to support behavioral modeling. The modeling and simulation tool named Ptolemy is able to support the description of system behavior, but it lacks effective support for structural modeling. For this reason, the goal of the paper is to explore a mechanism to combine structural and behavioral modeling, which can not only effectively support the architecture design but also support the expression of system behaviors. As a proof of concept, we extend the SMDL by adding the synchronous data flow (SDF) elements, and use this new language, namely, the extended Simulation Model Definition Language (ESMDL), to specify a radar system for both of structural and behavioral modeling.

Synchronous reactive data flow is a paradigm that provides a high-level abstract programming model for embedded and cyber-physical systems, including the locally synchronous components of IoT systems. Security in such systems is severely compromised due to low-level programming, ill-defined interfaces and inattention to security classification of data. By incorporating a Denning-style lattice-based secure information flow framework into a synchronous reactive data flow language, we provide a framework in which correct-and-secure-by-construction implementations for such systems can be specified and derived. In particular, we propose an extension of the Lustre programming framework with a security type system. We prove the soundness of our type system with respect to the co-inductive operational semantics of Lustre by showing that well-typed programs exhibit non-interference.

International audience; Modern Cyber-Physical Systems (CPSs) are composed of numerous components, some of which require real-time management: for example, management of sensors and actuators requires periodic deadlines while processing parts do not. We refer to these systems as partially periodic. In a partially periodic system, precedence constraints may exist between periodic and aperiodic components. It is notably the case in CPSs where sensors measuring physical variables at a fixed sampling rate are typically feeding data to one or more processing part. A critical challenge for any real-time CPS software is its scheduling on an embedded computing platform. The increasing number of cores in such platforms (as Kalray MPPA Bostan having 288 cores) makes offline non-preemptive scheduling techniques efficient to respect real-time constraints, but requires new analysis and synthesis algorithms. In this paper, we study the schedulability of partially periodic systems modeled as Synchronous Data Flow (SDF) graphs. Our contributions are a few necessary conditions on any live SDF graph, and a linearithmic offline non-preemptive scheduling algorithm on vertices of any directed acyclic task graph. The presented algorithm has been evaluated on a set of randomly generated SDF graphs and on one real use-case. Experiments show that our proposed non-preemptive scheduling algorithm allocates thousands of tasks in less than a second. In the last experiment, the computed schedules achieve a throughput close to that one obtained with global Earliest Deadline First (EDF) scheduling.

A new method of the pipelined datapath synthesis which is based on the genetic programming approach is proposed. The method is based on the representation of the algorithm by the spaced synchronous data flow (SDF), transferring it to a chromosome, and using the conventional genetic optimization algorithm. The respective creation, duplication, mutation and recombination functions are proposed as well. The method effectiveness is shown on the example of the DCT transform datapath synthesis.

IoT systems are getting more complex with the exponential growth of embedded applications which reduces their robustness and compromises the quality of service. Some solutions based on performance estimation have been proposed to overcome this problem. However they are manually processed and limited such as complex heuristics and random process. One solution is to implement an automatic scheduling approach that meets the constraints of application and making compromise between the needs imposed by it and the offers proposed by the target IoT in order to obtain gains in term of total equitable distribution of workload over the various resources available in the system, reduce processing time and achieve performance satisfaction for a multiprocessing IoT system. In this paper, we propose an original methodology which deals with both Task Partitioning and CO-design Methodology that we called (TPCOM) that allows a good scheduling from a SDF (Synchronous Data Flow) graph of the application. An experiment study on the MJPEG reference application is conducted in order to illustrate the effectiveness of our approach.

Novel memory architectures have been introduced in multi/many-core processors to address the performance bottle neck due to shared memory accesses. Taking the advantages brought by these architectures in scheduling analysis is still an open challenge. In this article, we present a scheduling analysis technique that exploits a shared multi-bank memory architecture to efficiently schedule parallel real-time applications modeled as synchronous data flow (SDF) graphs by minimizing the memory access contentions. Our approach aims at producing a static time-triggered schedule with the objective of minimizing the makespan and buffer size requirements while respecting consistency and data dependency constraints. An Integer Linear Programming formulation of the scheduling problem is presented, as well as a heuristic with significantly lower time complexity. Experimental results are given using synthetic SDF graphs generated by the SDF3 tool and applications available in the StreamIt benchmark.

Synchronous Data-Flow as a deterministic variation of Khan Process Networks is a good model for distributed applications that allows for verification of the properties of the applications both at the design level and at run-time. Real-Time extensions exist which allow to specify Real-Time clocks for some of the processes in the graph. With the addition of Real-Time clocks, the behavior of the complete system can be easily differentiated from a nominal Real-Time mode where all the required data for processing is available when a clock tick occurs, and an error mode can be triggered when the condition is not met. Our contribution in this paper is –first– to show a set of graph transformations that allow to account for the execution and communication time on a real platform while at the same time maximizing the parallelism of execution and –second– on top of these transformations to provide the execution constraints as a linear program that must be met at run-time to guarantee the real-time requirements. It is illustrated on a subset of a real-life automotive example.

In all modern computer systems power consumption and thermal management is a major concern to control battery life and ageing to guarantee system availability. In such systems, a power manager changes the hardware component parameters at runtime to control the power consumption. E.g. it may temporarily switch off unused hardware components. To enable this switching together with arbitrary software applications, a feasible approach is to divide the application behaviour into different scenarios that represent different operation and power modes.In this paper, we extend an approach for translating Simulink models into a Synchronous Dataflow (SDF) representation that allow a seamless mapping to a shared memory MPSoC architecture. This paper focuses on an extension for modelling a power manager by using the Finite State Machine (FSM)-Scenario Aware Dataflow (SADF) extension of SDF. To demonstrate our approach, a Simulink traffic sign recognition model is translated into an SDF and FSM-SADF representation, where the latter one is used to express two different scenarios for employing power management. The feasibility of our approach is validated through an implementation on a Xilinx ZC702 board.

Data flow formalisms are commonly used to model systems in order to solve problems of buffer sizing and task scheduling. A prerequisite for static analysis of a modeled system is the existence of a periodic schedule in which the sizes of communication channels can be bounded for an unbounded execution (consistency), and that communication dependencies do not introduce a deadlock in such an execution (liveness). In the context of Cyber-Physical Systems, components are often interfaced with the physical world and have frequency constraints. The existing data flow formalisms lack expressiveness to fully cover the expected behavior of these components. We propose an extension to Synchronous Data Flow (SDF) formalism, called Polygraph, that includes frequency constraints and adjustable communication rates. We show that with these extensions, the conditions for a model to be consistent and live are no longer sufficient, and we extend the corresponding theorems with necessary and sufficient conditions to preserve these properties. We also introduce a framework to check the liveness of a Polygraph model, implemented in the tool DIVERSITY, along with preliminary experiments to validate this approach.