Hi Pau,<br><br>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...<br><br>Thanks,<br>Abe<br><br><br><div><span class="gmail_quote">
On 10/11/07, <b class="gmail_sendername">Pau Arumi</b> <<a href="mailto:parumi@iua.upf.edu">parumi@iua.upf.edu</a>> wrote:</span><blockquote class="gmail_quote" style="margin-top: 0; margin-right: 0; margin-bottom: 0; margin-left: 0; margin-left: 0.80ex; border-left-color: #cccccc; border-left-width: 1px; border-left-style: solid; padding-left: 1ex">
En/na abe kazemzadeh ha escrit:<br>> Hi again,<br>><br>> (I decided to put this in a different email b/c it's a different topic).<br>>  I'm taking an algorithms class this semester and we're studying network
<br>> flow algorithms now.  The whole concept reminded me of clam networks,<br>> but I was wondering how far the similarity goes... Does clam use any of<br>> the network flow algorithms like Ford-Fulkerson or Edmonds-Karp?  I'm
<br>> just curious b/c it seems to have some similarities.  Also it would be<br>> cool to see a concrete implementation b/c the class is all theory/pen<br>> and paper...<br><br>Hi Abe,<br>a nice topic to bring out. Precisely a month or so ago a friend
<br>of mine handed me a book about network flow algorithms since (as<br>you do now) he thought the topic resembles the synchronous data<br>flow scheduling I was trying to implement for CLam.<br><br>A synchronous data flow (SDF) is a data flow whose production and
<br>consumption rates (token count) per each port are integers known<br>a priori. Since port rates are not to be changed at run-time Clam<br>model is a SDF.<br>Some models in flow networks resembles very much SDFs, also they
<br>define some kind of balance equations to express that the amount<br>of tokens incoming to a edge equals the outgoing amount. However,<br>as I understand, there is a key difference in that flow networks<br>just pass along the incoming data (be it discrete tokens or real
<br>amounts) and they can distribute it into various outports. So it<br>is useful to model pipes of flowing water or network traffic but<br>not for data flow processing. So summing up, the mathematic<br>constructs are very similar to those in SDF but I couldn't find
<br>any flow network algorithm directly usable in for data flows.<br><br>The good thing about SDF is that they are powerful enough to<br>model many real-world problems (including ones exhibiting<br>multi-rate) and "easy" enough to be able to perform some static
<br>analysis. In particular, on can know if a graph have a (periodic)<br>schedule or not and find one if it exist, statically or compile<br>time, so all the scheduling overhead evaporates.<br><br>This paper from Lee and Messerschmitt that explains the technique
<br>in detail<br><br><a href="http://ptolemy.eecs.berkeley.edu/publications/papers/87/staticscheduling/">http://ptolemy.eecs.berkeley.edu/publications/papers/87/staticscheduling/</a><br><br>And this python script using sympy is my implementation which
<br>will be integrated in Clam in short, thus avoiding the many<br>runtime checkings done by our current scheduling.<br><br><a href="http://ocata48123.upf.es/~parumi/synchronous_data_flow_scheduler.py">http://ocata48123.upf.es/~parumi/synchronous_data_flow_scheduler.py
</a><br><br>The static schedule is a two step algorithm, first find a<br>non-zero vector of the graph's topology matrix (the smallest<br>integer vector, actually). This represents the number of firings<br>of each node to cover an iteration. Then we use dynamic
<br>programming to find an actual scheduling (list of firings).<br>Another bonus is that this analysis can easily show what is the<br>maximum needed memory at each arc, the maximum latency and so on.<br>I hope we also can take advantage of this in the near future.
<br><br>Have fun!<br>   Pau<br><br><br>_______________________________________________<br>Clam-devel mailing list<br><a href="mailto:Clam-devel@llistes.projectes.lafarga.org">Clam-devel@llistes.projectes.lafarga.org</a><br>
<a href="https://llistes.projectes.lafarga.org/cgi-bin/mailman/listinfo/clam-devel">https://llistes.projectes.lafarga.org/cgi-bin/mailman/listinfo/clam-devel</a><br></blockquote></div><br>