From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id BEE5FBC88 for ; Tue, 8 Feb 2005 18:08:22 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j18H8M6R015162 for ; Tue, 8 Feb 2005 18:08:22 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA31130 for ; Tue, 8 Feb 2005 18:08:21 +0100 (MET) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j18H8JVQ013918 for ; Tue, 8 Feb 2005 18:08:21 +0100 Received: from [192.168.1.200] (ppp212-197.lns2.syd3.internode.on.net [203.122.212.197]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id j18H8AYV062584; Wed, 9 Feb 2005 03:38:18 +1030 (CST) Subject: Re: [Caml-list] Re: paralell assignment problem From: skaller Reply-To: skaller@users.sourceforge.net To: Stefan Monnier Cc: caml-list In-Reply-To: <87y8dzi0ns.fsf-monnier+gmane.comp.lang.caml.inria@gnu.org> References: <1107832025.13571.260.camel@pelican.wigram> <87y8dzi0ns.fsf-monnier+gmane.comp.lang.caml.inria@gnu.org> Content-Type: text/plain Message-Id: <1107882489.5022.175.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 09 Feb 2005 04:08:10 +1100 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4208F206.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 4208F203.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 sourceforge:01 wrote:01 rhs:01 prepend:01 rhs:01 prepend:01 glebe:01 061:98 arbitrary:01 nsw:01 tail:01 tail:01 algorithm:01 algorithm: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: 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, Here's the algorithm I have implemented, I believe it works, but I'm not sure it finds the minimal solution. The main difficulty is in step 5. 1. Strip out equations of the form xi = xi since they don't do anything. 2. Create 3 lists: head, middle, and tail. 3. For each assignment in the working set: if the RHS does not depend on a variable in the working set, prepend it to the tail else if no RHS in the working set depends on the LHS variable, prepend it to the head else add it to the middle 4. If we moved any assignment to the head or tail list, set the working set to the middle, and go back to step 3 5. The middle now has the property that for any assignment, there is at least one other assignent such that the RHS of one whch depends on the LHS variable of the other. So pick one assignment x = e out of the middle, create a temporary variable t, prepend t = e to the head list and x = t to the tail list, set the working set to the remaining assignments of the middle. If the working set is empty, the result is the reversed head list concatenated with the tail, otherwise go back to step 3 This algorithm (a) finds an equivalent set of serial assignments, and (b) it is clearly locally minimal in the sense that whenever it introduces a temporary in step 5, there was no alternative but to do so. 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. -- 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