• Home
• Descriptor
• Announcements
• Schedule and Notes
• Assignments
• Feedback
• Sponsors

• View
• Print
• Logout ()
• Login

Mattan’s slides (prepared but used board)

Introduction

Patterns of parallel programming can be classified into 4 categories:

• Code/Program Structures → find concurrency
• Algorithm Structures → decomposition (e.g, divide and conquer, …)
• Support Structures → how to write the actual software
• Mapping → low-level system structures

The first 2 are used for algorithm expression (analysis on how to parallelize a program), and the later 2 are used for actually writing the program.

In this lecture, we will study about support structures. These are the software constructs which construct the parallel programs.

• Code structuring patterns tell how to write parallel code for a particular problem. It also dictates how the parallel pieces of code communicate with each other.
• Data structuring patterns describe how to divide and distribute data in a parallel program.

There are following five code and data supporting structures:

• Parallel loops
• Master/worker
• Client/server
• Fork/join
• SPMD (single program multiple data)

Loop Parallelism Pattern

This construct can be used in places where loop iterations are independent of each other. It is easy to see for a loop whether all of its iterations are independent of each other. If yes, then each iteration can be handed off to a unit of execution (UE) such as a thread (independent execution stream either in software or hardware) and run in parallel (or iteration space is divided into chunks and then these chunks are distributed among multiple UEs for parallel execution).

OpenMP is one programming model which provide directives for this kind of loop-level parallelism. There is further fine tuning available for describing how to divide loop iterations among threads, e.g., how big the chunks should be etc.

Note that the work to do (task) is often equal in amount for each iteration, but that is not necessary in this model and conditionals within the loop are permitted. It can be seen that this kind of construct is very useful in cases where code cannot be massively restructured. An example code would look like:

In OpenMP, the parallel code would look like:

Master/Worker Pattern

In this pattern, usually there is a work pool, and a master associated with it. The work pool consists of tasks that can be executed in parallel. Thus, it is most suitable for task-level parallelism. Note that each task can have different amount of work to do.

The master (thread) assigns work (tasks) to workers (threads) in the pool. When a worker finishes the task(s) that has been assigned to it by the master, it requests for more, and then master, depending on policy on work assignment, assigns more work to this particular thread. Each task could be of different length (execution time). Thus, unless each of the task is finished executing, it is hard to determine when would the entire problem be complete (finished executing). It can be seen that load balancing would be another issue.

Note that it is also possible for currently executing tasks to produce more tasks which are then added to the work pool. There is another pattern called Client/server which looks like the same as Master/worker, rather it is a preliminary step for Master/worker.

Fork/Join Pattern

In this pattern, tasks are created dynamically in a recursive (or iterative) manner. More tasks can be added in the work pool by executing the current tasks. The name fork/join comes from the fact that in the start, there is only one task to do. We call it parent task. The parent task then starts executing, and creates new tasks (fork). It then waits until the children complete (join) before continuing on with the computation.

The children tasks are independent of each other, and thus, can be run in parallel. The Cilk programming language follows this model of parallelism. Note that it is also possible for the original parent task to keep executing after it has spawned the children if there is no dependency (so that it can spawn more independent tasks if it has to, or keep doing independent computations, both of which increase parallelism). It would have to create a dummy parent, which can combine the result of children (dummy has the dependent code). The Intel’s TBB library follows this kind of pattern.

SPMD Pattern

In this pattern, a single source program is written, and all parallel units of execution run this single program. The program first does some initializations. It then obtains an identifier which would be unique for each processor (or thread). It then runs the same program, but the identifier and input data differentiates the behavior.

MPI is an example of programming paradigm which uses the SPMD pattern. SPMD is a higher level of granularity of SIMD. The main challenges in this pattern is how to distribute the data between processors, and then how to communicate between them? The different behavior is generally achieved by if evaluating the identifier. Load balancing could also be a problem in this pattern.

Map-Reduce Pattern

In this pattern, a problem is taken, and a map function is applied to each of its data set (which has been provided as part of the program, or could be dynamically determined). After the application of map function, a new representation of the problem has been achieved. After that, a reduce function is applied to this new representation, and a single output is produced (which is the desired solution of the problem). Map is process in which we take a collection, and apply a map function to all members. The result of the mapping are new values along with identifier tags. Reduction is generally a process in which we start with large number of values and come up with a small set of results, often only one. Essentially, the mapped values are reduced based on the tags, such that all mapped values that share a tag are reduced to a single result (see Invalid BibTex Entry!.

It can be seen that fork/join is a subset of Map-Reduce. Some examples where Map-Reduce would work are: finding the minimum, maximum, sum, average, median for a collection.

Patterns for Communication

• Point-to-Point → each unit talks directly to another unit
• Broadcast → Every communication is for all of the units
• Multi-cast → Each communication can be directed to particular participants
• Reduction/tree → Multi-cast, but regular, making a tree like strucutre
• A combination of these

Patterns for Synchronization

• Locks/Semaphores → ensures mutual exclusion
• Monitors/wait (events)
• Barriers (wait for all)

• Atomic constructs → not actually synchronization construct, but could be used

Patterns for Data Distribution

• Distributed array → Subset of the array is used for each execution unit
• Shared central structure (non distributed data)
• Random graph/tree (kind of distributed array, but distribution is irregular)

Algorithm Structure and Organization

Fork/join is best suited to Divide and Conquer kind of parallelism (or for recursive data). SPMD is most suited to Pipelining, and Master/Worker pattern is most suited for Event-based coordination. SPMD and loops can also be done in a Divide and Conquer approach, but they are feasible only after enough number of divisions. Before that, they are not feasible. It can be seen that fork/join is not suitable for pipelining. Note that this discussion and the table below are different from those in the book.