11
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Can you reformulate this sentence: "For example, I would like to have a language why the obvious parallel approach to the following problems have different qualitative behaviour" $\endgroup$
    – Gopi
    Sep 30, 2011 at 11:52
  • $\begingroup$ Done. I hope this is more acurate. $\endgroup$
    – shuhalo
    Oct 5, 2011 at 13:04

3 Answers 3

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – shuhalo
    Oct 5, 2011 at 13:06
  • $\begingroup$ 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. $\endgroup$
    – Gopi
    Oct 5, 2011 at 16:22
  • 1
    $\begingroup$ ux.stackexchange.com/questions/12100/… $\endgroup$
    – hippietrail
    Oct 7, 2011 at 13:37
  • $\begingroup$ +1 for the NSF/IEEE-TCPP Curriculum Initiative, but I suggest that you remove OpenMP & MPI, as they are not really relevant here. $\endgroup$
    – Jukka Suomela
    Oct 7, 2011 at 18:38
  • $\begingroup$ Indeed, I forgot to remove it after the comment of @Martin. Thanks. $\endgroup$
    – Gopi
    Oct 7, 2011 at 21:44
7
$\begingroup$

If you do not want to delve into the gory details, a very good introduction to parallelization design patterns is provided by the book Patterns for Parallel Programming by Mattson, Sanders and Massingill.

You will find general, widely applicable solutions to parallelization and even a brief introduction to both OpenMP and MPI. The book starts by introducing design patterns and concurrency. Then, the authors proceed to illustrate how to exploit the concurrency, how to structure the algorithm, and how to actually implement the algorithm taking into account synchronization and communication.

Again, this is not a textbook on parallel algorithms. It does a very good job of presenting materials strictly related to parallel software engineering, with both a practical and theoretical focus. Therefore, it should suit perfectly your needs.

Improve this answer
$\endgroup$
1
$\begingroup$

MPI_RUBY ... need to find my latest stable build. I would suggest adding parallel-prefix (scan) to the list. I would just teach parallel prefix, and show them how to use a space filling curve to get better cache efficiency on the all pairs problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.