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:  20050209 (11:34) 
From:  Pascal Zimmer <Pascal.Zimmer@s...> 
Subject:  Re: [Camllist] Re: paralell assignment problem 
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 > suboptimal]. 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 > inedges 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 inedges of marked nodes we obtain a tree". That's true. But now, let's make a remark: since the marked nodes have only outedges, they cannot participate in any cycle anymore. So, in fact, we can also remove their outedges, 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 NPcomplete: 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 *outedges* 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 OCamlrelated anymore...