hpc @ aub day 2

the message passing interface (MPI)

acknowledgements

• much of this lecture builds on slide material from William Gropp, University of Illinois
• mpi4py is a cythonized wrapper around MPI written by Lisandro Dalcin, CIMEC

overview

• yesterday we discussed the "power tools" of computational software usage and development.
• today we dive into the Message Passing Interface standard, with some notes on tuning i/o.
• tomorrow is an overview of the free computational tools available through the Sage toolkit, including numpy, scipy, and sympy.
• Thursday we integrate some of what we've learned from each day, and dive into two application codes, Clawpack and PETSc, through their Python wrappers.

today's lecture - the message passing interface (MPI)

• the high performance computing landscape
• communication contexts
• point to point communication
• collective communication
• buffering and one-sided communication
• parallel i/o

the free lunch is over

the multiple forms of parallelism

• instruction - multiple program instructions are simultaneously dispatched in a pipeline or to multiple execution units (superscalar)
• data - the same program instructions are carried out simultaneously on multiple data items (SIMD)
• task - different program instructions on different data (MIMD)
• collective - single program, multiple data, not necessarily synchronized at individual operation level (SPMD)

the rise of manycore

parallel architectures

• all modern supercomputing architectures are connected over toroidal networks
  • close mapping to physically n-dimensional problems
  • efficient algorithms exist for local point to point and collective communications across toroids
• expect to see higher dimensional interconnects and power-efficient networks that consume less power when not sending traffic

parallel programming paradigms

• a parallel programming paradigm is a specific approach to exploiting parallelism in hardware
• many programming paradigms are very tightly coupled to the hardware beneath!

• CUDA assumes large register files, same instruction multiple thread parallelism, and a mostly flat, structured memory model, matching the underlying GPU hardware

parallel programming paradigms

• a parallel programming paradigm is a specific approach to exploiting parallelism in hardware
• many programming paradigms are very tightly coupled to the hardware beneath!

• OpenMP exposes loop level parallelism with a fork/join model, assumes the presence of shared memory and atomics

parallel programming paradigms

• a parallel programming paradigm is a specific approach to exploiting parallelism in hardware
• many programming paradigms are very tightly coupled to the hardware beneath!

• OpenCl tries to generalize CUDA, but still assumes a 'coprocessor' approach, where kernels are shipped from a master processor to worker cores

the message passing model

• a process is (traditionally) a program counter for instructions and an address space for data
• processes may have multiple threads (program counters and associated stacks) sharing a single address space
• message passing is for communication among processes, which have separate address spaces
• interprocess communication consists of
  • synchronization
  • movement of data from one process's address space to another's

why MPI?

• communicators encapsulate communication spaces for library safety
• datatypes reduce copying costs and permit heterogeneity
• multiple communication modes allow more control of memory buffer management
• extensive collective operations for scalable global communication
• process topologies permit efficient process placement, user views of process layout
• profiling interface encourages portable tools

communicators

• processes can be collected into groups
• each message is sent in a context, and must be received in the same context
• a communicator encapsulates a context for a specific group
• a given program may have many communicators with any level of overlap
• two initial communicators
  • MPI_COMM_WORLD (all processes)
  • MPI_COMM_SELF (current process)

datatypes

• the data in a message to send or receive is described by address, count and datatype
• a datatype is recursively defined as:
  • predefined, corresponding to a data type from the language (e.g., MPI_INT, MPI_DOUBLE)
  • a contiguous, strided block, or indexed array of blocks of MPI datatypes
  • an arbitrary structure of datatypes
• there are MPI functions to construct custom datatypes

tags

• messages are sent with an accompanying user-defined integer tag to assist the receiving process in identifying the message
• messages can be screened at the receiving end by specifying the expected tag, or not screened by using MPI_ANY_TAG

checkpoint

if tags allow us to screen/separate peer-to-peer messages, why do we need communicators?`

mpi basic (blocking) send

C

int MPI_Send(void* buf, int count, MPI_Datatype type,
int dest, int tag, MPI_Comm comm)

Python (mpi4py)

Comm.Send(self, buf, int dest=0, int tag=0)
Comm.send(self, obj=None, int dest=0, int tag=0)

mpi basic (blocking) recv

C

int MPI_Recv(void* buf, int count, MPI_Datatype type,
int source, int tag, MPI_Comm comm, MPI_Status status)

Python (mpi4py)

Comm.Recv(self, buf, int source=0, int tag=0,
Status status=None)
Comm.recv(self, obj=None, int source=0,
int tag=0, Status status=None)

synchronization

C

int MPI_Barrier(MPI_Comm comm)

Python (mpi4py)

Comm.Barrier(self)
Comm.barrier(self)

broadcast/reduce

C

int MPI_Bcast(void *buf, int count, MPI_Datatype type,
int root, MPI_Comm comm)

Python (mpi4py)

Comm.Bcast(self, buf, int root=0)
Comm.bcast(self, obj=None, int root=0)

collective data movement

collective data movement

collective data movement

understanding performance

• not all programs will run faster in parallel - the benefit of additional processors may be outweighed by the cost of moving data between them
• a typical cost model is

$$T = \frac{T_p}{p} + T_s + T_c $$

• T_c = communication overhead
• T_s = serial (non-parallelizable work)
• T_p = parallel work

latency and bandwidth

• simplest model: $$T = s + r \cdot n $$ where
• n is message size
• s includes both hardware (gate delays) and software (context switch, setup)
• r includes both hardware (raw bandwidth of interconnection and memory system) and software (packetization, copies between user and system)

timing and profiling

the elapsed (wall-clock) time between two points in an MPI program can be computed using MPI_Wtime:

• C

  double t1, t2;
  t1 = MPI_Wtime();
  t2 = MPI_Wtime();
  printf("time elapsed is: %e s\n", t2-t1);
  

timing and profiling

the elapsed (wall-clock) time between two points in an MPI program can be computed using MPI_Wtime:

• Python (mpi4py)

  t1 = MPI.Wtime()
  t2 = MPI.Wtime()
  print("time elapsed is: %e\n" % (t2-t1))
  

one-sided communication

• synchronization is separate from data movement
• balances efficiency and portability across a wide class of architectures
• retains MPI-1's "look and feel"
• helps deal with subtle memory behavior issues

why use remote memory access (RMA?)

• performance
• may allow more dynamic, asynchronous algorithms
• but get/put is not load/store
  • synchronization is exposed in one-sided communications

overview of one-sided api

• MPI_Win_create exposes local memory to RMA operation by other processes in a communicator

  • collective operation
  • create window object

• MPI_Put moves data from local memory to remote memory

• MPI_Get retreives data from remote memory into local memory

• MPI_Accumulate updates remote memory using local values

• data movement operations are non-blocking

• synchronization on window object still needed to ensure operation is complete

RAM functions for synchronization

multiple ways to synchronize

• MPI_Win_fence - barrier across all processes in communicator
• MPI_Win_{start, complete, post, wait} - involves groups of processors
• MPI_Win_{lock, unlock} - involves single other process

mpi i/o

• provides collective, distributed i/o using MPI's communicators
• writing is like sending, reading is like receiving

why not use mpi i/o

• sometimes the synchronization of collective calls is not natural
• sometimes the overhead of collective calls outweighs their benefits

some performance tuning thoughts

• collective i/o combined with noncontiguous accesses yield the highest performance
• try to coalesce as much of your i/o into few, large requests to minimize metadata overhead
• keep data as close as you can (memory > local disk > network-attached storage)
• buy sufficient i/o hardware for the machine
• use fast file systems instead of NFS-mounted home directories
• for noncontiguous requests, use derived datatypes and a single collective i/o call

challenges for exascale

• millions of processing elements demand new programming paradigms
• energy will be incredibly precious (optimistically, 60 MW)
• checkpointing and fault tolerance are still unsolved at scale
• many algorithms will no longer work, new approaches will be needed

Credits

• Pygments Integration
• MathJax Integration
• Original Slides - William Gropp
• Numerics/Guinea Pig - Jed Brown, Argonne National Laboratories