Subscribe by Email

Your email:

Multicore Programming Blog

Current Articles | RSS Feed RSS Feed

FREE DOWNLOAD: "Multithreaded Algorithms" chapter from Introduction to Algorithms

Posted by Ilya Mirman on Tue, Mar 31, 2009
 | Submit to Digg digg it | Submit to Reddit reddit | Add to delicious delicious | Submit to StumbleUpon StumbleUpon | Share on Twitter Twitter 

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

You can download it here...

(And we would love to hear your feedback on it!)

Tags: , ,

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


I'd like to follow up on some of the citations, but there is no bibliography. Any idea where to find bib. entries?

posted @ Monday, February 08, 2010 1:19 PM by Dylan


Post Comment
Name
 *
Email
 *
Website (optional)
Comment
 *

Allowed tags: <a> link, <b> bold, <i> italics

Receive email when someone replies.