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