Worst Case Execution Time Tool?

Worst Case Execution Time Tool?

[StationSteve]

Are there any tools that quantitatively determine the worst case
execution time (WCET) of an Ada83 program or subprogram?  Execution
platform is Intel 80386SX bare machine.  I think I'm looking for
something similar to SPARK Examiner's WCET analysis, but for Ada83.

Thanks in advance for any help...

Re: Worst Case Execution Time Tool?

[Ted Dennison]

In article <3C0D536C.2E059EE8@computer.org>, StationSteve says...
>
>Are there any tools that quantitatively determine the worst case
>execution time (WCET) of an Ada83 program or subprogram?  Execution
>platform is Intel 80386SX bare machine.  I think I'm looking for
>something similar to SPARK Examiner's WCET analysis, but for Ada83.

Wouldn't such a tool also be able to solve the Halting Problem? (
http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=halting+problem )

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Worst Case Execution Time Tool?

[Stuart Palin]

Ted Dennison wrote:

> In article <3C0D536C.2E059EE8@computer.org>, StationSteve says...
> >Are there any tools that quantitatively determine the worst case
> >execution time (WCET) of an Ada83 program or subprogram?

> Wouldn't such a tool also be able to solve the Halting Problem? (
> http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=halting+problem )

<simple answer>
No!
</simple answer>

If a WCET tool was developed on general terms with the intention of
dealing with all forms of program, then it is most likely that if a
non-terminating program was submitted for analysis the analysis itself
would not halt.

In more practical terms, this type of tool will typically constrain the
types of program that it will analyze.  Typically this might prohibit
recursion and demand upper limits for loops to be statically
determinable (either from the code or from annotations).  Such rarified
problems as the Halting Problem are hardly a consideration.

--
Stuart Palin
Principal Software Engineer
BAE SYSTEMS Avionics Ltd, Rochester
G-NET 791 3364    mailto:stuart.palin@baesystems.com

Re: Worst Case Execution Time Tool?

[Ted Dennison]

In article <3C0E5927.5657963A@baesystems.com>, Stuart Palin says...
>In more practical terms, this type of tool will typically constrain the
>types of program that it will analyze.  Typically this might prohibit
>recursion and demand upper limits for loops to be statically
>determinable (either from the code or from annotations).  Such rarified
>problems as the Halting Problem are hardly a consideration.

Ah. So we aren't looking for something that can handle any old program (which it
still seems to be would be reducable to the Halting Problem), but rather one
that can handle programs that fit certian restrictions.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Worst Case Execution Time Tool?

[StationSteve]

Of course.  Er, I mean sorry, I guess I should have said that I was looking for a
*practical* tool that could *productively* address a *real world* problem! ;-)
Steve S.

Ted Dennison wrote:

> In article <3C0E5927.5657963A@baesystems.com>, Stuart Palin says...
> >In more practical terms, this type of tool will typically constrain the
> >types of program that it will analyze.  Typically this might prohibit
> >recursion and demand upper limits for loops to be statically
> >determinable (either from the code or from annotations).  Such rarified
> >problems as the Halting Problem are hardly a consideration.
>
> Ah. So we aren't looking for something that can handle any old program (which it
> still seems to be would be reducable to the Halting Problem), but rather one
> that can handle programs that fit certian restrictions.
>
> ---
> T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
>
> No trees were killed in the sending of this message.
> However a large number of electrons were terribly inconvenienced.

Re: Worst Case Execution Time Tool?

[Ted Dennison]

In article <3C0F7B36.52960668@computer.org>, StationSteve says...
>
>Of course.  Er, I mean sorry, I guess I should have said that I was looking 
>for a *practical* tool that could *productively* address a *real world* 
>problem! ;-)
>
>Ted Dennison wrote:
>> Ah. So we aren't looking for something that can handle any old program 
>> (which it still seems to be would be reducable to the Halting Problem), but 
>> rather one that can handle programs that fit certian restrictions.

:-)

For that to be accurate though, you'd have to be able to say that all programs
that don't fit within the restrictions are not "real world" programs for some
reason. That could be the case I suppose. However, I'd bet quite a few "real
world" programs wouldn't meet all the restrictions in any such existing tool.
Certianly "No recursion" and "no loops with a dynamicly determined amount of
iterations" (which is what Stuart said) would take out a great deal of the "real
world" code I have seen. 

For instance, just about anything that handles terminated I/O would be out. A
lot of dynamic data structure code would be out too. I could easily see where a
hard realtime app might want to measure the worst-case execution time of a list
traversal (eg: the scheduler's list of scheduled tasks). It'd be a pretty darn
smart tool if it could handle that, no matter how the list is implemented.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Worst Case Execution Time Tool?

[StationSteve]

Ok, do you have time to educate me a little bit?
Why would a tool have to be "pretty darn smart" to measure the worst-case execution
time of a list traversal?  What's the big driver in making such a thing hard to do?
How hard are we talking?  Ph.D/New Theory Required hard or Grad Student Thesis hard
or Kappa-Key undergrad hard or Lock-the-new-hire-in-the-lab-just-get-it-done hard?

Ted Dennison wrote:

> In article <3C0F7B36.52960668@computer.org>, StationSteve says...
> >
> >Of course.  Er, I mean sorry, I guess I should have said that I was looking
> >for a *practical* tool that could *productively* address a *real world*
> >problem! ;-)
> >
> >Ted Dennison wrote:
> >> Ah. So we aren't looking for something that can handle any old program
> >> (which it still seems to be would be reducable to the Halting Problem), but
> >> rather one that can handle programs that fit certian restrictions.
>
> :-)
>
> For that to be accurate though, you'd have to be able to say that all programs
> that don't fit within the restrictions are not "real world" programs for some
> reason. That could be the case I suppose. However, I'd bet quite a few "real
> world" programs wouldn't meet all the restrictions in any such existing tool.
> Certianly "No recursion" and "no loops with a dynamicly determined amount of
> iterations" (which is what Stuart said) would take out a great deal of the "real
> world" code I have seen.
>
> For instance, just about anything that handles terminated I/O would be out. A
> lot of dynamic data structure code would be out too. I could easily see where a
> hard realtime app might want to measure the worst-case execution time of a list
> traversal (eg: the scheduler's list of scheduled tasks). It'd be a pretty darn
> smart tool if it could handle that, no matter how the list is implemented.
>
> ---
> T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
>
> No trees were killed in the sending of this message.
> However a large number of electrons were terribly inconvenienced.

Re: Worst Case Execution Time Tool?

[Ted Dennison]

In article <3C0FE2DE.4BD905B9@computer.org>, StationSteve says...
>
>Ok, do you have time to educate me a little bit?
>Why would a tool have to be "pretty darn smart" to measure the worst-case 
>execution time of a list traversal?  What's the big driver in making such a 
>thing hard to do?

Well, if its a dynamicly allocated list, then theoreticly the "worst case" would
be the amount of time it takes to iterate through n/j items, where n is the
amount of free memory you have after your program loads and j is the amount of
bytes per list item. :-)

In most cases there is a smaller "worst case" available, but you have to know a
fair bit about the system to know what it is. For my real-time scheduler
example, it could be that the list is implemented in an array with a hard limit
of 40 items, and it wouldn't be too horribly dificult for a code analyzer to
figure that out (although not trivial). On the other hand, it could be that the
limit is the number of items listed in a configuration file that is read in at
runtime. There's no possible way a tool could figure that out, because it isn't
really set at all.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.

Re: Worst Case Execution Time Tool?

[annonymous]

Ted writes:
> In most cases there is a smaller "worst case" available, but you have to
know a
> fair bit about the system to know what it is. For my real-time scheduler
> example, it could be that the list is implemented in an array with a hard
limit
> of 40 items, and it wouldn't be too horribly dificult for a code analyzer
to
> figure that out (although not trivial). On the other hand, it could be
that the
> limit is the number of items listed in a configuration file that is read
in at
> runtime. There's no possible way a tool could figure that out, because it
isn't
> really set at all.

There are many cases where it may be necessary to supply guidance to the
timing tools in the form of annotations.  As long as the tool can identify
these
or they are easy to spot by huge variations between measured and theoretical
times it is usually not difficult for the systems engineer to supply the
constraints
needed to do WCET analysis.  The tool needs to be able to accept this
information
information in the some form that can be correlated with the program
(usually
specialized comments).

-Tom

Re: Worst Case Execution Time Tool?

[Rod Chapman]

StationSteve <Steven.Suchting@computer.org> wrote in message news:<3C0D536C.2E059EE8@computer.org>...
> Are there any tools that quantitatively determine the worst case
> execution time (WCET) of an Ada83 program or subprogram?  Execution
> platform is Intel 80386SX bare machine.  I think I'm looking for
> something similar to SPARK Examiner's WCET analysis, but for Ada83.
> 
> Thanks in advance for any help...

Now here's a blast from the past... :-)

I developed the SPATS toolset as part of my DPhil work - it was a
static WCET tool for SPARK targetting 68020.  It was very much a
"research prototype" (i.e. total hack) and so never saw the light
of day.

York Software Engineering Ltd then went on to develop a tool
called STAMP that incorporated some of the ideas from SPATS.  As far
as I know, STAMP remains the only commercially available static WCET tool.
It has been ported to analyse 68020 and PPC 603e object code - no 
386SX I'm afraid...

There is no "offical" SPARK WCET tool, or (currently) any support
for it in the Examiner, other than the inherent analysability of the
language in the first place.  We have the annotations and analysis
all worked out, but the funding (either internal or external) to
make it a reality has never materialized - it's just not a priority
for our customers I'm afraid.

 - Rod

Re: Worst Case Execution Time Tool?

[StationSteve]

Oh, I guess I read the SPARK-Examiner web page wrong:
http://www.sparkada.com/examiner.html

I thought because the following words were on the SPARK-Examiner page, that Examiner could actually DO
WCET analysis of a SPARK program:

The Examiner checks conformance of a SPARK source text to the rules of SPARK by performing the
             following analyses.
...
other bullets here
...
Worst-Case Execution Time Analysis
                  The static analysis of program execution time requires analysis of program source text,
object code, and
                  user-supplied annotations. The latter supply information that cannot be determined
automatically, such as
                  a bound on the number of iterations made by each looping statement. By combining the
control-flow
                  graph for each subprogram, the program's call-tree, and the worst-case execution time
for each object
                  code fragment, the worst-case execution time (WCET) of a subprogram can be determined.
Such
                  analysis has several uses:
                       - Potential timing problems can be found earlier than usual, and thus can be
corrected more cheaply
                       and effectively.
                       - Watchdog timers can be set to monitor and control the execution of time-critical
code.
                       The program path that leads to WCET can be identified and tested with confidence.
...

Guess the marketing guys got tricky again, eh? ;-)

So how (or do?) people typically PROVE that their program will actually meet their deadlines?  If
somebody does a rate monotonic design, they have to assume the execution time of task.  How does one
determine the true execution time so that the design can be shown to be correct?

Thanks again...

Rod Chapman wrote:

> StationSteve <Steven.Suchting@computer.org> wrote in message news:<3C0D536C.2E059EE8@computer.org>...
> > Are there any tools that quantitatively determine the worst case
> > execution time (WCET) of an Ada83 program or subprogram?  Execution
> > platform is Intel 80386SX bare machine.  I think I'm looking for
> > something similar to SPARK Examiner's WCET analysis, but for Ada83.
> >
> > Thanks in advance for any help...
>
> Now here's a blast from the past... :-)
>
> I developed the SPATS toolset as part of my DPhil work - it was a
> static WCET tool for SPARK targetting 68020.  It was very much a
> "research prototype" (i.e. total hack) and so never saw the light
> of day.
>
> York Software Engineering Ltd then went on to develop a tool
> called STAMP that incorporated some of the ideas from SPATS.  As far
> as I know, STAMP remains the only commercially available static WCET tool.
> It has been ported to analyse 68020 and PPC 603e object code - no
> 386SX I'm afraid...
>
> There is no "offical" SPARK WCET tool, or (currently) any support
> for it in the Examiner, other than the inherent analysability of the
> language in the first place.  We have the annotations and analysis
> all worked out, but the funding (either internal or external) to
> make it a reality has never materialized - it's just not a priority
> for our customers I'm afraid.
>
>  - Rod

Re: Worst Case Execution Time Tool?

[Jeffrey L. Susanj]

What we have always done is select a scenario that looks like it would
produce the worst case time and run the software on the bench.  The
executive can capture the time the frame ends.  Not very elegant and not
very rigorous but it gives us a warm fuzzy feeling.


Jeff S.


"StationSteve" <Steven.Suchting@computer.org> wrote in message
news:3C0E3535.58437022@computer.org...
> ...
>
> Guess the marketing guys got tricky again, eh? ;-)
>
> So how (or do?) people typically PROVE that their program will actually
meet their deadlines?  If
> somebody does a rate monotonic design, they have to assume the execution
time of task.  How does one
> determine the true execution time so that the design can be shown to be
correct?
>
> Thanks again...
>
> Rod Chapman wrote:
>

Re: Worst Case Execution Time Tool?

[Stuart Palin]

StationSteve wrote:

<snip>

> So how (or do?) people typically PROVE that their program will actually meet their deadlines?  If
> somebody does a rate monotonic design, they have to assume the execution time of task.  How does one
> determine the true execution time so that the design can be shown to be correct?

On several projects we have used [in-house] WCET tools, our most recent
being for a MC68020/MC68882 target with code generated by the XD-Ada
compiler.

Unfortunately this does not help you (not a commercially available tool
and not '386).

--
Stuart Palin
Principal Software Engineer
BAE SYSTEMS Avionics Ltd, Rochester
G-NET 791 3364    mailto:stuart.palin@baesystems.com