Theoretical Computer Science
reference-request soft-question dc.parallel-comp survey
Updated Thu, 26 May 2022 13:19:17 GMT

Introductory notes on parallelization, in particular patterns of problems and algorithms

I am looking for online available Lecture notes or other resources that give a good introduction into parallel programming, just like parallel analog of basic classes in computer science.

My focus is the following: while I am able to talk about divide&conquer, greedy algorithms, dynamic programming and the like, i.e. basic patterns of sequential algorithms (and problems), and I do not have the appropiate language to classify approaches in parallel algorithms.

For example, I would like to acquire the appropiate terms to express the fact that the obvious parallel approaches to each of the following problems have different qualitative behaviour:

  1. setting an array of integers all-zero (scales perfectly.)
  2. summing an array of integers (the more threads you use, the more overhead.)
  3. Given an array, list the products of each entry with each other entry (if we parallelize the canonical double-for-loop, the running-time will scale to the sqrt of the number processors.)

A shared memory enviroment suffices, and interprocess communication is not so relevant for me (in fact, I am interested in algorithms that avoid it at all). Furthermore, the technical aspects are neglegible for me.


For an introductory book for parallel programming (I do not know about online material), I have been learning it with Parallel Algorithms by Casanova, Legrand and Robert, which is very helpful for beginning in theoretical parallel algorithmic.

Furthermore, in SPAA'11 was a discussion about what should a parallel algorithm and distributed computing student know and what should be teach. This Curriculum Initiative on Parallel and Distributed Computing, will help you to find not a course, but the list of different topic that should be cover during an undergrad course. Then I suppose it is easier to find documentation on every specific topic.

Comments (5)

  • +1 – The term "language" refered to natural language, not programming language or similar. Just like mathematics is a language, and for example category theory or group theory is said to provide a "language" for certain structures, relations and facts. But thanks anyway. — Oct 05, 2011 at 13:06  
  • +0 – indeed, my bad :). Then For the three questions you had, I really recommend the book I linked which is very theoretical. They study all kind of parallel algorithms and techniques on different kind of parallel architecture. Then the part that might answer your three questions would be the part on Uniform Loops. — Oct 05, 2011 at 16:22  
  •… — Oct 07, 2011 at 13:37  
  • +0 – +1 for the NSF/IEEE-TCPP Curriculum Initiative, but I suggest that you remove OpenMP & MPI, as they are not really relevant here. — Oct 07, 2011 at 18:38  
  • +0 – Indeed, I forgot to remove it after the comment of @Martin. Thanks. — Oct 07, 2011 at 21:44