[Clam-devel] question about flow network algorithms

[Pau Arumi]

En/na abe kazemzadeh ha escrit:
> Hi again,
> 
> (I decided to put this in a different email b/c it's a different topic). 
>  I'm taking an algorithms class this semester and we're studying network 
> flow algorithms now.  The whole concept reminded me of clam networks, 
> but I was wondering how far the similarity goes... Does clam use any of 
> the network flow algorithms like Ford-Fulkerson or Edmonds-Karp?  I'm 
> just curious b/c it seems to have some similarities.  Also it would be 
> cool to see a concrete implementation b/c the class is all theory/pen 
> and paper...

Hi Abe,
a nice topic to bring out. Precisely a month or so ago a friend
of mine handed me a book about network flow algorithms since (as
you do now) he thought the topic resembles the synchronous data
flow scheduling I was trying to implement for CLam.

A synchronous data flow (SDF) is a data flow whose production and
consumption rates (token count) per each port are integers known
a priori. Since port rates are not to be changed at run-time Clam
model is a SDF.
Some models in flow networks resembles very much SDFs, also they
define some kind of balance equations to express that the amount
of tokens incoming to a edge equals the outgoing amount. However,
as I understand, there is a key difference in that flow networks
just pass along the incoming data (be it discrete tokens or real
amounts) and they can distribute it into various outports. So it
is useful to model pipes of flowing water or network traffic but
not for data flow processing. So summing up, the mathematic
constructs are very similar to those in SDF but I couldn't find
any flow network algorithm directly usable in for data flows.

The good thing about SDF is that they are powerful enough to
model many real-world problems (including ones exhibiting
multi-rate) and "easy" enough to be able to perform some static
analysis. In particular, on can know if a graph have a (periodic)
schedule or not and find one if it exist, statically or compile
time, so all the scheduling overhead evaporates.

This paper from Lee and Messerschmitt that explains the technique
in detail

http://ptolemy.eecs.berkeley.edu/publications/papers/87/staticscheduling/

And this python script using sympy is my implementation which
will be integrated in Clam in short, thus avoiding the many
runtime checkings done by our current scheduling.

http://ocata48123.upf.es/~parumi/synchronous_data_flow_scheduler.py

The static schedule is a two step algorithm, first find a
non-zero vector of the graph's topology matrix (the smallest
integer vector, actually). This represents the number of firings
of each node to cover an iteration. Then we use dynamic
programming to find an actual scheduling (list of firings).
Another bonus is that this analysis can easily show what is the
maximum needed memory at each arc, the maximum latency and so on.
I hope we also can take advantage of this in the near future.

Have fun!
   Pau