Theory

Theoretical background

Dataflow graph can be compared to a Petri Net. Actors corresponds to transitions, actor parameters to places, argument values to tokens. Semafor is a place for plain tokens, and other parameter classes contain colored tokens. In contrast to Petri Nets, each place feeds only one transition.

Each actor has also one hidden place for single plain token which represents access to the actor instance, just like methods of an object have a hidden parameter which references the object's state.

Firing is not an atomic action and consists of following steps:

• when all places are not empty, hidden token is consumed (removed from its place) to prevent parallel executions of the same actor's instance

• actor is submitted to a thread pool executor. Its run method first invokes user defined method act(). This method reads information (colored) tokens from their places, computes values of output tokens and sends them to other actors. Unlike input places, output places are not declared in the actor's body. Programmer can choose any suitable way to pass references to output places to the actor: pass as constructor's arguments, assign to global or instance variables, or send as tokens to the input places.

• then method run() consumes tokens from all inputs (places). If all explicit inputs are still ready, run() calls act() in a loop. If some of explicit inputs are not ready, then run() returns the hidden token to its place and exits.

The hidden token not only represents the state of the token, but also ability to execute the transition procedure. This is the same control token used in Control Flow Graph. Generally, control token represents a processor and its command counter, with all accessible memory. In multithreaded environment, control token is represented by a thread, which is given a physical processor from time to time. This way we can have many more threads than processors. Actor is the next step in minimizing resources used by the control token: it is stripped of the stack for procedure invocations. A stack is given to an actor only for time of execution, just like a thread is given physical processor only when it is ready to run. As a result, we can have many more actors than threads in the same core memory. The price for this is that an actor can run only simple algorithm like

while(true) {
  _wait for all inputs to be filled_;
  act();
}

while a thread can stop and wait for input in different places of its main procedure and in any invoked procedures. If algorithm requires several points of waiting for inputs, each such point must be represented as a separate actor.

Interested in more scientific approach should read the paper Dataflow Process Networks.

A wide range of computational dataflow models and their implementations has been developed in Ptolemy project at Berkely.

Next

Advanced Features: https://github.com/rfqu/df4j/wiki/Advanced