The AAA Methodology and
HOME DOWNLOAD DOCUMENTATION COLLABORATIONS PUBLICATIONS SCICOS/SynDEx SynDEx-IC

SynDEx is a system level CAD software based on the algorithm-architecture adequation (AAA) methodology intended to optimize the implementation, under real-time constraints, of embedded control applications onto multicomponent architectures built from several processors/cores and specific integrated circuits all interconnected. It has been designed and developed in the INRIA Paris-Rocquencourt Research Center France, by the AOSTE team.

 

Key features

Rapid prototyping of complex distributed real-time embedded applications based on automatic code generation in three steps:

  1. implementation onto a workstation for functional simulations,
  2. implementation onto a multi-workstation for studying the parallelism benefits and accelerating functional simulations,
  3. implementation onto the targetted multicomponent architecture, i.e. an architecture made of programmable components (processors/cores) and non programmable components (specific integrated circuits) all interconnected through communication media (bus, links, crossbar, etc.), for real-time execution.

Automatic generation of correct by construction and optimized distributed real-time code thanks to formal verifications and exploration of possible implementations manually, or automatically with optimization heuristics, based on multi-periodic distributed real-time scheduling analyses.

Hardware/Software codesign through multicomponent architecture when some parts of the application must be implemented by software running on processors/cores, while other parts must be implemented by hardware running on specific integrated circuits.

Interface with domain specic languages (DSL) such as the synchronous languages (Esterel, SyncCharts, Signal) providing formal verifications, AIL a language for automotive, Scicos a Simulink-like language (access to the Scicos-SynDEx gateway), CamlFlow a functional data-flow language, UML2.0 with the MARTE profile, etc.

System level CAD tool offering a seamless software environment to help the user from the specification level (functional specifications, distributed hardware specifications, real-time and embedding constraints specifications) to the distributed real-time embedded code level, through (multi-)workstation functional and timing simulations.

Interface with the integrated circuit level CAD tool SynDEx-IC which allows the implementation of a function (operation) onto a specific integrated circuit that can be used as a non programmable component in the multicomponent architecture.

Downloadable freeware, multi-platform (Windows, Linux, Mac OS), full documentation (user manual, reference manual, and tutorial).

Real-Time Embedded Applications

Real-time embedded applications are mostly found in the domains of transportation (avionics, automotive, railway, autonomous transportation, etc.), mobile robotics, telecommunications, consumer electronics, industrial control, etc. Such complex applications are mainly based on signal processing and/or image processing and/or process control algorithms. They must permanently interact with their environment that they control. They must react to every input event received from the environment, by executing the functions of the application whose results are output events sent to the environment. The reaction time between an input event and the corresponding output event is equal to the total execution time of the application executed onto the multicomponent. In order to keep control over its environment, otherwise dramatic consequences occur, both the reaction time of the application and the period of its imput stimuli, must be guaranteed. That kind of applications are qualified of hard real-time. In addition, embedding constraints leads to minimize resources (amount of program or data memory, silicium surface, power consumption, etc.).

When the complexity of the application algorithms leads to a high ratio between its computation volume and its reaction time, standard off the shelf sequential architectures are inadequate. Therefore, distributed, parallel, multiprocessor, multi/manycore architectures are required. Programming such architectures is an order of magnitude harder than with uniprocessor sequential ones, and even more when architecture resources must be minimized to match cost, power and volume constraints required for embedded applications.

The AAA methodology and the SynDEx CAD software that supports it, have been developed to help designers in optimizing the implementation of such applications while satisfying real-time constraints.

Multicomponent Architectures

Although new uniprocessor architectures (workstations), provide ever increasing computation power, they cannot cope with the ever increasing complexity of some control, signal and image processing applications. Distributed, parallel, multiprocessor, multi/manycore architectures are needed, to satisfy real-time constraints (by increasing the computation power), as well as to take into account the modularity issues and the distributed nature of the resources (sensor/actuator, computation, memory) of real-time embedded applications. We called multicomponent these heterogeneous architectures, built from different types of programmable components (RISC, CISC, DSP processors) and/or of non programmable components (ASIC, FPGA, full-custom integrated circuits), all interconnected through a network of different types of communication components (point-to-point serial or parallel links, multipoint shared serial or parallel buses, with or without memory capacity). Hardware/software codesign consists, for the designer, in choosing the part of the application algorithm which will be implemented onto non programmable components (hardware), and the part of the application algorithm which will be implemented onto programmable components (software).

AAA Methodology

AAA means algorithm-architecture adequation. The goal of the AAA methodology is to find out the best implementation of an algorithm specifying the functions (operations) the application has to perform onto a multicomponent architecture, while satifying real-time and embedding constraints. Adequation means an efficient implementation. Notice that it is different from adequacy.

The AAA methodology is based on graphs models to exhibit both the potential parallelism of the application algorithm and the available parallelism of the multicomponent. The algorithm graph is a conditioned factorized dataflow graph repeated infinitely according to every reaction. A conditioned vertex is a hierarchical vertex which contains several sub-dataflow graphs. According to the value of its specific input called "condition" only one of the possible sub-dataflow graphs will be executed during the considered reaction. A factorized vertex is also a hierarchical vertex which contains a repetition of N times of one sub-dataflow graph. These hierarchical vertices are the equivalent in the dataflow model of respectively "If...Then...Else..." and "For i= 1 to N Then..." in the controlflow model. In addition, hierarchy may also be typically used to specify application algorithm with a top-down approach. The implementation consists in distributing and scheduling the algorithm graph onto the multicomponent graph while satisfying real-time constraints (deadline=period, reaction time). This is formalized in terms of graph transformations. Heuristics based on distributed real-time scheduling analyses taking into account timing characteristics attached to operations (period, worst case execution time of computations and of inter-component communications), are used to automatically explore the possible implementations of a given application onto a given multicomponent that satisfy real-time constraints, and to optimize the reaction time as well as resources allocation. For the purpose of hardware/software codesign, resources may be of processor type when a program must be allocated on it (a sequence of operations executed by a processor and a sequence of communications), or may be of integrated circuit type when only a unique operation must be allocated on it (a net-list of interconnected logical blocks, CLBs).

The result of graph transformations is an optimized Synchronized Distributed Executive (SynDEx) dedicated to the application, automatically built from a library of architecture dependent executive primitives composing each executive kernel. There is one executive kernel for each supported processor. Synchronized means that inter-component communications are performed through automatically generated synchronisation semaphores in order to avoid any deadlock. The executive primitives support boot-loading, memory allocation, inter-component communications, scheduling of user supplied computation functions, and of inter-component communications, and finally synchronization of functions and communications sequences.

The fundamentals of the AAA methodology are described more in details here. You may also read our publications.

SynDEx CAD Software

SynDEx is a graphical interactive software (see examples) with on-line documentation, implementing the AAA methodology. It allows:

  • specification and verification of an application algorithm as a directed acyclic graph (DAG) of operations where edges are dependences between operations, or interface with DSL allowing potential parallelism, such as the synchronous languages (Esterel, SyncCharts, Signal) providing formal verifications, AIL a language for automobile, Scicos a Simulink-like language (access to the Scicos-SynDEx gateway), CamlFlow a functional data-flow language, etc.,
  • specification and verification of a multicomponent architecture as a graph composed of programmable components (processors) and/or specific non programmable components (ASIC, FPGA), all interconnected through communication media (point-to-point, bus, shared memory, message passing),
  • specification of the application algorithm characteristics relatively to the hardware components or vice versa (WCET - worst case execution time - and period - presently non preemptive strict period - of operations and WCCT - worst case communication time - of data transfers), specification of the real-time constraints to satisfy (presently deadline=period), and specification of distribution and scheduling constraints,
  • exploration of possible implementations (distribution and scheduling) of the application algorithm onto the multicomponent, performed manually or automatically with optimization heuristics, based on multi-periodic distributed real-time scheduling analyses ,
  • visualization of a timing diagram (scheduling table) simulating the distributed real-time implementation, useful for real-time constraints verification and for application algorithm improvement,
  • generation of dedicated distributed real-time executives with optional real-time performance measurement, or configuration of general purpose real-time operating systems (RTOS) such as Linux, Linux/RTAI, Windows/RTX, Osek, etc. You can access a comparison of the main RTOS. These executives are deadlock free and based on scheduling tables. Dedicated executives which induce minimal over-head are built from processor-dependent executive kernels. Some of them are provided for the following processors: PIC18F2680, ADSP21060, TMS320C40, i80386, MC68332, MPC555, i80C196, Linux and Linux/RTAI workstations, and the following communication media: TCP/IP, RS232, CAN. Executive kernels for other processors can be easily ported from the existing ones.

The distribution and scheduling heuristics, as well as the timing diagram, help the user to parallelize his application algorithm and to explore architectural solutions while satisfying real-time constraints. Since SynDEx provides a seamless framework from the specification to the distributed real-time execution, formal verifications obtained during the early stage of the specification, are maintained along the whole development cycle. Moreover, since the executives are automatically generated, part of tests and low level hand coding are eliminated, decreasing the development lifecycle.

You can download free of charge the latest version of SynDEx, and read the latest web documentation.

SynDEx is written in Objective Caml. The GUI is written in Tcl/Tk with the OCaml library CamlTk.

Take a look at a SynDEx demo!



Last update: October 4th 2019
For any scientific or administrative questions, please contact: Yves.Sorel@inria.fr
For any technical question, please contact: syndex-support@inria.fr