Opportunity: Software Execution Time Determinism

[Johannes Pfau via Digitalmars-d]

Am Wed, 13 Apr 2016 18:35:34 -0700
schrieb Walter Bright <newshound2 at digitalmars.com>:

> On 4/13/2016 5:31 PM, Simen Kjaeraas wrote:
> > On Wednesday, 13 April 2016 at 22:58:26 UTC, Walter Bright wrote:  
> >> The compiler could be fairly easily compute cyclomatic complexity,
> >> but how that would be used to determine max time escapes me.
> >>
> >> For example, how many times would a particular loop be executed?
> >> Isn't this the halting problem, i.e. not computable?  
> >
> > The first step is simple - we care only about functions being
> > constant-time. Let's invent a @keyword for that: @constanttime.
> >
> > @constanttime functions can only call other functions marked
> > @constanttime, and may not contain conditionals, gotos or
> > while-loops.
> >
> > @constanttime functions may contain for and foreach-loops, iff
> > the number of iterations are known at compile-time, and 'break'
> > is never used.  
> 
> Very interesting. Recursion would have to be disallowed as well.
> 

Unless you can calculate the recursion 'depth'. Though that could
get very complicated.

> 
> > The part about conditionals seems a bit harsh, but it's got to
> > be there for determinism.  
> 
> Understood.
> 
> 
> > Not knowing Nordlöw's use case I can't say for sure what he
> > actually needs.  
> 
> Your ideas are good. Let's see what Nordlöw says.
> 

Such deterministic code is usually very restricted. This is expected.
See also: https://en.wikipedia.org/wiki/Worst-case_execution_time

I assume Nordlöw only cares about the WCET, not 'complete'
determinism (if a loop executes 5 or 6 times depending on input data the
run time is not deterministic but the maximum is)

As a compiler we can't give a useful estimate of WCET without knowing
the target architecture very well (calculating some upper bound is not
too difficult, but if you ignore pipelining and caches the calculated
WCET might be 4-5x higher than the real WCET).

What we can do though is limit the language to a subset which can be
WCET analyzed by other tools. As these tools have to determine if code
is time-deterministic as well it might make sense to have a closer look
at some WCET tools:

http://users.ece.utexas.edu/~bevans/courses/ee382c/lectures/spring2000/23_hwsw/cinderella.pdf
https://www.rapitasystems.com/WCET-Tools