[LLVMdev] Re: idea 10

[Se'bastien Pierre]

Hello Valery,

I have some comments regarding your thoughts on LLVM support for 
distributed computing.

Valery A.Khamenya wrote:

>There should be an engine and layer for making dispatching optimizations in run-time. If one CPU is loaded and code is 
>"parallelizable" why then not to send some part of 
>calculation to other CPU? This kind of on-fly decision will
>be one day incorporated in something like LLVM. 
>  
>
I'm not sure to correctly understand what you mean, but I interpret it 
as LLVM deciding where the code should be executed, like some 
load-balancing strategy. In this perspective, I think this should be 
left up to the higher-level language, or event to the application 
developer: I don't think incorporating load balancing strategies 
directly into LLVM would be interesting, because strategies are high 
level patterns.

>Consider this Fibonacci function as the model for our
>using case:
>
>f(int n) {
>  if(n<2) return 1;
>  return f(n-1) + f(n+2);
>}
>
>the complexity of this non-optimal version of Fibonacci 
>function is O(2^n). The number of calls after start 
>grows exponentionaly. It means that we have CPU loaded 
>very quickly and we have a lot of calls to be 
>"outsourced" to other CPUs. 
>  
>
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... but I don't think these features 
belong to the set of languages low level primitives and constructs.

I personally don't think that automating the conversion of an algorithm 
from non-distributed to distributed execution can be done at a low 
level, mainly because it involves many high-level constructs. On the 
other hand, I have heard of languages that try to implement primitives 
for easy distributed computing, like the "Unified Parallel C" (see 
http://www.gwu.edu/~upc/documentation.html and 
http://ludo.humanoidz.org/doc/report-en.pdf), which may help to figure 
out what kind of primitives would be useful for adding distributing 
computing support into LLVM.

Maybe you were thinking of something similar to UPC primitives added to 
LLVM ?

-- Se'bastien