Designing parallel programs

Designing Parallel Programs

Understand the Problem and the Program

Undoubtedly, the first step in developing parallel software is to first understand the problem that you wish to solve in parallel. If you are starting with a serial program, this necessitates understanding the existing code also.
Before spending time in an attempt to develop a parallel solution for a problem, determine whether or not the problem is one that can actually be parallelized.

Who Needs Communications?

You DON’T need communications
- Some types of problems can be decomposed and executed in parallel with virtually no need for tasks to share data. For example, imagine an image processing operation where every pixel in a black and white image needs to have its color reversed. The image data can easily be distributed to multiple tasks that then act independently of each other to do their portion of the work.
- These types of problems are often called embarrassingly parallel because they are so straight-forward. Very little inter-task communication is required.
You DO need communications
- Most parallel applications are not quite so simple, and do require tasks to share data with each other. For example, a 3-D heat diffusion problem requires a task to know the temperatures calculated by the tasks that have neighboring data. Changes to neighboring data has a direct effect on that task’s data.

Definition:

A dependence exists between program statements when the order of statement execution affects the results of the program.
A data dependence results from multiple use of the same location(s) in storage by different tasks.
Dependencies are important to parallel programming because they are one of the primary inhibitors to parallelism.

Examples:

Loop carried data dependence


DO 500 J = MYSTART,MYEND
   A(J) = A(J-1) * 2.0
500 CONTINUE

The value of A(J-1) must be computed before the value of A(J), therefore A(J) exhibits a data dependency on A(J-1). Parallelism is inhibited.