<p>If you do not want to delve into the gory details, a very good introduction to parallelization design patterns is provided by the book <a href="http://rads.stackoverflow.com/amzn/click/0321228111">Patterns for Parallel Programming</a> by Mattson, Sanders and Massingill. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-09-29T10:09:42.800Z
2011-09-29T10:09:42.800Z
Massimo Cafaro
<p>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.</p>

CC BY-SA 3.0
2011-09-29T18:55:12.570Z
2011-09-29T18:55:12.570Z
Chad Brewbaker
<p>For an introductory book for parallel programming (I do not know about online material), I have been learning it with <a href="http://www.crcpress.com/product/isbn/9781584889458;jsessionid=ih2qkvkxYf4fn-g9gntuBA%2a%2a" rel="nofollow">Parallel Algorithms</a> by Casanova, Legrand and Robert, which is very helpful for beginning in theoretical parallel algorithmic.</p>

<p>Furthermore, in SPAA'11 was a discussion about what should a parallel algorithm and distributed computing student know and what should be teach. This <a href="http://www.cs.gsu.edu/~tcpp/curriculum/index.php" rel="nofollow">Curriculum Initiative on Parallel and Distributed Computing</a>, 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.</p>

CC BY-SA 3.0
2011-10-05T13:06:10.777Z
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.
shuhalo
CC BY-SA 3.0
2011-10-05T16:22:27.380Z
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*.
Gopi
CC BY-SA 3.0
2011-10-07T13:37:31.930Z
http://ux.stackexchange.com/questions/12100/why-shouldnt-we-use-the-word-here-in-a-textlink
hippietrail
CC BY-SA 3.0
2011-10-07T18:38:54.733Z
+1 for the NSF/IEEE-TCPP Curriculum Initiative, but I suggest that you remove OpenMP & MPI, as they are not really relevant here.
Jukka Suomela
CC BY-SA 3.0
2011-10-07T21:44:35.870Z
Indeed, I forgot to remove it after the comment of @Martin. Thanks.
Gopi
CC BY-SA 3.0
2011-09-29T09:30:03.630Z
2011-10-07T21:38:59.307Z
2011-10-07T21:38:59.307Z
Gopi
<p>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.</p>

<p>My focus is the following: while I am able to talk about divide&amp;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.</p>

<p>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:</p>

<ol>
<li>setting an array of integers all-zero (scales perfectly.)</li>
<li>summing an array of integers (the more threads you use, the more overhead.)</li>
<li>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.)</li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2011-09-30T11:52:07.140Z
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"
Gopi
CC BY-SA 3.0
2011-10-05T13:04:39.297Z
Done. I hope this is more acurate.
shuhalo
<reference-request><soft-question><dc.parallel-comp><survey>
Introductory notes on parallelization, in particular patterns of problems and algorithms
shuhalo
# Introductory notes on parallelization, in particular patterns of problems and algorithms

(Asked by: username_0 on 2011-09-29)

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.

**Tags:** reference-request, soft-question, dc.parallel-comp, survey
> **Comments:**
> **username_1**: 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"  
> **username_0**: Done. I hope this is more acurate.  

---

## 3 answers

### Answer by username_1 on 2011-09-29. Score: 6 | Accepted answer

For an introductory book for parallel programming (I do not know about online material), I have been learning it with [Parallel Algorithms](http://www.crcpress.com/product/isbn/9781584889458;jsessionid=ih2qkvkxYf4fn-g9gntuBA%2a%2a) 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](http://www.cs.gsu.edu/~tcpp/curriculum/index.php), 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:**
> **username_0**: 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.  
> **username_1**: 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*.  
> **username_4**: http://ux.stackexchange.com/questions/12100/why-shouldnt-we-use-the-word-here-in-a-textlink  
> **username_5**: +1 for the NSF/IEEE-TCPP Curriculum Initiative, but I suggest that you remove OpenMP & MPI, as they are not really relevant here.  
> **username_1**: Indeed, I forgot to remove it after the comment of @Martin. Thanks.  

---

### Answer by username_2 on 2011-09-29. Score: 7

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](http://rads.stackoverflow.com/amzn/click/0321228111) 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.


---

### Answer by username_3 on 2011-09-29. Score: 1

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.


---

