llvm dev - Jan 2004 - [LLVMdev] Re: idea 10

> I did not mean that one must change the Fibonacci function code, but 
> that there are other way to express it, and that some of these 
> expression are more suitable for parallelization. The "continuation 
> passing style" is just a possibility among many others.
well, what to do with this example then? :)

 
> The problem I see is that the Fibonacci function you propose only fits 
> to a particular domain of "distributed computing", and does not
cover
> the broad range of needs that arise in distributed computing. As I 
> presented in an earlier post, parallelization can be implemented in many 
> ways, and can unravel many issues.
I am not that brave as to try to cover the broad range of needs 
just with one example :)

I'd only say, that more simple examples could bring this 
discussian to somthing clear and hopfully somthing 
valuable.
> Anyway, I'm curious to see how the Fibonacci function could be 
> optimized. What kind of optimizations would you propose ?
oh, it is the worst form of Fibonacci function! 
it has O(2^n) complexity! There is a
lot of optimization abilities even at single CPU,
up to linear time and constant memory  ;)

However in this form it is a good model to discuss 
simple problems of distributed computations.
(we could use Ackerman function as alternative)

--
Valery

Hi Valery,

Valery A.Khamenya wrote:
>>To me this appears more as an algorithmic design issue, this function 
>>could be rewritten in "continuation passing style", and each 
>>continuation could be distributed by a load-balancing strategy to the 
>>computers sharing CPU resources. Using mechanisms such as
"futures" (as
>>in Mozart) allows to do this easily...
>>    
>>
>
>1. It looks like you mean here, that one *must* change the 
>code of Fib function in order to control the 
>parallelization, right?
>
>2. do you propose to ignore languages not supporting "continuation
passing style"?
>  
>
I did not mean that one must change the Fibonacci function code, but 
that there are other way to express it, and that some of these 
expression are more suitable for parallelization. The "continuation 
passing style" is just a possibility among many others.
>>but I don't think these features 
>>belong to the set of languages low level primitives and constructs.
>>    
>>
>
>if you don't pollute Fib. function with explicit 
>optimizations and use language like C, then what kind 
>of level should bring "parallel optimization" 
>to your Fib. code?.. 
>
>don't forget, I'd like to parallelize any parallelizable 
>code, like in this Fib. example, written in C
>  
>
>More practically: let's use Fib example to get it parallelized 
>in terms of LLVM. The example is simple enough!
>  
>
The problem I see is that the Fibonacci function you propose only fits 
to a particular domain of "distributed computing", and does not cover 
the broad range of needs that arise in distributed computing. As I 
presented in an earlier post, parallelization can be implemented in many 
ways, and can unravel many issues.

Anyway, I'm curious to see how the Fibonacci function could be 
optimized. What kind of optimizations would you propose ?

-- Se'bastien