[Swift-devel] Problem with iterate

[Ioan Raicu]

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.

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 15:37 -0600, Ioan Raicu wrote:
>   
>> 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.
>>     
>
> Think a bit harder.
>
>   
>>  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. 
>>     
>
> 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.
>
>   
>> 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?
>>     
>
> 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.
>
>   

-- 
=================================================================
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/75300a2f/attachment.html>