Prev: TextMate Common Lisp Bundle
Next: THANKS GOD! I GOT $2000 FROM PAYPAL....
From: D Herring on 6 Aug 2010 21:59
On 08/06/2010 04:58 AM, Pascal Costanza wrote:

> The actual term is "work stealing". It was originally used in
> MultiLisp and QLisp, and then picked up by Cilk and Cilk++. The Cilk
> and Cilk++ versions have what seems to be the most mature versions of
> work stealing, and they have backed their approach with a series of
> excellent papers that show why work stealing is indeed an extremely
> good approach for parallelization.

Yes. That's the term and the proper heritage.

- Daniel
From: Tamas K Papp on 7 Aug 2010 03:54
On Fri, 06 Aug 2010 21:59:21 -0400, D Herring wrote:

> On 08/06/2010 04:58 AM, Pascal Costanza wrote:
>
>> The actual term is "work stealing". It was originally used in MultiLisp
>> and QLisp, and then picked up by Cilk and Cilk++. The Cilk and Cilk++
>> versions have what seems to be the most mature versions of work
>> stealing, and they have backed their approach with a series of
>> excellent papers that show why work stealing is indeed an extremely
>> good approach for parallelization.
>
> Yes. That's the term and the proper heritage.

It seems that a lot of the tools/concepts I am looking for have been
invented a long time ago, it's just that I don't know about them (I am
a self-taught programmer, never had formal CS education).

Can either of you (or anyone else) recommend a good introduction /
tutorial to the relevant concepts and algorithms? Ideally, I am
looking for a book that would cover threads & related concepts the
same way PCL covers Lisp, for the total newbie. Doesn't have to be
Lisp-based though.

Thanks,

Tamas
From: D Herring on 7 Aug 2010 23:37
On 08/07/2010 03:54 AM, Tamas K Papp wrote:

> Can either of you (or anyone else) recommend a good introduction /
> tutorial to the relevant concepts and algorithms? Ideally, I am
> looking for a book that would cover threads& related concepts the
> same way PCL covers Lisp, for the total newbie. Doesn't have to be
> Lisp-based though.

I've never seen such a beast, but I didn't look much either, being
satisfied with a hodge-podge of small articles, chapters, and papers.
AFAICT, multithreading is still something of a black art. There are
some patterns that work, and some pitfalls to watch out for. The Java
language was one of the first with good threading support (including
an actual memory model); thus there is good documentation and
guidelines for Java threading. The Linux kernel has some good
documentation on all the ways memory can get out of sync between
threads (e.g. Documentation/memory-barriers.txt). POSIX also has a
good set of the classic primitives (e.g. `apropos pthread` and `man
pthreads` and google pthreads).

For basic stuff, you want to learn about the mutex (mutual exclusion -
lock protected areas), (counting) semaphore (locking and event
notification), barrier, condition variable, and thread-local/specific
storage.

For advanced stuff, I strongly recommend investigating lock-free
algorithms and nonblocking synchronization. The classic locking
algorithms have a major problem: they don't compose. The program
must maintain a strict (partial) ordering on the locks it uses;
otherwise deadlock will occur (generally after delivery). This is
very hard when libraries introduce or modify their own internal locks...

Maybe Pascal has a good reference.

- Daniel
From: Thomas Munro on 8 Aug 2010 04:09
On Aug 7, 8:54 am, Tamas K Papp <tkp...(a)gmail.com> wrote:

> Can either of you (or anyone else) recommend a good introduction /
> tutorial to the relevant concepts and algorithms?  Ideally, I am
> looking for a book that would cover threads & related concepts the
> same way PCL covers Lisp, for the total newbie.  Doesn't have to be
> Lisp-based though.

I've been really enjoying 'The Art of Multiprocessor Programming',
published in 2008, by Herlihy and Shavit. (It has a section on work
stealing.)

http://www.amazon.com/Art-Multiprocessor-Programming-Maurice-Herlihy/dp/0123705916
From: Pascal Costanza on 10 Aug 2010 07:09
On 08/08/2010 05:37, D Herring wrote:
> Maybe Pascal has a good reference.

Unfortunately not.


Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: TextMate Common Lisp Bundle
Next: THANKS GOD! I GOT $2000 FROM PAYPAL....