General

Point-to-Point Communication

• MPI_Send() - send data from one process to another

• MPI_Recv() - receives data from another process

Collective Communication

• MPI_Bcast() - broadcasts data from one process to all

• MPI_Reduce() - combines results from multiple processes

• MPI_Gather() - collects data from multiple processes to one

• Pipelining: overlap individual parts

• Superscalar execution: multiple things at same time

• Out of Order execution (OOO): re-order operations

fast (expensive) memory which keeps copy of data in main memory (hidden from software)

• cache-hit: in-cache memory access (cheap, fast)

• cache-miss: non-cached memory access (expensive, slow)

how cache memory structured to map main memory to cache locations

• Direct-mapped: only 1 address line

• Fully-associative: line can be stored anywhhere in cache

• n-way set associative: determine set for line

• Compulsory: 1st access to a block

• Capacity: cant contain all blocks -> increase size

• Conflict: collision

• Coherence: invalidation

increasing amount of parallel resources can be used

Strong Scaling: (harder to achieve)

• constant problem size

• hope for linear devrease in execution time with increasing nubmer of cores

Weak Scaling:

• increase problem size in accordance to number of cores

• hope for constant execution time

Distributed Memory

= main memory (RAM) is physically distributed (CPU can only access portion of it)

Shared Memory

= main memory (RAM) is physically shared (CPU can directly read/write all of it)

• UMA - uniform memory acces (all memory accessible with same speed

• NUMA - non-unform meemory access (some parts of memory accessible faster)

Threading

= program consists of several threads

• prrivate data

• shared data (read/written by all threads)

• communication is implicity

Message Passing

= program consists of several processes

• private data

• no shared data

• communication is explicity (sending messages)

occurs in multi-threaded programs

multiple threads modify different variables on same cache line

—> cause unnecessary cache invalidations

Solutions:

• (Cache-line) Padding

  make extra space btw variables -> placed in separate lines

• Align Data Structures

  -> cache line boundaries

multiple threads share and modify same variable

—> leading to cache synchronization overhead

Solution: Atomic operations, distributed counters, thread-local storage