Logical Execution Time (LET)

[edwardalee]

The proposal is to specify a logical execution time (LET) for a reaction as follows:

reactor Foo {
    input in:int;
    output out:int;
    reaction(in) -> out after 10 msec {=
        ...
    =}
}

The idea is that all the effects of the reaction (outputs, actions, and state variables) are seen only after 10 msec of logical time has elapsed. For actions that are scheduled by the reaction, the delay of the action should be relative to the end of the LET.

There are quite a few subtleties here, mostly around what I will call interrupting reactions, which are reactions that are triggered after the LET reaction is triggered but before the tag at which the LET reaction logically completes. Generally, we should probably consider it bad practice to design a system that has such interrupting reactions, but we have to give them a clear semantics.

An interrupting reaction will be invoked at its designated logical time. It will see a self struct that has not been modified in any way by the LET reaction that is currently executing. If it updates a state variable, its update may be overwritten by the LET reaction when its logical execution time has elapsed.

To implement this in the C target, when a LET reaction is pulled off the reaction queue, the self struct is copied, a new thread is created to execute the reaction using the copy of the self struct. Another reaction gets scheduled to be invoked after expiration of the logical execution time. That reaction joins the thread and then copies its self struct, overwriting the default self struct.

During the execution of thread, calls to functions like lf_time and lf_schedule have to be modified so that they read times from the self struct rather than globally. I proposed to do that by replacing these functions with macros.

This relates to enhanced deadlines as in #403.

[Soroosh129]

I personally liked the previous proposal more, where interrupting reactions were not allowed. Reactions in a reactor can also share state through the environment (e.g., they all control a motor in different ways). A LET reaction can change the state of the environment at a nondeterministic tag. If we allow other reactions of the same reactor to execute in the meantime, the order of the state changes can become nondeterministic as well.

To implement this in the C target, when a LET reaction is pulled off the reaction queue, the self struct is copied, a new thread is created to execute the reaction using the copy of the self struct. Another reaction gets scheduled to be invoked after expiration of the logical execution time. That reaction joins the thread and then copies its self struct, overwriting the default self struct.

I think we might not need a new thread since we have workers that can execute these LET reactions. Why not modify our existing schedulers or add a new one that is capable of this?

[Soroosh129]

Correction: I think I misunderstood the proposal. Based on the June 1st meeting, my understanding is that interrupting reactions are triggered at their original intended tag but don't execute until the LET reaction finishes. The changes to state variables are logically instantaneous but changes to the effects of a LET reaction take place at the end of the logical execution time.

In that case, my previous comment is not relevant.

[edwardalee]

I think it will behove us to create a simple implementation for this that deals efficiently with the usual use cases, where there will be no interrupting reactions. When there are interrupting reactions, I propose that it is legitimate to sacrifice parallelism by blocking reaction executions as needed to preserve correctness.

Specifically: Suppose a upstream reaction becomes enabled that has the potential to trigger an interrupting reaction (it has an effect an output that connects to an input triggering the LET reaction). We should block the execution of that upstream reaction until the LET reaction has completed its execution. This prevents the upstream reaction from changing the input values of the LET reaction while it is executing, and therefore eliminates the need for the LET reaction to copy the inputs.

[rvhanxleden]

Summary of discussion today:

Motivation for LET: specification of timing behavior, decoupled from execution time uncertainties.

"Giotto specifies time-triggered sensor readings, task invocations, actuator updates, and mode switches independent of any implementation platform."
[Thomas A. Henzinger, Benjamin Horowitz, and Christoph M. Kirsch, "Giotto: A Time-triggered Language for Embedded Programming", Proceedings of the IEEE 91:84-99, 2003]

Hypothesis: can use "after" keyword to express LET.

Conceptually, "after d" affects the tag associated with outputs.
If reaction takes place at time t, output is associated with time t + d.
"after" could be applied to

1. the whole reactor, affecting all reactions and their outputs (coarsest variant - in that case, LET should be at least the sum of WCETs of all reactions)
2. a specific output (which may have multiple connections)
3. a specific connection (i.e,, it would be possible to have different LETs associated with same output, of the same or different reactions)
4. a specific reaction (i.e., it would be possible to have different reactions with different LETs that affect the same output)

Generally, tags control when outputs become "visible" to downstream reactors.

Orthogonally to that, there are state variables, local to a reactor.
Writes/reads to state variables are (deterministically) ordered by the textual order of reactions - independent of any LETs associated with reactions.

Reactions can only execute in parallel (e.g., in a worker thread) if they are in different reactors.

Simple example, with two reactions r1_let and r2:

r1_let(x) -> y after 10 ms;
r2(x) -> z;

When r1_let and r2 are triggered at time t, y will be output with tag t+10ms, z will be output with tag t.
State variables written by r1_let() will be read with new value by r2().
It would be possible to start r2() at time t and, e.g., at time t + 1ms, i.e., before output of r1_let() has become visible.
So, the above has a clear semantics, compatible with LF without LET. However, it probably is advisable for the programmer to have the order of reactions to comply with the order of output tags. I.e., in the example, to have r2(), which produces outputs instantaneously, ordered before r1_let(). Alternatively, the compiler may even enforce such an ordering, i.e., reject programs that violate that order.

Open questions:

• Which of the options 1-4 should be supported?
• Should state variables also be associated with tags? If so, which one?
  Suggestion: all should be associated with tag t

[petervdonovan]

There seem to be a few ways to minimize the conceptual weight that LET might add to our implementation, especially if LET reactions are treated like normal reactions that can be executed by the existing workers:

• There seems to be a symmetry between LET and chain ID. With chain ID, we block reactions that are downstream of reactions whose outputs are not known, whereas with LET, we block reactions that are upstream of reactions that are still executing a previous tag. We already know how to take care of this blocking, with bit fields and transfer queues, etc.
• Since federated execution already has the desired behavior, we can replicate its behavior by drawing loose parallels between federates and workers. In particular, it is not really necessary for each reactor to have its own logical time; instead, each worker may have its own logical time. At the end of each reaction execution, we can determine which outputs are still not accounted for and at which tags those outputs are expected to become visible; this effectively establishes a NET. If the NET increases, all the workers see a TAG that enables them to proceed with popping events off the event queue and processing the reactions that result.
• After listening to Reinhard's explanations, I no longer think I understand why any additional copying is needed. If the reactions immediately upstream are blocked, the inputs are safe and needn't be copied. If the current reactor executes only the LET reaction at a given time, the state is safe and needn't be copied. The outputs can just go into tokens that get forwarded by generated delay reactors, and this is already implemented (i.e., we already have after delays).

[edwardalee]

These are interesting observations from @petervdonovan . The second I would summarize as "make each worker be like a federate, and provide an RTI-like coordination between workers." I think this approach could be tricky to realize efficiently, however. A key difference between workers and federates is the reactors (and their reactions) are preallocated to federates, but not to workers. This is why the RTI can know the dependencies between federates.

On the third, I agree that the only copying needed, given blocking of upstream reactions, is the copying already implemented by after delays. In view of this, I don't think we need to add new syntax for LET. A reaction where, for all outputs in its effects, there is an after delay of at least L, and all actions in its effects have a minimum delay at least L, is a LET reaction with logical execution time L.

[edwardalee]

This issue is superseded by #1261. In summary, no additional syntax is needed to support LET. Instead, any reaction whose effects are all delayed either by after delays or by minimum delays on actions can, in principle, be executed in parallel with other reactions that are triggered at later logical times, provided that those later logical times are less than time the LET reaction is triggered plus the minimum of all the delays on its effects.