From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 59771BC88 for ; Wed, 9 Feb 2005 12:34:58 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j19BYvYc031540 for ; Wed, 9 Feb 2005 12:34:57 +0100 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id MAA30999 for ; Wed, 9 Feb 2005 12:34:57 +0100 (MET) Received: from daimi.au.dk (daimi.au.dk [130.225.16.1]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j19BYuSA015679 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 9 Feb 2005 12:34:57 +0100 Received: from [10.11.23.57] (pzimmer@dhcp-11-23-57 [10.11.23.57]) (authenticated bits=0) by daimi.au.dk (8.12.11/8.12.11) with ESMTP id j19BYosO031820; Wed, 9 Feb 2005 12:34:50 +0100 Message-ID: <4209F53D.5030506@sophia.inria.fr> Date: Wed, 09 Feb 2005 12:34:21 +0100 From: Pascal Zimmer User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.5) Gecko/20050105 Debian/1.7.5-1 X-Accept-Language: fr, fr-fr, en MIME-Version: 1.0 To: Radu Grigore Cc: skaller@users.sourceforge.net, caml-list Subject: Re: [Caml-list] Re: paralell assignment problem References: <1107832025.13571.260.camel@pelican.wigram> <87y8dzi0ns.fsf-monnier+gmane.comp.lang.caml.inria@gnu.org> <1107882489.5022.175.camel@pelican.wigram> <7f8e92aa05020810335ab052e0@mail.gmail.com> <7f8e92aa050209014322b561e@mail.gmail.com> In-Reply-To: <7f8e92aa050209014322b561e@mail.gmail.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-DAIMI-Spam-Score: -2.82 () ALL_TRUSTED X-Scanned-By: MIMEDefang 2.44 X-Miltered: at nez-perce with ID 4209F561.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 4209F560.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 wrote:01 reuse:01 notations:01 computed:01 computed:01 topological:01 rhs:01 sub-optimal:01 topological:01 nodes:01 nodes:01 subset:01 wrote:01 rhs:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: 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...