[Clam-devel] question about flow network algorithms

[abe kazemzadeh]

Hi Pau,

Cool... thanks for all the info!  I'm glad I asked :)  The reference looks
interesting and I'm looking forward to seeing how it works out for Clam...

Thanks,
Abe


On 10/11/07, Pau Arumi <parumi at iua.upf.edu> wrote:
>
> 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
>
>
> _______________________________________________
> Clam-devel mailing list
> Clam-devel at llistes.projectes.lafarga.org
> https://llistes.projectes.lafarga.org/cgi-bin/mailman/listinfo/clam-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.clam-project.org/pipermail/clam-devel-clam-project.org/attachments/20071011/33981edf/attachment-0003.htm>