Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What thought process should one follow to convert a sequential algorithm to a parallel one ? Are there any specific code pattern that can be parallelized. Some patterns that I normally use are:

  • Looking for loops that can parallelized.
  • Try to break algo in some form of Map-reduce format.
  • Looking for producer-consumer pattern.
share|improve this question

migrated from stackoverflow.com Dec 7 '11 at 19:23

This question came from our site for professional and enthusiast programmers.

2  
This is a more general question, and better suited for programmers.se. –  David Thornley Dec 7 '11 at 18:58
2  
Look for divide-and-conquer, or something like quick-sort where it breaks the problem in half recursively. In that case, every time it splits it in two, and each half isn't affected by the other half, you could parallalize there. –  arasmussen Dec 7 '11 at 19:02
4  
Look for dependencies. Dependencies imply serialization. Non-dependencies imply parallelization. –  Jim Clay Dec 7 '11 at 19:08
add comment

2 Answers

Ian Foster describes four basic steps in his book "Designing and Building Parallel Programs":

  1. Partitioning - find possible ways to split the data among the workers as fine-grain as possible.
  2. Communication - identify the communication patterns.
  3. Agglomeration - reduce the initial partitions to coarse-grain tasks according to the resources available.
  4. Mapping - map the tasks onto the processing units.

The book is free online, you can find it here: http://www.mcs.anl.gov/~itf/dbpp/text/book.html

share|improve this answer
add comment

To somewhat formalize what you have already said about looking for loops that can be parallelized, the key concept being exploited is flat data parallelism. A majority of the parallel libraries (that I know of) seem to exhibit this (e.g. Microsoft Task Parallel library for .NET, Microsoft Parallel Patterns Library for C++)

Flat data parallelism happens when you have a chunk of (flat) data (e.g. an array) that you want to perform work on, you then divide up the data into chunks of how many processors you have, does independent work in parallel for each of those chunk, and finally potentially aggregate/combine the result of each chunk to get your final result.

A sample article on this: http://goose.ycp.edu/~dhovemey/spring2011/cs365/lecture/lecture18.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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