| Published On : | October 28, 2009 1:00 AM PDT |
Rate |
|
Posted by Ilya Mirman originally on www.cilk.com on Tue, Mar 31, 2009
Hot Off The Press: The award-winning Introduction to Algorithms (coauthored by our own Charles E. Leiserson) is the leading textbook on computer algorithms and the most cited reference in all of computer science.
In the "Multithreaded Algorithms" chapter, the authors extend the algorithmic model to encompass parallel algorithms, which can run on a multiprocessor computer that permits multiple instructions to execute concurrently. In particular, the authors explore the elegant model of dynamic multithreaded algorithms, which are amenable to algorithmic design and analysis, as well as to efficient implementation in practice.
Contents:
- Dynamic multithreaded programming
- The basics of dynamic multithreading
- A model for multithreaded execution
- Performance measures
- Scheduling
- Analyzing multithreaded algorithms
- Parallel loops
- Race conditions
- Multithreaded matrix multiplication
- Multithreaded merge sort
(And we would love to hear your feedback on it!)
COMMENTS
I would advocate to use spawn on every concurrent call. Right now when we have a k-way parallelism, it is expressed as (k-1) spawns and followed by one non-spawn. Personally I find the code looks very awkward this way. I can see why avoiding spawn on the last call can be technically preferable (say, so that the scheduler has no chance to play music chair and destroy processor locality). But perhaps we can just let the compiler take care of the last spawn by defining the last spawn in a group before a sync as a no-op?I don't program in Cilk++ (yet) so this doesn't affect me in programming, but I certainly wish my textbook algorithms "look parallel" in parallel calls.
posted @ Thursday, April 02, 2009 12:42 AM by Maverick Woo
The download link is broken
plz provide a new link soon
posted @ Wednesday, October 07, 2009 10:22 AM by rk
