<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
OK, I'll (I mean a student of mine) take the approach of implementing a
simple system to create DAGs, and then execute them. I'll report back
if I learn anything interesting.<br>
<br>
Ioan<br>
<pre class="moz-signature" cols="72">--
=================================================================
Ioan Raicu, Ph.D.
NSF/CRA Computing Innovation Fellow
=================================================================
Center for Ultra-scale Computing and Information Security (CUCIS)
Department of Electrical Engineering and Computer Science
Northwestern University
2145 Sheridan Rd, Tech M384
Evanston, IL 60208-3118
=================================================================
Cel: 1-847-722-0876
Tel: 1-847-491-8163
Email: <a class="moz-txt-link-abbreviated" href="mailto:iraicu@eecs.northwestern.edu">iraicu@eecs.northwestern.edu</a>
Web: <a class="moz-txt-link-freetext" href="http://www.eecs.northwestern.edu/~iraicu/">http://www.eecs.northwestern.edu/~iraicu/</a>
<a class="moz-txt-link-freetext" href="https://wiki.cucis.eecs.northwestern.edu/">https://wiki.cucis.eecs.northwestern.edu/</a>
=================================================================
=================================================================
</pre>
<br>
<br>
Mihael Hategan wrote:
<blockquote cite="mid:1266617968.32175.21.camel@localhost" type="cite">
<pre wrap="">On Fri, 2010-02-19 at 15:37 -0600, Ioan Raicu wrote:
</pre>
<blockquote type="cite">
<pre wrap="">
Mihael Hategan wrote:
</pre>
<blockquote type="cite">
<pre wrap="">On Fri, 2010-02-19 at 14:08 -0600, Ioan Raicu wrote:
</pre>
<blockquote type="cite">
<pre wrap="">Yes, I think my confusion is coming from the fact that the order of
statement in the source code is not preserved in the execution order
(assuming there are dependencies). You are saying that the order in
the source code doesn't matter in Swift. Perhaps this is what is
making the analysis harder, to detect these deadlocks?
</pre>
</blockquote>
<pre wrap="">Yes it does. It's also necessary because it's what achieves
parallelization.
</pre>
</blockquote>
<pre wrap="">Thinking about this problem briefly, I don't think its *necessary* for
the parallelization.
</pre>
</blockquote>
<pre wrap=""><!---->
Think a bit harder.
</pre>
<blockquote type="cite">
<pre wrap=""> I can certainly think of how to execute a DAG in parallel (as long as
there are no dependencies), and where-ever dependencies exist, things
are done in the right order to maintain the dependencies. I believe
this is what gets done in Swift right now. The difference is perhaps
how you build the DAG. If you keep the order of statements from the
source code, you just have to make sure that order is maintained when
adding nodes (and edges) to the DAG.
For example:
b = f(a)
a = f(b)
You add the first node f_1 to the DAG, with a as input edge, and b as
output edge. Then you process the second statement, adding another
node f_2, adding an edge between f_1 and f_2 with dependency b, and
create an output edge from f_2 with an edge a. The trick is to detect
that edge a already existed, as an input to node f_1, which would
cause a loop, which in turn should not be allowed (per the definition
of a DAG), and an error should be raised.
</pre>
</blockquote>
<pre wrap=""><!---->
Right. Except edges in dags are traditionally the dependencies. So if
you replace "edge" with "node" and the other way around in your above
statement, we may be closer to the generally accepted terminology. And
yes, this is precisely how swift works.
And yes, the trick is to detect loops in the dag. You can do it by
actually constructing a dag or using the nice method hinted about by Ben
(i.e. seeing this as a system of inequations):
b > a
a > b
(you can see ">" as "edge from left to right" if you want).
Now you realize I hope that you've evaluated nor b nor a when you
constructed the dag. Which is where you confusion seemed to be. And if
you re-order the two statements, you get the same dag. And I hope you
also realize that the order in which things are executed in the dag has
little to do with the order in which the edge and node declarations
appear.
</pre>
<blockquote type="cite">
<pre wrap="">I don't understand why you say its necessary to achieve
parallelization. I am sure this discussion would be much simpler in
person in front of whiteboard, or perhaps even in a skype call. Should
we try that?
</pre>
</blockquote>
<pre wrap=""><!---->
I've already spent too much time on this. Sorry.
But I think you are on the right track towards understanding how this
works. I think you should actually try to implement a simple system
(doesn't have to have the full swift semantics) based on what you said
above and see what problems you run into.
So far from the discussion it looks like you pretty much took the same
steps that we did when we first wrote swift, so I suspect that if you
try it out yourself you will learn better why things are the way they
are.
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
=================================================================
Ioan Raicu, Ph.D.
NSF/CRA Computing Innovation Fellow
=================================================================
Center for Ultra-scale Computing and Information Security (CUCIS)
Department of Electrical Engineering and Computer Science
Northwestern University
2145 Sheridan Rd, Tech M384
Evanston, IL 60208-3118
=================================================================
Cel: 1-847-722-0876
Tel: 1-847-491-8163
Email: <a class="moz-txt-link-abbreviated" href="mailto:iraicu@eecs.northwestern.edu">iraicu@eecs.northwestern.edu</a>
Web: <a class="moz-txt-link-freetext" href="http://www.eecs.northwestern.edu/~iraicu/">http://www.eecs.northwestern.edu/~iraicu/</a>
<a class="moz-txt-link-freetext" href="https://wiki.cucis.eecs.northwestern.edu/">https://wiki.cucis.eecs.northwestern.edu/</a>
=================================================================
=================================================================
</pre>
</body>
</html>