[WIP] LET reactions

[erlingrj]

Scheduling LET reactions in the C target

Purpose

Track the progress of supporting scheduling LET reactions in the C target.

Background

The team in Korea has added support in LFC to annotate each reaction with a LET. Edward has added some additional commits here during the Sonoma retreat which generates C code to set the LET field of each reaction. An important realization is that this currently will only work with reaction that only has logical actions with min_delays as effects. Not ports with after-delays as we initially thought.

Simple test case that motivates the need for LET

target C {
    timeout: 200 ms
}
/**
 * Reactor that has a long-running reaction whose effects are
 * only to schedule a logical action with a minimum delay.
 * This emulates a logical execution time.
 */
reactor LET {
    output out:int;
    timer t(0, 100 ms);
    logical action let(100 ms):int;
    reaction(t) -> let {=
        instant_t physical_time = lf_time_physical();
        while (lf_time_physical() < physical_time + MSEC(50)) {
            // Do nothing.
        }
        lf_schedule_int(let, 0, 42);
    =}
    reaction(let) -> out {=
        lf_set(out, let->value);
    =}
}
reactor Fast {
    timer t(1 ms, 10 ms);
    reaction(t) {=
        
    =} deadline (10 ms) {=
        lf_print_error_and_exit("Failed to take into account LET.");
    =}
}
reactor Sink {
    input in:int;
    reaction(in) {=
        if (in->value != 42) {
            lf_print_error_and_exit("Expected 42. Got %d.", in->value);
        }
    =}
}
main reactor {
    let = new LET();
    fast = new Fast();
    sink = new Sink();
    let.out -> sink.in;
}

Design

The initial design will allow for a conservative utilization of LET reactions. In prose the scheduler will work as follows:
If an idle worker thread finds the system in a state where (1) the reaction_q is empty and (2) the minimum LET of currently executing reactions is greater than 0. Then this worker thread may advance the logical time with an amount that is less than the minimum LET. The worker thread might also just advance the reaction level and unblock other reactions scheduled for the same tag.

1. Interrupting reactions

We can, under no circumstance, allow multiple reactions to execute concurrently within the same Reactor. We call a later reaction for an interrupting reaction if it belongs to the same Reactor as an already executing LET reactions. The solution to this is to check whether there already is a reaction executing inside the Reactor before invoking any reaction. If there is, then wait on a condition variable.

A proposed implementation based on Edwards comments is:

void _lf_worker_invoke_reaction(int worker_number, reaction_t* reaction) {
    ...
    // Get reference to parents self struct
    self_base_t self = (self_base_t *) reaction->self;
    lf_mutex_lock(&self->mutex);

    // We now can safely execute the reaction
    self->executing_reaction = reaction;
    lf_mutex_unlock(&mutex);

    _lf_invoke_reaction(reaction, worker_number);
   
    // Grab mutex and signal possible sleeping workers.
    lf_mutex_unlock(&self->mutex);
     ...
}

Question 1: Are we sure that there are no race condition wrt other uses of the event_q_changed cond var?
Question 2: Should we use a separate mutex for this?

2. Keeping track of currently executing LET reactions

If we have n LET reactions executing we need to store the n finishing times. The other worker threads are not allowed to advance logical time to the minimum of the finishing times. Before executing a LET reaction the worker thread must add the finishing time to group of finishing times and compute the new earliest finishing time. As LET reactions complete they will have to remove their finishing time from the pool of finishing times and compute the earliest finishing time again.

To avoid race conditions this might be done while holding the mutex in (1).

Question: What data structure should we use for storing the finishing times? It seems like a Min Heap could be suitable for this.

A proposal using an undefined global data structure below:

    ...
    // This is an extract of the code snippet from (1)
    // We now can safely execute the reaction
    self->executing_reaction = reaction;
    
    // Update pool of finishing times
    if (reaction->let) {
        heap_add(&_lf_finishing_times, lf_time_logical() + reaction->let);
    }
    
    lf_mutex_unlock(&mutex);

    _lf_invoke_reaction(reaction, worker_number);
   
    // Grab mutex and signal possible sleeping workers.
    lf_mutex_lock(&mutex);

    // Update pool of finishing times
    if (reaction->let) {
        heap_remove(&_lf_finishing_times, lf_time_logical() + reaction->let);
    }
    
    ....

3. Managing the worker threads

Edwards initial idea was to "remove" LET workers from the pool of workers by decrementing the number_of_workers variable before a worker starts executing a LET reactions and incrementing the variable when returning. This could also be done while holding the mutex from (1). However atomics can also achieve this. A proposal using the mutex below:

    ...
    // This is an extract of the code snippet from (1)
    // We now can safely execute the reaction
    self->executing_reaction = reaction;
    
    // Remove this worker from pool of worker threads
    if (reaction->let) {
        _lf_number_of_workers -= 1;
    }
    
    lf_mutex_unlock(&mutex);

    _lf_invoke_reaction(reaction, worker_number);
   
    // Grab mutex and signal possible sleeping workers.
    lf_mutex_lock(&mutex);

    // Add this worker back to the pool of worker threads
    if (reaction->let) {
        _lf_number_of_workers += 1;
    }
    
    ....

4. Advancing time

The current mode of operation is that each worker reactor_threaded.c calls into the scheduler.h to get new reactions with lf_sched_get_ready_reaction. This will eventually return a reaction which it can execute. Before returning a reaction the thread of execution might pass back into reactor_threaded.c to the lf_next_locked to advance time to next tag. The worker threads can either sleep inside the Scheduler due to global barrier synchronization before advancing to the next reaction level, or it can sleep in lf_next_locked.

The protocol is that only a single worker should call lf_next_lock and advance time while all other workers are waiting on a semaphore. We have to consider the edge case where we have only LET reactions executing, but the minimum finishing time is less than the next tag. In which case the worker thread should either wait on the event_q_changed cond_var. This will wake it up either if a LET reaction finishes or if a physical action occurs. Both scenarios can lead to time advancement being appropriate.

5. lf_time_logical()

Since we now have possible multiple timelines we can store the current logical time local in each self_base_t for each reactor. This will require us to change the API and require a self_base_t pointer as an argument to lf_logical_time.

typedef struct self_base_t {
	struct allocation_record_t *allocations;
	struct reaction_t *executing_reaction;   // The currently executing reaction of the reactor.
#ifdef MODAL_REACTORS
    reactor_mode_state_t _lf__mode_state;    // The current mode (for modal models).
#endif
    tag_t current_logical_tag;
} self_base_t;

instant_t lf_time_logical(self_base_t *self) {
    return self->current_logical_tag.time;
}


interval_t lf_time_logical_elapsed(self_base_t *self) {
    self->current_logical_tag.time- lf_start_time();
}

This means that also lf_schedule will have to take the self_base_t as an argument to know when to schedule it. I think we might want to keep the global variable current_tag. Right before executing a reaction its self->current_logical_tag is set to current_tag. I hope this will work considering microsteps also. But I am actually not sure at the moment. These are also questions we have to tackle if we wanna implement the affiliated execution.

[edwardalee]

@erlingrj 's first attempt to implement LET raises some interesting semantic questions:

LET in Modal Models

The question of how modal models work with LET would be a good discussion point for a Wednesday meeting. My view is that LET reactions have delayed outputs, but still execute logically instantaneously. Hence, the LET reaction completes its execution in the current mode (the mode in which it was triggered), but if the mode is exited before the outputs become visible to downstream reactors, then they will be delayed (if the mode is later is re-entered with a history transition) or discarded (if the mode is not reentered or is reentered with a reset transition). I think this is the implementation we will get by default, with no additional effort.

LET and Requesting a Stop

The question of how lf_request_stop() should behave when called within a LET reaction is another interesting one that bears discussion. This relates to what lf_request_stop() means in federated execution. Our plan at some point (never implemented, I think), was to define lf_request_stop() to mean "Stop as soon as possible" and that it should return the tag at which the stop will occur. In the case of a LET reaction in unfederated execution, I think it could return the tag that other reactors have reached. In the case of an affiliation, it should return the maximum tag that any affiliate has reached (plus one microstep, in each case).

[petervdonovan]

The code block given in section 1, "interrupting reactions," is different from what we discussed today (because it does not use one mutex for each LET reactor). I am not sure which is better. If you do it this way, then maybe the other workers are supposed to go and do something else instead of just blocking on the mutex. In that case, I guess I can see why you would want to use a condition variable, although it does seem weird to use the event_q_changed condition variable for that purpose. Typically, the workers go to sleep when they are out of work. If the real reason why they go to sleep is that they do have work, but their available reactions are blocked due to busy LET reactors, then they do not necessarily have to block using the same mechanism.

Nit: For lf_time_logical, I still do not see why you would put a LET reactor's current logical time on the heap (in its self struct) instead of on the stack (by passing it as a parameter to the reaction), since I like to think of a logical time as a parameter of a specific reaction execution and not of its containing reactor. However, I do not want to waste too much of your time with this opinion since whatever you choose will work and will have the same implications wrt whether the API functions have to be macros.

[erlingrj]

Thanks for this feedback. Yes you are right. The code examples here are a bit outdated. I updated that part to use a reactor-local mutex. If a worker thread is blocked from executing an interrupting reaction the current implementation will block it there until the LET reaction finishes. There are some room for optimization where the worker thread can execute another reaction at the same level. But that would require more work.

As for the current tag. Yes you could have it as a argument to the reaction. But I don't think there would be a significant performance increase by it. But putting it on the self struct of the reactor has the additional advantages of:

1. Code "inside" reactor-c can use the same API lf_time_logical(self) or lf_tag(self) to get the local time of a reactor.
2. The lf_schedule API can remain unchanged. The lf_schedule functions uses the current tag behind the scenes to calculate the tag of the generated event. The current tag must be the one local to the executing reaction. I