FBP in the context of Data Flow

[Harsha]

I recently discovered http://ptolemy.eecs.berkeley.edu/books/Systems/.
In addition to this I have read http://www.jpaulmorrison.com/fbp/ (both versions) and https://leanpub.com/dataflowbook.

The terminologies used offered me a way to clarify FBP.

1. Static Data Flow / Synchronous Data Flow: Unix Pipes, XML Processing, ETL, Batch Processing Systems, ML ...

2. Kahn Process Networks: Hardware Implementations

3. Dynamic Data Flow: FBP

Dynamic Data Flow > KPN > Static Data Flow in terms of expressivity.
Dynamic Data Flow is turing complete.

In other words FBP is a turing complete version of Data Flow. Fairly certain of it.

Discrete Events, FSM / HSM, Workflows and Asynchronous Messaging are not even in the same computation league as FBP.

The only thing common to all the above is the use of Graphical Notation.

Because of big data and AI there has been an explosion of DAG based graphical editors for Static Data Flow.

I suppose the with some effort we can probably answer the commonly asked question, "is FBP like ..."

although I might not be the best person to to write it.

Thoughts ?

[John Cowan]

Harsha scripsit:

> 1. Static Data Flow / Synchronous Data Flow: Unix Pipes, XML Processing,
> ETL, Batch Processing Systems, ML ...

[...]

> 3. Dynamic Data Flow: FBP

Not really the case. Unix pipeline systems can call pipe() or any of its
higher-level functions like popen() and system() to get dynamic behavior.
Per contra, most FBP networks are designed statically, though dynamic
behavior is certainly possible.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org
If I have not seen as far as others, it is because giants were standing
on my shoulders. --Hal Abelson

[Harsha]

Ah, that was a bit unclear on my part.

Dynamic Data Flow is term used and defined in the first book mentioned.

http://ptolemy.eecs.berkeley.edu/books/Systems/ 

[John Cowan]

Harsha scripsit:

> Dynamic Data Flow is term used and defined in the first book mentioned.
> http://ptolemy.eecs.berkeley.edu/books/Systems/

On p. 25 (physical page 41), the terms synchronous (not static) and
dynamic data flow are defined as follows:

The synchronous dataflow (SDF) domain (Lee and Messerschmitt,
1987b) is particularly simple, and is possibly the most used
domain of all. When an actor is executed in SDF, it consumes a
fixed amount of data from each input port, and produces a fixed
amount of data to each output port. An advantage of the SDF domain
is that (as described in Chapter 3) the potential for deadlock and
boundedness can be statically checked, and schedules (including
parallel schedules) can be statically computed. Communication
in this domain is realized with first-in, first-out (FIFO)
queues with fixed finite capacity, and the execution order of
components is statically scheduled. SDF can be timed or untimed,
though it is usually untimed, as suggested in Figure 1.6.

In contrast, the dynamic dataflow (DDF) domain is more
flexible than SDF and computes schedules on the fly. In DDF,
the capacity of the FIFO queues is not bounded. DDF is useful
when communication patterns between actors are dependent on the
data that is passed between actors.

Unix pipes and FBP are intermediate between SDF and DDF as defined here,
because they do make use of fixed finite capacity queues, but consume
and produce unbounded amounts of data (subject to the constraint that
if the data is bigger than the queue it will get fragmented, in the case
of Unix pipes), and therefore cannot be statically scheduled.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org

After fixing the Y2K bug in an application:
WELCOME TO <censored>
DATE: MONDAK, JANUARK 1, 1900

[Harsha]

I was referring to the definition given on Page 93.

The Synchronous dataflow (SDF) domain, also called static dataflow, 1 was introduced by Lee and Messerschmitt (1987b), and is one of the first domains (or models of computation) developed for Ptolemy II. It is a specific type of dataflow model. In dataflow models, actors begin execution (they are fired) when their required data inputs become available. SDF is a relatively simple case of dataflow; the order in which actors are executed is static, and does not depend on the data that is processed (the values of the tokens that are passed between actors).

In Dynamic Data Flow the order in which the Actors are executed depends on the tokens themselves.

BooleanSelect is an example of Dynamic Data Flow.

Here is another short paper with useful references / diagrams 

http://www.artist-embedded.org/docs/Events/2006/MoCC_Zurich/geilen-MoCC06.pdf