[LLVMdev] Re: idea 10

[Reid Spencer]

Interesting email address there :)

On Thu, 2004-01-08 at 01:18, =?koi8-r?Q?=22?=Valery
A.Khamenya=?koi8-r?Q?=22=20?= wrote:

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

On the same machine, LLVM definitely needs to support both symmetric and
asymmetric multi-processing. I believe some primitives to support this
are being worked on now by Misha. However, I don't really consider this
"distributed systems" because distribution by a few inches doesn't
really amount to much. In my way of thinking distributed computing
*always* involves a network.

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

Okay, this kind of "distribution" (what I call parallel computing)
should also definitely be supported by LLVM. There are several
primitives that could be added to LLVM to enable compiler writers to
more easily write parallel programs. However, I don't think LLVM should
get involved in parallel programs that run on multiple computers, only a
single computer (possibly with multiple CPUs).

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

Yes, but I think the confusion was simply one of terminology. What
you're talking about is what I call parallel computing or
multi-processing (symmetric or asymetric). This isn't really distributed
computing although one could think of the operations being "distributed"
across several CPUs on the _same_ computer.

> 
> > How would code evaluation
> > distributed to multiple hosts benefit anyone?

Okay, now you're talking about "hosts" which I take to mean separate
physical computers with the only way for the "hosts" to communicate is
via a network. Is this what you mean by "host"?

> 
> For me it sounds like:
> "do we need distributed computations at all?"

No, we don't. Distributed computing would be built on top of LLVM (in my
opinion). But, we _do_ need support for parallel or multi-processing
computation as you described above (again, on a single physical
computer).

> oh... could we take this as axiom?.. :-)

I would accept "we need parallel computation support" as an axiom. I
don't think Chris will disagree, but I'll let him chime in on that.

> anyway, if you accept this model examlpe above we could 
> see how it really could work.

Sure ..

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

okay .. again, this isn't "distributed", just "parallel", and I agree
its needed.

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

I would tend to agree. I fully expect LLVM to fill the mission that Java
started: ubiquitous computing. I would expect to see LLVM programs
running on everything from gameboy to supercomputer, possibly with
kernel support. I've toyed with the idea of a Linux kernel module for
LLVM already. It would allow a bytecode file to be executed like any
other program. The JIT essentially inside the kernel. Weird idea but it
could be beneficial in terms of security. The module could be written in
such a way that it examines the bytecode before executing anything
making sure the bytecode isn't doing anything "weird". Since only the
kernel can create the actual executable for the bytecode, no malicious
bytecode program could run. This assumes that "malicious" is detectable
:) 

> 
> What should I expand/reformulate?

Nothing at this point. I think I realize where you're coming from now
and agree that _parallel_ computing is a very important next step for
LLVM.  Let's see what happens with the current work on synchronization
and threading primitives. These things will be needed to support the
kind of parallelization you're talking about.

> 
> Valery.

Best Regards,

Reid.
-------------- 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/20040108/49887f05/attachment.sig>