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 <[EMAIL PROTECTED]> 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@llistes.projectes.lafarga.org > https://llistes.projectes.lafarga.org/cgi-bin/mailman/listinfo/clam-devel >
_______________________________________________ Clam-devel mailing list Clam-devel@llistes.projectes.lafarga.org https://llistes.projectes.lafarga.org/cgi-bin/mailman/listinfo/clam-devel