Olivier Bompis

Pierre-Yves Guidotti

Michel Delpech

Bernard Pontet

Simulation and Validation Strategy on Real-Time Autocoded Onboard Software for Formation Flying In-Orbit Ranging Demonstration

Keywords: Embedded Autocoded Software, Model Based Design, IV&V, Matlab/Simulink®, RTW®, LEON3, RTEMS

This article gives an overview of the simulation and validation strategy used for a realtime onboard software (OBSW) module developed on Matlab/Simulink® environment and autocoded into C language using the Real-Time Workshop Embedded Coder® (RTW). This module is the key point of the Formation Flying In-Orbit Ranging Demonstration (FFIORD) on PRISMA satellite mission. To respect requirements on real-time execution conditions and software reliability for space missions, the OBSW module is carefully tested before delivery and integration. Interesting results are obtained based on an inconstancies analysis of the C code produced by RTW, which leads to "good practice" guidelines for Simulink model implementation. Actions realised through this experiment aim at providing a background for the development of adequate Independent Verification and Validation (IV&V) procedures. They give more confidence and experience on the Model-Based Design domain before applying it to large scaled projects.

Introduction

FFIORD Mission Description

PRISMA is a Formation Flying mission proposed by the Swedish National Space Board (SNSB) for validation of formation flying concepts and technologies as early as 2009. Two satellites set the formation. The Main is a fully manoeuvrable satellite with a six thrusters' configuration for attitude and orbit control. The Target uses magnetorquers for attitude control only, without orbit control capability. The CNES participation on PRISMA consists of embarking the Formation Flying RF Metrology subsystem (FFRF) on the two PRISMA satellites as passenger equipment. This radiofrequency-based sensor developed by Thales Alenia Space is partly designed on existing GPS technology. It will be used as a coarse metrology and safety monitoring sensor for future Formation Flying missions. Thus, FFIORD will include closed loop operations with the FFRF sensor, allowing genuine autonomous formation flying scenarios and associated GNC algorithms to be tested in real-life conditions. Once developed and validated on the Matlab/Simulink® environment, "CNES_GNC_lib" is integrated in the main PRISMA OBSW Simulink® model on the Swedish side. An automatic code generation process is then performed using the Real-Time Workshop Embedded Coder®. In order to be run on the Main satellite onboard computer, the autocoded C code is cross compiled for the LEON3-FT (SparcV8 design). The first part of this paper describes the validation process realised on the CNES GNC module within two consecutive steps. The second part contains an evaluation of code generation quality through Code reliability and coverage analysis with specific tools. The last part provides a validation strategy for any autocoded software obtained with the Real-Time Workshop Embedded Coder®. Every section contains associated results.

CNES GNC Module IV&V Process

A quick and efficient two steps process is performed for the CNES GNC Module validation.

Firstly, a dedicated Matlab/Simulink® test harness is developed to run GNC algorithms in their native context, using space environment and equipment simulation models. A numeric simulator representing accurate behaviour of the FFRF sensor is developed and used in the further OBSW testing. Thus, this simulator is considered as reference for further hybrid tests.

Secondly, a hybrid simulator based on a LEON-3FT processor is developed under the real-time operating system RTEMS. This allows real-time testing for autocoded algorithms obtained from the code generator with PRISMA mission representative processor board and operating system. This hybrid simulator provides realistic estimations of computational load, and evaluates final autocoded algorithm performances by using a set of reference scenarios. Comparisons between these two different environments are realised on produced results.

Simulation of the "CNES_GNC_lib" Model

The GNC library is entirely developed on Simulink environment in order to be integrated inside the main OBSW developed as Simulink model. This allows experiment capabilities such as simulation tools provided by this environment. Furthermore, the Model-Based Design approach is well-adapted for any non computer software engineer (i.e. GNC engineer). Each function can be implemented through combination of functional blocks which realise unit operations. At this step, each algorithm is developed on a functionality sense not on a software one. Every requirement and specification comes from functionality analysis.

The "All Software" (AS) test facility consists of a Simulink® simulation which contains several items: • Environment models which simulate realistic In-Orbit flight conditions. • TC Generator model which allow controlling the CNES GNC module through specific Telecommands.

• FFRF Sensor model which interacts with the CNES GNC module. • PRISMA System models which simulate the main OBSW of the Swedish side and other PRISMA services afforded by the spacecrafts. These items are connected as inputs / outputs to the "CNES_GNC_lib" library to be tested. A typical simulation output is presented there after to illustrate the validation strategy of the GNC functions. The simulation scenario begins with station keeping of the Main satellite at [50, 190, 0 m] in the Target Local Orbital Frame named SLO (Z is Earth Oriented, Y is opposite to the orbit kinetic momentum, X is almost the velocity vector for near circular orbit). Then a forced translation is commanded to reach in 2000s the point [30, 0, 0 m].

Simulation of the autocoded CNES GNC library

After having performed Verification & functional validation of the GNC library inside the "All Software" Test Facility, automatic code generation process can be run using the Real-Time Workshop Embedded Coder®. In order to have runs of the generated C code on the mission representative processor (LEON3), a specific real-time embedded benchmark is developed. This benchmark handles RTW C code on a real-time task of the RTEMS operating system which is also mission representative.

An Ethernet data link is used between the Simulink simulation on Unix Workstation or PC, and the LEON3-FT GR-CPCI-AX2000 development board. The client is implemented inside a specific S-Function in Simulink while the server is on the LEON3-FT side. This S-Function replaces the "CNES_GNC_lib" model in the previous "All Software" Test Facility. Such an iterative approach shall be followed soon in the development process to avoid issue when testing the full software on the board at the end of the development. A good illustration comes from the use of Simulink state vector block "1/z delay" that shall be used with an extreme care. Indeed, even if only a small subset of the state vector shall be updated within a given time step, the whole vector is copied (full variable copy of the previous state) and then updated (copy of the incoming subset). This can lead to a huge CPU consumption for big state vectors. The solution is to design the Simulink® model by replacing any inadequate big state vector with several distributed state vectors. Following this philosophy, CPU load was decreased from more than 13ms down to 6ms for the "Depack_TC" subsystem.

Results comparison analysis between "All

Software" and "Hybrid" Test Facilities

In order to validate the autocoded GNC software obtained from the GNC Simulink® library, it becomes necessary to compare outputs produced from the two Test Facilities ("All Software" configuration on Windows PC and Hybrid configuration on PC-UNIX/LEON3). Here focus is made on the Target satellite absolute states estimation (3-axis position in inertial frame) as computed by the "CNES_navigation" subsystem of the CNES GNC library running a specific reference scenario.

Two configurations are considered for the "All Software" Test facility, depending on the computer used to host together the Simulink® simulator and the CNES GNC library model (Sun Sparc Solaris or PC Intelx86). Hardware details used for "All Software" and Hybrid simulations are summarised in the table below.

Test Facility Configuration

Hardware Design

Hardware Name

All Software (config #1)

Intelx86 IBM® Laptop All Software (config #2) Ultra Sparc III+ Sun Blade 1000 UNIX Workstation Intelx86 IBM® Laptop Hybrid LEON3-FT SparcV8 GR-CPCI- AX2000
Table 1: Hardware details of "All Software" and "Hybrid" simulations for the "CNES_GNC_lib" model Note: Analysed outputs are totally independent of the Simulink® simulator part. In fact, no computation is made on the simulator side for the Hybrid Test Facility. Thus, the simulator is only run on the Intelx86 design.

Differences are studied between the two Test Facilities outputs obtained for the GNC library running in open-loop mode (identical inputs for both cases) on specific designs (different compilation and execution processes). The next figure presents evolution of absolute difference on three-axis position of the "Main" satellite as computed from the "CNES_navigation" S/S of the GNC library. This experiment is realised with nominal test scenario which remains unchanged all along analysis. Two parameters which produce changes are identified: rounding direction † for float arithmetic and hardware design.

Figure 10: Absolute difference evolution on threeaxis position of the "Target" satellite between "All Software" and Hybrid Test Facilities

The maximum absolute difference value on Z axis is about 3.25e-4m which shall be compared to the order of magnitude of the estimated position (7000km). This test is realised by differencing position values obtained from "All Software" Test Facility in Windows-PC (rounding direction † set to "NEAREST") and the Hybrid Test Facility on Windows-PC for the simulator side and on LEON3-FT for the autocoded CNES GNC library (rounding direction † set to "INF").

The following The previous results show that even with a same hardware design and rounding direction, exact reproducibility between "All Software" and Hybrid Test Facilities is not complete. Regarding GNC constraints on position accuracy of the "Target" satellite, the maximum difference position value measured is acceptable (3.25e-4m towards the order of magnitude of 7000km on position). In any case, computation environments have to be as close as possible to avoid great disparities between different hardware designs.

Performance validation can't be achieved in trying to retrieve exact results between two simulation run on different environments, but in analysing macroscopic tendencies (convergence time, …) and performance criteria (results accuracy, …).

Autocoded Software Quality & Reliability Analysis

After having achieved performance validation on autocoded software from functional model, an evaluation of code quality and reliability has been performed. For the PRISMA project, a static analysis is realised using PolySpace®. Interesting results are obtained such as logic code coverage and analysis of error occurred in the auto-generated code.

Auto-generated Code Quality Analysis

Typical code metrics have been measured:

• STMT: Number of statements in a function's body.

• AVGS: AVeraGe Size of Statements corresponds to the average number of operands and operators used by each of the function's executable statements. AVGS is calculated as follows:

stat lc N N AVGS _ ) 2 1 ( + = [1]
where: N1 is the number of operator occurrences, N2 is the number of operand occurrences, lc_stat = STMT

• VOCF: VOCabulary Frequency corresponds to the average number of times the vocabulary is used (sum of distinct operands and operators) in a component. VOCF is calculated as follows:

) 2 1 ( ) 2 1 ( n n N N VOCF + + = [2]
where: N1 is the number of operator occurrences, N2 is the number of operand occurrences, n1 is the number of distinct operators, n2 is the number of distinct operands

• LEVL: Maximum nesting level in a function plus one.

• PARA: Number of a function parameters.

• VG: McCabe cyclomatic complexity number of the function. This number depends on the number of nodes of decision in the control graph with the formula:

∑ - + = ision NodesOfDec i n VG 1 1 [3]
where: i n is the number of edges departing from the node i.

• LVAR: Total number of variables declared in a function (Local VARiables).

• DRCT_CALLS: number of direct calls in a function. Different calls to the same function count for one call.

• RETU: Number of Return statements in the function (plus one if the function's last statement is not Return statement).

• GOTO: Number of "Goto" statements.

• COMF: COMments Frequency. Through this analysis, auto-generated code on RTW from a complex functional model can quickly become difficult to read by human despite of comments frequency. The last section of this paper describes some tools which may improve autogenerated code quality and readability.

DRCT CALLS 19 (< 7) 1 (< 7) RETU 0 (< 1) 0 (< 1) GOTO 0 (0) 0 (0) COMF 0,31 (> 0,2) 0,29 (> 0,2)

Auto-generated Code Reliability Analysis

The PolySpace Verifier® tool allows to check software errors such as unreachable code or uncalled procedure or any possible cause of execution exception (underflow / overflow, arithmetic exception, division by zero …). From a logic call functions tree, every function of autocoded software is executed following a normal call sequence. Global variables are initialised with representative definition intervals. Four diagnostic levels are provided at the end of the reliability analysis:

• Statement with non proved reliability (R).

• Statement non reachable (dead line) (Gy).

• Statement with reliability proved (Gr).

• Statement with indeterminate reliability (O).

Indeterminate reliability may indicate potential error or simple warning on specific statement. These points should be analysed manually. Some results on the GNC library are summarised in the following table. Occurrences of possible cause of software exception are classified with respect to the four diagnostic levels previously presented. Auto-generated code can't be directly declared unreliable since there is no presence of red level occurrences. However, orange level cases need to be resolved to ensure code safety. These indeterminate cases should be removed by analysing inputs intervals which are implied to the corresponding statement. For example, an indeterminate reliability case for the "Overflow / Underflow" issue on particular variable must be resolved in analysing definition interval.

Check

Grey (Gr) level occurrences which correspond to unreachable code may appear in the generated RTW code when specific blocks are badly used. Typical example is given below for blocks which protect arithmetic operations in autocoded software.

The following figure presents an unreachable code case due to a bad usage of the "Saturation" block. In that case, the "mask_in" signal is never greater than 65535 during analysis, so the saturation condition in bold never occurs. This design could be maintained to increase model robustness (no prerequisite is made on the "mask_in" input signal).

It shall be removed if functional analysis proves that the "mask_in" variable never reaches 65535.

Auto-generated Code Coverage Analysis

RTW Code coverage analysis can be realised through specific Code Coverage Tool (CCT) [1]. This tool provides coverage information for every statement of autocoded software running as a RTW S-Function. Reference scenarios from Model Validation are re-used here to obtain corresponding code coverage information. These three reference scenarios provides specific CNES GNC S/S activation such as guidance modes according nominal functional cases. These modes are triggered from dedicated telecommands defined in reference scenarios. Concatenating coverage results from each scenario allows obtaining global RTW code coverage information. The CCT uses the automatic code generation process to insert instrumentation code which allows determining whether specific statements are executed or not. At the end of simulation, an automatic code coverage report is provided. This report contains coverage information for each line of auto-generated code.

Autocoded Software Validation Strategy

This last section proposes a validation strategy which may be applied for auto-generated code produced by the Real-Time Workshop® code generator. Each validation step which belongs to the Model-Based Design software development process is described. Advantages gained from automatic code generation are obtained despite of code quality and readability (unitary module, generic and arbitrary variables names, low comments frequency). Time saving during code production may be lost through validation activities. An efficient validation strategy needs to be defined in order to evaluate code quality and reliability.

Model Based Software Design Rules

Automatic code production is based on use and organization of functional blocks inside simulation. Good usage and configuration of these blocks can avoid code error generation and increase code quality of final software.

Through the Model-Based On Board Software PRISMA project (MBOBSW), an interesting knowledge on functional blocks configuration has been developed. These rules define coding standard for functional blocks to prepare auto generation process. This standard definition can improve model & code robustness, and associated documentation readability. It becomes an essential step in the software development cycle to obtain reliable autogenerated software. As presented above, these rules can introduce code redundancy and dead code lines. Despite of these, they need to be applied by any model designer as soon as possible in the autocoded software development process. For further projects, a specific blocks library which implements directly these design rules may be defined

The following table gives an example of one design rule on usual functional block.

« Divide » block

RTW doesn't check block inputs. Arithmetic exception can occurs.

Insert the "Saturation" block in front of the input and set specific definition interval to avoid null input values.

Motivation: code reliability (avoid arithmetic exception).

Table 5: Examples of Design Rules for MBOBSW.

Model-Based Software Functional Validation

In order to realise validation operation before code generation operation, the simulation environment proposes a specific toolbox which allows functional verification of functional models.

With this toolbox, user can specify requirements from preliminary design studies on any targeted S/S in the simulation model. These requirements can be checked through unit tests during simulation and are automatically reported as comments into the autogenerated code.

After checking requirements, model designer can handle functional coverage which points out every non executed blocks and S/S. Several metrics are provided such as design complexity estimation (cyclomatic complexity), condition / decision coverage (decision tree from logic combinatory of specific blocks), and MC/DC tests (from the RTCA DO-178B standard). Coverage report which corresponds to specific test scenario is produced after simulation. Metrics values are provided for each block and S/S of simulated model. Different runs can be compiled to obtain global coverage results.

The next figure presents a coverage metric (MC/DC) for a particular logic block. To conclude, functional model validation is an essential step before any validation operation on the auto-generated code. This "Model In the Loop" (MIL) phase ensures specification verification for every block and S/S. Test scenarios are validated by corresponding functional model coverage.

Auto-generated Code Functional Validation

Three main validation phases can be distinguished depending on different configurations:

• The "Software In the Loop" (SIL) phase is the first step for code functional validation. It describes auto-generated code implementation into Simulink®. The code generator provides capability to produce an "RTW S-Function" to use auto-generated code into a test harness on Simulink®. Thus, previous integration tests of the "MIL" test phase can be replayed here.

• The "Processor In the Loop" phase occurs after the "SIL" phase to insert representative processor in the previous test harness. This phase is required when CPU load of real-time auto-coded software needs to be monitored on the mission representative processor. The "PIL" phase is compliant to the European Coordination for Space Standardisation (ECSS) E-40 and Q-80 standards regarding requirements to test OBSW on the mission representative processor.

• Finally, the "Hardware In the Loop" (HIL) phase ends code functional validation in performing tests on benchmark with hardware representative equipments (i.e. hardware sensors, processor, and actuators for GNC module). The same test scenarios of the "MIL" phase can be adapted for the "PIL" and "HIL" phases considering that no exact outputs can be retrieved due to different test environments.

Figure 1 :

 1 Figure 1: Main (left) and Target (right) satellites.

Figure 2 :

 2 Figure 2: CNES GNC Module Development.

Figure 3 :

 3 Figure 3: CNES GNC Model Test Facility.

Figure 4 :

 4 Figure 4: Evolution of the Main satellite position on X axis in SLO frame. Comparison between Reference State from the Environment Models and Real State from the GNC library allows checking the expected functional behaviour and the performances.

Figure 5 :

 5 Figure 5: CNES GNC Hybrid Test Facility

Figure 6 :

 6 Figure 6: Hybrid Test Facility Software Architecture

Figure 7 :

 7 Figure 7: Worse CPU load obtained during Hybrid Tests to check real-time constraint (board oscillator is 25 MHz, Data & Instruction Caches deactivated)This easy-to-use benchmark allows an iterative process between Simulink® code production, performance measurement on the representative board, and then Simulink® code improvement if required.

Figure 8 :

 8 Figure 8: CPU Execution Time obtained for the first version of "Depack_TC" S/S

Figure 11 :

 11 Figure 11: Diagnostic levels repartition during RTW generated code reliability analysis

Figure 12 :

 12 Figure 12: Use of "Saturation" block in simulation model and corresponding auto-generated code

Figure 13 :

 13 Figure 13: Autocoded GNC model code coverage analysis

Figure 14 :

 14 Figure 14: Code coverage report produced by CCT

Figure 15 :

 15 Figure 15: Model coverage report Every functional cases need to be tested through dedicated scenario to obtain complete model functional coverage. The fine granularity of this tool allows easy validation of each model's component in relation of corresponding specifications.

4. 4

 4 Model-Based Software Development Life-cycle To conclude on this validation strategy, proposal on a possible Model-Based Software Development cycle can be made. This V life-cycle contains every validation phases describes here. Comparison between model-based and traditional software development plans is provided with explanations on what benefits can be get in term of time.

Figure 16 :

 16 Figure 16: Model-Based Development Cycle

CNES_GNC_lib Simulink Model Simulink (Unix or PC)

	CNES
	GNC
		T T generator generato generato TC
	Simulin Environmen t Model s state s comman d state s Simulin Environmen t Model s command Model s Models states Environment states	PRISM A syste m model s FFR F Senso r mode l C r PRISM A syste m model s FFR F Senso r mode l C r PRISM A PRISMA models system FFR F FFRF Sensor	FFRF commands FFRF messages delta V commands + even t PRISM A signal s FFRF delta V commands + even t PRISM A signal s commands + events deltaV PRISMA signals commands FFRF messages FFRF commands FFRF messages
	k k

PRISMA OBSW RF Sensor Driver FFRF Sensor LEON-3FT Processor (RTEMS) RTW -EC OBSW (C Code) Cross Compilation for LEON3-FT / RTEMS PRISMA OBSW Simulink Model TM/TC handler CNES_GNC_lib Simulink Model

Table 2 :

 2 table summarises influence of rounding direction and hardware design. †: Rounding direction refers to the IEEE Standard 754 Floating Point Numbers. influence of rounding direction and hardware design on maximum absolute difference value

	AS Hardware Design	Rounding direction † for AS	Rounding direction † for Hybrid	Max difference (absolute value)
	Intelx86	NEAREST	INF	3.25e-4 m

Table 3 :

 3 RTW generated Code Quality AnalysisBold metrics values point out some disadvantages of the code generator. Indeed, autocoded functions often contain very important amount of executable statements which increase code length and introduce poor vocabulary frequency. McCabe cyclomatic complexity number and total number of local variables declared per function are directly linked to these previous metrics.

Table 4 :

 4 RTW generated Code Reliability AnalysisTotal distribution of occurrences on the four diagnostic levels for the autocoded GNC library is depicted below.

Conclusion

Embedded Autocoded Software generation are growing up better and better in aerospace industry which leads to a new development and validation approach for OBSW. Thus, an important knowledge on validation of autocoded embedded software for critical application is required. Actions realised through the SMART1, PROBA, and soon PRISMA space missions give more confidence and experience on the Model-Based Design domain before applying it to future large scaled projects.

Acknowledgement

The authors would like to thank the whole PRISMA project team at CNES and CS-SI for produced results and positive cooperation on this paper.

RTEMS:

Real-Time Executive for Multiprocessor Systems.

RTW-EC:

Real-Time Workshop Embedded Coder.

SIL:

Software In the Loop.

SLO:

Satellite Local Orbit.

SNSB:

Swedish National Space Board.

S/S:

Subsystem.

TM/TC:

Telemetry / Telecommand.


E Bonnafous
email: eric.bonnafous@c-s.fr

E Saves
email: eric.saves@c-s.fr

E Gilbert
email: eric.gilbert@c-s.fr

J Honoré

Experience of an efficient and actual MDE process : design and verification of ATC onboard systems

Keywords: Model driven engineering, critical software, simulation

Since 2002, CS is involved in the conception and the specification of ATC systems for A320, A340, A380, A400M and A350 aircrafts. The ATC module, a ground/onboard communication system, is designed with SDL, a modelling language normalized by the ITU-T and which is described as a UML2-profile, too. The SDL well defined semantic allows to have homogeneous code generators and model simulators: these two technics are used in the process of the ATC projects, giving to the process a very efficient productivity. The automatic code generator generates the C code of the application. The code generator is qualified in accordance to the DO178B requirements (C level). This very strict qualification (development tool qualification) allows to highly reduce the tests effort of the ATC application. Verifications based on tests are realized on the SDL models, through execution simulation. CS uses RTDS, a SDL Z.100 simulator developed by Pragmadev. As well as providing edition and syntax/semantic checking of SDL models, RTDS provides debugging facilities such as breakpoints and step-by-step execution at the model level and a powerful scenarios language which enables to call some directives of the simulator such as MSC generation, internal signals sending, variables printing and so on… In order to improve the quality and effectiveness of the ATC model verification, CS has developed a set of applications that are plugged with the SDL simulator through TCP/IP, in order to interact with the system to be tested. These applications are onboard systems (FM, cockpit HMIs simulations: CDS or MCDU/DCDU) and ATC ground simulations: CPDLC, ADS, A623…). For the parts of the complete application manually coded in C code, the simulator is able to call such services using the XmlRpc protocol. With this complete set of high level and very representative simulation, the process is able to detect and reproduce quite all problems detected very late in traditional processes. In parallel to this actual process, some research actions are leaded in the ATC project area by CS and ENSIETA. To enhance the safety and the maturity of the ATC product, CS and ENSIETA study and develop a way to perform exhaustive verification of ATC models requirements. The technics used is model checking; studies are focused on a way to systematically reduce the combinatory explosion, and to improve the formalism of properties to be verified. The goal is to make this technic an industrial, cost-effective, and certifiable way of verification.

Introduction

The process described below is of interest because it has led to certification in accordance with DO-178B recommendations at criticality level C for applications used in commercial flight since the late 1990s. These air traffic control applications can be of the utmost importance as they form part of the CNS/ATM (Communication Navigation Surveillance/ Air Traffic Management). Initially used in low density areas such as oceanic areas, they are being developed more towards surveillance in higher density areas. Communication is one of the enlarging domain in the aeronautical context : it follows growing circulation in the air space. ATC (for Air Traffic Control) data-link applications are dealing with communications between an Air Traffic Control Center and an aircraft. It allows manual (involving the pilot) and automatic information exchanges such as alerts, position, speed, weather, etc. ; it is used for certain route and departure clearances too. These applications can operate in ACARS (Aircraft Communication Addressing and Reporting System) or in ATN (Aeronautical Telecommunication Network) networks.

These data were obviously an influence on the main choices that define the process of development. The choice of formalism SDL (Specification and Design Language) is one of them. Indeed, the power of formalism is to specify and design applications unambiguous and driving through automatic code generation to a program true to its specifications. This aspect is crucial to any critical software development where the concept of traceability is central.

Process overview

Development cycle overview

Methodology overview

The methodology is a classical « V Cycle » methodology. At the earliest system development phases, requirements are classified. Two main sources are identified : requirements for platform definition and requirements dedicated to ATC applications. The platform is hardware dependant and support applications running and datas exchanges between those applications. Platform software and various components linked to models of the ATC applications are developed following a standard DO-178B process and conforms to level C recommendations. The ATC applications:

-AFN (ATC Facilities Notification): sort of logon for ATC applications, -CPDLC (Controller Pilot Data Link Communications) : automation than assists with workload management for the flight crew and the controller, -L'ADS Automatic Dependent Surveillance : position and speed report to the ground -L'ARINC 623 : Essentially weather information application, are designed using SDL formalism. SDL models obtained are identified as detailed specifications of those applications. The activity of traceability between the system and the models leads to the identification of derivated requirements. Those requirements are clearly marked out and are specifically verified. Those verifications bring credit for system certification in addition to system requirements verifications realized on target. The evidence of verification of these requirements are provided by the results of SDL model simulations.

Development of ATC applications

MDA -SDL approach

Airbus ATC applications are based on a model driven approach, MDA. The architecture and detailed specifications are defined using the ITU-T' s SDL formalism. This language is perfectly suitable as it can be used to model asynchronous objects that communicate by exchanging signals. Three types of diagrams are used in SDL:

• architecture diagrams representing the breakdown of the application into blocks and processes along with the signals exchanged between those entities; • state-transition diagrams representing each process' s internal behavior; • MSC diagrams generated by the SDL simulator SDL, allowing all messages exchanged between the various processes to be verified. The RTDS software from Pragmadev is used for the edition and simulation of SDL models.

Using this high-level formalism avoids problems related to hardware services, process scheduling and memory allocation, etc., facilitating faster development and a very high degree of responsiveness.

Automatic and qualified generation of code

The Automatic and qualified generation of code allows substantial cost savings in addition to an enhanced traceability. Indeed, the verification of automaticaly generated code is greatly reduced.

There is no need of reviews of code and additional verifications of the Low Level Requirements. The specific qualified code generator has been specifically design so that hazardous mechanisms should be avoid. Special verification tools prevents from these mechanisms and brings some additional evidences useful for certification credit such as semantic controls according to special SDL design standard.

The SDL generator tool is DO-178B level C qualified.

Verification

As the semantics of SDL (abstract data types, action language) are unambiguous, ATC applications can be checked by simulation. These verifications are performed on PC well before tests are conducted on the actual computer using real equipment. This is much less expensive and allows the functional part of the application to be verified very early in the development cycle.

History of the process improvement

Starting point

In 2002, CS started producing A380 ATC systems on the basis of work already carried out on site in the AIRBUS design office. Regarding the reply to the call for tender, one of AIRBUS' s main requirements for potential suppliers was to improve the process. This mainly concerned test phases and activity traceability.

Improving the verification process

In general, the first phase for CS consisted in integrating the specific field and assessing the existing processes. The firm' s experience in flat-fee management services was one of its most important assets in order to successfully optimize this process.

The two main improvements were made in traceability and test methodologies.

As regards traceability, CS implemented a software solution based on Reqtify, increasing the level of detail of traceability. As a result, the certification audit demonstrated a satisfactory level.

An overall strategy was adopted for the tests, as shown in the following diagram.

Certification process

CRI-F22 tests are among the tests required for the certification of ATC applications and servers. Some of these tests are performed on the CS simulation workshop in single-application mode (application/server isolated from other applications/servers) and cover: -all the requirements specified in DFD (Derived Functions Document), -functional requirements of specifications that AIRBUS laboratory test facilities cannot cover.

The representativeness of the simulation facilities is thus one of the key criteria for this A380 ATC certification phase. For this purpose, CS integrated a representativeness improvement process into its simulation workshop. Each fault detected on an AIRBUS aircraft or simulation bench is played back on the CS simulation bench. The test results are compared and, in case of any discrepancy, the modifications required to increase the workshop' s representativeness are implemented.

By this iteration process to improve the representativeness of the simulation of ATC detailed specifications, such a high level of maturity has now been achieved that behavior is the same on the CS simulation bench as on aircraft or the AIRBUS bench for virtually 100% of faults detected. This environment now enables CS to achieve excellent quality in the integration of modifications and fault corrections.

The current use of a simulation workshop for both the CRI certification of derived functions and those requirements that cannot be tested on AIRBUS benches is paving the way to the wider use of virtualization tools for certification.

In keeping with its aim of improving the quality of ATC systems, CS has anticipated the traceability requirements for certification. This has enabled CS to provide for a traceability granularity that goes well beyond the initial prerequisite. This anticipation was crucial for certification, since this new granularity has proved to be necessary.

Lastly, a study of formal proofs on the basis of detailed technical specifications is being carried out at CS in order to provide for the future of certification tests, and this study is expected to lead to positive results.

Conclusion and further work

In conclusion, the process of developing ATC applications by means of SDL formalism has proved itself in terms of reliability since this new system' s introduction on the SA and LR AIRBUS. This history along with rigorous formalism and the process' s constant improvement has instilled confidence in the certification authorities, end users and airlines. This example of the successful utilization of models in the context of highly asynchronous, critical applications provides a wealth of information. It contributes support for the MDE approach and holds out promising prospects for the utilization of simulation results as proof supporting the certification of critical aeronautical systems.

As modern avionics incorporate a growing number of increasingly complex systems and as the current trend is to meet increasingly strict reliability requirements, the manufacturing process will have to continue to evolve towards greater exhaustiveness and formalization. With this in mind, CS has since 2004 taken the initiative of conducting studies on the applicability of formal proof to ATC models, as part of its R&D. Between 2007 and 2010, this work will involve the writing of a thesis aimed at incorporating exhaustive verification by means of proof techniques using ModelChecking into the current process. CS has great hopes that this approach will equip it to tackle the challenges to come.

  Figure 1: SDL architecture diagram

  This simulation is made possible by the use of equipment simulating the external behavior of ATC applications: HMIs in the aircraft cockpit (CDS, DCDU, MCDU), CPDLC stations for the transmission and reception of messages between ground and aircraft, etc.. This equipment is able to communicate with the SDL simulator. The model is simulated by sending signals and reacting to signals output from the simulator (HMI updates, sending of automatic replies, etc.). The simulator can also call configurable external operators that simulate hardware services, enabling the carrying out of certain degraded mode tests that are difficult to implement on the end product. In addition, by close co-operation with Pragmadev, the supplier of the SDL RTDS simulator, developments have been integrated in the package in order to come closer to the actual behavior observed on the target computer. For example, the simulator now includes an option allowing internal signals to be consumed before external signals (i.e. signals from the environment). Using this complete simulation workstation (customized simulator, HMIs, external stations and operators), extremely good representativeness can be achieved in the simulations performed.

  In terms of architecture, ATC systems are made up of six high-level blocks, each of which represents a specific function. Four of these are ATC-specific functions and two are servers.The tests fall into the following categories:-Single-application tests: The function is tested independently. The boundaries are blocked off around the function's perimeter. -When the applications have been validated, integration tests are implemented with the aim of validating pairs of communicating functions in client-server mode. -Then, "multi-application" tests covering all functions are performed. CS then also defined a methodology for the performance and passing of certification tests. CS automated these tests, reducing the number of certification test cycles. The process was then further improved, the singleapplication tests being close to certification tests. The process is still developing. The formalization of single-application and certification tests has been enhanced. Like debugging tests, simulation tests are no longer formalized. Multi-application tests have been completed from the functional point of view and provide the end customer with a basis for customer acceptance tests.


C Ferdinand

R Heckmann

M Jersak

F Martin

K Richter

Integrating System-Level and Code-Level Timing Analysis for Dependable System Development

Keywords: Schedulability analysis, timing analysis, worst-case execution time, worst-case response time

Developers of safety-critical real-time systems have to ensure that their systems react within given time bounds. Sophisticated tools for timing analysis at the code-level, controller-level and networked system-level are becoming state-ofthe-art for efficient timing verification in light of ever increasing system complexity. This trend is exemplified by two tools: AbsInt's timing analyzer aiT, which can determine safe upper bounds for the execution times (WCETs) of non-interrupted tasks, and Symtavision's SymTA/S tool, which computes the worst-case response times (WCRTs) of an entire system from the task WCETs and information about possible interrupts and their priorities. The two tools thus complement each other in an ideal way. They have recently been coupled to further increase their utility. Starting from a system model, a designer can now seamlessly perform timing budgeting, performance optimization and timing verification, considering both the code of individual functions, as well as function and sub-system integration. The paper explains and exemplifies various use cases and tool flows.

Introduction

Developers of safety-critical real-time systems have to ensure that their systems react within given time bounds. Tests and measurements cannot guarantee that this holds in every possible situation, but tools for static program analysis can obtain results valid for all possible system runs and inputs, even before the first real prototypes are available. Examples for such tools are AbsInt's timing analyzer aiT, which can determine safe upper bounds for the execution times (WCETs) of non-interrupted tasks, and Symtavision's SymTA/S tool, which computes the worst-case response times (WCRTs) of an entire system from the task WCETs and information about possible interrupts and their priorities. The focus of aiT on single tasks and the focus of SymTA/S on the interplay of several tasks com-plement each other in an ideal way. Coupling these tools therefore highly increases their utility. The system developer creates a system model in SymTA/S, consisting of a task graph, information on task scheduling (priorities, time slots, etc.), and information on task activation (time tables, interrupts, etc.). To determine the WCRTs of the tasks with possible interrupts, the WCETs of the noninterrupted tasks are required. To obtain these WCETs, SymTA/S sends requests to aiT. Then aiT asks the developer for necessary information on hardware configuration and executables, determines the requested WCETs, and sends them back to SymTA/S. To increase the user comfort, the communication is based on cookies in which the configuration information is stored so that this information need not be input again when further WCET calculations are performed. These cookies are organized hierarchically: general information valid for the entire system, information about all parts of the system running on a specific CPU, information for runnables (i.e., atomic pieces of software), and modes (specific control-flow paths through a runnable). The coupling of SymTA/S with aiT allows SymTA/S to determine end-to-end timings in an early development phase, with automatic identification of problematic system configurations and automatic system optimization as a next step. In the EU project INTEREST (Integrating European Embedded Systems Tools) the tool coupling is extended towards modelling tools such as ASCET and SCADE to support the entire development process from the model till the implementation with formally verified timing behavior. In the following, we present the tools, the experimental integration, preliminary results and plans for further tool integration.

The WCET Analyzer aiT

aiT is AbsInt's timing analyzer, which can find upper bounds for the worst-case execution times (WCETs) of sequential tasks. For a precise computation of the WCET, aiT operates on the executable. The graphical user interface of aiT (see Figure 1) Figure 1: Graphical user interface of aiT offers ways to specify the memory architecture of the target, the location of source files, the name of the executable, the name of a separate parameter file called .ais file, the name of the report files to be written, etc., and the start point of the analysis (a routine name or an address). All this information can be stored in a project file (.apf file). The .ais file may contain the clock rate of the target processor, upper bounds for the iteration numbers of loops, possible targets of computed calls, etc. The analyses of aiT are mainly based on the executable. If available, aiT can also read the source files for further information. The association between addresses in the executable and positions in the source files is obtained from the debug information in the executable.

aiT can be started in three ways:

1. When started for interactive usage, the GUI depicted in Figure 1 is opened. The fields in the GUI can be filled with appropriate values, which may be stored in a project file (.apf file). Alternatively, an existing project file can be loaded.

2. aiT can also be started in simple batch mode with a project file. In this case, the project file is loaded and then aiT behaves as if the "WCET analysis" button had been clicked.

3. aiT can be started in batch mode with a control file. A control file contains the name of a project file and specifies various analysis tasks, which are performed automatically in this case.

Control files can also be used interactively if the GUI is switched from Manual to Automatic mode (see Figure 1). aiT determines the WCET of a given task in several phases [START_REF] Ferdinand | Reliable and precise WCET determination for a real-life processor[END_REF] (see Figure 2). In the first step a decoder reads the executable and reconstructs the control flow [START_REF] Theiling | Extracting Safe and Precise Control Flow from Binaries[END_REF]. Then, value analysis determines lower and upper bounds for the values in the processor registers for every program point and execution context, which lead to bounds for the addresses of memory accesses (important for cache analysis and if memory areas with different access times exist). Value analysis can also determine that certain conditions always evaluate to true or always evaluate to false. As consequence, certain paths controlled by such conditions are never executed. Thus value analysis can detect and mark some unreachable code.

WCET analysis requires that upper bounds for the iteration numbers of all loops be known. aiT tries to determine the number of loop iterations by loop bound analysis [START_REF] Ferdinand | New developments in WCET analysis[END_REF], but succeeds in doing so for simple loops only. Bounds for the remaining loops must be provided as specifications in the AIS file or annotations in the C source.

If the target processor has caches, an optional cache analysis follows, which classifies the accesses to main memory into hits, misses, or accesses of unknown nature. Pipeline analysis models the pipeline behavior to determine execution times for sequential flows (basic blocks) of instructions as done in [START_REF] Schneider | Pipeline Behavior Prediction for Superscalar Processors by Abstract Interpretation[END_REF]. It takes into account the current pipeline state(s), in particular resource occupancies, contents of prefetch queues, grouping of instructions, and classification of memory references by cache analysis. The result is an execution time for each basic block in each distinguished execution context. Using this information, path analysis determines a safe estimate of the WCET. The program's control flow is modeled by an integer linear program [START_REF] Yau-Tsun | Performance Analysis of Embedded Software Using Implicit Path Enumeration[END_REF][START_REF] Theiling | Combining abstract interpretation and ILP for microarchitecture modelling and program path analysis[END_REF] so that the solution to the objective function is the predicted worst-case execution time for the input program. After a successful analysis, aiT reports its results in several ways: 1. aiT can produce a graphical output showing the call graph of the analyzed part of the application, showing the routines and their calling relationships (see Figure 3). The routine boxes can be opened to show their control-flow graphs with WCET results for basic blocks. Technically, aiT writes a description of these graphs in a GDL file, which can be visualized by AbsInt's graph browser aiSee. 2. aiT can write a text report meant to be human readable, and a more formal XML report. These reports contain detailed results for all analyzed routines in all calling contexts, including specific results for the first few iterations of loops vs. a result for the remaining iterations.

Scheduling Analysis with SymTA/S

SymTA/S [START_REF] Henia | System level performance analysis -the SymTA/S approach[END_REF] is Symtavision's tool for timing and scheduling analysis and optimization for controllers, networks and entire systems. SymTA/S computes

• worst-case response times (WCRTs) of tasks

• worst-case end-to-end communication delays taking into account all relevant WCETs and information about RTOS scheduling, bus arbitration, possible interrupts and their priorities. Scheduling analysis is a systematic approach that automatically finds and evaluates critical timing situations resulting from function and system integration. Such corner case identification is the opposite of traditional test-based methods: instead of massive testing to try to find all corner cases, scheduling analysis systematically constructs scenarios leading to worst-case timing. SymTA/S combines decades of research (started with Liu's and Layland's 1973 paper on Rate-Monotonic scheduling [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF]) into an industrystrength tool. SymTA/S provides detailed analysis results that are comprehensively visualized and thus easy to understand. The graphical user interface of SymTA/S (see Figure 4) offers ways to specify a system architecture, select scheduling on controllers and arbitration on buses, map functions to controllers and communication to busses, and to describe dataflow, activation conditions, deadlines and other timing constraints. The analysis results are displayed in a variety of ways. The most powerful and easy to understand are Gantt-Charts that visualize to the designer why and under which conditions deadlines can be violated (see Figure 5). There are two main use cases for SymTA/S: 1. timing design / budgeting during early design stages and 2. timing verification during later design stages. The added value for verification is exemplified in Figure 6: the upper part of the diagram displays a typical timing trace, showing a response time of Figure 5: Graphical display of worst-case timing along a datapath (end-to-end Gantt chart) Figure 6: Safeguarding timing using scheduling analysis (as compared to measurement) 6.9 ms for a task executed every 10 ms -well below the 10 ms deadline. In the lower part, SymTA/S scheduling analysis has constructed a worst-case schedule leading to a WCRT of 9 ms for the 10 ms task -still below the deadline, but much closer. The key message is that no other schedule will produce a longer WCRT. SymTA/S thus safeguards against deadline violations resulting from worstcase schedules. Furthermore, the Gantt-display enables the designer to check the reasoning of SymTA/S and thus to see if some important information has been omitted in the model.

At the same time, SymTA/S allows to perform what-if scheduling analysis during system design. It is easily possible to estimate how additional functions and their scheduling will influence over-all system timing, and whether deadlines can be safely met for a specific design alternative. As a result, timing budgets for individual functions of sub-systems can be derived early on, and given to a designer as part of a requirements specification.

SymTA/S supports timing design through productivity plugins, which can be integrated with the scheduling analysis engine.

1. Design-space exploration allows designers to automatically evaluate the strengths and weaknesses of alternative designs with respect to timing and performance.

2. Sensitivity analysis allows users to automatically determine the amount of extra load (e.g., caused by additional functions) permissible without violating deadlines.

XML Timing Cookies (XTC)

Timing analysis is a novel domain, and the requirements for coupling code-level and system-level tools were not suitably covered by any existing exchange format. Therefore, the concept of "Timing Cookies" has been developed in the INTEREST project, and an "XML Timing Cookies" exchange format (XTC) has been defined.

The main idea behind "Timing Cookies" stems from two observations:

1. The envisioned flow between SymTA/S and aiT is essentially cyclic, suggesting a requestresponse mechanism.

2. Each tool requires a (potentially large) set of data about the system under design, but the intersection of these two sets is small. "Timing Cookies" have been introduced to avoid the duplication of the sophisticated user-interfaces available in each tool. The concept of "Timing Cookies" allows to keep entering the required information in the appropriate place, and to store the information for the next round of communication between the tools. This is similar to repeatedly visiting a web site that requires certain user information. Such information is typically stored in a cookie and retrieved when the user visits the site again, hence the name "Timing Cookie".

An XML Timing Cookie consists of two main parts:

1. One common section that describes the analysis request when the cookie is sent from SymTA/S to aiT, and additionally holds the response to that request when the cookie is returned from aiT to SymTA/S.

2.

A cookie section per communicating tool to hold each tool's local information required for servicing a request and for putting the response in its appropriate context.

This partitioning has the following advantages:

• Key information is stored in one place, the common section.

• Tool-specific information is stored in a private cookie section. It is only modified by the respective tool; other tools leave this information untouched. XTC is defined as an XML schema. It is organized hierarchically since some information can be reused for different analyses. For instance, a CPU configuration can be reused for different runnables sharing the same CPU. The information in the common section is structured in four blocks: 1. general 2. CPU 3. runnable (i.e., an atomic piece of software 1 ) 4. mode (a specific control-flow path through the runnable). Structuring of the cookie section has to follow the top-level structuring of the common section. XML name spaces are used to avoid ambiguities during parsing. The schema definitions are available upon request. SymTA/S and aiT communicate by exchanging XML Timing Cookies (XTC, see section 4). From a system model, SymTA/S launches a request for WCET information for specific pieces of code (see Figure 7). This request is tagged with a unique ID and sent to aiT in an XTC. If necessary, aiT queries the user for all missing information required to service the request. For the first request issued for a system model, this typically includes the type of processor, the location of the executable code, the starting point of the analysis etc. When aiT answers the request by sending an XTC with a response back to SymTA/S, it stores this information in the private aiT-part of the cookie. This aiT-1 AUTOSAR [START_REF]The AUTOSAR Development Partnership. Automotive Open System Architecture (AUTOSAR)[END_REF] terminology has been adopted specific information will be included in subsequent requests so that aiT can use the information already gathered without the need to ask the user again.

The Interaction between SymTA/S and aiT

Application Example

The example in this section has been adapted from an aeroplane controller. It illustrates the application of the described methodology and tools using a real-world example. Figure 8: System example illustrating WCET analysis and WCRT analysis

The system is initially modelled in SymTA/S (see Figure 8). It consists of 3 main tasks2 T0, T1, and T2, one background task, and several interrupt service routines (ISRs), most notably three ISRs performing deadline monitoring. A deadline overrun indicates a serious problem and must not occur under normal conditions. Therefore, WCET analysis and WCRT analysis are used during system design to validate the timeliness under all relevant conditions.

The three main tasks are triggered periodically with different periods and offsets. Such activation can be modelled using a time-table. We shall assume the following values: Task T1 executes one major function T1 F1 . The designer would like to add a second function T1 F2 . However, this is only possible if T1 does not violate its deadline even if both T1 F1 and T1 F2 are executed. The other tasks must also not violate their deadlines.

In the first step, WCETs are obtained for T0, T2, T1 F1 and T1 F2 . For this purpose, aiT is polled using an XTC request file. A simple example looks as follows:

<requestResponseCommunication> <common> <CPU unit="MHz" speed="10.0" name="Controller" id="ID_0"> <runnable name="T0" id="ID_1"> <mode id="ID_2"> <description>T0</description> <request type="WCET-Analysis"/> </mode> </runnable> </CPU> </common> </requestResponseCommunication> Since there are different instances of aiT for different target architectures, the cookie is not sent directly to aiT, but to an aiT driver program that asks for the target architecture unless this information is already contained in the cookie, and then calls the appropriate aiT instance. The aiT driver also translates the information in the cookie into the formats readable by aiT (project file, AIS parameter file, and control file).

If sufficient information for WCET analysis is already available, aiT can be run in batch mode. If not, it can be used interactively for entering the missing information, e.g., cache and memory configuration of the target processor, the path name of the executable, targets of computed calls and branches (unless found by static program analysis), loop bounds and recursion bounds (unless found by static program analysis), and declaration of volatile memory areas.

The information collected in this way is stored by aiT in its proprietary formats (project file, AIS parameter file, and control file) and returned to the aiT driver together with the results of the WCET analysis. The driver puts all this information into an XTC response file that is returned to SymTA/S. The WCETs are contained in the common part of the cookie for use by SymTA/S. The aiT-specific information is stored in the aiT-specific part of the cookie. This part can be copied by SymTA/S into the next XTC request file so that the information provided during the previous interactive aiT session need not be entered by the user again.

A simple example for the common part of an XTC response file looks as follows: <requestResponseCommunication> <common> <CPU unit="MHz" speed="10.0" name="Controller" id="ID_0"> <runnable name="T0" id="ID_1"> <mode id="ID_2"> <description>T0</description> <request type="WCET-Analysis"/> <response type="WCET-Analysis"> <WCET unit="us" value="180.0"/> </response> </mode> </runnable> </CPU> </common> </requestResponseCommunication> Let us assume that aiT returned the following values:

task WCET T0 180 us T1 F1 1100 us T1 F2 100 us T2 300 us Scheduling analysis can now be performed. Considering also the execution time of ISRs (not further discussed here but obtained using the same process), the resulting worst-case schedule and WCRT for T1 as obtained by SymTA/S is displayed in Figure 9. As can be seen in Figure 9, the first execution of T1 where only T1 F1 is executed meets its deadline (left tall vertical bar). However, when also executing T1 F2 (second execution of T1), the deadline (right vertical bar) is missed. The designer can now perform targeted timing optimization to resolve this problem. There are several options: 1. optimize the code of T1 F2 to reduce its WCET such that the deadline will be met; 2. optimize the assignment of offsets; 3. delay the deadline (if this is possible); 4. optimize the code of some other function to reduce its WCET; 5. some combination of these remedies. Of the remedies, the first three are probably the most cost efficient, since they do not re-quire re-certification of already certified functions. SymTA/S sensitivity analysis can be used to calculate by which amount each parameter would have to be changed.

Let us assume that code improvement of T1 F2 reduces its WCET to 50 us (verified by aiT). Sensitivity analysis tells us that this is not good enough, but there is an opportunity to start T1 earlier by up to 5 us. Combined, these two remedies mean that the deadline can be safely satisfied, with T0 maintaining a reserve of 15 us, and T1 maintaining a reserve of 5 us until its deadline (see Figure 10). 1. Extending the XTC mechanism to also calculate stack usage. For many target architectures, the aiT tool can already determine the maximum stack usage of a task.

2. Integrating aiT and SymTA/S in larger tool flows.

For the latter, integration with ESTEREL's SCADE tool is well under way [START_REF] Ferdinand | Combining a highlevel design tool for safety-critical systems with a tool for WCET analysis on executables[END_REF]. A second integration is being developed with ETAS's ASCET and INTE-CRIO. The goal is to provide seamless integration of timing analysis on all levels with established flows -from modelling/simulation to code-generation and code-optimization.

Conclusion

The code-level timing analysis tool aiT and the system-level timing analysis tool SymTA/S have been coupled to provide software and system designers with an efficient way to verify timing properties of ECU software.

The tool coupling allows you to

• determine upper bounds for the execution times (WCETs) of tasks using AbsInt's aiT;

• compute worst-case response times (WCRTs) of functions and tasks considering integration and scheduling using Symtavision's SymTA/S;

• trigger AbsInt's timing analyses at the code level from the SymTA/S GUI;

• import safe analysis results from aiT into SymTA/S in a fully automatic way.

XML Timing Cookies (XTC) provide for a userfriendly, open, and efficient tool integration. SymTA/S communicates with aiT via XTC, sending analysis requests and receiving responses.

Figure 2 :

 2 Figure 2: Phases of WCET computation

Figure 3 :

 3 Figure 3: Call graph with WCET result

Figure 4 :

 4 Figure 4: Graphical user interface of SymTA/S (application view)

Figure 7 :

 7 Figure 7: Flow of requests and responses

  measured from the time of activation of the corresponding task.

Figure 9 :

 9 Figure 9: Bad schedule of example system missing the deadline for task T1 if both T1 F1 and T1 F2 are executed (2nd execution of T1)

Figure 10 :

 10 Figure 10: Fixed schedule of example system leading to all deadlines satisfied, even if both T1 F1 and T1 F2 are executed

  Collaboration between AbsInt GmbH and Symtavision GmbH has been supported by the FP6 STREP project INTEREST (INTEgrating euRopean Embedded Systems Tools).

Note that tasks are sometimes referred to as processes.


P Feiler

J Hansson

Impact of Runtime Architectures on Control System Stability

Keywords: Embedded system, control system stability, end-to-end latency, latency jitter

Control systems are sensitive to the endto-end latency and age of signal data. Control engineers develop their control system model under certain latency and age assumptions and deviation from these assumptions can lead to controller instability. In this paper we discuss how choices in the runtime architecture of the embedded software system can affect latency and introduce unexpected latency jitter. We propose the use of AADL as a basis for a flexible framework that support co-design of control systems by control engineers and by embedded software engineers through quantitative analysis.

Introduction

Control systems are highly time sensitive. They are developed by control engineers through a process of model validation. The physical plant and the desired control algorithm are represented by continuous time models to capture the physics of the system. They are then mapped into discrete time models to take into account digital processing by software. Finally, they control components are translated into source code. These models may exist in different levels of fidelity, and they are validated through simulation and model checking and source code execution in a simulated environment and with hardware in the loop. During this development process the control algorithms are calibrated to the physical system characteristics. Reflected in the calibration are assumptions regarding the end-to-end latency of the signal stream from the sensor and to the actuator, as well as the latency jitter and the age of signal data. One of these assumptions is that the runtime system exhibits deterministic execution and communication behavior. Control system applications are components of an embedded software system. These components interact in the context of specific runtime architectures utilizing a variety of communication and scheduling mechanisms and policies. Similarly, the resulting runtime architecture deployed and distributed on different hardware platforms. These choices are often made by software engineers with limited awareness of their impact on latency, latency jitter, and age of signal streams are affected. Without managing the impact by ensuring the latency assumptions made by control engineers in the runtime architecture the stability of the controllers is impacted without recalibration. This separation of concerns between control and computation has traditionally been addressed by first developing the control algorithm, and then configuring the resulting software components into an embedded application.

This approach was feasible while control systems were physically separate components with their dedicated processors. As embedded systems increasingly use a common compute hardware platform that is shared among software implementations of control components, and embedded systems increasingly require control components to interact to provide desired functionality, the work of embedded software engineers must go hand in hand with that of control engineers. In this co-design approach embedded software engineers must be able to quantify latency and latency jitter contributions by choices in the runtime system implementation and ensure latency assumptions of control algorithms where critical. Similarly, control engineers must be able to quantify the robustness of their control algorithms with respect to variation in latency in order to allow for more flexibility in the runtime architecture and better utilization of the compute hardware [START_REF] Cervin | Control Loop Timing Analysis Using TrueTime and Jitterbug[END_REF]. In this paper we utilize the international industry standard notation SAE AADL [START_REF]Architecture Analysis & Design Language (AADL)[END_REF] to gain a better understanding of the impact of runtime architecture choices on controller stability. AADL has been designed to characterize embedded software applications, and deployment of compute hardware, and their interface with the physical environment. Its rich semantics with respect to task execution and communication between components allows us to model the signal flow processing architecture as a flow-based architecture. We will use AADL to model the execution and communication timing characteristics assumed by control engineers are they develop their control design. We will also use the AADL to characterize various aspects of the runtime architecture of a control system implementation and identify contributors to end-toend latency and to latency jitter. This analysis will highlight the importance of determinism to manage latency jitter to maintain the stability of controllers under jitter assumptions established by control engineers.

In this paper we will first characterize the latency and latency jitter assumptions made by control engineers as they develop their design independent of software implementation considerations. Then we will examine contributors to latency and latency jitter in the runtime architecture and identify a systematic way of determining such impact. Finally, we identify the need for a flexible analytic framework for determining end-to-end latency and latency jitter that embedded software engineers and control engineers to make informed design choices through modelbased analysis early and throughout the development process in a co-design design setting.

A Control Engineering Perspective

Control system components process a signal data stream from sensors and affect the external environment, e.g., a physical plant, through actuators. Processing of such a signal stream is time sensitive. The degree of time sensitivity depends on the lag of the physical systems and the responsiveness of the control algorithm. The control systems are initially expressed as continuous time models in differential equations in order to capture the physical characteristics and behaviors of the physical systems. These models are then mapped into discrete time models to reflect sampled control in a computer-based control system implementation [START_REF] Åström | Computer Controlled Systems -Theory and Design[END_REF]. Simulink is an example of a commercial modeling environment for control engineers that supports both continuous time and discrete time modeling. Such modeling environments assume a computational model whose execution behavior is implemented in their simulation engine. In the next sections we will examine this assumed model of computation and communication, model its essence in AADL, and discuss its sensitivity to latency variation and jitter.

A Model of Computation and Communication

The computational model consists of computational components that execute periodically with an inputcompute-output (ICO) behavior. This model provides data consistency during computation in that the input to the computation is determined in the input phase and is not affected by newly arriving output during the time of computation. Similarly, output is made available to successors during the output phase upon completion of computation. Data consistency of communication is established through a port-based communication model with atomic send/receive (write/read) operations. Such port automata represent an algebra of concurrent processes [START_REF] Steenstrup | Port Automata and the Algebra of Concurrent Processes[END_REF]. In a modeling environment such as Simulink this computational model is represented by blocks representing components, pins representing ports, and connections representing communication of data through variables from the output of one component to the input of another component. Components execute at a specified rate. Different components may execute at different rates, resulting in over-and under-sampling of the predecessor output. The simulation executes the components sequentially in discrete time frames at the specified rates. Within a frame the execution order of the components is fixed and can be specified by the modeler. The execution order of the components determines the send/receive order of the input and output operations, i.e., determines whether the data is received by the receiver within the same frame or at the next frame. If the recipient executes after the sender the communication is mid-frame, and if the recipient executes before the sender the communication is phase-delayed. When communicating components execute at different rates, rate transformation blocks, representing zero-order hold and unit-delay, effectively perform double buffering of the result in order to assure data consistency of computation while performing mid-frame and phase-delayed communication.

Since the execution order is always the same, data is always communicated deterministically mid-frame or phase-delayed between components. The end-toend latency of a data stream determined by the initial sampling of the sensor readings, the processing time of sequences of components with mid-frame communication. This cumulative processing latency is then sampled by phase-delayed communication with the cumulative processing latency rounded up to the next frame. This provides an effective way of managing execution time jitter, i.e., variation in actual execution time of individual components. For example, the control system may apply a filter to the sensor data before computing the output to the actuator. These two tasks are shown as T11 and T12 in Figure 1. By passing the output phasedelayed to task T2, T2 will feed data to the actuator at the beginning of the next frame independent of any variation in execution time to perform the filtering or control computation. Often the task providing data to the actuator executes at a multiple rate of the control algorithm and deterministically oversamples the controller output. Latency can have data ports, i.e., unqueued ports that communicate state data, as well as ports for communicating events and messages. Data ports make the most recently recent data value available to a thread at thread dispatch time. During the execution of the thread this data value is not affected by any newly received data. The output of data ports is made available to other threads at execution completion. In other words, the AADL thread model supports the ICO behavior desirable for control systems. For periodic threads with data ports users can specify immediate and delayed port connections. The timing semantics correspond to mid-frame and phase-delayed communication. In the case of an immediate connection the execution of the recipient thread is suspended until the sending thread completes its execution and makes its output available to the recipient. In the case of a delayed connection the output of the sending thread is not transferred until the sending thread's deadline, typically the end of the period. In other words, its output is not available to the recipient until the next frame. These communication timing semantic assure deterministic over-and under-sampling when a data stream is processed. The timing characteristics of immediate and delayed connections are shown in Figure 2.

Figure 2 Immediate and Delayed Connections

This allows us to describe the expected execution and communication timing behavior of a control system simply as a sensor device that samples the physical environment at a given period. Its output is fed to a filter thread via immediate connection. This filter thread and the control computation thread, which is connected via immediate connection, execute at twice the period of the sensor device. The output of the control computation is fed to an actuator device via delayed connection. The actuator device is specified to execute at half the period of the control computation. AADL also allows us to specify an end-to-end flow. This is done by first specifying a flow source for the sensor, flow paths for the filter and control thread, and a flow sink for the actuator. These flow specifications provide an external specification of information flow path through an AADL component from an incoming port to an outgoing port (in case of a flow source starting from within a component, and a flow sink ending within a component). If a component consists of subcomponents, this flow is elaborated within the component implementation as a flow through these subcomponents. An end-to-end flow is specified by starting with the flow source of a component, in our case the sensor device, to follow the connection to the filter thread, following its flow path and the connection to the control thread, the control thread flow path and the connection to the actuator device flow sink. The end-to-end flow and the flow specifications can have AADL properties, in our case the specification of the desired end-to-end flow latency attached to the end-to-end flow specification. The latency within a sensor or actuator can be attached to its flow source or flow sink specification. The latency contributed by a thread can be determined from its period, deadline, and worst-case execution time and the type of data port connection [START_REF] Feiler | Flow Latency Analysis with the Architecture Analysis and Design Language (AADL)[END_REF]. AADL also supports specification of sampling port connections as well as data driven processing with arrival of data triggering the execution of threads. In addition, AADL supports modeling of shared access to data components by threads with write and read access determining the information flow.

2.3

Non-determinism in Computation and Communication Control algorithms are sensitive to latency and sampling jitter as well as variation in age of the data. The end-to-end latency and the age of data in a signal stream may differ. End-to-end latency is the amount of time it takes for a new data value from a sensor to get processed and output at the actuator. If data elements are missing or the data stream is oversampled, the same data element may be processed multiple times. In that case, the age of the data value being processed may be larger than the end-to-end latency. Cervin et.al. [START_REF] Cervin | Control Loop Timing Analysis Using TrueTime and Jitterbug[END_REF] illustrate how sampling jitter and latency jitter affect the stability of controllers. They also show that jitter varies according to the scheduling algorithm used for executing a task set. The standard task model with a single assigned priority and input and output performed as part of this task performs worse than a task model in which input and output is managed separately at higher priority, thus, making task interaction more deterministic. Sampling and latency jitter as well as variation in data age is perceived by the control algorithm as increased noise in the data causing the control algorithm to become less stable.

In the next section we examine how latency and age of data streams are affected by choices made by software engineers as they integrate control components into a set of communicating software tasks that share processors, execute concurrently on different processors, and communicate over highspeed or slow communication channels. Those choices may introduce unintended non-determinism, thus, increase latency jitter [START_REF] Caspi | On the Implementation of Control Loops by Software[END_REF].

Embedded Software Engineering Perspective

When implementing an embedded software system software engineers make a number of decisions regarding the runtime system of the application. Algorithms may vary in execution time, tasks may be scheduled on a static time line or may execute preemptively to improve processor utilization. Tasks may communicate through shared data variables or use a send/receive communication paradigm. Multiple tasks executing at the same rate may be executed in the same operating system thread in order to reduce the number of context switches. The embedded system may be ported to a partitioned architecture in order to improve configurability and deployment options of the embedded system. Different communication protocols can be used for communication across processors. Different processor in a distributed system operate asynchronously on different clocks. All of these considerations can have an impact on the end-toend latency and its jitter. In the next sections we discuss the impact of these latency contributors.

Execution Time Variation

Latency jitter is due to variation in actual execution time. Different data values may require different amounts of computation. Latency jitter is also due to the use of preemptive scheduling techniques in order to increase the utilization of processors. Preemptive scheduling causes one task to be preempted to allow a higher priority task to complete, delaying its completion by varying amounts of time. As pointed out earlier, such execution time variation of a data stream with can be masked by a sampling task ass long as the jitter does not exceed the sampling rate. Variation in execution time is recorded in AADL models as a time range. Similarly, AADL processors have a property that indicates the type of scheduling protocol, i.e., it can identify whether preemptive scheduling is being performed.

Non-Deterministic Communication

Preemptive scheduling of tasks as well as concurrent execution of tasks on different processors, e.g., different cores one a multi-core processor, can have a greater effect on jitter. The execution of send/receive (e.g., write/read to variables) to accomplish the communication, when executed as part of the application code, can lead to a non-deterministic send/receive order [7]. This leads to frame-level latency jitter. Let us illustrate with an example shown in Figure 3.

Figure 3 Frame-level Latency Jitter Mid-frame and phase-delayed communication semantics guarantee that a task deterministically samples a data stream. For example, if the rates of two communicating tasks are harmonic, i.e., the sending task rate is twice the rate of the receiver, then the receiver reads every second element in the data stream written by the sending task. However, if the write and read order is not guaranteed to be deterministic, then the receiving tasks may read two successive elements in the data stream and then skip two elements to read the third. The effect is that sampling of the data stream may vary by as much as two frames. In AADL, deterministic data port communication can be explicitly modeled through immediate and delayed connections. In addition, AADL supports modeling of sampled port connection as well as explicit modeling of communication through shared data components.

Rate Group Optimization

Rate group optimization is the process of mapping tasks that have the same execution rate on a specific processor into a single operating system (OS) thread of that rate. The benefit of rate group optimization is that context switch time between tasks of the same rate is greatly reduced because the operating system thread executes these tasks on a static time by calling them as subprograms. Rate group optimization affects the task execution order within a frame as it places tasks of the same rate into groups and executes them in order within each group.

A task sequence with mid-frame communication with tasks of different rates has an expected execution order of these tasks. The rate group optimization may result in a task execution order that is in conflict with the desired order for the task sequence.

Figure 4 Phase Delay due to Rate Group Optimization

Let us illustrate with an example shown in Figure 4. Let us assume a sequence of three tasks with midframe communication. Task Ts and Ta are higher rate tasks (50 ms), while Tc is a lower rate task (100ms). Rate group optimization will place Ts and Ta in a high rate group G1, and Tc in a low rate group G2. If G1 is executed before G2, e.g., if rate group priority is assigned based on rates, the constraint Tc->Ta is violated, and if G2 is executed before G1 the constraint Ts->Tc is violated. In other words, the rate group optimization forces one of the mid-frame communication steps to become a phasedelayed communication step. The general rule to be checked is whether there is an immediate connection between threads in different rate groups and the execution order of those rate groups cannot be guaranteed to be the same as that implied by the immediate connection. A corollary to this rule is that if there exists an immediate connection from a thread in one rate group to a thread in a second rate group, and there exists a second immediate connection from a thread in the second rate group to a thread in the first rate group the immediate connection timing semantics cannot be guaranteed. When the immediate connection semantics cannot be guaranteed one of two things happens to the end-to-end latency: the end-to-end latency will increase if the execution order of the rate groups deterministic; or latency jitter will occur due to preemption or concurrent execution of rate group threads. AADL supports modeling of rate group optimization at several levels of abstraction. For example, logical tasks can be modeled by AADL threads. An AADL property can be introduced to define the mapping into a rate group for each AADL thread. The actual implementation of the rate group as an operating system thread is then derived (generation) from this model. Other modeling options to more explicitly represent the rate group include the use of virtual processors of AADL V2 [9].

Partitioned Architectures

Partitioning is used to support integrated modular avionics (IMA). A partition provides a virtual processor that ensures space partitioning through address space protection and time partitioning by ensuring its processor allocation is not exceeded. Within partitions multiple threads may execute and each partition may implement its own policy for scheduling its threads. All interactions between partitions is accomplished through port-based communication. This allows embedded applications to be modularized and configured in different ways to run on a common computing platform. The ARINC 653 standard for embedded avionics systems [8] specifies that all inter-partition communication must be phase-delayed if deterministic communication behavior is desired (see Figure 5). This makes the behavior of the application insensitive of the partition execution order or partitions executing concurrently. However, this may require double buffering in order to assure the correct data to be available to the recipient. As we place an embedded application into a partitioned architecture and the end-to-end flow spans multiple partitions, then the end-to-end latency is increased by the phase-delayed communication across partition boundaries.

Figure 5 Phase Delayed Inter-partition Communication

The phase-delayed inter-partition communication model can have unexpected side-effects on existing legacy applications that implement an ICO model. A common way of implementing this model is to have a high priority task (Periodic I/O) take the output from a shared data area and send it to other control subsystems, as well as place the input from other subsystems into the shared data area (see Figure 6). Note that this has the effect of phase-delayed communication. When ported into a partitioned architecture, the partition communication mechanism will phase delay the cross-partition data traffic, but the data it receives from the application, i.e., its Periodic I/O task, is already delayed. This will result in doubling of the latency contributed by communication across partitions.

Figure 6 Legacy Cyclic Executive Implementation

If the partitioned architecture does not ensure phase delayed communication, e.g., by application send/receive calls without the communication protocol performing double-buffering to delay the receipt, we get two effects on the end-to-end latency. Let us first examine partitions on the same processor. In this case communication from the first partition to the second partition is mid-frame, while communication from the second partition to the first partition is phase-delayed. If we change the statically determined execution order of partitions, then the immediate connection becomes delayed and the delayed connection becomes immediate -resulting in a change in the flow latency through either connection.

If the partitions execute on different processors, then the send/receive order may be non-deterministic resulting in frame-level jitter due to concurrent execution. If the execution order of partitions is changed on one of the processors and the processors clocks are synchronized, one partition may always be executing before the other, i.e., the execution order may become predictable with communication in one direction immediate and the other delayed. In summary, in a partitioned architecture we can isolated the embedded application from nondeterminism, or we can determine whether a control application needs to accommodate latency jitter or be recalibrated for a change in latency. Partitions can be modelled in AADL through AADL processes. They represent space partitions in their default semantics. Partition-specific properties can be introduced to characterize the partition execution rate and the scheduling protocol supported by the partition for executing its threads. In AADL V2 [9] we can use the virtual processor concept to more explicitly represent the partition as an entity that provides time partitioning and scheduling of threads.

Communication Protocols

Communication protocols contribute to end-to-end latency as well. There is the transmission latency, i.e., the amount of time it takes to transmit the data from the source to the destination. This figure is dependent on the speed of the underlying transmission medium, and on the amount of data to be transmitted. It is the equivalent to processing latency contributed by tasks.

In addition, communication protocols contribute transmission delay due to queuing or due to waiting for the transmission time slot. Examples of the latter are signal data transfer over CANBus or a time-triggered protocol. Such time-division protocols can be viewed as sampling the data stream to be transmitted, thus, contributing sampling latency. Communication protocols are modeled as part of the AADL bus abstraction. The AADL bus has a number of properties that allow modelers to specify data transmission costs. Additional properties can be introduced to specify protocol characteristics such as guaranteed delivery, and slot assignment in a timedivision protocol. In order to better support modeling of protocols independent of physical connections, AADL V2 [9] has introduced the virtual bus concept.

Globally Asynchronous Systems

In a synchronous system, task dispatches are aligned. As a result, the sampling latency can be determined by rounding the processing latency to the next multiple of the sampling rate (see also Section 2.1). In a globally asynchronous system, the sampling latency has to be added to the processing latency to accommodate worst-case assumptions of misalignment of clocks. Furthermore, clock drift becomes evident as small changes in latency jitter. Resynchronization of clocks has the effect of a jump in latency, whose size is dependent on the degree of drift and resynchronization frequency. The base semantics of AADL [START_REF] Cervin | Control Loop Timing Analysis Using TrueTime and Jitterbug[END_REF] are defined in terms of synchronous systems. However, the standard allows AADL properties to be used to introduce clock asynchronicity. For example, AADL processor can have properties that indicate the clock used as its time reference point. The AADL device concept can be used to represent clocks explicitly and associate clock specific properties, such as drift with respect to some universal time. The AADL V2 standard [9] will provide additional guidance and support for modeling multiple time spaces, i.e., support for modeling various forms of asynchronicity such as globally asynchronous locally synchronous (GALS) systems or physically asynchronous logically synchronous (PALS) systems.

A Flexible Framework for Latency Analysis

There is a need for control engineers and embedded software engineers to cooperate in a co-design setting when developing software-intensive control systems.

In support of such a co-design environment there is a need for flexible framework for end-to-end latency analysis. This framework must be flexible in several dimensions. First, it must usable early and throughout the development life cycle, i.e., it must accommodate multi-fidelity modeling and analysis. This means it must support partial models of systems with few runtime architecture decisions that can produce initial insights, and that can later be refined into more complete models for further analysis. Second, the framework must be extensible to accommodate new contributors to latency and latency jitter as new runtime architectures and communication mechanisms are developed and deployed. This analysis framework must accommodate a few principal concepts of time-sensitive data stream processing and their realization in software [START_REF] Caspi | On the Implementation of Control Loops by Software[END_REF]. These include synchronous and asynchronous processing and communication, sampled and datadriven processing and communication, characterization of determinism, resource sharing delay, and predictable worst-case and best-case performance. By centering the framework around data stream characteristics we can express assumed timing characteristics from a control engineering perspective, and contributors to these characteristics due to processing tasks and communication mechanisms in the runtime architecture of the software implementation. We suggest that AADL can be a good platform for such an analytical framework.

AADL allows modelers to capture expected data stream characteristics, and its allows users to represent the runtime architecture of the embedded software system at different levels of abstraction. We have developed an initial realization of such a framework around AADL [START_REF] Feiler | Flow Latency Analysis with the Architecture Analysis and Design Language (AADL)[END_REF]. In this framework we have demonstrated how a lower bound of worst-case endto-end latency can be quantified for models of the control system at various levels of fidelity. For example, end-to-end latency may be calculated based decisions regarding partitioning of major subsystems without any details about the tasks, and later revisited when processing tasks are known in terms of sampling, period, and communication timing, when binding decisions are made with respect to deployment on compute hardware. This framework can be extended to accommodate contributions of protocols used in the communication, effects of data stream miss rates, and choices in fault tolerance mechanisms. This framework can accommodate worst-case and best-case latency, as well as determination of age.

The impact of such timing measures of data streams on control system behaviour can also be determined analytically [START_REF] Åström | Computer Controlled Systems -Theory and Design[END_REF]. Commercial tools are starting to address this need for specific application domains, e.g., the automotive domain [10].

Conclusion

In this paper we have examined the sensitivity of control systems to implementation choices in runtime architectures for embedded software systems. For a control engineering perspective we have identified commonly assumed timing characteristics for processing a data stream in a control loop. We have identified non-determinism in sampling a data stream as a key contributor to latency jitter, which in turn causes instability in control behavior. We have then examined several runtime architecture concepts for their contributions to latency and latency jitter. We have shown that AADL can be used to characterize the control application and the runtime system that implements this control application and that the semantics associated with AADL concepts are well suited to capture the essence of the timing problem space to be the basis for an adaptable analytical framework that allows control engineers and embedded software engineers to evolve the design of a system in a co-design setting through repeated analysis of models of different fidelity.

Figure 1 :

 1 Figure 1: Processing Time and Sampling Latency 2.2 An AADL Model of the Control System AADL supports modeling of periodic and event or data-driven tasks (AADL threads). These threads