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 BE96EBC88 for ; Tue, 8 Feb 2005 18:39:03 +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 j18Hd3P9019150 for ; Tue, 8 Feb 2005 18:39:03 +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 SAA32246 for ; Tue, 8 Feb 2005 18:39:02 +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 j18Hd07P017645 for ; Tue, 8 Feb 2005 18:39:02 +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 j18HccYV067898; Wed, 9 Feb 2005 04:08:50 +1030 (CST) Subject: Re: [Caml-list] paralell assignment problem From: skaller Reply-To: skaller@users.sourceforge.net To: Florian Hars Cc: caml-list In-Reply-To: <4208E2D3.3090700@bik-gmbh.de> References: <1107832025.13571.260.camel@pelican.wigram> <4208E2D3.3090700@bik-gmbh.de> Content-Type: text/plain Message-Id: <1107884318.5022.195.camel@pelican.wigram> Mime-Version: 1.0 X-Mailer: Ximian Evolution 1.2.2 (1.2.2-4) Date: 09 Feb 2005 04:38:38 +1100 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4208F937.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 4208F934.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 sourceforge:01 florian:01 hars:01 wrote:01 wrote:01 compilers:01 lazy:01 restores:01 pubs:01 compiler:01 compiler:01 glebe:01 burger:98 061:98 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 03:03, Florian Hars wrote: > skaller wrote: > > Does anyone know how to solve the parallel assignment problem > > I seek a solution which minimises the number of assignments. > > What, in polynomial time? Actually total exhaustion may be quite feasible for small numbers of assignments which is typical for many tight loops presented as tail-recursive self calls. In this case 'perfection' is desirable, whereas if there are 20 arguments, 'good enough' is probably good enough.. > But the comp.compilers link seems relevant and points further to > > [3] Robert G Burger, Oscar Waddell, and R. Kent Dybvig. > Register allocation using lazy saves, eager restores, > and greedy shuffling. In 1995 ACM Conference on Programming > Language Design and Implementation, June 1995, pages 130-138. > Available online via > ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/Reg-Alloc-PLDI95.ps.gz > > which claims NP-completeness for the problem. Ah, section 2.3 suggests 'Greedy Shuffling' is useful. At present my algorithm is picking an arbitrary assignment, but this paper suggests picking the which is depended on most. They claim in only one program, their compiler, did this yield non-optimal results, and in the compiler only in 6 of 20,245 cases, in all of which only one additional temporary was allocated. So, thanks, this seems to be enough to finish of the algorithm with some confidence the results will be good! -- 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