Re: [Caml-list] Re: paralell assignment problem

[Pascal Zimmer <Pascal.Zimmer@sophia.inria.fr>]

OK, I think I can add my stone now :)

Radu Grigore wrote:
> OK, I took 1h to think about this problem more carefully. Now I'm
> almost convinced that it is NP :)

It is. I will reuse your notations:

> I'll use the example given in the previous mail:
> a = b+c
> b = c
> c = a+b
> 
> We can read the first equation as "a must be computed before b and c".
> So we can construct a graph whose edges mean "source should be
> computed before target". In this case it is:
> 
> a -> b
> a -> c
> b -> c
> c -> a
> c -> b
> 
> If this graph has no cycles the problem is simple: just do a
> topological sort and the problem is solved in O(V+E). If the graph has
> cycles then we need to break them by introducing temporaries. Without
> looking at the form of RHS expressions, that is without considering
> computing an expression partially then we are left with two uses for
> temporaries:
> 
> 1. hold the original value of a variable
> 2. hold the result of an expression and write it later to the destination
> 
> Point (1) requires one extra assignment, while point (2) requires two
> extra assignments. The effect is however the same: one of the
> variable's value can be computed as soon as desired. Therefore we will
> only use (1). [NOTE that your approach used (2) and hence is clearly
> sub-optimal].

First, a remark here, case (2) can *always* be reduced to case (1). 
Suppose you are saving the expression for variable a into a temporary 
variable t, and assign a later when you don't need the old value anymore:

...
t <- some expression
... <-  ... a ...
... <-  ...
... <-  ... a ...
a <- t
...

This can be replaced by the assignments:

...
t <- a
a <- some expression
... <- ... t ...
... <- ...
... <- ... t ...
...

(Of course, you can also do the converse transformation.)

Thus, as you noticed, all you have to do is decide for which variables 
we should keep the old values, and then compute all the expressions with 
them (using a topological sort of what remains).

> The effect of (1) (and (2)) on the constructed graph is that all
> in-edges of a variable are removed. So we have reduced the problem to
> this: "Given a graph mark as few nodes as possible such that the after
> removing in-edges of marked nodes we obtain a tree".

That's true. But now, let's make a remark: since the marked nodes have 
only out-edges, they cannot participate in any cycle anymore. So, in 
fact, we can also remove their out-edges, which means remove the node 
completely from the graph.

The problem can now be rephrased as: "Given a directed graph, find a 
minimal set of vertices whose deletion leaves an acyclic graph". To put 
it another way, "given a directed graph G=(V,E), find a minimal subset 
of vertices V' such that every cycle of G has a vertex in V'".
This problem is known as the minimum feedback vertex set, and (sadly) it 
is NP-complete:
http://www.nada.kth.se/~viggo/wwwcompendium/node19.html#3336

Last, to comment Skaller's last post:

skaller wrote:
 > However, your solution, whilst correct, breaks one of
 > the rules: one of the RHS is refering to the old value
 > of 'c' using the name 't'. The original rules required
 > only assignments using the original LHS variables,
 > the original RHS expressions, and the temporaries,
 > that is, only permitted buffering the RHS expressions,
 > not old values of variables.
 >
 > Allowing *both* RHS expressions (new values of variables)
 > and LHS variables (old values of variables) makes sense,
 > however, as your example demonstrates. And also seems
 > to make solving the problem harder :)

Actually, they are fully equivalent. If you think about the graph 
defined above, you want to find the set of variables, for which you will 
compute their expressions, save them into temporary variables, compute 
the rest, and affect those variables. This now amounts to deleting 
*out-edges* for the elected variables in the graph. Now, use the same 
arguments and you get exactly the same graph problem.

To summarize:
- build the graph as described by Radu
- use an approximation algorithm for a minimum feedback vertex set
- compute expressions for variables in this set, and store results in 
temporary variables
- use topological sorting on the subgraph to find a correct ordering for 
the other variables
- assign temporary variables to their final destination

Hope this helps...

Pascal

PS: I am not sure this conversation is much OCaml-related anymore...