[Swift-devel] Problem with iterate

[Ioan Raicu]

Mihael Hategan wrote:
> On Fri, 2010-02-19 at 14:08 -0600, Ioan Raicu wrote:
>   
>> 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?
>>     
>
> Yes it does. It's also necessary because it's what achieves
> parallelization.
>   
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.

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.

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?
>   
>>  If Swift insisted on an ordering in execution, relative to the source
>> code ordering, perhaps the analysis would be simplified? 
>>     
>
> 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.
>   
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.
>   
>> 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?
>>     
>
> 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.
>   
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).

Should we try a skype call? I can talk anytime up to 5PM today, or 
Monday any time.

Thanks,
Ioan
> 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
> Swift-devel at ci.uchicago.edu
> http://mail.ci.uchicago.edu/mailman/listinfo/swift-devel
>
>   

-- 
=================================================================
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: iraicu at eecs.northwestern.edu
Web:   http://www.eecs.northwestern.edu/~iraicu/
       https://wiki.cucis.eecs.northwestern.edu/
=================================================================
=================================================================


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/swift-devel/attachments/20100219/ffb2176f/attachment.html>