Parallel Programming with Message Passing

Introduction

• This chapter focuses on message passing computing, which is a method of parallel programming.
• It explores the basic concepts of message passing, the structure of message passing programs, techniques for specifying communication between processes, and methods for evaluating message passing programs.

Parallel Programming with Message Passing Libraries

• Key aspects of parallel programming with message passing libraries include knowing:
  • Which processes are to be executed.
  • When to pass messages between concurrent processes.
  • What data to send in the messages.

Process Creation

• A process is an instance of a program in execution.
• Two methods of process creation exist:
  • Static Process Creation.
  • Dynamic Process Creation.
    • Processes are created and initiated during the execution of other processes.

Static vs. Dynamic Process Creation

• Dynamic process creation provides more flexibility but introduces overhead associated with creating processes.

Process Identification (ID)

• Processes in an application are typically not all identical.
• A master process controls the execution of other processes, known as slave or worker processes.
• Slave processes are similar but have different process IDs, which can be used to modify process behavior or determine message destinations.

Programming Models

• Two main programming models are used for parallel programming:
  • MPMD (Multiple Program, Multiple Data): Each processor executes a completely separate program.
  • SPMD (Single Program, Multiple Data): Each processor executes the same program but on different data.

Multiple Program Multiple Data (MPMD) Model

• Each processor executes a different program, allowing for diverse tasks.
• In practical use, often only two distinct programs are used: a master program and a slave program.

Message Tag

• It provides a mechanism for more precise message selection, allowing processes to differentiate between multiple messages.

Broadcast, Gather, and Scatter

• These are "group" message passing routines used to send/receive messages to/from a group of processes.
• They are known as collective operations and generally have higher efficiency compared to separate point-to-point routines.

Broadcast Routines

• Send the same message to all processes involved.
• Multicast routines are also considered broadcast routines in this context, as they send the same message to a specific group of processes.

Scatter Routines

• Distribute elements of an array from the root process to individual processes, with each element going to a different process.

Gather Routines

• A process collects individual values from a set of processes.

Reduce

• A gather operation combined with a specified arithmetic or logical operation.
• Example: Values could be gathered and added together by the root process.

MPI (Process Creation and Execution)

• MPI is a standard for message passing in parallel computing.
• It defines the messages, operations, and data types for communication between processes.
• Creating and starting MPI processes is implementation-dependent and not defined in the MPI standard.
• The SPMD model is typically used, meaning one program is executed by multiple processors.

Communicators

• Communicators define the scope for communication operations in MPI.
• Processes within a communicator have ranks associated with them.
• MPI_COMM_WORLD is the default communicator for all processes in an application.
• Other communicators can be created for specific groups of processes.

Using the SPMD Computational Model

• It is ideal when all processes execute the same code.
• Different code execution for specific processors can be achieved with conditional statements in the program.
• Both master and slave code must be within the same program in the SPMD model.

Unsafe Message Passing

• Message passing communications can be error-prone due to the use of wildcards.
• MPI communicators are used to solve this issue by defining safe communication domains.

MPI Solution "Comunicators"

• A communicator defines a set of processes that can communicate amongst themselves.
• MPI uses communicators for all message passing operations: point-to-point and collective.
• Two communicator types exist:
  • Intracommunicator: Within a single group of processes.
  • Intercommunicator: Between different groups of processes.
• MPI_COMM_WORLD is the initial communicator containing all processes in the application.

Non-Blocking Routine Formats

• MPI_Isend: Initiates non-blocking data send.
• MPI_Irecv: Initiates non-blocking data receive.
• Completion of non-blocking operations is detected using:
  • MPI_Wait: Blocks until the operation completes.
  • MPI_Test: Returns a flag indicating whether the operation has completed.

Send Communication Modes

• Standard Mode: The send operation can complete before the receive operation starts if the buffer is available.
• Buffered Mode: The send operation can complete before the receive operation; user must attach a buffer using MPI_Buffer_attach().
• Synchronous Mode: The send operation completes only when the matching receive operation is also complete.
• Ready Mode: The send operation only starts if the matching receive operation has already begun.

Collective Communication

• Involves a set of processes defined by an intra-communicator.
• Message tags are not used.
• The main collective operations are:
  • MPI_Bcast(): Broadcast from a root process to all others.
  • MPI_Gather(): Gather values from a group of processes.
  • MPI_Scatter(): Scatter the buffer into parts for a group of processes.
  • MPI_Alltoall(): Sends data from all processes to all processes.
  • MPI_Reduce(): Combine values from all processes into a single value.
  • MPI_Reduce_scatter(): Combine values and scatter the results.

Barrier

• A synchronization mechanism that stops all processes until they reach a specific barrier call.

Evaluating Parallel Programs

• It's essential to evaluate parallel algorithms to determine their effectiveness.
• Two key metrics are:
  • Computation time: The time spent on actual calculations.
  • Communication time: The time spent on transmitting data.

Equations for Parallel Execution Time

• Sequential execution time, ts: Estimated by counting the computational steps of the best sequential algorithm.
• Parallel execution time, tp: In addition to computational steps (tcomp), it also considers communication overhead (tcomm).
  • tp = tcomp + tcomm

Computational Time

• Computed based on the number of computational steps.
• It is typically a function of the problem size (n) and the number of processors (p).
  • tcomp = f(n, p)
• The computation time can be broken down into parts separated by message passing.

Communication Time

• It depends on:
  • Number of messages.
  • Size of messages.
  • Transfer mode.
  • Interconnection network structure.
  • Network contention.

Estimating Communication Time

• A first approximation can be made using:
  • tcomm1 = tstartup + ntdata
  • tstartup: Startup time (message latency), time to send a message with no data.
  • tdata: Transmission time to send one data word.
  • n: Number of data words in the message.

Final Communication Time

• The final communication time (tcomm) is the sum of communication times for all messages sent from a process.

Key Takeaways

• Message passing computing is a key technique for achieving parallelism.
• MPI is a widely used standard for message passing.
• Effective parallel program evaluation requires understanding both computational time and communication time.

This quiz covers the fundamental concepts of message passing computing, focusing on parallel programming techniques. It delves into process creation methods, communication between concurrent processes, and the use of message passing libraries. Test your knowledge on static and dynamic process creation and their implications in parallel programming.