Version française
Home     About     Download     Resources     Contact us    
Browse thread
paralell assignment problem
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Radu Grigore <radugrigore@g...>
Subject: Re: [Caml-list] Re: paralell assignment problem
On Tue, 08 Feb 2005 09:12:32 -0800 (PST), skaller
<skaller@users.sourceforge.net> wrote:

> 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.

I'm mildly convinced that it works.

Imagine a graph where an arrow is drawn from A to B only if A appears
in the expression to be assigned to B. You can imagine the process of
introducing temporaries as marking a few edges in this graph so that
you break all cycles. One marked edge = one temporary. But since no
identifier appears more than once on the left side, in this graph the
in-degree is at most 1 and each node is part of at most one cycle.
>From this it follows that each marked edge breaks at most one cycle.
Since all your temporaries break at least one cycle the algorithm
should work.

-- 
regards,
 radu
http://rgrig.idilis.ro/