Re: Specifying time limits in source code ?

On 14 Jul 1999 02:06:43 -0400, <hat@se-46.wpa.wtb.tue.nl> wrote:
>At the processor-side, things are a bit more difficult, but not impossible.
>- I would have to specify the max #iterations of each loop construct.


Someone already suggested using the range limits of the loop
variables, but that is realistically possible only if they are small:
ie. 8-bit byte or 16-bit word, or if the language allows sub-ranging
(like Pascal and its daughters). It would be idiotic to attempt
otherwise on a 32-bit CPU.


>- There is no way that the compiler can take scheduling of tasks
> (including interrupts) into account. In other words, the designer must
> specify time limits such that scheduling poses no threat of violating
> the dead line. In the context of hard real-time systems, this is a
> problem with a known solution.


The known solution is


repeat
code it
test it
until satisfied


Interrupts are only predictable in the sense that you can determine
the maximum frequency at which they can arrive, the maximum latency to
enter any particular service routine and the maximum time to service a
particular interrupt. This looks wonderful on paper, but the dynamic
mix of tasks, interrupts and service routines becomes important in
practice, particularly with CPUs which prioritize interrupts [ie.
allow interrupt service to itself be interrupted].


Context switching is also a problem because the time required to do it
may depend on what the CPU was doing at the time of the switch.
Saving [sufficient] CPU state to restart occurs in bounded time but
depends on what precisely has to be saved. Even on relatively simple
processors, an RTOS may offer options to save location only, location
+ ALU state, location + ALU/FPU, etc., at the switch. CPUs with
alternate register sets may have to spill to or refill from RAM if all
sets are already in use.


Most of the more advanced RISC CPUs won't react immediately to an
interrupt if they are currently processing an exception. On some of
the superpipelined units, exception handling can take *many* cycles
and the occurence of the exceptional condition is not always
predictable from the code. CISC processors also typically offer some
multiple cycle uninterruptable instructions.




>- Also, current processors do prefetching and out of order execution
> which is very unpredictable (this may be considered as a form of
> run-time optimization).


This affects the running time of a basic block but generally not
context switching because those CPUs also offer alternate register
sets, register renaming, scoreboarding, speculative execution, etc.
However, see above.




> - Current `normal' processors in real-time systems are not always that
> advanced, so the problem may not even exist in some cases.


Not necessarily true any more. Lots of modern R-T systems are being
built around 68K, i960 and PowerPC cores. Look around in
comp.realtime and comp.arch.embedded.




> - If it does exist, at least it will only make the program run faster
> not slower, which means that the time limit will always be met.
> However, it may cause a grossly over-estimated time limit.


A deadline driven scheduler may refuse to accept a task with a
severely overestimated running time. Also interrupt handlers are not
scheduled at all, they execute asynchronously.




> In some projects the time saved by not having somebody check the
> timing of the code may outweigh the extra cost of the processor.
> - Maybe execution time of an opcode is not a good measure, in which
> case there may be alternative methods, such as counting memory refs.


The execution time of the code is an incidental concern to a real time
system - what matters is that the target execution window is *always*
hit. Many systems have both minimum and maximum execution limits - if
the code runs too soon or too quickly, that is just as bad as code
that runs too slowly or not at all.


>Assuming that some else would have considered the above, I was
>surprised to learn that the archive of comp.compilers had no
>discussion about specifying time-limits on fragments of programs.


The problem can only be solved in severely restricted examples where
all the variables are known.




> Is there work being done on this kind of compilers ?


Not likely.




George Neuner
Dynamic Resolutions, Inc.

Return to the comp.compilers page.
Search the comp.compilers archives again.