<!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">
<br>
<br>
Mihael Hategan wrote:
<blockquote cite="mid:1266612363.31122.26.camel@localhost" 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>
Thinking about this problem briefly, I don't think its *necessary* for
the parallelization. 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. <br>
<br>
For example:<br>
b = f(a)<br>
a = f(b)<br>
<br>
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. <br>
<br>
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?<br>
<blockquote cite="mid:1266612363.31122.26.camel@localhost" type="cite">
<pre wrap="">
</pre>
<blockquote type="cite">
<pre wrap=""> If Swift insisted on an ordering in execution, relative to the source
code ordering, perhaps the analysis would be simplified?
</pre>
</blockquote>
<pre wrap=""><!---->
Right. The analysis of deadlocks is very much simplified in languages
that don't allow concurrency as Ben pointed out (i.e. deadlocks don't
exist, being replaced by infinite loops of one form or another).
a = f(1);
b = f(2);
If b is evaluated after a has a value (which would be the execution
order you suggest) then f(1) and f(2) would not be evaluated in
parallel.
</pre>
</blockquote>
but there are no dependencies between these 2 statements, so they can
be executed in parallel, according to the way I built the DAG in my
example above. You would have a DAG with 2 nodes, and no edges between
the nodes. All nodes that have no unresolved dependencies should be
able to execute at any time.<br>
<blockquote cite="mid:1266612363.31122.26.camel@localhost" type="cite">
<pre wrap="">
</pre>
<blockquote type="cite">
<pre wrap="">My curiosity is mostly driven by trying to understand what assumptions
in Swift is making this analysis hard to do, and how you would do
things differently to help this kind of analysis be easier to do?
</pre>
</blockquote>
<pre wrap=""><!---->
Right. Of course. But it turns out that you can't have everything and to
me it looks like deadlocks in a parallel languages is a problem of the
same class as the halting problem in non-parallel languages.
</pre>
</blockquote>
This is true in a general parallel language, but we are looking at a
constraint case, in which we have single assignments, and loops aren't
allowed as part of the DAG. So I am not convinced that deadlocks are
innevitable, at a theoretical level, given all the assumptions we made
about the parallel languages we care about (plus the ordering
requirement).<br>
<br>
Should we try a skype call? I can talk anytime up to 5PM today, or
Monday any time.<br>
<br>
Thanks,<br>
Ioan<br>
<blockquote cite="mid:1266612363.31122.26.camel@localhost" type="cite">
<pre wrap="">
This is pretty much what the earlier emails in the discussion were
about.
That said, there are trivial cases, such as the a > b, b > a case that
can be detected quickly.
_______________________________________________
Swift-devel mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Swift-devel@ci.uchicago.edu">Swift-devel@ci.uchicago.edu</a>
<a class="moz-txt-link-freetext" href="http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel">http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel</a>
</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>