Parallel computing with common lisp
by Eric Lavigne · in Technical Issues · 03/19/2005 (9:32 am) · 8 replies
I'm pretty sure that parallel computing is not part of ANSI Common Lisp. I'm also pretty sure that a lot of parallel computing is done in Lisp (google searches and library searches on Lisp give lots of parallel computing hits). This combination leads to a lot of confusion for a Lisp newbie (me).
Are there any common threads in terms of how parallel computing features are implemented in Common Lisp interpreters/compilers? Is it all focused on explicit message passing, or are certain types of Lisp operations naturally parallelizeable? Do I divide my program into 100 threads and let the interpreter load balance those threads over 10 processors automatically or do I need to keep track of thread performance and move threads manually? Are there parallel computing libraries that work with a variety of compilers or does each one have its own way of implementing parallel computing?
So far all I have found are research articles (loads of them, very easy to find) about how some researcher used Lisp to solve this huge problem that involved parallel computing. What I am looking for is something more general aimed at how to do parallel computing with an emphasis on implementation in Common Lisp variants. I have also tried searching for Lisp compilers that support parallel computing, but instead I keep finding pages that list many compilers, some of which are Lisp and some of which support parallel computing, no overlap.
The ideal solution that I am looking for is a compiler/interpreter that I can use now for free, a fast professional quality compiler/interpreter that I can use later, a relatively straightforward migration path between the two for my parallel computing code, and a matching programmer's guide for learning about parallel computing strategy on these two implementations of Lisp. If parallel were part of the ANSI standard, I would just grab a free implementation and worry about porting to a better compiler later. If the implementations are too different, though, that could be a bad idea.
Any ideas about how to research this problem (or better yet links to articles) are appreciated.
Are there any common threads in terms of how parallel computing features are implemented in Common Lisp interpreters/compilers? Is it all focused on explicit message passing, or are certain types of Lisp operations naturally parallelizeable? Do I divide my program into 100 threads and let the interpreter load balance those threads over 10 processors automatically or do I need to keep track of thread performance and move threads manually? Are there parallel computing libraries that work with a variety of compilers or does each one have its own way of implementing parallel computing?
So far all I have found are research articles (loads of them, very easy to find) about how some researcher used Lisp to solve this huge problem that involved parallel computing. What I am looking for is something more general aimed at how to do parallel computing with an emphasis on implementation in Common Lisp variants. I have also tried searching for Lisp compilers that support parallel computing, but instead I keep finding pages that list many compilers, some of which are Lisp and some of which support parallel computing, no overlap.
The ideal solution that I am looking for is a compiler/interpreter that I can use now for free, a fast professional quality compiler/interpreter that I can use later, a relatively straightforward migration path between the two for my parallel computing code, and a matching programmer's guide for learning about parallel computing strategy on these two implementations of Lisp. If parallel were part of the ANSI standard, I would just grab a free implementation and worry about porting to a better compiler later. If the implementations are too different, though, that could be a bad idea.
Any ideas about how to research this problem (or better yet links to articles) are appreciated.
About the author
#2
1) The professional level Lisp interpreters/compilers are LispWorks(Xanalys) and Franz. LispWorks has a Personal Edition that is free, but the Personal Edition has parallel processing support ripped out. The version with parallel processing is thousands of dollars, way out of my price range. Franz also has a trial edition, which you have to renew every two months and reaffirm that you are just trying it. It is missing lots of features also, and I haven't figured out if parallel processing is one of the missing features.
2) There is a standard for parallel processing in Common Lisp. It is called CORBA and is maintained by omg.org. Both of the Common Lisp companies above support the CORBA standard. OMG claims that CORBA is also used by many other languages (FORTRAN, C++, Python, Java....) so I wonder if anyone else has heard of it. Well, whether they are exagerating or not, they do seem to be the standard for Lisp so I found what I was looking for.
3) There is CORBA support for free versions of Common Lisp, such as clisp which I am using now. To get CORBA support for clisp, I need to use CLORB from clorb.sourceforge.net. It is marked as an alpha version, so I am bracing myself for a nightmarish installation process. Anyway, light at the end of the tunnel.
>for i = 1 to 100 for each processor a to z
>...
>end
I think I've seen this construction before, probably for fortran 90. I like this one, looks much cleaner than a message oriented setup.
>A good source for parallel stuff is Cray site, it has info on Parallel
>C and Parallel fortran.
I haven't looked at this yet, but it sounds like a good idea. I'll check that out tomorrow.
>Programming paralel functions for dual processors require some
>thread starting and stopping functions. maybe if you check your
>compiler reference, it will show you a flag that optimizes parallel
>processing in some arithmetic evaluation
I am thinking more along the lines of 10-100+ processors, each with dedicated memory. A beowolf cluster or supercomputer rather than just a dual processor PC. For initial development (no budget) I'd like to simulate such an environment on my single processor PC (no speed boost of course) just to get the hang of parallel programming. I've never done anything like this before, though, so the whole thing is rather overwhelming.
03/19/2005 (5:56 pm)
I've started to answer some of my questions:1) The professional level Lisp interpreters/compilers are LispWorks(Xanalys) and Franz. LispWorks has a Personal Edition that is free, but the Personal Edition has parallel processing support ripped out. The version with parallel processing is thousands of dollars, way out of my price range. Franz also has a trial edition, which you have to renew every two months and reaffirm that you are just trying it. It is missing lots of features also, and I haven't figured out if parallel processing is one of the missing features.
2) There is a standard for parallel processing in Common Lisp. It is called CORBA and is maintained by omg.org. Both of the Common Lisp companies above support the CORBA standard. OMG claims that CORBA is also used by many other languages (FORTRAN, C++, Python, Java....) so I wonder if anyone else has heard of it. Well, whether they are exagerating or not, they do seem to be the standard for Lisp so I found what I was looking for.
3) There is CORBA support for free versions of Common Lisp, such as clisp which I am using now. To get CORBA support for clisp, I need to use CLORB from clorb.sourceforge.net. It is marked as an alpha version, so I am bracing myself for a nightmarish installation process. Anyway, light at the end of the tunnel.
>for i = 1 to 100 for each processor a to z
>...
>end
I think I've seen this construction before, probably for fortran 90. I like this one, looks much cleaner than a message oriented setup.
>A good source for parallel stuff is Cray site, it has info on Parallel
>C and Parallel fortran.
I haven't looked at this yet, but it sounds like a good idea. I'll check that out tomorrow.
>Programming paralel functions for dual processors require some
>thread starting and stopping functions. maybe if you check your
>compiler reference, it will show you a flag that optimizes parallel
>processing in some arithmetic evaluation
I am thinking more along the lines of 10-100+ processors, each with dedicated memory. A beowolf cluster or supercomputer rather than just a dual processor PC. For initial development (no budget) I'd like to simulate such an environment on my single processor PC (no speed boost of course) just to get the hang of parallel programming. I've never done anything like this before, though, so the whole thing is rather overwhelming.
#3
You can spawn multiple threads on just one node using both MPI and OpenMP, so a single processor system can be used to test parallel algorithms.
Learning both MPI and OpenMP is relatively simple and you can write a lot of code using just a few of the available functions. The difficult part is deciding how to parallelize a problem for anything that isn't "embarassingly parallel".
Some languages such as Fortran 90 are data parallel (SIMD) and good compilers for it will perform some operations in parallel.
In my opinion, if you want to really write parallel code, learn MPI.
03/19/2005 (6:37 pm)
There are standard APIs for parallel computing, these being OpenMP and MPI, allowing for portable parallel code. OpenMP is best suited for shared memory architecture whereas MPI can be used for shared and distributed memory systems. MPI is more powerful but also requires the programmer to decide how, when, and where messages are passed, whereas OpenMP is more automatic. As far as I know, OpenMP and MPI are currently supported for C/C++ and Fortran only. You can download a free implementation of MPI called MPICH from Argonne National Lab that is supported on a number of platforms including windows.You can spawn multiple threads on just one node using both MPI and OpenMP, so a single processor system can be used to test parallel algorithms.
Learning both MPI and OpenMP is relatively simple and you can write a lot of code using just a few of the available functions. The difficult part is deciding how to parallelize a problem for anything that isn't "embarassingly parallel".
Some languages such as Fortran 90 are data parallel (SIMD) and good compilers for it will perform some operations in parallel.
In my opinion, if you want to really write parallel code, learn MPI.
#4
I will do that, or at least learn the basic concepts, to get an idea of what is possible in distributed computing. MPI does seem to be available or Lisp:
STAR/MPI
Whether I stick with it or not, well I don't know what else is out there yet. Still drowning in a sea of possibilities at this point, and I don't understand any of them yet ^^
>The difficult part is deciding how to parallelize a problem for
>anything that isn't "embarassingly parallel".
My problem is not embarrassingly parallel, and this will certainly be a challenge. I am doing neutron transport calculations. To avoid explaining nuclear physics, let's just say it's computationally similar to calculating the flow of water through a region. Every part of the region has some effect on the flow in every other part of the region (indirectly), but parts that are closer to each other have more effect (directly). It is possible to break the problem up spatially, solve a small part based on assumptions about other parts, stop to check against the results of nearby regions (how close were my initial assumptions), and do the whole thing over again using more accurate assumptions. This definitely breaks the problem up, but there is a lot of synchronization going on that reduces parallel efficiency. There will also be issues of how finely to break up the problem (high flow and high turbulence areas require finer meshing). I think the success of my project will depend very heavily on how well I handle the meshing. Some codes use constant meshing (inefficient, you end up using fine mesh everywhere for reasonable accuracy). I know of only one code that does variable meshing, but that is enough to raise the bar. I have to match that and add a few extra features to make this worthwhile. One idea I have to beat that code's performance is dynamic meshing, in which the mesh becomes more fine later in execution as needed. This has two advantages:
(1)Early calculations to get the first rough estimates are fast because the earlier mesh is very course.
(2)Final meshing is better optimized because it is based on intermediate results rather than on guessing where finer meshing is needed before the program is run.
>2) There is a standard for parallel processing in Common Lisp.
>It is called CORBA and is maintained by omg.org. Both of the
>Common Lisp companies above support the CORBA standard. OMG
>claims that CORBA is also used by many other languages (FORTRAN,
>C++, Python, Java....) so I wonder if anyone else has heard of it.
>Well, whether they are exagerating or not, they do seem to be the
>standard for Lisp so I found what I was looking for.
I spoke too soon on this one. Yes, both of the commercial interpreters I found support CORBA, but they also support many other styles of parallel computing. CORBA seems to be the least-common-denominator approach which allows you to communicate with any other programs (web servers, C++, Java, whatever), while the other options provide a lot more power with the assumption that you will only use them to communicate with other threads in the same language. More power? What sort of power? Well, I heard something about defining new functions and then evaluating them in another thread... I don't really understand everything I read. Looks like I need to get over being a Lisp newbie before I figure out parallel processing in Lisp.
Edit: typo
03/19/2005 (7:48 pm)
>In my opinion, if you want to really write parallel code, learn MPI.I will do that, or at least learn the basic concepts, to get an idea of what is possible in distributed computing. MPI does seem to be available or Lisp:
STAR/MPI
Whether I stick with it or not, well I don't know what else is out there yet. Still drowning in a sea of possibilities at this point, and I don't understand any of them yet ^^
>The difficult part is deciding how to parallelize a problem for
>anything that isn't "embarassingly parallel".
My problem is not embarrassingly parallel, and this will certainly be a challenge. I am doing neutron transport calculations. To avoid explaining nuclear physics, let's just say it's computationally similar to calculating the flow of water through a region. Every part of the region has some effect on the flow in every other part of the region (indirectly), but parts that are closer to each other have more effect (directly). It is possible to break the problem up spatially, solve a small part based on assumptions about other parts, stop to check against the results of nearby regions (how close were my initial assumptions), and do the whole thing over again using more accurate assumptions. This definitely breaks the problem up, but there is a lot of synchronization going on that reduces parallel efficiency. There will also be issues of how finely to break up the problem (high flow and high turbulence areas require finer meshing). I think the success of my project will depend very heavily on how well I handle the meshing. Some codes use constant meshing (inefficient, you end up using fine mesh everywhere for reasonable accuracy). I know of only one code that does variable meshing, but that is enough to raise the bar. I have to match that and add a few extra features to make this worthwhile. One idea I have to beat that code's performance is dynamic meshing, in which the mesh becomes more fine later in execution as needed. This has two advantages:
(1)Early calculations to get the first rough estimates are fast because the earlier mesh is very course.
(2)Final meshing is better optimized because it is based on intermediate results rather than on guessing where finer meshing is needed before the program is run.
>2) There is a standard for parallel processing in Common Lisp.
>It is called CORBA and is maintained by omg.org. Both of the
>Common Lisp companies above support the CORBA standard. OMG
>claims that CORBA is also used by many other languages (FORTRAN,
>C++, Python, Java....) so I wonder if anyone else has heard of it.
>Well, whether they are exagerating or not, they do seem to be the
>standard for Lisp so I found what I was looking for.
I spoke too soon on this one. Yes, both of the commercial interpreters I found support CORBA, but they also support many other styles of parallel computing. CORBA seems to be the least-common-denominator approach which allows you to communicate with any other programs (web servers, C++, Java, whatever), while the other options provide a lot more power with the assumption that you will only use them to communicate with other threads in the same language. More power? What sort of power? Well, I heard something about defining new functions and then evaluating them in another thread... I don't really understand everything I read. Looks like I need to get over being a Lisp newbie before I figure out parallel processing in Lisp.
Edit: typo
#5
I seem to recall that neutron transport was first modeled using Monte Carlo simulations by Ulam or maybe Pauli.
03/19/2005 (8:42 pm)
There are mesh and adaptive mesh refinement algorithms (AMR) out there that address some of the same issues you face. Might look at some CFD algorithms or something like UMT98 or UMT2000.I seem to recall that neutron transport was first modeled using Monte Carlo simulations by Ulam or maybe Pauli.
#6
>out there that address some of the same issues you face. Might
>look at some CFD algorithms or something like UMT98 or UMT2000.
Excellent point. Neutron transport codes were my first introduction to parallel computing, so I looked at the best ones and assumed they were state of the art. I will certainly check out the methods of other fields, including CFD. It was foolish of me to assume that my field was at the leading edge of parallel computing technology.
>I seem to recall that neutron transport was first modeled
>using Monte Carlo simulations by Ulam or maybe Pauli.
This is not relevant. My code will be a deterministic code. In other words, solving differential equations that describe the overall behavior of a group of neutrons. Monte Carlo tracks individual neutrons and generates statistics based on recording many simulated histories. Both methods are used frequently. Both have their inherent advantages and disadvantages. My impression, though, is that Monte Carlo is already done very well and I have no chance to make a significant contribution there. The deterministic codes all have significant weaknesses, though, and there is an opportunity for me to make a difference in that area.
03/19/2005 (9:12 pm)
>There are mesh and adaptive mesh refinement algorithms (AMR) >out there that address some of the same issues you face. Might
>look at some CFD algorithms or something like UMT98 or UMT2000.
Excellent point. Neutron transport codes were my first introduction to parallel computing, so I looked at the best ones and assumed they were state of the art. I will certainly check out the methods of other fields, including CFD. It was foolish of me to assume that my field was at the leading edge of parallel computing technology.
>I seem to recall that neutron transport was first modeled
>using Monte Carlo simulations by Ulam or maybe Pauli.
This is not relevant. My code will be a deterministic code. In other words, solving differential equations that describe the overall behavior of a group of neutrons. Monte Carlo tracks individual neutrons and generates statistics based on recording many simulated histories. Both methods are used frequently. Both have their inherent advantages and disadvantages. My impression, though, is that Monte Carlo is already done very well and I have no chance to make a significant contribution there. The deterministic codes all have significant weaknesses, though, and there is an opportunity for me to make a difference in that area.
#7
www.lispworks.com
www.franz.com
Comparing MPI and CORBA
[The MPI communication package] has many advantages, e.g., ease of use and efficiency, but it is also inherently tied to procedural programming. As object-oriented languages are becomming more and more popular, we found it interesting to investigate an alternative to MPI, namely CORBA, which can be used from a variety of object-oriented languages.
Beowulf HOW-TO
Step by step instructions for configuring some linux boxes to work together using MPI.
MPI - message passing interface
PVM - Parallel Virtual Machine
Erlisp
Why is it that Common Lisp is better than "mainstream" languages in a lot of ways, but not in parallelism and distributed programming? Is it just because threads with shared memory and locking are the best we can do for parallelism, and because socket and RPC libraries are totally adequate for distributed programming? I think the answer is no. Some older Lisps and a few younger, non-Lisp languages like Erlang have intriguing approaches to concurrency that are easier to use and less "low-level" than this industry best practice.
Blogs
Parallel Computing in Lisp 1
Parallel Computing in Lisp 2
Parallel Computing in Lisp 3
Parallel Computing in Lisp 4
www.paulgraham.com/
03/20/2005 (4:35 pm)
Commercial Interpreterswww.lispworks.com
www.franz.com
Comparing MPI and CORBA
[The MPI communication package] has many advantages, e.g., ease of use and efficiency, but it is also inherently tied to procedural programming. As object-oriented languages are becomming more and more popular, we found it interesting to investigate an alternative to MPI, namely CORBA, which can be used from a variety of object-oriented languages.
Beowulf HOW-TO
Step by step instructions for configuring some linux boxes to work together using MPI.
MPI - message passing interface
PVM - Parallel Virtual Machine
Erlisp
Why is it that Common Lisp is better than "mainstream" languages in a lot of ways, but not in parallelism and distributed programming? Is it just because threads with shared memory and locking are the best we can do for parallelism, and because socket and RPC libraries are totally adequate for distributed programming? I think the answer is no. Some older Lisps and a few younger, non-Lisp languages like Erlang have intriguing approaches to concurrency that are easier to use and less "low-level" than this industry best practice.
Blogs
Parallel Computing in Lisp 1
Parallel Computing in Lisp 2
Parallel Computing in Lisp 3
Parallel Computing in Lisp 4
www.paulgraham.com/
Torque Owner Bruno Grieco
AFAIK, paralell languages compiler do not stick to any ANSI standard. That's because they need to stick to a specified platform.
The main difference I'm aware of is the "for each" clausule that sticks to loops, eg.
for i = 1 to 100 for each processor a to z
...
end
This and similar commands will say that the for will be distributed to all processors or if each will have it's own loop.
A good source for parallel stuff is Cray site, it has info on Parallel C and Parallel fortran.
Programming paralel functions for dual processors require some thread starting and stopping functions. maybe if you check your compiler reference, it will show you a flag that optimizes parallel processing in some arithmetic evaluation
a = ( b + c ) * ( d + e ) can be paralelized, while
a = ( a + (b * ( c + d ))) cannot
HTH