This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

paralell assignment problem
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2005-02-08 (16:02) From: skaller Subject: Re: [Caml-list] Re: paralell assignment problem
```On Wed, 2005-02-09 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: 061-2-9660-0850,
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

```