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

[Radu Grigore <radugrigore@gmail.com>]

On Tue, 8 Feb 2005 20:33:52 +0200, Radu Grigore <radugrigore@gmail.com> wrote:
> On Tue, 08 Feb 2005 09:12:32 -0800 (PST), skaller
> <skaller@users.sourceforge.net> wrote:
> 
> > 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.
> 
> I'm mildly convinced that it works.

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

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].

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". Now, that looks a
lot like SET-COVER. In the example above we have these cycles:

1: abc
2: bc
3: ac

The set is {1, 2, 3} and the subsets from which we have to choose are
a:{1, 3}, b:{2}, c:{1, 2, 3}. The minimum cover is clearly c:{1, 2, 3}
and hence the solution is to create a temporary for the original value
of c. After removing all in-edges of c and topologically sorting the
graph we get: c, a, b. So this is the order in which we should do the
other assignments. Yes -- we reached the correct solution.

Now, it looks like that starting from a SET-COVER problem one can
build a graph with the right relationship between nodes and cycles and
then an assignment problem. I can't give a  (semi-)formal argument but
I have tried on a few instances and the process of construction seems
to be fairly algorithmic (although hard to formalize -- at least in an
email -- since I used pictures). This is why I say your problem looks
NP.

An acceptable algorithm might be this one:
1. detect strongly connected components (optional)
2. within each SCC find all cycles and group them in subsets according
to the nodes they have in common
3. within each SCC solve SET-COVER (for cycle sets given by common nodes)
4. sort topologically the graph after removing the in-edges of nodes
marked at step 3

Step 2 is clearly exponential in the number of variables (consider a
complete graph).

For step 3 you probably want to use an approximation algorithm. It
looks like there are ones with good complexity (but I do not know them
so I can't tell anything about the constants). In any case, have a
look at: http://www.nada.kth.se/~viggo/wwwcompendium/node146.html
If you use the lg C algorithm (C = cycles) then the overall complexity
is something like O(2^V), where V is the number of variables.

-- 
regards,
 radu
http://rgrig.idilis.ro/