Parallel Lisp

Kjetil wrote:
> anon wrote:
>> Sometime between 1995 and 2005 (last time I checked) all parallel and
>> concurrent languages seam to have disappeared. Now, that the average
>> person can buy or build a multi-processor system, we needs these
>> languages but for some reason they are no where to be found.
>> I know of only one parallel language that is non-lisp called "Sisal".
>> It is still on the net but is no longer supported by LLNL. It
>> automatic creates parallels code for the user.
>
> Does Erlang qualify?

There's also Mozart/Oz: http://www.mozart-oz.org/

On Sep 5, 9:54 am, "Mike G." <michael.graf...@gmail.com> wrote:
> Well, parallel programming languages have always been in something of
> a funk.

This is changing now, I think, mostly because of the multicore thing
and GPU's. Intel (Ct and other libraries) and NVidia (CUDA) each have
their own parallel languages and language extensions coming out.

> > I know of only one parallel language that is non-lisp called "Sisal". It
> > is still on the net but is no longer supported by LLNL. It automatic
> > creates parallels code for the user.

There are gobs and gobs of non-Lisp parallel languages out there. A
lot of them didn't survive longer than a PhD thesis, but some are used
regularly by small communities, enough for companies to justify
investing effort in developing optimizing compilers, despite the
existence of academic optimizing compilers that are pretty good. UPC
(Unified Parallel C) in particular comes to mind. Cilk has been
around for a while and is quite good for shared-memory environments; I
don't think they have a cluster back-end, at least not yet.

Erlang is a great language, but I don't think they have a good cluster
backend yet. Their shared-memory backend is fairly recent (it's
covered in an Erlang book that came out this year), and their
distributed-memory backend still relies on TCP/IP (rather than going
over MPI or GASNet and thus exploiting specialized high-bandwidth, low-
latency cluster network hardware). This was a logical choice for
Erlang's original purpose in telecommunications. Hopefully porting it
to use MPI or GASNet won't be too hard...

I think someone is working on an Erlang-like extension to CL, called
"ErLisp." I'm not sure whether that project is active.

mfh

On Sep 5, 7:23 am, "Mike G." <michael.graf...@gmail.com> wrote:
> I've spent a little free time over the last two months building a
> multi-processor / multi-core network computer in my basement. In no
> time at all, I've been able to hack up some primitives for doing
> parallel processing across this network in SBCL.

I'd love to hear about the details -- are you using MPI for the back-
end?

mfh

Scott Burson <FSet.SLB@gmail.com> writes:

> On Sep 5, 9:59 am, Kjetil <n...@no.no> wrote:
> > Does Erlang qualify?
>
> And does anyone here have any experience with Erlisp?
>
> http://common-lisp.net/project/erlisp/
>
> (Just asking -- I haven't tried it.)
>
> -- Scott

Since noone else feels inclined to answer, I'll have a go for it: I tried
Erlisp and the examples worked nice for me. It looks like a nice language
if you have a problem which can be mapped to interacting processes (e.g. a
game of multiple players). For my application domain (numerics of partial
differential equations), I am more interested in parallelization for
efficiency (i.e. exploting multiple processors). At the moment, I am
parallelizing on a shared-memory basis, with quite a lot of
"communication". Erlisp is not (yet?) adequate here, because it
communicates using strings, and because it does not work for distributed
memory architectures. However, I think that it might be a rather good
interface also in this situation, if it is extended appropriately (probably
using MPI under the hoods).

Nicolas

Sorry, forget this post. I had tested CL-MUPROC, not Erlisp.

Nicolas

Nicolas Neuss <lastname@mathematik.uni-karlsruhe.de> writes:

> Scott Burson <FSet.SLB@gmail.com> writes:
>
> > On Sep 5, 9:59 am, Kjetil <n...@no.no> wrote:
> > > Does Erlang qualify?
> >
> > And does anyone here have any experience with Erlisp?
> >
> > http://common-lisp.net/project/erlisp/
> >
> > (Just asking -- I haven't tried it.)
> >
> > -- Scott
>
> Since noone else feels inclined to answer, I'll have a go for it: I tried
> Erlisp and the examples worked nice for me. It looks like a nice language
> if you have a problem which can be mapped to interacting processes (e.g. a
> game of multiple players). For my application domain (numerics of partial
> differential equations), I am more interested in parallelization for
> efficiency (i.e. exploting multiple processors). At the moment, I am
> parallelizing on a shared-memory basis, with quite a lot of
> "communication". Erlisp is not (yet?) adequate here, because it
> communicates using strings, and because it does not work for distributed
> memory architectures. However, I think that it might be a rather good
> interface also in this situation, if it is extended appropriately (probably
> using MPI under the hoods).
>
> Nicolas

On Sep 6, 6:02 pm, "Mark H." <mark.hoem...@gmail.com> wrote:
> On Sep 5, 7:23 am, "Mike G." <michael.graf...@gmail.com> wrote:
>
> > I've spent a little free time over the last two months building a
> > multi-processor / multi-core network computer in my basement. In no
> > time at all, I've been able to hack up some primitives for doing
> > parallel processing across this network in SBCL.
>
> I'd love to hear about the details -- are you using MPI for the back-
> end?
>
> mfh

No, I'm not using MPI just yet -- but that is an evolution I might
take.
I used MPI for awhile back in university and thought it was great,
but
I'm not sure how much of a win it would be for Lisp. Any thoughts?

In any event, my core primitives are quite simple and it would be
easy
to abstract the data/code-passing out to MPI-bindings in the future.
At least, from what I remember of MPI it will be easy, any way

Right now I'm just using raw sockets in a peer-to-peer fashion. Peers
are assumed to have identical Lisp worlds. They query a tracker
(possibly
one of many) to find other free peers who can do some work for them.
There is a simple RPC-like mechanism, which I haven't exploited much
yet - generally I just send out S-expressions to be EVALed.

The trackers also maintain parallel variables (stored in hash
tables),
with simple spin-locks to keep everything tip-top.

On top of primitives to eval code and set/fetch parallel variables,
I have implemented pmap and plet* and a few other parallel analogs of
ordinary Common Lisp. They work quite well, and give a reasonable
speed
up given the circumstances -- i'm going to work in some logic to
determine
what sorts of expressions can be invoked by my RPC mechanism instead
of
invoking the full EVAL. I doubt it will do much good, but its a worthy
compile-time optimization.

Its all quite crude, to be sure, but it is still REALLY fun to be able
to run paralleled stuff from the REPL.

For kicks, I think I'm going to hook up some LEDs to the parallel
ports
of these boards. As each thread goes active I'll have it turn on a
light
and when it idles it will turn it off. Might actually help with some
debugging too

On Sep 5, 4:23 pm, "Mike G." <michael.graf...@gmail.com> wrote:

> The idea is that the variables get initialized (as per an ordinary
> let), each form in the body gets executed in parallel, and exit-form
> is a chunk of code that executes after all parallel threads have ended
> which ties everything together. This macro expands into my primitives
> to initialize / access variables via my centralized tracker and a loop
> which patiently waits for the threads to complete. Works well enough.
>
> I also have a parallel MAP which splits a map up across multiple
> cpu's / cores.
>
> Implementing this is what made me come looking for guidance because I
> can think of several ways to split up a MAP that might make sense
> under different circumstances.
>

I am afraid, on average, these schemes will not typically buy much
especially when the threads are unbalanced in terms of time they take
to finish. Parallel processing is gaining interest quickly again
because we seem to be forced to go this route to keep up with Moore's
law. In some recent benchmarks some clever Sony programmers did not
quite manage to get a significant benefit from the 8 Cell processors
of the SonyPlaystation 3 because of the communication +
synchronization overhead almost completely absorbed the parallel
advantage. At the time of the Connection machine we failed to gain
much advantage of the 64k CPU for similar reasons.

In the end you need a higher level of representation than individual
map statements or parallel assignments. You need computational models
that are parallel at a conceptual level such as spreadsheets. For
instance, you could analyze complex spreadsheets. The dataflow can be
nicely parallelized and mapped onto your cluster and executed as
functions.

Personally, I would be interested to see Antiobjects mapped onto your
cluster. Take for instance a Collaborative Diffusion of a 2D or 3D AI
problem. Give the user some tools to define the entire space but let
your cluster split that space up into chunks that you distribute onto
your cores/cpus. With fairly minimal communication overhead you can
solve hard AI problems with nearly perfect load balancing yet minimal
if any cognitive overhead to the programmer. That would be exciting.


Repenning, A., Collaborative Diffusion: Programming Antiobjects. in
OOPSLA 2006, ACM SIGPLAN International Conference on Object-Oriented
Programming Systems, Languages, and Applications, (Portland, Oregon,
2006), ACM Press.


http://www.cs.colorado.edu/~ralex/pa...ntiobjects.pdf

alex.repenning@gmail.com wrote:

> Repenning, A., Collaborative Diffusion: Programming Antiobjects. in
> OOPSLA 2006, ACM SIGPLAN International Conference on Object-Oriented
> Programming Systems, Languages, and Applications, (Portland, Oregon,
> 2006), ACM Press.
>
>
> http://www.cs.colorado.edu/~ralex/pa...ntiobjects.pdf
>

Very interesting, thanks a lot for sharing this.

Sacha

On Sep 10, 3:03 am, alex.repenn...@gmail.com wrote:
> On Sep 5, 4:23 pm, "Mike G." <michael.graf...@gmail.com> wrote:
>
> > The idea is that the variables get initialized (as per an ordinary
> > let), each form in the body gets executed in parallel, and exit-form
> > is a chunk of code that executes after all parallel threads have ended
> > which ties everything together. This macro expands into my primitives
> > to initialize / access variables via my centralized tracker and a loop
> > which patiently waits for the threads to complete. Works well enough.
>
> > I also have a parallel MAP which splits a map up across multiple
> > cpu's / cores.
>
> > Implementing this is what made me come looking for guidance because I
> > can think of several ways to split up a MAP that might make sense
> > under different circumstances.
>
> I am afraid, on average, these schemes will not typically buy much
> especially when the threads are unbalanced in terms of time they take
> to finish.

Well, yes and no. If the thread itself is not parallelized, then
you're
certainly correct. But in a situation where initial threads take more
time
than later threads, some of the unbalance can be corrected if initial
threads are parallelized - my system is peer-to-peer, so as peers
finish
up their work, they are available to take some more load from the
initial
thread. Provided, of course, that the threads are written in such a
way
as to make that possible.

> In some recent benchmarks some clever Sony programmers did not
> quite manage to get a significant benefit from the 8 Cell processors
> of the SonyPlaystation 3 because of the communication +
> synchronization overhead almost completely absorbed the parallel
> advantage. At the time of the Connection machine we failed to gain
> much advantage of the 64k CPU for similar reasons.

I had contemplated using PS3's instead of my bare-bones Xeons. It
costs
me more money per core this way (about twice as much, in fact) but I
can
easily add all the RAM I like.

> In the end you need a higher level of representation than individual
> map statements or parallel assignments. You need computational models
> that are parallel at a conceptual level such as spreadsheets. For
> instance, you could analyze complex spreadsheets. The dataflow can be
> nicely parallelized and mapped onto your cluster and executed as
> functions.

Well, yes. Much more is needed than some simple macros, of course.
After I work through some more reading from the QLisp and *Lisp
materials
I have, I'm going to start looking at some things like this. Not
necessarily
spreadsheet or matrix related stuff.. I'll probably do something for
polynomials.

>
> Personally, I would be interested to see Antiobjects mapped onto your
> cluster. Take for instance a Collaborative Diffusion of a 2D or 3D AI
> problem. Give the user some tools to define the entire space but let
> your cluster split that space up into chunks that you distribute onto
> your cores/cpus. With fairly minimal communication overhead you can
> solve hard AI problems with nearly perfect load balancing yet minimal
> if any cognitive overhead to the programmer. That would be exciting.
>
> Repenning, A., Collaborative Diffusion: Programming Antiobjects. in
> OOPSLA 2006, ACM SIGPLAN International Conference on Object-Oriented
> Programming Systems, Languages, and Applications, (Portland, Oregon,
> 2006), ACM Press.
>
> http://www.cs.colorado.edu/~ralex/pa...ntiobjects.pdf

Thanks for the link. I'll let you know if I end up doing anything
related to this.

anon <anon@anon.org> wrote:
> Sometime between 1995 and 2005 (last time I checked) all parallel and
> concurrent languages seam to have disappeared. Now, that the average
> person can buy or build a multi-processor system, we needs these
> languages but for some reason they are no where to be found.

Hmm, Occam is still alive, with at least two freely available compilers:
- KROC (Kent Retargetable Occam Compiler):
http://www.cs.kent.ac.uk/projects/ofa/kroc/
- The Amsterdam Compiler Kit also appears to contain an Occam compiler
http://tack.sourceforge.net/

Occam was designed as the native programming language for transputer
systems (inherently parallel to massive parallel architecture).

There is also ADA, which has multiprocessing as part of the language
spec, with GNAT as a free compiler environment:
http://www.gnu.org/software/gnat/gnat.html

One can also do parallel programming in Lisp, preferable one that maps Lisp
threads to operating system threads. As far as I'm aware, the only
freely available Lisp for x86 that does this is SBCL - where it works
nicely as the previous poster already wrote.

> I know of only one parallel language that is non-lisp called "Sisal". It
> is still on the net but is no longer supported by LLNL. It automatic
> creates parallels code for the user.

I am rather wary of such claims - typical code not explicitly designed for
parallel execution tends not to win much by automagic parallelisation.

> Just found an older parallel version of *lisp or StarLisp simulator which
> may be downloaded at bottom of the following archive URL page but it
> was created back in 1989.
> File Name = Starsim-f20.zip File size = 580 KB
>
> http://examples.franz.com/index.html
>
> "*Lisp (pronounced "star Lisp") is a data parallel extension of the
> Common Lisp programming language, designed for the Connection
> Machine system."
>
>
>
> In <1189002231.167450.110710@k79g2000hse.googlegroups .com>, "Mike G." <michael.graffam@gmail.com> writes:
>>I've spent a little free time over the last two months building a
>>multi-processor / multi-core network computer in my basement. In no
>>time at all, I've been able to hack up some primitives for doing
>>parallel processing across this network in SBCL.
>>
>>My question is: can someone provide some names of parallel lisp
>>environments? I know of *Lisp. Anything else? I've been trying to
>>scare up a copy of the *Lisp Dictionary.
>>
>>Ultimately, I'm looking for parallel Lisp idioms to implement on top
>>of my primitives.
>>
>>Right now, I have a macro plet which has the form:
>>
>>(plet ((var1 (foo1))
>> (var2 (foo2))
>> ...)
>> (exit-form)
>> (form1)
>> (form2)
>> ...)
>>
>>The idea is that the variables get initialized (as per an ordinary
>>let), each form in the body gets executed in parallel, and exit-form
>>is a chunk of code that executes after all parallel threads have ended
>>which ties everything together. This macro expands into my primitives
>>to initialize / access variables via my centralized tracker and a loop
>>which patiently waits for the threads to complete. Works well enough.
>>
>>I also have a parallel MAP which splits a map up across multiple
>>cpu's / cores.
>>
>>Implementing this is what made me come looking for guidance because I
>>can think of several ways to split up a MAP that might make sense
>>under different circumstances.
>>
>>Any ideas or pointers area welcome.


--
"Opportunity is missed by most people because it is dressed in overalls and
looks like work." -- Thomas A. Edison