Image

Image

• Which model to use? This is often a combination of what is available and personal choice. There is no "best" model, although there certainly are better implementations of some models over others.
• The following sections describe each of the models mentioned above, and also discuss some of their actual implementations.

Shared Memory Model (without threads)

• In this programming model, processes/tasks share a common address space, which they read and write to asynchronously.
• Various mechanisms such as locks / semaphores are used to control access to the shared memory, resolve contentions and to prevent race conditions and deadlocks.
• This is perhaps the simplest parallel programming model.
• An advantage of this model from the programmer's point of view is that the notion of data "ownership" is lacking, so there is no need to specify explicitly the communication of data between tasks. All processes see and have equal access to shared memory. Program development can often be simplified.
• An important disadvantage in terms of performance is that it becomes more difficult to understand and manage data locality:
  • Keeping data local to the process that works on it conserves memory accesses, cache refreshes and bus traffic that occurs when multiple processes use the same data.
  • Unfortunately, controlling data locality is hard to understand and may be beyond the control of the average user.

Implementations

• On stand-alone shared memory machines, native operating systems, compilers and/or hardware provide support for shared memory programming. For example, the POSIX standard provides an API for using shared memory, and UNIX provides shared memory segments (shmget, shmat, shmctl, etc.).
• On distributed memory machines, memory is physically distributed across a network of machines, but made global through specialized hardware and software. A variety of SHMEM implementations are available: http://en.wikipedia.org/wiki/SHMEM.

Threads Model

• This programming model is a type of shared memory programming.
• In the threads model of parallel programming, a single "heavy weight" process can have multiple "light weight", concurrent execution paths.
• For example:
  • The main program a.out is scheduled to run by the native operating system. a.out loads and acquires all of the necessary system and user resources to run. This is the "heavy weight" process.
  • a.out performs some serial work, and then creates a number of tasks (threads) that can be scheduled and run by the operating system concurrently.
  • Each thread has local data, but also, shares the entire resources of a.out. This saves the overhead associated with replicating a program's resources for each thread ("light weight"). Each thread also benefits from a global memory view because it shares the memory space of a.out.
  • A thread's work may best be described as a subroutine within the main program. Any thread can execute any subroutine at the same time as other threads.
  • Threads communicate with each other through global memory (updating address locations). This requires synchronization constructs to ensure that more than one thread is not updating the same global address at any time.
  • Threads can come and go, but a.out remains present to provide the necessary shared resources until the application has completed.

Implementations

• From a programming perspective, threads implementations commonly comprise:
  • A library of subroutines that are called from within parallel source code
  • A set of compiler directives imbedded in either serial or parallel source code

In both cases, the programmer is responsible for determining the parallelism (although compilers can sometimes help).

• Threaded implementations are not new in computing. Historically, hardware vendors have implemented their own proprietary versions of threads. These implementations differed substantially from each other making it difficult for programmers to develop portable threaded applications.
• Unrelated standardization efforts have resulted in two very different implementations of threads: POSIX Threads and OpenMP.

POSIX Threads

• Specified by the IEEE POSIX 1003.1c standard (1995). C Language only.
• Part of Unix/Linux operating systems
• Library based
• Commonly referred to as Pthreads.
• Very explicit parallelism; requires significant programmer attention to detail.

OpenMP

•  Industry standard, jointly defined and endorsed by a group of major computer hardware and software vendors, organizations and individuals.
• Compiler directive based
• Portable / multi-platform, including Unix and Windows platforms
• Available in C/C++ and Fortran implementations
• Can be very easy and simple to use - provides for "incremental parallelism". Can begin with serial code.
• Other threaded implementations are common, but not discussed here:
  • Microsoft threads
  • Java, Python threads
  • CUDA threads for GPUs

More Information

• POSIX Threads tutorial: hpc.llnl.gov/sites/default/files/2019.08.21.TAU_.pdf
• OpenMP tutorial: hpc-tutorials.llnl.gov/openmp/

Distributed Memory / Message Passing Model

• This model demonstrates the following characteristics:
  • A set of tasks that use their own local memory during computation. Multiple tasks can reside on the same physical machine and/or across an arbitrary number of machines.
  • Tasks exchange data through communications by sending and receiving messages.
  • Data transfer usually requires cooperative operations to be performed by each process. For example, a send operation must have a matching receive operation.

Implementations:

• From a programming perspective, message passing implementations usually comprise a library of subroutines. Calls to these subroutines are imbedded in source code. The programmer is responsible for determining all parallelism.
• Historically, a variety of message passing libraries have been available since the 1980s. These implementations differed substantially from each other making it difficult for programmers to develop portable applications.
• In 1992, the MPI Forum was formed with the primary goal of establishing a standard interface for message passing implementations.
• Part 1 of the Message Passing Interface (MPI) was released in 1994. Part 2 (MPI-2) was released in 1996 and MPI-3 in 2012. All MPI specifications are available on the web at http://www.mpi-forum.org/docs/.
• MPI is the "de facto" industry standard for message passing, replacing virtually all other message passing implementations used for production work. MPI implementations exist for virtually all popular parallel computing platforms. Not all implementations include everything in MPI-1, MPI-2 or MPI-3.

More Information

• MPI tutorial: hpc-tutorials.llnl.gov/mpi/

Data Parallel Model

• May also be referred to as the Partitioned Global Address Space (PGAS) model.
• The data parallel model demonstrates the following characteristics:
  • Address space is treated globally
  • Most of the parallel work focuses on performing operations on a data set. The data set is typically organized into a common structure, such as an array or cube.
  • A set of tasks work collectively on the same data structure, however, each task works on a different partition of the same data structure.
  • Tasks perform the same operation on their partition of work, for example, "add 4 to every array element".
• On shared memory architectures, all tasks may have access to the data structure through global memory.
• On distributed memory architectures, the global data structure can be split up logically and/or physically across tasks.

Implementations:

• Currently, there are several parallel programming implementations in various stages of developments, based on the Data Parallel / PGAS model.
• Coarray Fortran: a small set of extensions to Fortran 95 for SPMD parallel programming. Compiler dependent. More information: https://en.wikipedia.org/wiki/Coarray_Fortran
• Unified Parallel C (UPC): an extension to the C programming language for SPMD parallel programming. Compiler dependent. More information: https://upc.lbl.gov/
• Global Arrays: provides a shared memory style programming environment in the context of distributed array data structures. Public domain library with C and Fortran77 bindings. More information: https://en.wikipedia.org/wiki/Global_Arrays
• X10: a PGAS based parallel programming language being developed by IBM at the Thomas J. Watson Research Center. More information: http://x10-lang.org/
• Chapel: an open source parallel programming language project being led by Cray. More information: http://chapel.cray.com/

Hybrid Model

• A hybrid model combines more than one of the previously described programming models.
• Currently, a common example of a hybrid model is the combination of the message passing model (MPI) with the threads model (OpenMP).
  • Threads perform computationally intensive kernels using local, on-node data
  • Communications between processes on different nodes occurs over the network using MPI
• This hybrid model lends itself well to the most popular (currently) hardware environment of clustered multi/many-core machines.
• Another similar and increasingly popular example of a hybrid model is using MPI with CPU-GPU (graphics processing unit) programming.
  • MPI tasks run on CPUs using local memory and communicating with each other over a network.
  • Computationally intensive kernels are off-loaded to GPUs on-node.
  • Data exchange between node-local memory and GPUs uses CUDA (or something equivalent).
• Other hybrid models are common:
  • MPI with Pthreads
  • MPI with non-GPU accelerators

SPMD and MPMD

Single Program Multiple Data (SPMD)

• SPMD is actually a "high level" programming model that can be built upon any combination of the previously mentioned parallel programming models.
• SINGLE PROGRAM: All tasks execute their copy of the same program simultaneously. This program can be threads, message passing, data parallel or hybrid.
• MULTIPLE DATA: All tasks may use different data
• SPMD programs usually have the necessary logic programmed into them to allow different tasks to branch or conditionally execute only those parts of the program they are designed to execute. That is, tasks do not necessarily have to execute the entire program - perhaps only a portion of it.
• The SPMD model, using message passing or hybrid programming, is probably the most commonly used parallel programming model for multi-node clusters.

Multiple Program Multiple Data (MPMD)

• Like SPMD, MPMD is actually a "high level" programming model that can be built upon any combination of the previously mentioned parallel programming models.
• MULTIPLE PROGRAM: Tasks may execute different programs simultaneously. The programs can be threads, message passing, data parallel or hybrid.
• MULTIPLE DATA: All tasks may use different data
• MPMD applications are not as common as SPMD applications, but may be better suited for certain types of problems, particularly those that lend themselves better to functional decomposition than domain decomposition (discussed later under Partitioning).

Designing Parallel Programs

Automatic vs. Manual Parallelization

• Designing and developing parallel programs has characteristically been a very manual process. The programmer is typically responsible for both identifying and actually implementing parallelism.
• Very often, manually developing parallel codes is a time consuming, complex, error-prone and iterative process.
• For a number of years now, various tools have been available to assist the programmer with converting serial programs into parallel programs. The most common type of tool used to automatically parallelize a serial program is a parallelizing compiler or pre-processor.
• A parallelizing compiler generally works in two different ways:

Fully Automatic

• The compiler analyzes the source code and identifies opportunities for parallelism.
• The analysis includes identifying inhibitors to parallelism and possibly a cost weighting on whether or not the parallelism would actually improve performance.
• Loops (do, for) are the most frequent target for automatic parallelization.

Programmer Directed

• Using "compiler directives" or possibly compiler flags, the programmer explicitly tells the compiler how to parallelize the code.
• May be able to be used in conjunction with some degree of automatic parallelization also.
• The most common compiler generated parallelization is done using on-node shared memory and threads (such as OpenMP).
• If you are beginning with an existing serial code and have time or budget constraints, then automatic parallelization may be the answer. However, there are several important caveats that apply to automatic parallelization:
  • Wrong results may be produced
  • Performance may actually degrade
  • Much less flexible than manual parallelization
  • Limited to a subset (mostly loops) of code
  • May actually not parallelize code if the compiler analysis suggests there are inhibitors or the code is too complex
• The remainder of this section applies to the manual method of developing parallel codes.

Understand the Problem and the Program

Programs = algorithms + data + (hardware)

• 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 means 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.
  • Example of an easy-to-parallelize problem:

Calculate the potential energy for each of several thousand independent conformations of a molecule. When done, find the minimum energy conformation.

This problem is able to be solved in parallel. Each of the molecular conformations is independently determinable. The calculation of the minimum energy conformation is also a parallelizable problem.

• Example of a problem and algorithm with little-to-no parallelism:

Calculation of the first 10,000 members of the Fibonacci series (0,1,1,2,3,5,8,13,21,...) by use of the formula:

F(n) = F(n-1) + F(n-2)

The calculation of the F(n) value uses those of both F(n-1) and F(n-2), which must be computed first.

An example of a parallel algorithm for solving this problem (using Binet's formula):

 

 

where

 

 

 

 

• Identify the program's hotspots:
  • Know where most of the real work is being done. The majority of scientific and technical programs usually accomplish most of their work in a few places.
  • Profilers and performance analysis tools can help here
  • Focus on parallelizing the hotspots and ignore those sections of the program that account for little CPU usage.
• Identify bottlenecks in the program:
  • Are there areas that are disproportionately slow, or cause parallelizable work to halt or be deferred? For example, I/O is usually something that slows a program down.
  • May be possible to restructure the program or use a different algorithm to reduce or eliminate unnecessary slow areas
• Identify inhibitors to parallelism. One common class of inhibitor is data dependence, as demonstrated by the Fibonacci sequence above.
• Investigate other algorithms if possible. This may be the single most important consideration when designing a parallel application.
• Take advantage of optimized third party parallel software and highly optimized math libraries available from leading vendors (IBM's ESSL, Intel's MKL, AMD's AMCL, etc.).

Partitioning

• One of the first steps in designing a parallel program is to break the problem into discrete "chunks" of work that can be distributed to multiple tasks. This is known as decomposition or partitioning.
• There are two basic ways to partition computational work among parallel tasks: domain decomposition and functional decomposition.

Domain Decomposition

In this type of partitioning, the data associated with a problem is decomposed. Each parallel task then works on a portion of the data.

There are different ways to partition data:

Functional Decomposition

In this approach, the focus is on the computation that is to be performed rather than on the data manipulated by the computation. The problem is decomposed according to the work that must be done. Each task then performs a portion of the overall work.

Functional decomposition lends itself well to problems that can be split into different tasks. For example:

Ecosystem Modeling

Each program calculates the population of a given group, where each group's growth depends on that of its neighbors. As time progresses, each process calculates its current state, then exchanges information with the neighbor populations. All tasks then progress to calculate the state at the next time step.

Signal Processing

An audio signal data set is passed through four distinct computational filters. Each filter is a separate process. The first segment of data must pass through the first filter before progressing to the second. When it does, the second segment of data passes through the first filter. By the time the fourth segment of data is in the first filter, all four tasks are busy.

Climate Modeling

Each model component can be thought of as a separate task. Arrows represent exchanges of data between components during computation: the atmosphere model generates wind velocity data that are used by the ocean model, the ocean model generates sea surface temperature data that are used by the atmosphere model, and so on.

• Combining these two types of problem decomposition is common and natural.

Communications

Who Needs Communications?

The need for communications between tasks depends upon your problem:

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. These types of problems are often called embarrassingly parallel - little or no communications are required.
• 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.

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 2-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.

Factors to Consider

There are a number of important factors to consider when designing your program's inter-task communications:

Communication overhead

• Inter-task communication virtually always implies overhead.
• Machine cycles and resources that could be used for computation are instead used to package and transmit data.
• Communications frequently require some type of synchronization between tasks, which can result in tasks spending time "waiting" instead of doing work.
• Competing communication traffic can saturate the available network bandwidth, further aggravating performance problems.

Latency vs. bandwidth

• Latency is the time it takes to send a minimal (0 byte) message from point A to point B. Commonly expressed as microseconds.
• Bandwidth is the amount of data that can be communicated per unit of time. Commonly expressed as megabytes/sec or gigabytes/sec.
• Sending many small messages can cause latency to dominate communication overheads. Often it is more efficient to package small messages into a larger message, thus increasing the effective communications bandwidth.

Visibility of communications

• With the Message Passing Model, communications are explicit and generally quite visible and under the control of the programmer.
• With the Data Parallel Model, communications often occur transparently to the programmer, particularly on distributed memory architectures. The programmer may not even be able to know exactly how inter-task communications are being accomplished.

Synchronous vs. asynchronous communications

• Synchronous communications require some type of "handshaking" between tasks that are sharing data. This can be explicitly structured in code by the programmer, or it may happen at a lower level unknown to the programmer.
• Synchronous communications are often referred to as blocking communications since other work must wait until the communications have completed.
• Asynchronous communications allow tasks to transfer data independently from one another. For example, task 1 can prepare and send a message to task 2, and then immediately begin doing other work. When task 2 actually receives the data doesn't matter.
• Asynchronous communications are often referred to as non-blocking communications since other work can be done while the communications are taking place.
• Interleaving computation with communication is the single greatest benefit for using asynchronous communications.

Scope of communications

• Knowing which tasks must communicate with each other is critical during the design stage of a parallel code. Both of the two scopings described below can be implemented synchronously or asynchronously.
• Point-to-point - involves two tasks with one task acting as the sender/producer of data, and the other acting as the receiver/consumer.
• Collective - involves data sharing between more than two tasks, which are often specified as being members in a common group, or collective. Some common variations (there are more):

Efficiency of communications

• Oftentimes, the programmer has choices that can affect communications performance. Only a few are mentioned here.
• Which implementation for a given model should be used? Using the Message Passing Model as an example, one MPI implementation may be faster on a given hardware platform than another.
• What type of communication operations should be used? As mentioned previously, asynchronous communication operations can improve overall program performance.
• Network fabric—different platforms use different networks. Some networks perform better than others. Choosing a platform with a faster network may be an option.

Overhead and complexity

Finally, realize that this is only a partial list of things to consider!

Synchronization

• Managing the sequence of work and the tasks performing it is a critical design consideration for most parallel programs.
• Can be a significant factor in program performance (or lack of it)
• Often requires "serialization" of segments of the program.

Types of Synchronization

Barrier

• Usually implies that all tasks are involved
• Each task performs its work until it reaches the barrier. It then stops, or "blocks".
• When the last task reaches the barrier, all tasks are synchronized.
• What happens from here varies. Often, a serial section of work must be done. In other cases, the tasks are automatically released to continue their work.

Lock / semaphore

• Can involve any number of tasks
• Typically used to serialize (protect) access to global data or a section of code. Only one task at a time may use (own) the lock / semaphore / flag.
• The first task to acquire the lock "sets" it. This task can then safely (serially) access the protected data or code.
• Other tasks can attempt to acquire the lock but must wait until the task that owns the lock releases it.
• Can be blocking or non-blocking.

Synchronous communication operations

• Involves only those tasks executing a communication operation.
• When a task performs a communication operation, some form of coordination is required with the other task(s) participating in the communication. For example, before a task can perform a send operation, it must first receive an acknowledgment from the receiving task that it is OK to send.
• Discussed previously in the Communications section.

Data Dependencies

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 J = MYSTART,MYEND
       A(J) = A(J-1) * 2.0
    END DO

• 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.
• If Task 2 has A(J) and task 1 has A(J-1), computing the correct value of A(J) necessitates:
  • Distributed memory architecture - task 2 must obtain the value of A(J-1) from task 1 after task 1 finishes its computation
  • Shared memory architecture - task 2 must read A(J-1) after task 1 updates it

Loop independent data dependence

    task 1        task 2
    ------        ------

    X = 2         X = 4
      .             .
      .             .
    Y = X**2      Y = X**3

• As with the previous example, parallelism is inhibited. The value of Y is dependent on:
  • Distributed memory architecture - if or when the value of X is communicated between the tasks.
  • Shared memory architecture - which task last stores the value of X.
• Although all data dependencies are important to identify when designing parallel programs, loop carried dependencies are particularly important since loops are possibly the most common target of parallelization efforts.

How to Handle Data Dependencies

• Distributed memory architectures - communicate required data at synchronization points.
• Shared memory architectures -synchronize read/write operations between tasks.

Load Balancing

• Load balancing refers to the practice of distributing approximately equal amounts of work among tasks so that all tasks are kept busy all of the time. It can be considered a minimization of task idle time.
• Load balancing is important to parallel programs for performance reasons. For example, if all tasks are subject to a barrier synchronization point, the slowest task will determine the overall performance.