Is Intel's Flow Graph the same as Flow Based Programming?

[ifknot]

I am interested in FBP as a potential solution within my domain

*If* it is the case that FBP's Connections and Components are the
nodes and edges of a directed graph then...

Intel's Flow Graph:

http://software.intel.com/en-us/blogs/2011/09/08/the-intel-threading-building-blocks-flow-graph-is-now-fully-supported/

Is Flow Based Programming?

Different syntax same semantics?

It seems a fairly complete solution has anyone used it?

In particular I wondered what Paul thought?

Many thanks

[Paul Morrison]

On 19/05/2012 5:53 PM, ifknot wrote:

It seems a fairly complete solution

This seems to me a symptom of a problem, not a plus :-)  In fact, they seem to have thrown everything they could think of into a big grab-bag...  Unfortunately, it doesn't seem to be well integrated - a good stew should have the ingredients cooked together, rather than just left raw (although I guess it could be a salad)...

Some things that struck me right off the bat:

-  there is a block called "buffer" (actually 4?) - this reminds me of the early days of FBP, when I felt the need to draw the buffers on every line, but then I realized that it didn't add anything to comprehensibility, and in fact just cluttered up the diagram.  In FBP, every line is a buffer. 

- the very first para in the link you sent says, "We now use the name flow graph to emphasize that this feature expresses the control-flow in an application."  What the h*** does this mean?  This smells like an attempt to allay concerns about FBP that you don't have total control of the sequence of instruction execution - this makes old-guard programmers *very* nervous!  But remember we ran a bank using AMPS, and bankers worry about every penny!

- again in the early days of FBP, we considered showing different shapes/icons for different components (I believe ProtoSW still does that), but we gave that up as we wanted people to be able to contribute reusable components at will.  I suppose a half-way house would be to force component developers to assign their component to one of a limited number of categories, each with its own icon...  But why bother?!

- they keep saying "acyclic" - why?  FBP does not require acyclicity (is there such a word?). 

- what does Table 1 mean?  Does anyone understand it?

- I looked at the "wavefront" application, and as far as I can see this does not require any special block types in FBP - or any special handling by the scheduler for that matter.  Each process receives from one or two input ports (depending on how many are connected), does the computation, emits the result and terminates.  In fact, in a multithreaded environment, it seems to me that it is updating the array (something they rather gloss over) that might require some special treatment.   I may try building this app in FBP,  but I won't have time until later in the week.  I'll post the result when I do.  Or it could be left as an exercise for the reader...

I guess I could go on at length as I continue reading, but I am not too encouraged by what I have read so far.  @ifknot, if you have any contacts at Intel, *please* ask them to read my book! 

Here is as good a place as any to repeat my frequent  plaint: why don't people want to try out the existing tools (JavaFBP and C#FBP), and instead insist on building their own?  And BTW these two systems have been in the public domain on SourceForge for years - everyone is welcome to help to improve the scheduling logic, or any other parts of these systems - then we all benefit :-)

Sorry about the rant!

Paul

--
http://www.jpaulmorrison.com/fbp/

[ifknot]

Paul,

many thanks I share your initial impressions in particular the need for block types and sequencer nodes seems to arise because a node of 'unlimited concurrency' (sic) can auto spawn/reentrant on everything it is fed(?)

table 1 is comparing TBB's alternative approaches to concurrency ( a graph of spawned TBB::task vs TBB::pipe_line vs TBB::flow_graph)

historically TBB was centered around lightweight tasks and a poor filter (using void* no less) pipeline set of classes.

flow graph joins the expanding TBB base as a community project. I saw the poster presentation of it a few years back by its then main developer.

tbh, I think they did read your book then used their task model and underlying scheduler as the engine for a FBP approach but threw the nomenclature away in favor of graph idioms and tried to answer criticisms of their filter class and its dreadful void* by introducing typed connections/edges (which is old cos I did it first)

I think FBP versions of the examples would be very interesting.

Ultimately Paul, I would see it as the sincerest form of flattery.

If Intel are interested in pushing FBP, and as it represents the largest section in the new TBB manual pages 163-243 (beating concurrent containers by 9 pages) they really do seem to be interested, your efforts to popularize a FBP approach seems to be paying dividends.

ATB ifknot

[Paul Morrison]

On 21/05/2012 4:49 PM, ifknot wrote:
> many thanks I share your initial impressions in particular the need
> for block types and sequencer nodes seems to arise because a node of
> 'unlimited concurrency' (sic) can auto spawn/reentrant on everything
> it is fed(?)

Thanks for the kind words - I feel a bit better now :-) However, I am
afraid I didn't understand the para above, or the comments about void*.

Still, I have been thinking for a while that the only hope of getting
FBP into the mainstream is for some large company to pick up the
concepts - and we know what large companies do to small promising
concepts :-)

Regards,

Paul

--
http://www.jpaulmorrison.com/fbp/

[Paul Morrison]

On May 21, 4:49 pm, ifknot <ifk...@hotmail.com> wrote:

>
> I think FBP versions of the examples would be very interesting.
>

I did the "wavefront" example in JavaFBP - in JavaFBP you can't have
one output port feeding multiple input ports , plus I have added an
additional output to each node to feed a matrix build component.
Also, I was wrong in my earlier post: every node in the TBB example
has a single input port, which is fine in JavaFBP, so I have kept
that. Here is the network, where each instance of TBBWF receives 0, 1
or 2 values and performs the specified logic:

protected void define() {
/* Letters are columns and numbers are rows */
String[] cols = { "A", "B", "C", "D", "E", "F", "G", "H", "I",
"J" };
int dim = 5;
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
component(cols[i] + j, TBBWF.class);
}
}
component("LM", WriteToConsole.class);
for (int i = 0; i < dim; i++) {
for (int j = 0; j < dim; j++) {
if (i < dim - 1) {
connect(cols[i] + j + ".OUT1", cols[i + 1] + j + ".IN"); //
OUT1 -> right neighbour
}
if (j < dim - 1) {
connect(cols[i] + j + ".OUT2", cols[i] + (j + 1) +
".IN"); // OUT2 -> below neighbour
}
connect(cols[i] + j + ".OUT3", "LM.IN"); // OUT3 -> build
matrix
}
}
}

The code for TBBWF can be provided on request!

[Dan]

I fully agree with Paul regarding his remarks about Intel TBB.
The keyphrase from the short description on that page is: "We now use the name flow graph to emphasize that this feature expresses the control-flow in an application". FBP is about data flow and not control-flow.

Regarding the multiple outputs there is the following remark on the page:http://software.intel.com/en-us/blogs/2011/09/13/using-intel-tbb-40-features-to-simplify-dining-philosophers/ :
"One of the new Community Preview nodes is the multioutput_function_node. This node may be connected to one or more (currently up to 10) ports. The ports are passed as a std::tuple to each execution of the node’s functor, and during each execution the functor may send items to any combination of output ports or to none at all."

A very interesting remark about "Message Passing Protocol" is on their help page: http://threadingbuildingblocks.org/docs/help/ (Chapter: Flow graph):
"In an Intel® TBB flow graph, edges dynamically switch between a push and pull protocol for passing messages. An Intel® TBB flow graph G = ( V, S, L ), where V is the set of nodes, S is the set of edges that are currently using a push protocol, and L is the set of edges that are currently using a pull protocol. For each edge (Vi, Vj), Vi is the predecessor / sender and Vj is the successor / receiver. When in the push set S, messages over an edge are initiated by the sender, which tries to put to the receiver. When in the pull set, messages are initiated by the receiver, which tries to get from the sender."

Despite their paragraph about "control-flow" I can see in their documentation "data flow" graphs and this is what we are looking for.
My last remark is: in order to unleash the power of FBP concepts a specialized FBP declarative language should be used. The code done in any other language (e.g. C++) is very cluttered. I just can not see the data flow in the C++ code used to implement programs with Intel TBB.

Regards,
Dan

[Paul Morrison]

On 24/05/2012 7:46 AM, Dan wrote:

Regarding the multiple outputs there is the following remark on the page:http://software.intel.com/en-us/blogs/2011/09/13/using-intel-tbb-40-features-to-simplify-dining-philosophers/ :
"One of the new Community Preview nodes is the multioutput_function_node. This node may be connected to one or more (currently up to 10) ports. The ports are passed as a std::tuple to each execution of the node’s functor, and during each execution the functor may send items to any combination of output ports or to none at all."

In FBP, I felt it was better not to support one output port feeding multiple input ports because it wasn't clear to me whether that meant picking one of the input ports at random, or sending a copy to each the input ports.  In the latter case, it has to be a "deep" copy (because of the "ownership" rule), and, since FBP supports trees of connected IPs which travel through the network as a single unit, that could potentially become extremely complex.  I may be doing the TBB folks an injustice, but I don't get the impression they have thought these issues through!

--
http://www.jpaulmorrison.com/fbp/

[Paul Morrison]

PS The referenced TBB function somewhat resembles the FBP port array function, but in this case, you still cannot send "an item to a combination of output ports".   That seems very dangerous!  And why do they restrict it to 10?

--
http://www.jpaulmorrison.com/fbp/

[Dan]

I understand the underlying problems of connecting an output port to multiple input ports but there is an idea that it seems it is supported at least by me, Luke Hutchison (see their Google groups flowlang: http://groups.google.com/forum/?fromgroups#!forum/flowlang) and others people. The main idea is that there are two ways of transportation of the message (IP) from one component to another:

1. pushing the information from the sender to the receiver (sender has the initiative)
2. pulling the information from the sender to the receiver (receiver has the initiative)

Luke Hutchison is using the terms: scatter (push) and gather (pull).
I am using the terms: diverge (push) and converge (pull).

In the declarative FBP language I am thinking about, I am using two types of connections:

1. type "material". It is like an empty pipe
   
2. type "potential". It is like an electrical wire

In the first case ("material") the receiver can modify the object (IP) that is coming through the pipe because will own it.
In the second case ("potential") the receiver can not modify the object (IP) because has none (it is just like an electrical potential that you can read but can not modify otherwise you create a short circuit.

These two types of connections simulates two different aspects of the real world:

1. the type "material" (pipe) is like a path of transportation of some material from one location in space to another location in space. It expresses the discontinuity of objects (they are limited by their surface). It shows also the discontinuity of time: the object is at t1 at the beginning of the pipe and at t2 at the end of the pipe.
   
2. the type "potential" (electrical wire) expresses the unlimited speed of transportation, it is like the source (IP from the output port) is in many other places simultaneously but with the restriction to just read (not write). This type of connection expresses the continuity.
   

It is also good to understand the references in each case:

1. the type "material" (discontinuous) has the reference from the sender to the receiver (it is natural) -> PUSH
   
2. the type "potential" (continuous) has the reference from the receiver to the sender (it seems unnatural) -> PULL. The IP goes in the same direction (from the sender to the receiver) but it is pulled.
   

The connection of type (2) has also a big advantage: you can naturally implement lazy programming: some components are evaluated only if it is requested from some other components placed in the downstream. Type (2) simulates the information that is duplicated at the source and travels with high speed (like being simultaneously in different places). Take for instance a person that is speaking in a room. A lot of other persons can receive (listen) the message simultaneously but nobody can do anything to this message.

These types of connections can implement divergent and convergent paths as follows:

1. type "material" implements convergent paths
2. type "potential" implements divergent paths

So, I do not understand why not having the possibility to send IPs (information) from one output port to multiple input ports. After all this is a general case: the same information is used in several places as input for functions (processes, components) but without modifying it. Why to restrict this?

Regards,
Dan Pologea

[Dan]

I just want to mention that you can use the "potential" connections (type 2) also for the convergent paths not just the divergent.
In the case of "material" connections (type 1) you can use them in the divergent paths only if you have a special component that explicitly duplicates the IPs. In fact the divergence is implemented by the component that duplicates the IPs so you don't use the "material" connection to implement the divergence in fact.
Conclusion:

1. type "material" can be used anytime but not in the divergence from an output port. You can use it to send IP that can be transformed (modifed) by the receiver
   
2. type "potential" can be used anytime but not in the case where you want the IP to be independent and transformed (modified) later by the receiver
   

Regards,
Dan

[Brad Cox]

FWIW, it seems to me you're taking on a lot of complexity to support forked pipes that could be eliminated with splitter nodes. Tee joints if you will. Nodes that can't modify objects may be occasionally useful but that's a rare case.

--
Cell: 703-594-1883
Blog: http://bradjcox.blogspot.com
Web: http://virtualschool.edu
Manassas VA 20111

[Paul Morrison]

I agree, Brad. My inclination is always to put a given function into a process, if at all possible, rather than complexifying the underlying logic. I give examples of that in several places in my book - e.g. the NIP function <blush> - it seemed like a good idea at the time!

Sent from Samsung Galaxy Tab (tm) on Rogers

Brad Cox <brad...@gmail.com> wrote:

>FWIW, it seems to me you're taking on a lot of complexity to support forked
>pipes that could be eliminated with splitter nodes. Tee joints if you will.
>Nodes that can't modify objects may be occasionally useful but that's a
>rare case.
>
>On Thu, May 24, 2012 at 4:10 PM, Dan <dpol...@gmail.com> wrote:
>
>> I just want to mention that you can use the "potential" connections (type
>> 2) also for the convergent paths not just the divergent.
>> In the case of "material" connections (type 1) you can use them in the
>> divergent paths only if you have a special component that explicitly
>> duplicates the IPs. In fact the divergence is implemented by the component
>> that duplicates the IPs so you don't use the "material" connection to
>> implement the divergence in fact.
>> Conclusion:
>>

>> 1. type "material" can be used anytime but not in the divergence from

>> an output port. You can use it to send IP that can be transformed (modifed)
>> by the receiver

>> 2. type "potential" can be used anytime but not in the case where you

[Brad Cox]

Regarding this snippet... you're conflating two things that couldn't possibly be more different. In your terms, material is made of atoms, potential is made of electrons. A conveyor belt to haul both makes no engineering sense, other than a superficial resemblance when lines are drawn on paper.

[Dan]

Brad: "FWIW, it seems to me you're taking on a lot of complexity to support forked pipes that could be eliminated with splitter nodes."
I fully agree with you that they can be eliminated with splitter nodes but I don't need splitter nodes just for that. In real life when more people listen to a person's message (utterance) nobody splits it. In fact it is split because different molecules hit everybody's ears but I don't have to simulate that level of detail from the real life.
On the other hand I badly need to simulate the presence (information copy) of one object in different places with the restriction not to modify it (read but not write).
Do you think it is wrong to read the information contained in one variable in many places but without modifying it? It happens all the time, it is not something particular and it does not heart FBP principles. Your read the info (IP), it is used as parameter into a function and you can say that it is "consumed" immediately without having the possibility to modify and pass along.

Regards,
Dan

[Dan]

Hi Paul,

You said: "My inclination is always to put a given function into a process, if at all possible, rather than complexifying the underlying logic."

I do the same as long as I am not forced to complicate things somewhere else in the system. I strongly believe we shouldn't make things more complex than they are and keep them simple. When you have to implement certain complexity, simplifying in one place, another gets more complicated. In the case I have described above it is not more complicated, it is simpler. Having a splitter node is not simpler.
Our digital world is not the real world. In the process of translation / simulation we have to get rid of the most of complexity of the real world keeping in the same time the laws that we want to model.

[Dan]

Brad: "Regarding this snippet... you're conflating two things that couldn't possibly be more different. In your terms, material is made of atoms, potential is made of electrons. A conveyor belt to haul both makes no engineering sense, other than a superficial resemblance when lines are drawn on paper."

When you have an electrical potential you can't do anything to it. You don't need electrons to travel for it. It is just an electric field (for the sake of comparison, electrons create the electrical field but don't need to travel). Is the information you don't modify (you can by overlapping another field).

Regards,
Dan

[Paul Morrison]

Presumably allowing one IP to be sent to several destinations without copying only works within a single shared memory, so it does not scale up across multiple memories.  Also it violates the single ownership principle - unless we state that somehow the whole system becomes the owner...  Surely we would have to tag such IPs as somehow special...   I totally agree that we cannot allow more than one process to modify the shared IP, but it will probably be hard to enforce: the first process that somehow forgets that it doesn't own the IP will cause a lot of grief!  My picture of FBP also gives an IP a well-defined lifetime, so the IP has to somehow survive until everyone is finished with it...  Now I grant that garbage collection will take care of that - but, here again, this "enhancement" weakens some of the principles which, in my experience, make FBP programs so easy to debug and maintain.  However, de gustibus, etc...

Regards,

Paul

--
http://www.jpaulmorrison.com/fbp/

[John Cowan]

Paul Morrison scripsit:

> Presumably allowing one IP to be sent to several destinations
> without copying only works within a single shared memory, so it does
> not scale up across multiple memories. Also it violates the single
> ownership principle - unless we state that somehow the whole system
> becomes the owner... Surely we would have to tag such IPs as
> somehow special... I totally agree that we cannot allow more than
> one process to modify the shared IP, but it will probably be hard to
> enforce: the first process that somehow forgets that it doesn't own
> the IP will cause a lot of grief!

The general solution here, provided the substrate supports it (which the
JVM and CLR definitely do not) is copy-on-write. Each process gets a pointer
to the same IP, but there is a read barrier: any attempt to mutate it
will silently produce another copy private to that process. This is how
fork() on Posix operating systems works: it looks as though the child process
gets a complete copy of the memory of the parent process, but in fact they
share memory, and whichever is the first to change a particular memory page
traps to the OS, which substitutes a writable copy under the table.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org
Uneasy lies the head that wears the Editor's hat! --Eddie Foirbeis Climo

[Ged Byrne]

Hi Paul,

I think the shared ownership principle is the key element that FBP has that others do not.  It's real impact is in the designing of the system.

The question is: is there any situation where multiple copies of an IP are required?  I would say that there is not.

I would say that there are designs that require multiple copies of an IP.  I would say that for any such design there are exists a simpler design that does not.

Inspired by Occams Razor, I woud say of any two designs that provide the same functionality the simpler design is superior.

Therefore enforcing the single ownership principle will lead to a superior design.  

However, thinking about it I am beginning to think that the definition of an IP is to generic for enforcing such a rule.

In Domain Driven Design we have three artifacts for modelling domains:

Entity: An object that is not defined by its attributes, but rather by a thread of continuity and its identity.

Example: Most airlines distinguish each seat uniquely on every flight. Each seat is an entity in this context. However, Southwest Airlines (or EasyJet/RyanAir for Europeans) does not distinguish between every seat; all seats are the same. In this context, a seat is actually a value object.

Value Object: An object that contains attributes but has no conceptual identity. They should be treated as immutable.

Example: When people exchange dollar bills, they generally do not distinguish between each unique bill; they only are concerned about the face value of the dollar bill. In this context, dollar bills are value objects. However, the Federal Reserve may be concerned about each unique bill; in this context each bill would be an entity.

Aggregate: A collection of objects that are bound together by a root entity, otherwise known as an aggregate root. The aggregate root guarantees the consistency of changes being made within the aggregate by forbidding external objects from holding references to its members.

http://en.wikipedia.org/wiki/Domain-driven_design#Building_blocks_of_DDD

At first I thought that an IP is always an Entity.  I has an identity and a thread of continuity.  At any one time only one processor is working with that entity. 

However, this isn't true.  I suspect this is why the name "Entity" was dropped in favour of "IP".  Some IPs are entities, some are not.  A processor that prints a message to the screen takes an IP that is a Value.  A splitter takes an Aggregate.

Is the DDD taxonomy of Entity, Value and Aggregate useful for FBP?  Is there a need to distinguish between Entity IPs, Aggregate IPs and Value IPs.  Does the single ownership principle apply to all three types?

Let's say I have an Invoice entity with an Invoice Total Value.  I have 3 other processors interested in that value.  If there are not dependencies between the 3 do I really need to enforce the fact that they should execute serially? There are benefits to executing them in parallel.

I hope people are able to follow my reasoning.  If not I'll put together a concrete example when I have some time.\

Regards, 

Ged

On 26 May 2012 00:58, Paul Morrison <paul.m...@rogers.com> wrote:

Presumably allowing one IP to be sent to several destinations without copying only works within a single shared memory, so it does not scale up across multiple memories.  

Regards,

[Paul Morrison]

On 28/05/2012 6:14 AM, Ged Byrne wrote:
> Let's say I have an Invoice entity with an Invoice Total Value. I
> have 3 other processors interested in that value. If there are not
> dependencies between the 3 do I really need to enforce the fact that
> they should execute serially? There are benefits to executing them in
> parallel.

Hi Ged, I like this analysis - it seems to match my intuitions about
application design. In the above paragraph however, pragmatically, I
probably wouldn't make the total value a separate IP anyway - it
probably gets copied into an IP which is a report line or report page,
and maybe also into an IP which is a statistics or log record. I
believe this fits with your analysis above. I remember noticing in the
early days of FBP that the majority of values are in fact attributes (or
values) in IPs - this seemed to me to contrast with old-style programs
where you often just get a pile of variables in a program's working
storage. Based on your description, DDD seems a good fit with FBP,
but, when I Googled it, the first hit was
http://en.wikipedia.org/wiki/Responsibility-driven_design . Have you
given any thought to how these two (apparently antithetical) approaches
apply to FBP - maybe they both fit, and aren't antithetical at all...?!

John, the copy-on-write approach is cute, but a) I don't know how you
would generalize it to IP trees, and b) as Ged says, it's usually not
even necessary, or even desirable. If two initially identical IPs are
wandering through an FBP network, which eventually has the "real" data?
This seems to me a very dangerous situation - and one that I don't
recollect ever having to do in the huge banking project we implemented
using FBP (AMPS).

[John Cowan]

Paul Morrison scripsit:

> John, the copy-on-write approach is cute, but a) I don't know how
> you would generalize it to IP trees,

The same way: you mark the whole tree read-only and then clone elements
as needed. Remember that this relies on being able to substitute the
new copy for the shared original *transparently*. It's strictly blue-sky
as of now, for no OS I know of supports page sizes smaller than 4K.

> If two initially identical IPs are wandering through an FBP network,
> which eventually has the "real" data?

Presumably if you are broadcasting an IP to multiple destinations, you
*expect* them to have different fates. This is really no different
from having a broadcasting component with an array of outputs: the
system normally neither knows nor cares exactly which recipient gets
the original IP.

Indeed, DrawIP could insert such a component whenever the user draws a
fan-out diagram.

--
A few times, I did some exuberant stomping about, John Cowan
like a hippo auditioning for Riverdance, though co...@ccil.org
I stopped when I thought I heard something at http://ccil.org/~cowan
the far side of the room falling over in rhythm
with my feet. --Joseph Zitt

[Ralf Westphal]

I´d make copying or not copying data a non-issue for FBP.
Leave the decision to the application. If processes need to see there
own writable copies use a Software Transactional Memory (STM).
Deep copying is and expensive operation. So that at least should not
be the default.

As for the message, though, I vote for "each process gets its own
message copies". (Just the message data, not the data payload.)

[paul.tarvydas]

I came at this from a completely different perspective - real time control, embedded systems and EE (rather than banking).

We found "single output to multiple inputs" (multi-drop) to be a necessity.

If you look at the second diagram ("Hierarchical Schematics") at www.visualframeworksinc.com , you'll see many uses of this concept (this is real code that went into a smart meter - "software IC's" :-).

The easy cases : "reset" lines, "config", busses, etc.


The mechanics to support this concept are not all that hard:

1) many of the IP's ("events" in our lingo) were "scalar", hence, copying was not an issue

2) we left the issue of copying non-scalar data up in the air

3) the event delivery mechanism works in two passes -

- acquire a lock on the input queue of every receiver,
- then, drop the data into each of the queues
- (then unlock all the queues and kick some receiver into action)


The above guarantees correct "time semantics" - every receiver sees the messages in the same order.

The technique can be further optimized for parallelism by using "deferred signalling" - use an output queue to hold all output events until the software component is "finished", then unlock the component readying it to receive new inputs, and then process the output queue.

All of the above can be implemented with one stack (per core), no processes (nor threads) and without an O/S (this stuff rode bare-back on the embedded cpu's).

The components appear to be running in their own "processes", made asynchronous by their input and output queues (all concurrency "issues" are pushed onto the event delivery kernel and queue locks).

The technique also works "on top of" an O/S - spawn one process (per core) and have it encapsulate all of the components and run the event delivery mechanism inside.

(And, it was also used in a distributed manner, pc to pc and pc to embedded test bed).


My conclusion is that it depends on the architect and problem domain.  Bank/enterprise apps can be created as mostly serial chains of components, whereas reactive systems (embedded systems, gui's, etc) benefit from the ability to use multi-drop.

pt