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 (16:02) 
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, > > Most ML compilers do this sort of thing to break big blocks of mutually > recursive functions into smaller such blocks. The algorithm used is > generally to extract the "strongly connected components" of the graph. > Google for it and you'll surely find an algorithm. I'm not sure the problem is quite the same though. Call graphs are transitive: if A calls B, and B calls C, then A calls C. However, 'depends on' is not transitive. Here x,y = y,x x and y are mutually dependent, but in the solution: t = x; x = y; y = t t depends on x, x depends on y, and y depends on t. If the dependency were transitive, y would then depend on x, but it doesn't. That is: the graph of the solution seems strongly connected: T > X > Y + ^  ++ however, these are *sequential* and not parallel assignments. A solution using digraph decomposition may well be the right answer, perhaps changing the relation to 'depends on the old value of'. This would break the cycle above (since t has no old value, y now doesn't depend on anything). See another post for an algorithm..  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