Removing barrier synchronization on levels

[edwardalee]

The NP and GEDF_NP schedulers in the C runtime have a barrier synchronization on levels, where the level of a reaction is its depth in the reaction precedence graph.

In the GEDF scheduler, which has a single reaction queue, when a worker thread encounters a reaction on the reaction queue whose level is higher than the current level of the scheduler, then unless all other threads are idle, this worker goes idle waiting for the current level to advance. If all other threads are idle, then it advances the level. This policy seriously degrades performance and appears to be too stringent.

First, most reactions have at most one other reaction that they depend on (when their level is 0, they do not depend on any other reactions). If their only trigger is the one upstream reaction (no timer or action triggers), then they can safely be executed whenever they appear on the reaction queue. Hence, if the code generator were to mark such reactions, the scheduler could bypass the barrier synchronization and go ahead and execute the reaction.

In reactor_common.c, there is a very effective optimization that executes a downstream reaction immediately if the reaction that just completed is the last reaction that that downstream reaction depends on. However, this optimization is disabled when the just completed reaction has more than one downstream reaction. The rationale is explained in this comment:

                  // In this case, if we were to execute the downstream reaction
                  // immediately without changing any queues, then the second
                  // downstream reaction would be blocked because this reaction
                  // remains on the executing queue. Hence, the optimization
                  // is not valid. Put the candidate reaction on the queue.

However, at least in GEDF, there is no executing queue.

This optimization could therefore be generalized. Of the downstream reactions where the just completed reaction is the last one they depend on, the worker could immediately execute the one with the highest priority (lowest index, which combines deadline and level). The rest could just be put on the reaction queue for other workers to pick up. Moreover, all those that are put on the reaction queue for which the just completed reaction is the last one they depend on could be marked as ready to execute.

When a worker encounters a reaction on the reaction queue with a level higher than zero, it will be one downstream of a completed reaction (or it wouldn't be on the reaction queue) that is either marked ready to execute or has a not-yet-completed upstream reaction. In the former case, the worker can immediately execute it. In the latter case, and only in that case, the worker needs to stall.

I believe this eliminates the need for a notion of a current level and eliminates the need for a level-based barrier synchronization.