Hi,
I just wanted to report on a little success story.
In the recent few months, I have been working on a new project that concerns itself with parallel programming. For that purpose, I experimented with variations of a home-grown work-stealing scheduler. (See http://en.wikipedia.org/wiki/Cilk#Work-stealing for a description of what work stealing is.) The development platform is LispWorks 6.0, which comes with an excellent library for SMP. (I would say it's the best of any dynamic language I am currently aware of, not just those of Lisp dialects.)
Performance matters in parallel programming. The benchmark application was a structured grid computation, like is for example used for computing heat equations, for running game of life, or for similar applications. This is easy to parallelize, because each processor can perform part of the computation on a sub-grid independently of all the other processors.
The hardware that I ran the experiments on is a 4x 6-core Intel Xeon "Dunnington" 2.67 GHz running Ubuntu.
For 200 iterations on a 4096x4096 matrix of single float values, I got the following runtimes: - with 8 cores ca. 19-20 secs. - with 16 cores ca. 9-10 secs. - with 24 cores ca. 8 secs.
The same experiment was also implemented by others in our group in the following languages: Unified Parallel C, Cilk++, C with MPI, OpenMP, and C++ with Threading Building Blocks. They all have slight variations in runtime, but all roughly in the same ballpark. The runtimes were: - with 8 cores ca. 10-11 secs. - with 16 cores ca. 8-10 secs. - with 24 cores ca. 8-10 secs.
The advantage of using Common Lisp is that I could still use higher-order constructs (closures) and have a pretty decent separation of concerns in the software architecture, while still getting very good efficiency. Of course, this required some pretty low-level tricks with type and optimization declarations in several places, but the nice thing about Common Lisp is that you don't have to be low-level right from the start, and only at the places that you identify as bottlenecks.
Unfortunately, I cannot present a lot more details at this stage, because most of this is covered by an NDA. I hope, though, that I can make the work-stealing scheduler available as an open source library at some later stage.
Pascal
On Fri, Jan 21, 2011 at 9:07 PM, Pascal Costanza pc@p-cos.net wrote:
The development platform is LispWorks 6.0, which comes with an excellent library for SMP. (I would say it's the best of any dynamic language I am currently aware of, not just those of Lisp dialects.)
I would be interested on learning what aspects of LispWorks make it interesting for SMP, specially if some of those ideas can be adapted to ECL. Does their library provide a better granularity when controlling threads than C? Is it the inter-process communication?
Juanjo
Pascal, could you please also try your code with open-source free Lisp implementations and give the numbers? :-)
On Mon, Jan 24, 2011 at 1:04 AM, Juan Jose Garcia-Ripoll juanjose.garciaripoll@googlemail.com wrote:
On Fri, Jan 21, 2011 at 9:07 PM, Pascal Costanza pc@p-cos.net wrote:
The development platform is LispWorks 6.0, which comes with an excellent library for SMP. (I would say it's the best of any dynamic language I am currently aware of, not just those of Lisp dialects.)
I would be interested on learning what aspects of LispWorks make it interesting for SMP, specially if some of those ideas can be adapted to ECL. Does their library provide a better granularity when controlling threads than C? Is it the inter-process communication? Juanjo
-- Instituto de Física Fundamental, CSIC c/ Serrano, 113b, Madrid 28006 (Spain) http://juanjose.garciaripoll.googlepages.com
pro mailing list pro@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/pro
On 24 Jan 2011, at 09:37, Yakov Zaytsev wrote:
Pascal, could you please also try your code with open-source free Lisp implementations and give the numbers? :-)
I'm currently focusing on making everything work well on LispWorks before considering porting to other CL implementations. That's in general a good approach: First make things work well in one CL implementation, and worry about portability later. Portability is quite easy to achieve at a late stage with Lisp, but may distract you too much from the important concepts initially.
Pascal
On Mon, Jan 24, 2011 at 1:04 AM, Juan Jose Garcia-Ripoll juanjose.garciaripoll@googlemail.com wrote:
On Fri, Jan 21, 2011 at 9:07 PM, Pascal Costanza pc@p-cos.net wrote:
The development platform is LispWorks 6.0, which comes with an excellent library for SMP. (I would say it's the best of any dynamic language I am currently aware of, not just those of Lisp dialects.)
I would be interested on learning what aspects of LispWorks make it interesting for SMP, specially if some of those ideas can be adapted to ECL. Does their library provide a better granularity when controlling threads than C? Is it the inter-process communication? Juanjo
-- Instituto de Física Fundamental, CSIC c/ Serrano, 113b, Madrid 28006 (Spain) http://juanjose.garciaripoll.googlepages.com
pro mailing list pro@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/pro
On 23 Jan 2011, at 23:04, Juan Jose Garcia-Ripoll wrote:
On Fri, Jan 21, 2011 at 9:07 PM, Pascal Costanza pc@p-cos.net wrote: The development platform is LispWorks 6.0, which comes with an excellent library for SMP. (I would say it's the best of any dynamic language I am currently aware of, not just those of Lisp dialects.)
I would be interested on learning what aspects of LispWorks make it interesting for SMP, specially if some of those ideas can be adapted to ECL. Does their library provide a better granularity when controlling threads than C? Is it the inter-process communication?
What is important in an SMP library is the kinds of synchronization primitives you get. LispWorks provides both very high-level synchronization via mailboxes, which are extremely convenient to use and cover 80-90% of all cases, in my experience. On top of that, LispWorks provides the usual mutual exclusion via locks, but also more fine-grained synchronization primitives, like read/write (shared) locks, compare-and-swap / atomic operations, barriers, and ordering of memory accesses. The API is very well designed and covers a lot of practically occurring cases.
LispWorks doesn't focus on providing a single parallel programming paradigm, but rather gives you the building blocks to create your own approach. We have already experimented with building STM, work stealing, data parallelism and automatic parallelization internally (to different extents), and it all works extremely well on top of LispWorks.
If you are looking for inspiration, I think the LispWorks documentation is available for free on their website. There is also a personal edition of LispWorks 6.0 that you can play with.
I hope this helps, Pascal
On Mon, Jan 24, 2011 at 10:04 AM, Pascal Costanza pc@p-cos.net wrote:
What is important in an SMP library is the kinds of synchronization primitives you get. LispWorks provides both very high-level synchronization via mailboxes, which are extremely convenient to use and cover 80-90% of all cases, in my experience. On top of that, LispWorks provides the usual mutual exclusion via locks, but also more fine-grained synchronization primitives, like read/write (shared) locks, compare-and-swap / atomic operations, barriers, and ordering of memory accesses. The API is very well designed and covers a lot of practically occurring cases.
What you say sounds reasonable and also feasible for any implementation out there. In particular ECL already provides read/write locks, the usual locks and will soon export compare-and-swap and atomic operations using libatomic-ops (which is part of ECL already, as it is used by the garbage collector).
If you are looking for inspiration, I think the LispWorks documentation is available for free on their website. There is also a personal edition of LispWorks 6.0 that you can play with.
Thanks for the pointer. Obviously, I would rather refrain from using the personal edition, as there might be some conflicts :-) but the documentation seems inspiring and terribly simple.
Juanjo
-
Juan Jose Garcia-Ripoll -
Pascal Costanza -
Yakov Zaytsev