Class 2: Designing Parallel Algorithms

Announcements:
I will return all your problem statements today. Please go through them carefully, and incorporate the changes. Some comments that I made in the last class:

1. Make sure that you have given your project an appropriate title.
2. The graduate students should be doing an extensive literature survey to look at other work done on their problem. A good starting point might be to use CARL to look up relevant articles.
3. For some of the reports, a well written introduction that motivates the reader as to why it is important to solve the problem would be very desirable.
4. For some of the more advanced projects in specialized domains, make sure that you have provided adequate background for non-experts.

In today's class, we will discuss Chapter 2 of the Foster text. This chapter discusses a principled approach towards the design of parallel algorithms. The approach presented is laid out in such a manner that you consider machine-independent issues early on in the process, and the machine-specific ones later. This approach divides up the parallel algorithm design process into four steps:

1. Partitioning.
2. Communication.
3. Agglomeration.
4. Mapping.

The aim of Partitioning is to expose the maximum opportunities for exploiting parallelism in the problem. Thus, a fine grained partitioning is desirable at this stage. There are two ways to partition a problem:

1. Domain decomposition-divide up the data first, and see how the computation gets divided.
2. Functional decomposition-divide up the computations first, and then provide appropriate data to each.

The computation in one task may require data from another, and thus, they will need Communication between them. We therefore need to construct channels between the tasks that allow them to communicate with each other. In doing so, we try and avoid extra channels (therefore extra communication), and try and overlap communication as much as possible. Problems have different inherent communication patterns:

• Local vs. global communication.
• Structured vs. unstructured.
• Static vs. dynamic.
• Synchronous vs. asynchronous.

The subsection on Local Communication provides a nice discussion on the tradeoffs involved in using the Jacobi method versus the Gauss-Seidel method when solving Finite Difference Problems. The parallel implementation of the Gauss-Seidel method poses some interesting problems. Figure 2.5 in the text shows the ``wavefront'' and ``red-black'' methods of solving the problem.

The summation problem we had looked at in the last class provides an example of global communication requirements. There are many ways we can solve the problem, but the divide-and-conquer strategy works best.

We will talk a little bit about unstructured, dynamic and asynchronous communication behaviors, and finally discuss a checklist of items you should look at to ensure a good communication behavior in your algorithm.