[Swift-devel] Problem with iterate

[Ioan Raicu]

Oops, I sent it again from the wrong account.

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? If Swift 
> insisted on an ordering in execution, relative to the source code 
> ordering, perhaps the analysis would be simplified?
>
> 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).
>
> Thanks for all the explanations!!!
>
> Ioan
> -- 
> =================================================================
> 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/
> =================================================================
> =================================================================
>
>   
>
>
> Mihael Hategan wrote:
>> On Fri, 2010-02-19 at 12:28 -0600, Ioan Raicu wrote:
>>   
>>> If you preserve the order of statements, statement 1 and 2 would get
>>> done first, in parallel if enough resources were available.
>>>     
>>
>> How would you know the value of a[2] without the complex function in
>> statement 3 being evaluated?
>>
>>   
>>>  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.
>>>     
>>
>> 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.
>>
>>   
>>>  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.
>>>     
>>
>> 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;
>>
>>   
>>>  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.
>>>     
>>
>> 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
>>
>>
>>   

-- 
=================================================================
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/68803d27/attachment.html>