<!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">
Oops, I sent it again from the wrong account.<br>
<br>
Ioan Raicu wrote:
<blockquote cite="mid:4B7EEFD3.30902@eecs.northwestern.edu" type="cite">
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
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? If Swift insisted on an
ordering in execution, relative to the source code ordering, perhaps
the analysis would be simplified? <br>
<br>
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? BTW,
I have a student in my class that is interested automated
parallelization of code, so this conversation is highly relevant for
his project (and my understanding).<br>
<br>
Thanks for all the explanations!!!<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 moz-do-not-send="true" class="moz-txt-link-abbreviated"
href="mailto:iraicu@eecs.northwestern.edu">iraicu@eecs.northwestern.edu</a>
Web: <a moz-do-not-send="true" class="moz-txt-link-freetext"
href="http://www.eecs.northwestern.edu/%7Eiraicu/">http://www.eecs.northwestern.edu/~iraicu/</a>
<a moz-do-not-send="true" 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:1266605936.29592.15.camel@localhost" type="cite">
<pre wrap="">On Fri, 2010-02-19 at 12:28 -0600, Ioan Raicu wrote:
</pre>
<blockquote type="cite">
<pre wrap="">If you preserve the order of statements, statement 1 and 2 would get
done first, in parallel if enough resources were available.
</pre>
</blockquote>
<pre wrap=""><!---->
How would you know the value of a[2] without the complex function in
statement 3 being evaluated?
</pre>
<blockquote type="cite">
<pre wrap=""> However, statement 3 could not be evaluated until the complex
function runs, at which time it can be added to the DAG and executed.
This implies that you don't need a complete DAG in order to execute
the DAG. In other words, start building the DAG as much as you can
with static information, but also start executing the DAG as soon as
there is anything in the DAG.
</pre>
</blockquote>
<pre wrap=""><!---->
This is how swift works.
But then it's also the thing preventing you from checking the (not yet
fully built) dag at compile time.
</pre>
<blockquote type="cite">
<pre wrap=""> This would not work if you had to build the entire DAG apriori to
starting to execute it, due to the dynamic nature of the data
dependency.
So, your question about what should happen here, is that at run time
you figure out the value of the complex function, and execute the
statement accordingly. In the end, a[2] will have the same value as
a[0] or a[1]. In theory, I don't see why this example would have to
deadlock.
</pre>
</blockquote>
<pre wrap=""><!---->
Because if the complex function returns 1, then the program is the same
as (and forgive me for forgetting the dummy function, "+" in our case):
a[1] = a[2] + 1;
a[2] = a[1] + 1;
</pre>
<blockquote type="cite">
<pre wrap=""> Also, I don't think the order of the statements should be changed,
for example moving statement statement 3 up and statement 2 down,
preventing the a[2] overwrite.
</pre>
</blockquote>
<pre wrap=""><!---->
There is some fundamental misunderstanding here. There is no overwrite.
It's probably not useful to continue the discussion if you insist on its
existence. The confusion is probably up there with the "order of
execution of statements". There is no difference between any of the
permutations of the statements in that program. They all mean the same
thing. Assignment happens not when a statement is encountered in the
source code but when the value on the right is available. So in the case
of:
a = 0;
b = a + 1;
c = b + 1;
a = 0 happens at t0 (all constants are available at t0)
b = 1 happens at t0 + 1
c = 2 happens at t0 + 2
The exact same would happen if you wrote:
c = b + 1;
b = a + 1;
a = 0;
or
c = b + 1
a = 0
b = a + 1
</pre>
</blockquote>
</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>