<br><br><div class="gmail_quote">On Thu, Oct 28, 2010 at 10:46, Brian Granger <span dir="ltr">&lt;<a href="mailto:ellisonbg@gmail.com">ellisonbg@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Min,<br>
<div class="im"><br>
On Thu, Oct 28, 2010 at 12:57 AM, MinRK &lt;<a href="mailto:benjaminrk@gmail.com">benjaminrk@gmail.com</a>&gt; wrote:<br>
&gt; Hello,<br>
&gt; In order to test/demonstrate arbitrary DAG dependency support in the new ZMQ<br>
&gt; Python scheduler, I wrote an example using NetworkX, as Fernando suggested.<br>
&gt; It generates a random DAG with a given number of nodes and edges, runs a set<br>
&gt; of empty jobs (one for each node) using the DAG as a dependency graph, where<br>
&gt; each edge represents a job depending on another.<br>
&gt; It then validates the results, ensuring that no job ran before its<br>
&gt; dependencies, and draws the graph, with nodes arranged in X according to<br>
&gt; time, which means that all arrows must point to the right if the<br>
&gt; time-dependencies were met.<br>
<br>
</div>Very impressive demo and test.  Here is a very significant benchmark<br>
we could do with this...<br>
<br>
1. Make each node do a time.sleep(rand_time) where rand_time is a<br>
random time interval over some range of times.<br>
2. For a DAG of such tasks, you can calculate the fastest possible<br>
parallel execution time by finding the shortest path through the DAG,<br>
where, by shortest path, I mean the path where the sum of rand_time&#39;s<br>
on that path is the smallest.  </blockquote><div><br></div><div>It&#39;s actually slightly more complicated than that, because T_best should actually be the *longest* path from a root to any terminus. Remember that a node depends on all its parents, so the longest path is the earliest start time for a given node.  Since It&#39;s a DAG, there can&#39;t be any loops that would mess up the length of your route. It would be shortest if I set mode=&#39;any&#39; on the dependencies, and even then, T_best would be the *longest* path of the collection of shortest paths from each root to each node.</div>

<div><br></div><div>It&#39;s been a long time since the DAG unit of my Automata and Languages course, but I&#39;ll put this together.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Call that time T_best.  By analyzing<br>
the DAG, you can also tell the number of engines required to acheive<br>
that T_best.  We can also calculate things like the parallel and<br>
serial fraction of the DAG to find the max speedup.<br>
3. Run that same DAG on 1, 2, 4, 8, ... engines to see how close we<br>
can get to T_best and the max_speedup.<br>
<br>
This would be a very rigorous way of testing the system over a variety<br>
of different types of loads.<br></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im"><br>
&gt; It happily handles pretty elaborate (hundreds of edges) graphs.<br>
<br>
</div>That is quite impressive, but what is the limitation?  It should be<br>
able to do 1000s or more of edges right?<br></blockquote><div><br></div><div>The limitation is that my tasks take O(1 sec) to run, and I didn&#39;t want to wait for several minutes for the test to complete :).  There should be no problem internally with millions of tasks and dependencies.  The performance limitation will be the set methods used to check whether a dependency has been met and the memory footprint of the sets themselves. Quickly checking with %timeit, the set checks with 100k dependencies and 1M msg_ids to check against still only take ~5ms on my laptop (200ns for 10 dependencies and 10M msg_ids to check).  My interactive session starts running into memory issues with 100M ids, so that&#39;s something to consider.</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im"><br>
&gt; Too bad I didn&#39;t have this done for today&#39;s Py4Science talk.<br>
<br>
</div>Yes, defiinitely, that would have been &quot;epic&quot; as my teenage son would say.<br>
<div class="im"><br>
&gt; Script can be found here:<br>
&gt; <a href="http://github.com/minrk/ipython/blob/newparallel/examples/demo/dagdeps.py" target="_blank">http://github.com/minrk/ipython/blob/newparallel/examples/demo/dagdeps.py</a><br>
<br>
</div>Cheers,<br>
<br>
Brian<br>
<br>
<br>
&gt; -MinRK<br>
<div><div></div><div class="h5">&gt;<br>
<br>
<br>
<br>
--<br>
Brian E. Granger, Ph.D.<br>
Assistant Professor of Physics<br>
Cal Poly State University, San Luis Obispo<br>
<a href="mailto:bgranger@calpoly.edu">bgranger@calpoly.edu</a><br>
<a href="mailto:ellisonbg@gmail.com">ellisonbg@gmail.com</a><br>
</div></div></blockquote></div><br>