I have run across a funny issue in coding more complex images like this. In most of the modules, I want every input to potentially trigger a calculation (and output). But if several inputs change at the same time, I don't want to .
This isn't optimal, because each module is now slowing down the data-flow. You can also see that in 14:transform, the image is rendered twice per second anyway, as the rotate input is hit before the image from 5:text makes it (because 7:string-join and 5:text modules have the timeout as well).
Pure Data uses "hot" inputs. I could do something like this that would only send the data when a "send" input is hit, but that would make for more complicated graphs.
Is there a better or standard data-flow way to solve this?
If I have understood your problem well then my comments could be useful and I think this is a general issue. This is a classical problem of race condition as in electronics ( http://en.wikipedia.org/wiki/Race_condition). Please be aware that this kind of issue is more similar to the race condition as in electronics and not in computing (http://en.wikipedia.org/wiki/Race_condition#Computing). Even if the problem is the same (i.e. race condition), in computing it is perceived as specific to imperative languages that do operations upon shared states. FBP is really similar to electronics. The difference is control flow (imperative programming) versus data flow (declarative programming like FBP).
In electronics a way to solve this kind of problem is to create the final circuit using Karnaugh maps (http://en.wikipedia.org/wiki/Karnaugh_map). Our software program case is not suitable for a similar solution (i.e. the hardware is boolean at its lowest level but the software is a higher more functional level).
I have proposed a possible solution into another post of mine regarding types of connections (see: https://groups.google.com/d/msg/flow-based-programming/JkInzGvySAg/EH... the other post related). Even if at first glance it does not address your problem in fact it was exactly the problem I have started with in mind. It seems the depth of the consequences of what I have said in that post was not clearly understood. Please read first that post and come back here.
I want to translate the topic of that post to your problem. In any network (FBP in our case) there is a "wave of change" (wave of data triggering changes) expressed as IPs (events, messages) that travel through the network. Timing is an issue and we want to avoid it nevertheless we have to take it into account. Time is order.
In your case the network is dealing with discreet events (e.g. seconds ticks) that propagate and generate other events (i.e. IPs generated). The problem shows up when these events converge to a processor (same FBP node). The main questions are:
1. When exactly to start the evaluation of a process (or subprocess)? 2. Did all the "necessary" IPs (events, messages) arrived? 3. Are the IPs in sync? 4. Are they related to the same "logic" wave?
Normally the logic of your program that is the data flow network itself should not include all this problematics that is an "implementation detail" of the underlying system but when the time is part of the logic then the time is part of your data.
In that post of mine I have proposed "material" (discreet) connections and "potential" (continuous) connections. Whenever the logic says that the outputs of a component are continuously changing as its inputs are changing then you connect all the subcomponents that contribute to that process with "potential" connections (like in hardware with electrical wires). Of course the compiled software program will not act continuously but the sampling will be given by all the events (IPs) that are traveling through the (other) "material" connections. The catch is: all the potential connections are evaluated opposite as materials ones i.e. pull data versus push data. "Pull" case is similar to the classical imperative and functional languages were the parameters of a function are pulled from the environment exactly when the function is called (control flow) as opposed to the reactive programming where evaluation is triggered when the data arrives (data flow).
All that said, it means that the final block (node: "combine") should update the input data only when some sampling event (i.e. like a clock in electronics) is arriving through a "material" connection. This kind of differentiation between what I have called "material" and "potential" connections helps a lot in implementing lazy programming too i.e. not evaluating some nodes (subnetworks) until it will be really necessary the case (i.e. somewhere in the downstream there is a "pull" request). Also this is useful to implement "if...then..else" or other conditionals without evaluating all the paths.
Unfortunately this kind of "solution" is system related (FBP compiler, runtime system or interpreter). If you don't have it then you can not use this kind of features when you try to implement your network of components.
Instead of trying to have a long post here it would be nice to read the other materials referred in that post (for instance "flowlang" group of discussions).
In the end I am curious if my comments are related to your issue or I was just rambling around :).
> I have run across a funny issue in coding more complex images like this. > In most of the modules, I want every input to potentially trigger a > calculation (and output). But if several inputs change at the same time, I > don't want to .
> This isn't optimal, because each module is now slowing down the data-flow. > You can also see that in 14:transform, the image is rendered twice per > second anyway, as the rotate input is hit before the image from 5:text > makes it (because 7:string-join and 5:text modules have the timeout as > well).
> Pure Data uses "hot" inputs. I could do something like this that would > only send the data when a "send" input is hit, but that would make for more > complicated graphs.
> Is there a better or standard data-flow way to solve this?
On Sunday, June 17, 2012 5:17:48 PM UTC+3, Dan wrote:
> If I have understood your problem well then my comments could be useful > and I think this is a general issue. > This is a classical problem of race condition as in electronics ( > http://en.wikipedia.org/wiki/Race_condition). Please be aware that this > kind of issue is more similar to the race condition as in electronics and > not in computing (http://en.wikipedia.org/wiki/Race_condition#Computing). > Even if the problem is the same (i.e. race condition), in computing it is > perceived as specific to imperative languages that do operations upon > shared states. FBP is really similar to electronics. The difference is > control flow (imperative programming) versus data flow (declarative > programming like FBP).
> In electronics a way to solve this kind of problem is to create the final > circuit using Karnaugh maps (http://en.wikipedia.org/wiki/Karnaugh_map). > Our software program case is not suitable for a similar solution (i.e. the > hardware is boolean at its lowest level but the software is a higher more > functional level).
> I have proposed a possible solution into another post of mine regarding > types of connections (see: > https://groups.google.com/d/msg/flow-based-programming/JkInzGvySAg/EH... the other post related). Even if at first glance it does not address > your problem in fact it was exactly the problem I have started with in > mind. It seems the depth of the consequences of what I have said in that > post was not clearly understood. Please read first that post and come back > here.
> I want to translate the topic of that post to your problem. In any network > (FBP in our case) there is a "wave of change" (wave of data triggering > changes) expressed as IPs (events, messages) that travel through the > network. Timing is an issue and we want to avoid it nevertheless we have to > take it into account. Time is order.
> In your case the network is dealing with discreet events (e.g. seconds > ticks) that propagate and generate other events (i.e. IPs generated). The > problem shows up when these events converge to a processor (same FBP node). > The main questions are:
> 1. When exactly to start the evaluation of a process (or subprocess)? > 2. Did all the "necessary" IPs (events, messages) arrived? > 3. Are the IPs in sync? > 4. Are they related to the same "logic" wave?
> Normally the logic of your program that is the data flow network itself > should not include all this problematics that is an "implementation detail" > of the underlying system but when the time is part of the logic then the > time is part of your data.
> In that post of mine I have proposed "material" (discreet) connections and > "potential" (continuous) connections. Whenever the logic says that the > outputs of a component are continuously changing as its inputs are changing > then you connect all the subcomponents that contribute to that process with > "potential" connections (like in hardware with electrical wires). > Of course the compiled software program will not act continuously but the > sampling will be given by all the events (IPs) that are traveling through > the (other) "material" connections. The catch is: all the potential > connections are evaluated opposite as materials ones i.e. pull data versus > push data. "Pull" case is similar to the classical imperative and > functional languages were the parameters of a function are pulled from the > environment exactly when the function is called (control flow) as opposed > to the reactive programming where evaluation is triggered when the data > arrives (data flow).
> All that said, it means that the final block (node: "combine") should > update the input data only when some sampling event (i.e. like a clock in > electronics) is arriving through a "material" connection. This kind of > differentiation between what I have called "material" and "potential" > connections helps a lot in implementing lazy programming too i.e. not > evaluating some nodes (subnetworks) until it will be really necessary the > case (i.e. somewhere in the downstream there is a "pull" request). Also > this is useful to implement "if...then..else" or other conditionals without > evaluating all the paths.
> Unfortunately this kind of "solution" is system related (FBP compiler, > runtime system or interpreter). If you don't have it then you can not use > this kind of features when you try to implement your network of components.
> Instead of trying to have a long post here it would be nice to read the > other materials referred in that post (for instance "flowlang" group of > discussions).
> In the end I am curious if my comments are related to your issue or I was > just rambling around :).
> Regards, > Dan
> On Saturday, June 16, 2012 12:04:54 AM UTC+3, Forrest Oliphant wrote:
>> I have run across a funny issue in coding more complex images like this. >> In most of the modules, I want every input to potentially trigger a >> calculation (and output). But if several inputs change at the same time, I >> don't want to .
>> This isn't optimal, because each module is now slowing down the >> data-flow. You can also see that in 14:transform, the image is rendered >> twice per second anyway, as the rotate input is hit before the image from >> 5:text makes it (because 7:string-join and 5:text modules have the timeout >> as well).
>> Pure Data uses "hot" inputs. I could do something like this that would >> only send the data when a "send" input is hit, but that would make for more >> complicated graphs.
>> Is there a better or standard data-flow way to solve this?
Here's a newbe perspective from a programmer who has not thought about FPB in a while.
It seems that there is an implicit flow on information back through the network. Let's say final node want's to update it's display X times a second. After composing and displaying the image it signals that it can accept new inputs. This flows back through the network to the producer nodes at the beginning of the network. These guy's produce fresh data the flows forward through the network. That way no one is actually doing any computation until it is needed.
On Fri, Jul 20, 2012 at 9:51 AM, Patrick Down <patrick.d...@gmail.com>wrote:
> Here's a newbe perspective from a programmer who has not thought about FPB
> in a while.
> It seems that there is an implicit flow on information back through the
> network. Let's say final node want's to update it's display X times a
> second. After composing and displaying the image it signals that it can
> accept new inputs. This flows back through the network to the producer
> nodes at the beginning of the network. These guy's produce fresh data the
> flows forward through the network. That way no one is actually doing
> any computation until it is needed.
Patrick Down said: "This flows back through the network to the producer nodes at the beginning of the network. These guy's produce fresh data the flows forward through the network. That way no one is actually doing any computation until it is needed."
The mechanism of what I have described as "potential" connections is exactly this: the processes (i.e. components evaluations) are triggered from downstream toward upstream as needed (conventionally from right to left). Remember that the flow (data flow) is from left to right, only triggering in this case is from right to left (i.e. control flow). In this case the control flow tells how much data will be produced.
The IPs flows logically from left to right (it is just a drawing convention in order to understand better). In fact it is so similar to how the actual imperative languages are doing the evaluation of the functions (in the parameter place is a function call that has a parameter that is a function call and so on). Example: in->A -> B -> C->out; //FBP out = C(B(A(in))); // classic imperative The example above is simple. Imagine you have branches and "diamond shape" networks that we have discussed about some time ago. The bottom line is: we are discussing about "PUSH" vs. "PULL" but this is not just an implementation techniques; it is affecting the logic and the behavior.
Maybe that post deserves a second look from this perspective.
Yes, it is exactly lazy evaluation. Execute as needed. In the case I have described, the "potential" connections are "executed" (i.e. pull the IPs as oppose to push) only when they are triggered somewhere in the downstream, i.e. when an IP that flows through a parallel (other path) "material" connection will trigger the evaluation of a network of "potentially" interconnected components in the upstream.
Hi Forrest, I just want to make sure I understand your problem. I assume you have a process receiving inputs (IPs) at multiple input ports. If 2 or more inputs arrive at different input ports at the same time (?), you want to process - just one, or neither? Also, is it only when they arrive at exactly the same time, or within some specified time interval?
I suspect the latter because you talk about 1000/30 ms... but I am afraid I don't know what that means. Do you mean 33.333 ms?! Or does the slash mean something different? Once I get your answers, I can do some thinking about your problem. :-)
> I have run across a funny issue in coding more complex images like this. > In most of the modules, I want every input to potentially trigger a > calculation (and output). But if several inputs change at the same time, I > don't want to .
> This isn't optimal, because each module is now slowing down the data-flow. > You can also see that in 14:transform, the image is rendered twice per > second anyway, as the rotate input is hit before the image from 5:text > makes it (because 7:string-join and 5:text modules have the timeout as > well).
> Pure Data uses "hot" inputs. I could do something like this that would > only send the data when a "send" input is hit, but that would make for more > complicated graphs.
> Is there a better or standard data-flow way to solve this?
There are multiple inputs [background, image, scale, translate, rotate] that affect one output [image]. Changing any of them should change the output.
I ended up relying on the new requestAnimationFrame<https://developer.mozilla.org/en/DOM/window.requestAnimationFrame>browser function. This is a loop that runs at 60htz (or tries), but only if the browser window is visible. All hot inputs set a flag to render on the next requestAnimationFrame call.
If you switch to a new tab and back, you'll see the jump as it starts rendering again.
So, I just went with the "hot" input method, but with requestAnimationFrame it won't try to do more redraws than the refresh rate of the screen. There are still race condition issues, but I'm just ignoring them for now. The solutions seem too complicated for my goal of prioritizing simplicity in the UX.
On Saturday, July 21, 2012 4:49:09 PM UTC+3, Paul Morrison wrote:
> Hi Forrest, I just want to make sure I understand your problem. I assume > you have a process receiving inputs (IPs) at multiple input ports. If 2 or > more inputs arrive at different input ports at the same time (?), you want > to process - just one, or neither? Also, is it only when they arrive at > exactly the same time, or within some specified time interval?
> I suspect the latter because you talk about 1000/30 ms... but I am afraid > I don't know what that means. Do you mean 33.333 ms?! Or does the slash > mean something different? Once I get your answers, I can do some thinking > about your problem. :-)
> On Friday, June 15, 2012 5:04:54 PM UTC-4, Forrest Oliphant wrote:
>> I have run across a funny issue in coding more complex images like this. >> In most of the modules, I want every input to potentially trigger a >> calculation (and output). But if several inputs change at the same time, I >> don't want to .
>> This isn't optimal, because each module is now slowing down the >> data-flow. You can also see that in 14:transform, the image is rendered >> twice per second anyway, as the rotate input is hit before the image from >> 5:text makes it (because 7:string-join and 5:text modules have the timeout >> as well).
>> Pure Data uses "hot" inputs. I could do something like this that would >> only send the data when a "send" input is hit, but that would make for more >> complicated graphs.
>> Is there a better or standard data-flow way to solve this?
I am not sure I got an answer to my question, but I gather that you have a picture that is being refreshed at 60htz, which I assume works out to 16.67 ms per refresh - I think we can do it with FBP, without having to add any new function to the scheduler.../if/ I have understood correctly what you are trying to do.
The first thing is that, in FBP, you don't want to be waiting on two or more input ports, as you could be waiting on one input port while IPs pile up at another - this is a recipe for a deadlock. Your published solution I believe requires a non-supendable receive, which is not supported in any of the FBP implementations I've worked on --- nor needed IMO.
So first I would suggest you bring all of a process's inputs into a single input port, appropriately tagged so you can tell what they are. IPs arriving at a single input port fed by multiple output ports are handled on a first-come, first-served basis, so you don't risk deadlock.
Now, if I understand your application correctly, you want to make sure the diagram is updated at 60htz (or less), but you are worried that too many inputs may cause you to miss a clock tick. A somewhat similar problem is described in Chap. 19 of the 2nd edition, in the context of checkpointing. It's Chap. 20 in the first edition - http://www.jpaulmorrison.com/fbp/checkpt.shtml .
So, I am suggesting that you feed a series of timer IPs (generated by a separate timer process) into the same input port, giving you an input stream looking like Diagram 20.8 in the 1st edition of my book, or Diagram 19.6 in the 2nd edition. You don't have to drive the display using the clock ticks, although you could if the non-timer data IPs are relatively infrequent compared to the clock ticks, but I think you could just as well check the time after each IP is received and do the display if the time interval (16.67 ms) has expired. Injecting the clock tick IPs into the merged stream should ensure that you don't miss a refresh because you are waiting for some other kind of data.
What do you - or anyone else who is interested - think?!
> There are multiple inputs [background, image, scale, translate, > rotate] that affect one output [image]. Changing any of them should > change the output.
> I ended up relying on the new requestAnimationFrame > <https://developer.mozilla.org/en/DOM/window.requestAnimationFrame> > browser function. This is a loop that runs at 60htz (or tries), but > only if the browser window is visible. All hot inputs set a flag to > render on the next requestAnimationFrame call.
> If you switch to a new tab and back, you'll see the jump as it starts > rendering again.
> So, I just went with the "hot" input method, but with > requestAnimationFrame it won't try to do more redraws than the refresh > rate of the screen. There are still race condition issues, but I'm > just ignoring them for now. The solutions seem too complicated for my > goal of prioritizing simplicity in the UX.
> - Forrest
> On Saturday, July 21, 2012 4:49:09 PM UTC+3, Paul Morrison wrote:
> Hi Forrest, I just want to make sure I understand your problem. I
> assume you have a process receiving inputs (IPs) at multiple input
> ports. If 2 or more inputs arrive at different input ports at the
> same time (?), you want to process - just one, or neither? Also,
> is it only when they arrive at exactly the same time, or within
> some specified time interval?
> I suspect the latter because you talk about 1000/30 ms... but I am
> afraid I don't know what that means. Do you mean 33.333 ms?! Or
> does the slash mean something different? Once I get your answers,
> I can do some thinking about your problem. :-)
> On Friday, June 15, 2012 5:04:54 PM UTC-4, Forrest Oliphant wrote:
> I have run across a funny issue in coding more complex images
> like this. In most of the modules, I want every input to
> potentially trigger a calculation (and output). But if several
> inputs change at the same time, I don't want to .
> This isn't optimal, because each module is now slowing down
> the data-flow. You can also see that in 14:transform, the
> image is rendered twice per second anyway, as the rotate input
> is hit before the image from 5:text makes it (because
> 7:string-join and 5:text modules have the timeout as well).
> Pure Data uses "hot" inputs. I could do something like this
> that would only send the data when a "send" input is hit, but
> that would make for more complicated graphs.
> Is there a better or standard data-flow way to solve this?
In your example, the clock feeds into string-join (to make the text like
12:34:56) and color-hsla (to make the color). You then combine this
text and color in the text component, producing a rendered image of that
text in that color.
As I understand, your 'text' component might render the image twice,
because both inputs receive a signal at slightly different times.
But you want it to render only once, since they both came from the same
clock tick signal originally.
So, the evaluator should be configured to do as much work 'upstream' as
much as it can, before it updates a 'downstream' component having several
inputs.
Processing can continue to the downstream component if:
1. all inputs have been signalled, or
2. no further processing can be done upstream at that time
How best to implement that, I'm not exactly sure.
You're working with a different sort of network, compared to regular
FBP. It seems closer to a functional / relational / constraint logic
sort of network.
A simple, effective solution is to add a "touch" event to each dataflow.
When you know an update is coming soon, you send a touch event. Touches
propagate through the network independently of the primary data updates.
For linear dataflows, the touches are a simple propagation (see a touch?
send a touch). For dataflows that receive updates from multiple sources,
e.g. A & B -> C: we send a touch on C the first time we see a touch on A
or B. If B is touched, and we receive an update on A (or vice versa), we
wait to propagate. For dataflows that send updates to multiple sources,
e.g. A -> B & C, we might touch to both B&C after receiving touch on A.
We might also introduce a "cancel" message to account for those cases when
we've touched but decide (due to filtering or splitting) that we don't need
to update a given task. The important bit is that we always send an update
at some point after sending a touch. The idea can be modified easily with
features like counting, indicating how many updates are coming, etc.
Managing these touches has an overhead proportional to the size of the
network (though you can introduce barriers or model partitions across which
touches are dropped). But the costs are small, predictable - and the win
can be enormous, eliminating worst-case exponential costs in networks that
merge many data sources.
Regards,
David Barbour
On Fri, Jun 15, 2012 at 2:04 PM, Forrest Oliphant <auf...@forresto.com>wrote:
> I have run across a funny issue in coding more complex images like this.
> In most of the modules, I want every input to potentially trigger a
> calculation (and output). But if several inputs change at the same time, I
> don't want to .
> This isn't optimal, because each module is now slowing down the data-flow.
> You can also see that in 14:transform, the image is rendered twice per
> second anyway, as the rotate input is hit before the image from 5:text
> makes it (because 7:string-join and 5:text modules have the timeout as
> well).
> Pure Data uses "hot" inputs. I could do something like this that would
> only send the data when a "send" input is hit, but that would make for more
> complicated graphs.
> Is there a better or standard data-flow way to solve this?
Interesting idea, David. However, in the FBP context, I think you are either introducing a second network of essentially zero-capacity connections, or you are sacrificing configurability (if A and B both "know about" C, without going through the network). JavaFBP does have a component priority facility, which might be worth trying out. People have suggested adding a priority attribute to the IPs (queue-jumpers), but IMO that makes the application as a whole less reliable.
Either way, IMO it is much simpler to do what I suggested earlier - did you try it, Forrest? - which is to feed multiple output ports into a single input port. If you want really fast response, you can use a connection of capacity 1. If you want better than that, I suspect you are going to have to build your own scheduler!
On Saturday, July 28, 2012 11:57:39 AM UTC-4, dmbarbour wrote:
> Hello Forrest,
> A simple, effective solution is to add a "touch" event to each dataflow. > When you know an update is coming soon, you send a touch event. Touches > propagate through the network independently of the primary data updates.
> For linear dataflows, the touches are a simple propagation (see a touch? > send a touch). For dataflows that receive updates from multiple sources, > e.g. A & B -> C: we send a touch on C the first time we see a touch on A > or B. If B is touched, and we receive an update on A (or vice versa), we > wait to propagate. For dataflows that send updates to multiple sources, > e.g. A -> B & C, we might touch to both B&C after receiving touch on A.
> We might also introduce a "cancel" message to account for those cases when > we've touched but decide (due to filtering or splitting) that we don't need > to update a given task. The important bit is that we always send an update > at some point after sending a touch. The idea can be modified easily with > features like counting, indicating how many updates are coming, etc.
> Managing these touches has an overhead proportional to the size of the > network (though you can introduce barriers or model partitions across which > touches are dropped). But the costs are small, predictable - and the win > can be enormous, eliminating worst-case exponential costs in networks that > merge many data sources.
On Sat, Jul 28, 2012 at 11:23 AM, Paul Morrison <paul.morri...@rogers.com>wrote:
> Interesting idea, David. However, in the FBP context, I think you are
> either introducing a second network of essentially zero-capacity
> connections, or you are sacrificing configurability (if A and B both "know
> about" C, without going through the network). JavaFBP does have a
> component priority facility, which might be worth trying out. People have
> suggested adding a priority attribute to the IPs (queue-jumpers), but IMO
> that makes the application as a whole less reliable.
Excuse my notation. (A&B -> C) indicates a process that receives IPs on
ports labeled A and B, and pushes IPs on a port labeled C. The logic, the
FBP process, is hidden in the arrow. The arrow is a self-enclosed entity;
it doesn't know anything about the context in which it is used.
I am not suggesting a second network, nor am I sacrificing configurability.
Indeed, my suggestion can be directly modeled in FBP. However, some IPs
would serve as `control`, e.g. for touch or cancel-touch.
> Either way, IMO it is much simpler to do what I suggested earlier - did
> you try it, Forrest? - which is to feed multiple output ports into a
> single input port. If you want really fast response, you can use a
> connection of capacity 1. If you want better than that, I suspect you are
> going to have to build your own scheduler!
I believe you misunderstood the problem Forrest is attempting to solve. You
earlier wrote:
I assume you have a process receiving inputs (IPs) at multiple input ports.
> If 2 or more inputs arrive at different input ports at the same time (?),
> you want to process - just one, or neither?
Forrest wants to process both inputs, but wants to process them together
(rather than one at a time). E.g. if the time on the clock and the color of
the clock change at approximately the same time, we would want to send only
one "Render" IP that addresses change in both color and clock, as opposed
to sending two "Render" IPs in short succession.
Forrest's current solution is a makeshift hack: he uses timeouts to
estimate when IPs arrive at "the same time". This has the seriously
unfortunate consequence of increasing system latency at each step ("each
module is now slowing down the data-flow"). OTOH, the other choice of
sending an IP whenever we receive an IP to send updates
I'm from the reactive (FRP, synchronous reactive, etc.) community, never
have developed FBP. But Forrest is essentially modeling a reactive system
in FBP, and the problem he describes is a familiar one. (See a related
discussion at LtU: http://lambda-the-ultimate.org/node/4453#comment-69657).
While Forrest's ad-hoc clocked approach is semantically dubious and
drastically increases latency, it does avoid costs that are potentially
exponential in the size of the network.
The `touch` approach I described adds no latency, and allows us to stick
with composition of opaque processes. Whereas other traditional solutions
(such as topological sorts) could avoid the overheads of control messages,
but would require a more whitebox compilation.
> On Saturday, July 28, 2012 11:57:39 AM UTC-4, dmbarbour wrote:
>> Hello Forrest,
>> A simple, effective solution is to add a "touch" event to each dataflow.
>> When you know an update is coming soon, you send a touch event. Touches
>> propagate through the network independently of the primary data updates.
>> For linear dataflows, the touches are a simple propagation (see a touch?
>> send a touch). For dataflows that receive updates from multiple sources,
>> e.g. A & B -> C: we send a touch on C the first time we see a touch on A
>> or B. If B is touched, and we receive an update on A (or vice versa), we
>> wait to propagate. For dataflows that send updates to multiple sources,
>> e.g. A -> B & C, we might touch to both B&C after receiving touch on A.
>> We might also introduce a "cancel" message to account for those cases
>> when we've touched but decide (due to filtering or splitting) that we don't
>> need to update a given task. The important bit is that we always send an
>> update at some point after sending a touch. The idea can be modified easily
>> with features like counting, indicating how many updates are coming, etc.
>> Managing these touches has an overhead proportional to the size of the
>> network (though you can introduce barriers or model partitions across which
>> touches are dropped). But the costs are small, predictable - and the win
>> can be enormous, eliminating worst-case exponential costs in networks that
>> merge many data sources.
> I believe you misunderstood the problem Forrest is attempting to > solve. You earlier wrote:
> I assume you have a process receiving inputs (IPs) at multiple
> input ports. If 2 or more inputs arrive at different input ports
> at the same time (?), you want to process - just one, or neither?
> Forrest wants to process both inputs, but wants to process them > together (rather than one at a time). E.g. if the time on the clock > and the color of the clock change at approximately the same time, we > would want to send only one "Render" IP that addresses change in both > color and clock, as opposed to sending two "Render" IPs in short > succession.
You're right - I did misunderstand! OK, so how about taking the same approach that I suggested, with multiple streams feeding into one input port, plus a stream of clock ticks feeding into it as well... but just output one "consolidated" IP for clock ticks preceded by non-clock tick IPs.
If you don't like this, perhaps you could post some code for the touch solution - I'm afraid I am having trouble visualizing it... :-)
Your approach to clocking may be cleaner than Forrest's, but still
introduces considerable latency. E.g. if we chained 100 FBP processes in a
row, and each was pushing only on clock signals at 30Hz, we'd expect 3.33
seconds to see a change on one end reach the other. There is, of course,
always some latency involved in such chains, but avoiding a clocked logic
could cut the latency down to milliseconds even for 100 processes.
The touch solution is simple enough, and does not limit latency. If I were
modeling it in procedural it might look like:
process(iport A, iport B, oport C) {
var a_touched = false
var a_value = ""
var b_touched = false
var b_value = ""
while(true) {
var started_with_touch = (a_touched || b_touched);
wait([A,B]) // returns when data is available
while(!empty(A)) {
var v = take(A)
if(v == "touch") {
a_touched = true
} else {
a_touched = false
a_value = v
}
}
while(!empty(B)) {
var v = take(B)
if(v == "touch") {
b_touched = true
} else {
b_touched = false
b_value = v
}
}
var ended_with_touch = (a_touched || b_touched);
if (ended_with_touch && !started_with_touch)
put(C, "touch")
else if(!ended_with_touch)
put(C, foo(a_value,b_value))
}
}
Obviously, a lot here could be cleaned up, abstracted, made more
declarative, etc. And this only describes what happens in one specific
process (of type A&B->C), as opposed to the network effects. There is no
obvious change on the FBP network for including touches; it'd be a
discipline that each process supports, which makes it a good candidate for
adding to port communication protocols in general.
What happens at the network level, then, is that these touch values
propagate through the network ahead of the changes (usually not very far
ahead), and they can stall certain processes. Where touch is most
profitable is when one source results in multiple outputs (C->D&E) that may
be processed in parallel before zipping back together down the line.
Regards,
Dave
On Sat, Jul 28, 2012 at 2:18 PM, Paul Morrison <paul.morri...@rogers.com>wrote:
> I believe you misunderstood the problem Forrest is attempting to solve.
> You earlier wrote:
> I assume you have a process receiving inputs (IPs) at multiple input
>> ports. If 2 or more inputs arrive at different input ports at the same time
>> (?), you want to process - just one, or neither?
> Forrest wants to process both inputs, but wants to process them together
> (rather than one at a time). E.g. if the time on the clock and the color of
> the clock change at approximately the same time, we would want to send only
> one "Render" IP that addresses change in both color and clock, as opposed
> to sending two "Render" IPs in short succession.
> You're right - I did misunderstand! OK, so how about taking the same
> approach that I suggested, with multiple streams feeding into one input
> port, plus a stream of clock ticks feeding into it as well... but just
> output one "consolidated" IP for clock ticks preceded by non-clock tick
> IPs.
> If you don't like this, perhaps you could post some code for the touch
> solution - I'm afraid I am having trouble visualizing it... :-)
Paul: "So first I would suggest you bring all of a process's inputs into a single input port, appropriately tagged so you can tell what they are. IPs arriving at a single input port fed by multiple output ports are handled on a first-come, first-served basis, so you don't risk deadlock."
First of all one port has one single role. If we need to pile different IPs with different types and roles and push them into a single port it means we have a "technical issue". For me it does not make any sense.
The main problem here is that we want to compute the final result (a rendered image in our case) at a pace dictated by a clock tick. The rhythm of the incoming IPs used to compute the image is different than the clock tick used to render that image. The inability to deal with this difference in "data cadence" creates the problem in the first place. That's why I have described in my previous post that the IPs should be pulled only when needed (and latched) instead of pushed. Yes, some of the (input) IPs might be thrown away in the process. This remark is related to what a good FBP solution we can provide and not to practical aspects which Forrest need to implement in the particular framework he is using.
x = 4 (input)
y = x + 1
z = x * 2
a = y / z (output)
the answer a = 5/8 = 0.625
if we than set x = 5, as a different input,
we want to recalculate a only once, the new value of a is 6/10 = 0.6
we don't want to recalculate a twice because it has two inputs that
both changed. they both changed together, from a single cause, so we
recalculate y only once.
the original problem with drawing a clock is similar to this. When the
input (clock time) changes, we want to recalculate everything else in
the network exactly once, in order. It's not really a general FBP
problem, more relational logic, since one change in the input should
change everything else exactly once.
I stumbled upon this FBP group not really understanding the distinction
between FBP, reactive, and other paradigms... I know enough to be
dangerous, but I'm learning.
I am trying to understand the touch concept and pseudocode. In the clock
example, what sends the touch and how does it flow through the graph?
Also, thinking about clocks, it would make sense to process the image for
the next second. Then in the output you should show the processed image
much closer to the actual second tick.
On Sun, Jul 29, 2012 at 2:38 AM, David Barbour <dmbarb...@gmail.com> wrote:
> Your approach to clocking may be cleaner than Forrest's, but still
> introduces considerable latency. E.g. if we chained 100 FBP processes in a
> row, and each was pushing only on clock signals at 30Hz, we'd expect 3.33
> seconds to see a change on one end reach the other. There is, of course,
> always some latency involved in such chains, but avoiding a clocked logic
> could cut the latency down to milliseconds even for 100 processes.
> The touch solution is simple enough, and does not limit latency. If I were
> modeling it in procedural it might look like:
> process(iport A, iport B, oport C) {
> var a_touched = false
> var a_value = ""
> var b_touched = false
> var b_value = ""
> while(true) {
> var started_with_touch = (a_touched || b_touched);
> wait([A,B]) // returns when data is available
> while(!empty(A)) {
> var v = take(A)
> if(v == "touch") {
> a_touched = true
> } else {
> a_touched = false
> a_value = v
> }
> }
> while(!empty(B)) {
> var v = take(B)
> if(v == "touch") {
> b_touched = true
> } else {
> b_touched = false
> b_value = v
> }
> }
> var ended_with_touch = (a_touched || b_touched);
> if (ended_with_touch && !started_with_touch)
> put(C, "touch")
> else if(!ended_with_touch)
> put(C, foo(a_value,b_value))
> }
> }
> Obviously, a lot here could be cleaned up, abstracted, made more
> declarative, etc. And this only describes what happens in one specific
> process (of type A&B->C), as opposed to the network effects. There is no
> obvious change on the FBP network for including touches; it'd be a
> discipline that each process supports, which makes it a good candidate for
> adding to port communication protocols in general.
> What happens at the network level, then, is that these touch values
> propagate through the network ahead of the changes (usually not very far
> ahead), and they can stall certain processes. Where touch is most
> profitable is when one source results in multiple outputs (C->D&E) that may
> be processed in parallel before zipping back together down the line.
> Regards,
> Dave
> On Sat, Jul 28, 2012 at 2:18 PM, Paul Morrison <paul.morri...@rogers.com>wrote:
>> On 28/07/2012 3:14 PM, David Barbour wrote:
>> I believe you misunderstood the problem Forrest is attempting to solve.
>> You earlier wrote:
>> I assume you have a process receiving inputs (IPs) at multiple input
>>> ports. If 2 or more inputs arrive at different input ports at the same time
>>> (?), you want to process - just one, or neither?
>> Forrest wants to process both inputs, but wants to process them
>> together (rather than one at a time). E.g. if the time on the clock and the
>> color of the clock change at approximately the same time, we would want to
>> send only one "Render" IP that addresses change in both color and clock, as
>> opposed to sending two "Render" IPs in short succession.
>> You're right - I did misunderstand! OK, so how about taking the same
>> approach that I suggested, with multiple streams feeding into one input
>> port, plus a stream of clock ticks feeding into it as well... but just
>> output one "consolidated" IP for clock ticks preceded by non-clock tick
>> IPs.
>> If you don't like this, perhaps you could post some code for the touch
>> solution - I'm afraid I am having trouble visualizing it... :-)
This touch idea sounds similar to the null convention logic described in "Computer Science Reconsidered" by Karl Fant. In a nutshell the null convention logic is used to implement a "clock-less" system i.e. rather than relying on a central clock to synchronize the processing of multiple inputs into a logic gate, a null state (yeah, a third state, besides the 0 and 1 state) is emitted by the logic gate to indicate the "ready-ness" of the logic gate output.
On Saturday, 28 July 2012 19:38:25 UTC-4, dmbarbour wrote:
> Your approach to clocking may be cleaner than Forrest's, but still > introduces considerable latency. E.g. if we chained 100 FBP processes in a > row, and each was pushing only on clock signals at 30Hz, we'd expect 3.33 > seconds to see a change on one end reach the other. There is, of course, > always some latency involved in such chains, but avoiding a clocked logic > could cut the latency down to milliseconds even for 100 processes.
> The touch solution is simple enough, and does not limit latency. If I were > modeling it in procedural it might look like:
> process(iport A, iport B, oport C) { > var a_touched = false > var a_value = "" > var b_touched = false > var b_value = "" > while(true) { > var started_with_touch = (a_touched || b_touched); > wait([A,B]) // returns when data is available > while(!empty(A)) { > var v = take(A) > if(v == "touch") { > a_touched = true > } else { > a_touched = false > a_value = v > } > } > while(!empty(B)) { > var v = take(B) > if(v == "touch") { > b_touched = true > } else { > b_touched = false > b_value = v > } > } > var ended_with_touch = (a_touched || b_touched); > if (ended_with_touch && !started_with_touch) > put(C, "touch") > else if(!ended_with_touch) > put(C, foo(a_value,b_value)) > } > }
On Mon, Jul 30, 2012 at 3:22 AM, Forrest Oliphant <clawham...@gmail.com>wrote:
> I stumbled upon this FBP group not really understanding the distinction
> between FBP, reactive, and other paradigms... I know enough to be
> dangerous, but I'm learning.
> I am trying to understand the touch concept and pseudocode. In the clock
> example, what sends the touch and how does it flow through the graph?
One can send a touch when we believe an update will be sent very soon.
Since touch indicates an update is coming, we often send a touch whenever
we see a touch - i.e. the touch flows through the network like a wave,
saying "there's an update coming! there's an update coming!" except that we
don't need to repeat this if we've already reported it recently but have
yet to send an update (e.g. when we receive touch on two different ports).
Of course, there is no point to sending a touch if we can just directly
send the update.
So there are a few common situations in which we'd send the touch before
sending the update:
(a) If an FBP process performs an expensive computation per IP, or waits on
network, filesystem, or database queries that might take a while, it can
send the touch before it begins to compute the update.
(b) For splitter-processes (those which send on multiple ports), it can be
useful to touch all the ports (or all but the first one, as a minor
optimization) before before sending all the updates (starting with the
first one). In the FBP context, each port might cause a wait for IPs (due
to bounded buffer of IPs per port) so sending can be considered a
potentially expensive operation.
(c) For zipper-processes (those which receive on multiple ports), it can be
useful to send a touch the first time we see a touch on any port. It will
be common to see touches on two or more ports before seeing updates on any
of them. This allows us to wait for the updates on the ports that haven't
been touched yet.
Note that processes may ignore touches. It's really up to each process to
decide what it does when told there's an update coming. Similarly, it is
ultimately up to each process to decide when to send a touch. There are
some useful idioms, but nothing is set in stone. In the clock example in
particular, a lot of cases are a hybrid of (b) and (c), so could use both
idioms.
All synchronization is about waiting. With mutexes, we wait for another
process to release the mutex. With transactions, we wait at least for the
two or three phase commit. With promises or logic variables, we wait for
single-assignment shared state to become specified. With a clocked process
or timeouts, logical delays, or scheduling, we wait on time. With Fant's
clockless logic, we wait for an update to become available on every port.
With temporal logic or synchronous reactive, we wait for a computational
"instant" to complete. With time warp protocol, we go ahead and compute
optimistically but might perform a rollback if we discover we processed a
message out of order - i.e. we're filling those waits with
"probably-useful" computations to better utilize the computational
resources (on average). With touches, we wait for the update that was
promised (or at least an "oops, I was kidding" IP, i.e. cancel-touch).
If we want to minimize latency then waiting on time - on a clock or timeout
or explicit logical delays - is the very worst option. Basically, every
other option has the possibility of running as fast as the computation
allows. Waiting on time means we only have the potential to run as fast as
the clock allows.
Sometimes waiting on time is still a good option when we want to *control*
latency, i.e. where minimizing variance in latency is more valuable than
minimizing mean latency. (This happens often for real-time processes.)
However, the best way to achieve this is logical delay - i.e. like sending
a message at 1:00 saying "Hey, there's a meeting at 2:00". We aren't asking
the recipient to go to a meeting right away, but are letting them know of
an obligation with enough time to prepare and shift other tasks in their
schedule. And that also gives us some time to change our minds about the
meeting. (State-of-the-art for computation and UI is often like telling the
computer: "Hey, there's a meeting at 2:00, get there", but saying it at
1:59:58 then begrudging the two seconds for the application to start. Is it
any wonder our computers often seem unresponsive?)
> Also, thinking about clocks, it would make sense to process the image for
> the next second. Then in the output you should show the processed image
> much closer to the actual second tick.
That sort of technique can work well - anticipation, double buffering. In
the clock tick example, it works better than normal because clocks are very
predictable (and so is everything in your computation chain). Logical delay
can generalize that sort of advantage it to other domains.
> On Sun, Jul 29, 2012 at 2:38 AM, David Barbour <dmbarb...@gmail.com>wrote:
>> Your approach to clocking may be cleaner than Forrest's, but still
>> introduces considerable latency. E.g. if we chained 100 FBP processes in a
>> row, and each was pushing only on clock signals at 30Hz, we'd expect 3.33
>> seconds to see a change on one end reach the other. There is, of course,
>> always some latency involved in such chains, but avoiding a clocked logic
>> could cut the latency down to milliseconds even for 100 processes.
>> The touch solution is simple enough, and does not limit latency. If I
>> were modeling it in procedural it might look like:
>> process(iport A, iport B, oport C) {
>> var a_touched = false
>> var a_value = ""
>> var b_touched = false
>> var b_value = ""
>> while(true) {
>> var started_with_touch = (a_touched || b_touched);
>> wait([A,B]) // returns when data is available
>> while(!empty(A)) {
>> var v = take(A)
>> if(v == "touch") {
>> a_touched = true
>> } else {
>> a_touched = false
>> a_value = v
>> }
>> }
>> while(!empty(B)) {
>> var v = take(B)
>> if(v == "touch") {
>> b_touched = true
>> } else {
>> b_touched = false
>> b_value = v
>> }
>> }
>> var ended_with_touch = (a_touched || b_touched);
>> if (ended_with_touch && !started_with_touch)
>> put(C, "touch")
>> else if(!ended_with_touch)
>> put(C, foo(a_value,b_value))
>> }
>> }
>> Obviously, a lot here could be cleaned up, abstracted, made more
>> declarative, etc. And this only describes what happens in one specific
>> process (of type A&B->C), as opposed to the network effects. There is no
>> obvious change on the FBP network for including touches; it'd be a
>> discipline that each process supports, which makes it a good candidate for
>> adding to port communication protocols in general.
>> What happens at the network level, then, is that these touch values
>> propagate through the network ahead of the changes (usually not very far
>> ahead), and they can stall certain processes. Where touch is most
>> profitable is when one source results in multiple outputs (C->D&E) that may
>> be processed in parallel before zipping back together down the line.
>> Regards,
>> Dave
>> On Sat, Jul 28, 2012 at 2:18 PM, Paul Morrison <paul.morri...@rogers.com>wrote:
>>> On 28/07/2012 3:14 PM, David Barbour wrote:
>>> I believe you misunderstood the problem Forrest is attempting to solve.
>>> You earlier wrote:
>>> I assume you have a process receiving inputs (IPs) at multiple input
>>>> ports. If 2 or more inputs arrive at different input ports at the same time
>>>> (?), you want to process - just one, or neither?
>>> Forrest wants to process both inputs, but wants to process them
>>> together (rather than one at a time). E.g. if the time on the clock and the
>>> color of the clock change at approximately the same time, we would want to
>>> send only one "Render" IP that addresses change in both color and clock, as
>>> opposed to sending two "Render" IPs in short succession.
>>> You're right - I did misunderstand! OK, so how about taking the same
>>> approach that I suggested, with multiple streams feeding into one input
>>> port, plus a stream of clock ticks feeding into it as well... but just
>>> output one "consolidated" IP for clock ticks preceded by non-clock tick
>>> IPs.
>>> If you don't like this, perhaps you could post some code for the touch
>>> solution - I'm afraid I am having trouble visualizing it... :-)
On Mon, Jul 30, 2012 at 6:45 AM, Matt <mm...@sympatico.ca> wrote:
> Dave,
> This touch idea sounds similar to the null convention logic described in
> "Computer Science Reconsidered" by Karl Fant.
> In a nutshell the null convention logic is used to implement a
> "clock-less" system i.e. rather than relying on a central clock
> to synchronize the processing of multiple inputs into a logic gate, a null
> state (yeah, a third state, besides the 0 and 1 state)
> is emitted by the logic gate to indicate the "ready-ness" of the logic
> gate output.
> Matt
> On Saturday, 28 July 2012 19:38:25 UTC-4, dmbarbour wrote:
>> Your approach to clocking may be cleaner than Forrest's, but still
>> introduces considerable latency. E.g. if we chained 100 FBP processes in a
>> row, and each was pushing only on clock signals at 30Hz, we'd expect 3.33
>> seconds to see a change on one end reach the other. There is, of course,
>> always some latency involved in such chains, but avoiding a clocked logic
>> could cut the latency down to milliseconds even for 100 processes.
>> The touch solution is simple enough, and does not limit latency. If I
>> were modeling it in procedural it might look like:
>> process(iport A, iport B, oport C) {
>> var a_touched = false
>> var a_value = ""
>> var b_touched = false
>> var b_value = ""
>> while(true) {
>> var started_with_touch = (a_touched || b_touched);
>> wait([A,B]) // returns when data is available
>> while(!empty(A)) {
>> var v = take(A)
>> if(v == "touch") {
>> a_touched = true
>> } else {
>> a_touched = false
>> a_value = v
>> }
>> }
>> while(!empty(B)) {
>> var v = take(B)
>> if(v == "touch") {
>> b_touched = true
>> } else {
>> b_touched = false
>> b_value = v
>> }
>> }
>> var ended_with_touch = (a_touched || b_touched);
>> if (ended_with_touch && !started_with_touch)
>> put(C, "touch")
>> else if(!ended_with_touch)
>> put(C, foo(a_value,b_value))
>> }
>> }
> First of all one port has one single role. If we need to pile > different IPs with different types and roles and push them into a > single port it means we have a "technical issue". For me it does not > make any sense.
Hi Dan,
I didn't want to leave this statement unchallenged! Being able to mix multiple IP types on one connection is a very powerful capability - why would you want to give it up?! For a good example of its power, look at the logic for the batch update, described in Chap. 9. Funny how Chapter 9 keeps coming up in different discussions!
> Your approach to clocking may be cleaner than Forrest's, but still > introduces considerable latency. E.g. if we chained 100 FBP processes > in a row, and each was pushing only on clock signals at 30Hz, we'd > expect 3.33 seconds to see a change on one end reach the other. There > is, of course, always some latency involved in such chains, but > avoiding a clocked logic could cut the latency down to milliseconds > even for 100 processes.
Aha! It never occurred to me that anyone would assume I was going to use this technique for more than one process in the chain - I assumed it would be used only when the logic was constrained by the requirements of the display device.
I have to dig into your touch logic a bit - haven't had time recently :-)
> On 29/07/2012 7:58 AM, Dan wrote:
> > First of all one port has one single role. If we need to pile > > different IPs with different types and roles and push them into a > > single port it means we have a "technical issue". For me it does not > > make any sense.
> Hi Dan,
> I didn't want to leave this statement unchallenged! Being able to mix > multiple IP types on one connection is a very powerful capability - why > would you want to give it up?! For a good example of its power, look > at the logic for the batch update, described in Chap. 9. Funny how > Chapter 9 keeps coming up in different discussions!
Having built my versions of FBP before seeing JPM's book, I came along a different path with the same result.
My components have (strongly typed) ports.
The ports are internally connected to a single input queue.
IP's are tagged with the port id when enqueued.
A component processes inputs one at a time, in order of arrival.
This method mimics the operation of hardware IC's and makes much of this discussion moot (this discussion seems to be conflating data-flow with FBP).
You can't have two inputs "arrive at the same time", one or the other is enqueued first. (This is also true in hardware where the trace length affects the travel time of a leading edge from one point to another. IIRC, ECL designers had to take the speed of light into account during design of PCBs).
When you have the possibility of two inputs arriving so closely spaced in time that you can't reliably predict which one will be first, you dust off the old TTL manuals and use race-condition handling techniques (e.g. state machines, etc.) to engineer a desired behaviour.
Since two inputs cannot arrive at the same time, this isn't dataflow.
This also leads to a different solution to the OP (if I understood the question correctly, which I barely remember :-) for creating a dynamic "clutch" on update requests.
Add a feedback loop to the refresh component. When the component finishes an update, it sends itself a blip and enters a waiting-for-blip-state.
In that state, it simply pulls update requests off of the queue (in order of arrival) and dumps them on the floor.
Once the blip arrives (advances to the front of the input queue), the component goes back to the process-updates state, wherein the next update request will cause a full update as above.
