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

On Wed, 7 Jan 2004, Valery A.Khamenya wrote:
> Wednesday, January 7, 2004, 9:37:19 PM, you wrote:
>
> Well, Chris, let's forget about traditions (finally LLVM is
> tradition-breaking thing!). At which level the optimization like i've
> meant *should* be implemented?..
Ok, I thought you were concerned about LLVM breaking the _correctness_ of
distributed programs, sorry.  :)
> If a priori optimization is restricted to a one host, then nothing to
> discuss. But just imagine that you say: "OK, let's make a basic
> support for code eval distributed to multiple hosts" :)
>   2. LLVM could bring a *lot* to distributed computing, if distributed
>      computing will be a *part* of LLVM concept.
Sure, that makes sense.  It's quite possible that there are things that
make sense to move down to the LLVM level, exposing all kinds of neat
opportunities.  If you'd like to look into this, that would be cool!  :)

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

My $0.02 worth on this topic ..

I'm also interested in distributed computing as XPL/XPS will support it.
However, I find it unreasonable to expect LLVM to provide any features
in this area.  In order to do anything meaningful, LLVM would have to
have some kind of awareness of networks (typically an operating system
concern).  That seems at odds with the "low level" principles of LLVM.

Valery, could you be more explicit about what kind of features in LLVM
would support distributed computing? How would code evaluation
distributed to multiple hosts benefit anyone? The two programs only
communicate via a network connection. The only places you can optimize
that network connection are in (a) the kernel and (b) the application.
Case (a) is outside the scope of LLVM and case (b) is supported by LLVM
today.  I assume this is obvious so what else were you thinking?

Reid. 

On Wed, 2004-01-07 at 16:00, Chris Lattner wrote:
> On Wed, 7 Jan 2004, Valery A.Khamenya wrote:
> > Wednesday, January 7, 2004, 9:37:19 PM, you wrote:
> >
> > Well, Chris, let's forget about traditions (finally LLVM is
> > tradition-breaking thing!). At which level the optimization like
i've
> > meant *should* be implemented?..
> 
> Ok, I thought you were concerned about LLVM breaking the _correctness_ of
> distributed programs, sorry.  :)
> 
> > If a priori optimization is restricted to a one host, then nothing to
> > discuss. But just imagine that you say: "OK, let's make a
basic
> > support for code eval distributed to multiple hosts" :)
> >   2. LLVM could bring a *lot* to distributed computing, if distributed
> >      computing will be a *part* of LLVM concept.
> 
> Sure, that makes sense.  It's quite possible that there are things that
> make sense to move down to the LLVM level, exposing all kinds of neat
> opportunities.  If you'd like to look into this, that would be cool! 
:)
> 
> -Chris
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20040107/29a90bea/attachment.sig>

> My $0.02 worth on this topic ..
and again |0.02 of mein :-)
 
> However, I find it unreasonable to expect LLVM to provide 
> any features in this area.  In order to do anything meaningful, 
> LLVM would have to have some kind of awareness of networks
> (typically an operating system concern).  
> That seems at odds with the "low level" principles of LLVM. 
When I look at what we have today -- I agree.
But when I think about what we *should* have -- I don't agree.

For the very beginning think of a host with multiple CPUs. 
I could formulate my proposal even for this non-networked 
case. 

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. 
 
> Valery, could you be more explicit about what kind of 
> features in LLVM would support distributed computing? 
OK, np, I will try.

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. 

Is it OK up to here and I could continue using this 
model example?
> How would code evaluation
> distributed to multiple hosts benefit anyone?
For me it sounds like:
"do we need distributed computations at all?"

oh... could we take this as axiom?.. :-)
anyway, if you accept this model examlpe above we could 
see how it really could work.
> The two programs only communicate via a network connection. 
> The only places you can optimize that network connection are 
> in (a) the kernel and (b) the application.
> Case (a) is outside the scope of LLVM and case (b) is supported by LLVM
> today.  I assume this is obvious so what else were you thinking?
Let's consider both case (a) and (b) in more details.
Think of Fib. example as application from your case (b).
We transfer Fib. module into LLVM bytecode without 
optimization. Now I run this application
with some dispatcher (someday it will be part of kernel 
of LLVM-based OS). This dispatcher makes some reasonable 
optimizations to a LLVM-bytecode and starts the 
Fib code with argument provided by user. 
If argument is small enough, then function will give us a 
result soon, of course. Otherwize is however more interesting:
if argument is big enough then we load CPU very quickly and
we have to splash out our code to any other available CPUs.

Before LLVM project I'd never discuss something like this at
all, because of non-feasibility of such a realisation. I do
believe that with LLVM such a future is really possible. 
I do believe as well, that there should appear OSes 
with LLVM in kernel. Chris, you and others, could find 
these statements funny today, but tomorrow you could find 
more reason in these "strange" statements :)
(Who knows, maybe Chris is laughing now, because it is 
more then clear for him)

What should I expand/reformulate?

Valery.