For GNAT People

For GNAT People

[grt]

The GUARDS project is an Esprit activity of the European Community. 

It is intended to define the most suitable development environment for
hard real-time dependable software applications such as railway,
spacecraft and nuclear installation control.  

The involved partners are:
Technicatome, 
Matra Marconi Space, 
LAAS-CNRS, 
University of York,
Siemens AG Osterreich PSE, 
Ansaldo Trasporti, 
Intecs Sistemi (my company)
Pisa Dependable Computing Centre. 

I am currently involved in the selection of the design method, 
the related tool, the final implementation language.  

In the last years greater and greater importance has been attributed
to the non-functional requirements, in particular to the deadlines
associated to time requirements. If such requirements are not faced
very early in the software life-cycle, then the reliability of the
developed system might be hardly affected.  Techniques have been then
developed to be able to check that the deadlines are met even in the
worst case of execution.  Tools that apply such techniques are called
Schedulability Analyser.  They need a description of the system
dynamic behavior and the execution time of pieces of sequential code.
After the development phase it is easy to measure the required times,
but we would like to be able to perform the analysis BEFORE all code
is produced and without exercising the specific hardware.  At this
purpose it is needed a so called Worst Case Execution Time
Analyser. It is a tool able to estimate with a high degree of
confidence the execution time given the source code statements. My
company's role includes the development of such a tool.

Being GNAT one of the candidate Compilation System I am interested to
know your opininion about the level of support we can have from the
compiler: the basic idea is to have dis-assembled the selected piece
of code (it is still TBD how to select it) and analyse the assembly
code taking into account the CPU cycles for each statement. 
More, the final target for application is still TBD, but it will be an
industrial 32 bit board with a POSIX-like executive: 
what about Ada95 and C++ using GNU software?  
In particular for C++, does exist a validated factory in such
environment ?

Sandro Paganone

e-mail: sandro@pisa.intecs.it

Re: For GNAT People

[Frank Mueller]

In article <31F5FF33.167EB0E7@pisa.intecs.it>, grt <grt@pisa.intecs.it> writes:
> After the development phase it is easy to measure the required times,
> but we would like to be able to perform the analysis BEFORE all code
> is produced and without exercising the specific hardware.  At this
> purpose it is needed a so called Worst Case Execution Time
> Analyser. It is a tool able to estimate with a high degree of
> confidence the execution time given the source code statements. My
> company's role includes the development of such a tool.
> 
> Being GNAT one of the candidate Compilation System I am interested to
> know your opininion about the level of support we can have from the

I've been involved in worst-case execution time (WCET) estimation for some time.
In short, it's not ready for production use yet. Many hardware aspects require
analysis at the processor cycle level (pipelines, caches, superscalar).

Our approach has been to design a tool set for static analysis of programs (tasks or
smaller pieces of code, e.g. loops) wrt. WCET and a certain architecture. The RTSS
and RTAS conferences cover some of the on-going work.

We used the VPCC/VPO compiler which uses RTLs just like GNAT/GCC. We enhanced this
instruction-level analysis by hardware-specific information (pipeline structure, miss penalty,
cache configuration...) Our system produced estimates in a very short time (compared to
other approaches, e.g. using ILP) and overestimates the WCET by about 10%, assuming that loop
bounds are known etc.

I'm currently working together with FSU (Florida State University), TU Wien and Chalmers U.
on some issue. My main focus has been the problem of instruction caching.

Check out

http://www.informatik.hu-berlin.de/mueller/publications.html

and

http://www.cs.fsu.edu/~whalley
-- 
Frank Mueller   E-Mail: mueller@informatik.hu-berlin.de   WWW: http://www.informatik.hu-berlin.de/~mueller

Re: For GNAT People

[Greg Bond]

grt wrote:

> snip...
> 
> In the last years greater and greater importance has been attributed
> to the non-functional requirements, in particular to the deadlines
> associated to time requirements. If such requirements are not faced
> very early in the software life-cycle, then the reliability of the
> developed system might be hardly affected.  Techniques have been then
> developed to be able to check that the deadlines are met even in the
> worst case of execution.  Tools that apply such techniques are called
> Schedulability Analyser.  They need a description of the system
> dynamic behavior and the execution time of pieces of sequential code.
> After the development phase it is easy to measure the required times,
> but we would like to be able to perform the analysis BEFORE all code
> is produced and without exercising the specific hardware. At this
> purpose it is needed a so called Worst Case Execution Time
> Analyser. It is a tool able to estimate with a high degree of
> confidence the execution time given the source code statements. My
> company's role includes the development of such a tool.
>
> snip...

I don't think anyone would disagree with the fact that WCET analysis
before all code is complete would be valuable, however I'm curious to
know how one can approach WCET analysis without having all the code
involved. Any approach I'm familiar with analyzes RTL, or byte code i.e.
the result of compiling (completed) code. Is some sort of incremental
approach possible?





--
* Greg Bond                         * Dept. of Electrical Eng.  
* email: bond@ee.ubc.ca             * Univ. of British Columbia      
* voice: (604) 822 0899             * 2356 Main Mall                 
* fax:   (604) 822 5949             * Vancouver, BC              
* web: http://www.ee.ubc.ca/~bond   * Canada, V6T 1Z4

WCET Analysis (was For GNAT People)

[JP Thornley]

Greg Bond <bond@ee.ubc.ca> writes (talking about analysing code for 
worst case execution times):
>         Any approach I'm familiar with analyzes RTL, or byte code i.e.
> the result of compiling (completed) code. 

How do these approaches deal with problems such as:-
	semantically infeasible paths,
	maximum loop iterations,
	etc.
where you need information that isn't provided by the typical compiler?

I've used one tool that takes a rather crude approach to these, but 
would be interested in experience of other tools.

Phil Thornley

-- 
------------------------------------------------------------------------
| JP Thornley    EMail jpt@diphi.demon.co.uk                           |
------------------------------------------------------------------------