paralell assignment problem
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20050208 (17:08) 
From:  skaller <skaller@u...> 
Subject:  Re: [Camllist] Re: paralell assignment problem 
On Wed, 20050209 at 01:34, Stefan Monnier wrote: > > Does anyone know how to solve the parallel assignment problem? > > Name invented by me to describe this problem: > > > x1,x2,x3..xn = e1,e2,e3 .. en > > > where ei might contain the variables xj. (Note = here is assignment). > > > The solution is a sequence of assignments involving > > only xi, ei, and ti, where ti are temporaries introduced > > to save the values of the expressions. For example, Here's the algorithm I have implemented, I believe it works, but I'm not sure it finds the minimal solution. The main difficulty is in step 5. 1. Strip out equations of the form xi = xi since they don't do anything. 2. Create 3 lists: head, middle, and tail. 3. For each assignment in the working set: if the RHS does not depend on a variable in the working set, prepend it to the tail else if no RHS in the working set depends on the LHS variable, prepend it to the head else add it to the middle 4. If we moved any assignment to the head or tail list, set the working set to the middle, and go back to step 3 5. The middle now has the property that for any assignment, there is at least one other assignent such that the RHS of one whch depends on the LHS variable of the other. So pick one assignment x = e out of the middle, create a temporary variable t, prepend t = e to the head list and x = t to the tail list, set the working set to the remaining assignments of the middle. If the working set is empty, the result is the reversed head list concatenated with the tail, otherwise go back to step 3 This algorithm (a) finds an equivalent set of serial assignments, and (b) it is clearly locally minimal in the sense that whenever it introduces a temporary in step 5, there was no alternative but to do so. However it isn't clear (to me) that just picking an arbitrary assignment to split into two using a temporary actually minimises the number of temporaries.  John Skaller, mailto:skaller@users.sf.net voice: 061296600850, snail: PO BOX 401 Glebe NSW 2037 Australia Checkout the Felix programming language http://felix.sf.net