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 63D55BC88 for ; Tue, 8 Feb 2005 17:03:40 +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 j18G3dGa005849 for ; Tue, 8 Feb 2005 17:03:40 +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 RAA28907 for ; Tue, 8 Feb 2005 17:03:39 +0100 (MET) Received: from grisu.bik-gmbh.de (grisu.bik-gmbh.de [217.110.154.194]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j18G3cF5005846 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Tue, 8 Feb 2005 17:03:39 +0100 Received: from [192.168.125.193] ([192.168.125.193]) by grisu.bik-gmbh.de (8.12.11/8.12.11) with ESMTP id j18G3aAq050709; Tue, 8 Feb 2005 17:03:37 +0100 (CET). Message-ID: <4208E2D3.3090700@bik-gmbh.de> Date: Tue, 08 Feb 2005 17:03:31 +0100 From: Florian Hars User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.7.3) Gecko/20040924 Debian/1.7.3-1ubuntu1 X-Accept-Language: en MIME-Version: 1.0 To: skaller@users.sourceforge.net Cc: caml-list@inria.fr Subject: Re: [Caml-list] paralell assignment problem References: <1107832025.13571.260.camel@pelican.wigram> In-Reply-To: <1107832025.13571.260.camel@pelican.wigram> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4208E2DB.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 4208E2DA.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; florian:01 hars:01 hars:01 bik-gmbh:01 caml-list:01 wrote:01 compilers:01 lazy:01 restores:01 pubs:01 florian:01 %22:98 %22:98 burger:98 polynomial:02 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: 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? Most of the results seem to require paid subscriptions or a library at hand: http://www.google.com/search?q=%22parallel+assignment+problem%22 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. Yours, Florian.