Re: [Caml-list] paralell assignment problem

[skaller <skaller@users.sourceforge.net>]

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