Opportunity: Software Execution Time Determinism

Nordlöw via Digitalmars-d digitalmars-d at puremagic.com
Thu Apr 14 15:20:21 PDT 2016


On Thursday, 14 April 2016 at 00:31:34 UTC, Simen Kjaeraas wrote:
> 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.
>
> The part about conditionals seems a bit harsh, but it's got to
> be there for determinism.
>
> Constant time is easy, and may or may not be enough to cover
> Nordlöw's needs. Anything beyond it is very likely to be halting
> problem stuff.

Yest, that's what I had in mind. Those mentioned are the 
low-hanging fruits.

The situation is as follows:

A set of processes are tightly scheduled to run after one another 
within a 1/N frame, where N is typically either 60 Hz. Each of 
these processes run on a single CPU. The scheduler defines a 
specific order for the execution of the different processes.

After each process has completed its execution within a frame it 
copies its out-values to the in-values of other processes that 
uses its results which are then executed.

Each process is assigned a time- and space-budget collectively 
called WCRU (worst-case-resource-usage). Execution space can be 
restricted by forbidding any kind of dynamic memory 
(de)allocations. This is often straightforward but could be 
useful to have restriction qualifer for aswell, for instance 
`@noheap`.

Then a set of tedious manual code reviews are performed on the 
executable code to assert that it doesn't contain any 
non-deterministic constructs.

After that the main function of each process is run 100-1000 
times and the WCET (worst-case-execution-time) paired with WCSU 
(worst-case-stack-usage) is calculated through the maximum of a 
set of executions typically a thousand with the correct "stimuli" 
as input. Figuring out this stimuli is also cumbersome manual 
work.

To conclude, the manual code review could be greatly simplified 
or perhaps completely removed if a, say @constanttime as 
mentioned above, function attribute was available in the language 
and respected by the compiler.


More information about the Digitalmars-d mailing list