[Openmcl-devel] Speed, compilers and multi-core processors

Wed May 20 01:45:01 PDT 2009

Some thoughts...

There was quite a lot research about this at the end of the 80s and  
beginning of the 90s. There are several books published about parallel  
programming models in Lisp.

To exploit parallelism in popular hardware one can see several  
competing areas:

1) SIMD multimedia engines (Altivec, SSE, ...).   Lisp in general  
mostly missed this.
     There were some assembler-based approaches and some Lisps are  
using SSE for
     FP computation. Problem: different CPUs offfer different types of  
engines or none at all.

     Btw., the first Connection Machines (CM1, CM2) were a giant SIMD  
co-processor. The host (a Vax, SUN, Symbolics)
     was running a Lisp, too - controlling the Connection Machine.

2) Multiple cores/processors running concurrent threads.    Research,  
experiments and some products in Lisp.
     Due to 'Hyper-Threading' more than one thread may run on a core.
    Currently we have laptops with two native threads (two cores).  
Desktop computers already are offering
    16 native threads (8 cores with two threads each / Hyper- 
Threading) -> Mac Pro.
    CPUs may offer more threads in the coming years -> 64, 256.  
Existing examples are SUN's UltraSPARC T2 with
    up to 64 threads.

    The BBN Butterfly ( http://en.wikipedia.org/wiki/BBN_Butterfly_computers 
  ) computer ran a concurrent Scheme
    and on top of this a Common Lisp was implemented.

3) GPUs.    The LARGEST source of compute power for parallel  
computation in desktop computers and even many laptops:
      Graphic Processing Units. Apple works on that with OpenCL ( http://en.wikipedia.org/wiki/OpenCL 
  ), a language
     for programming CPUs, GPUs and DSPs based on C.
     The idea is that GPUs can be used for general purpose computing  
(GPGPU) ( http://en.wikipedia.org/wiki/GPGPU ).
     Some GPUs now offer more than 1000 GFlops (ATI Radeon 4890: 1360  
GFLOPS). Then you may put
     more than one GPU card in your desktop PC. Compare that to  
current CPUs offering in the range of 5 to 50 GFlops.

     Glen Foy mentioned 512 cores in ten years from now. The GPU is  
here today.

     Can't remember Lisp mentioned in the area of GPGPU.

     Definitely computing with GPUs is very attractive for scientific  
processing: processing of images, videos, sound, etc.

     Problem: this area is a moving target with rapidly changing  
products. Apple's Mac OS X 10.6 (Snow Leopard)
     will provide the foundations in the Mac area. I guess for the  
Desktop and Laptop user it may bring
     very interesting speed increases in the coming years, especially  
in computing with multimedia data.
     Conversions of video formats will run on the GPU. All kinds of  
video effects will run on the GPU.
     Music applications will render sounds on the GPU. Encryption,  
physics computation, rendering, etc.

4) Distributed computing: Clusters, P2P, code mobility, ...  Only some  
research and some experiments in Lisp.
      Erlang as programming language and runtime is notable in that  
area.

For some computing tasks it might not be enough to offer support for  
multiple concurrent threads on a CPU, when the GPU approach beats it  
by a factor of ten or even hundred. Most rendering, multimedia  
processing, etc. will move to GPUs, I'd guess.
Larger experiments are running on clusters - similar to what Dan  
Weinreb reports from their architectures at ITA.

Where does the multi-core-computing fit in? I'd say it is necessary to  
support it, but for many applications I would see other approaches to  
have advantages. Many network-applications and in the Lisp area many  
symbolic applications will benefit from concurrent threads.

More about 2)

Clozure CL currently offers some support for 2), running threads on  
multiple cores/processors.
There hasn't been much discussion lately of the problems of Common  
Lisp running on multiple cores.

Again, one could identify several levels of support for multi-core  
computing:

a) being able to run (native) threads on different cores.  CCL does  
this.

b) the Common Lisp implementation is thread safe. Say, if LOAD,  
DEFCLASS, COMPILE, are not reentrant, it
     is assured that only one can run at any one time. There is more  
to it, though.

c) Common Lisp constructs are thread safe and reentrant. Example: You  
could run multiple DEFCLASS (mostly) in parallel
     in one Lisp.

d) Common Lisp supports special programming facilities: futures,  
queues, stm, data parallelism, etc.

A special challenge is the garbage collector. Today we have few  
concurrent threads. In the near future one
may have 64 concurrent threads running on a desktop computer CPU. That  
means when all 64 threads are
busy, they may produce garbage 64 times as fast as a single thread. So  
it might be not that clever
to run the garbage generator with 64 threads and the garbage collector  
with only one thread (while halting other
Lisp computation).

It would also be interesting to identify general issues with Common  
Lisp with respect to implementing it with multiple concurrent threads  
- for example to compare implementations and to identify areas where  
implementations need to do something.

A useful 'conservative' approach is to advance the capabilities for  
programming with concurrent threads. But if a user's application  
domain offers chances for parallel computation, concurrent threads  
might not be the best answer. For the average user, the GPU approach  
could make a big difference in user experience in the next years - my  
guess.

Regards,

Rainer Joswig

Am 19.05.2009 um 14:05 schrieb Alexander Repenning:

> not so fast ;-)
>
> The "how can we make use of multiple cores" is currently on the the  
> hottest funding topics supported by NSF, DOE, Microsoft, .....
>
> Perhaps it is the Lisp way to look at architectures such as the x86  
> and see mostly limitations when indeed there are plenty of  
> opportunities. This is not about registers but about enabling end  
> user programmers such as scientists to make use of parallelism. The  
> big question is how to reconceptualize programming. One of the main  
> problems is the need to overcome bad algorithmic assumptions  
> especially the use of unnecessary loops. For instance, in  
> Bioinformatics textbooks are full of loop based implementations of  
> algorithms dealing with huge data structures such as gene sequences.  
> In many cases one could replace sequential loops with parallel  
> execution.
>
> Zoom out of the low level view of things. What could multi core Lisp  
> do? Look at the computational challenges that users are dealing  
> with. Try to come up with new computational paradigms that could  
> help. Lisp could be a great platform to explore these issues.  
> Careful: if you can contribute to this you may actually receive  
> funding.
>
> alex
>
>
>
> On May 18, 2009, at 10:45 AM, Brian Mastenbrook wrote:
>
>> On Mon, 2009-05-18 at 10:13 -0400, Glen Foy wrote:
>>
>>> My ignorance of compiler design is breathtaking, but could multi- 
>>> core
>>> compiler techniques be used to compensate for Intel's register- 
>>> starved
>>> architecture?
>>
>> In a word, no.
>
> Prof. Alexander Repenning
>
> University of Colorado
> Computer Science Department
> Boulder, CO 80309-430
>
> vCard: http://www.cs.colorado.edu/~ralex/AlexanderRepenning.vcf
>
>
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel

Rainer Joswig, Hamburg, Germany
http://lispm.dyndns.org/
mailto:joswig at lisp.de

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.clozure.com/pipermail/openmcl-devel/attachments/20090520/4827dbbc/attachment.htm>