MPI

A standard for message passing, implemented by several libraries (for instance OpenMPI).

MPI organises processes in communicators, which are collections of processes that can send messages to each other. MPI_COMM_WORLD contains all the processes. In addition, there are specialised communicators such as the cartesian communicator to simplify organising the processes in a cartesian grid.

MPI supports a lot of different calls. Only some are part of this subject (These are some of them, but the list is incomplete):

int MPI_Ssend( void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm )
int MPI_Wait ( MPI_Request *request, MPI_Status *status)
int MPI_Isend( void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request )
int MPI_Irecv( void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Request *request )
int MPI_Issend( void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request )

Note that the functions starting on an I are non-blocking. Their counterparts without the I are however not always blocking calls. The regular send function is in many implementations only blocking when the data that is to be sent is to large to fit in the send buffer. The size of this buffer may vary, so depending on the system running the program it may or may not deadlock.

Let's look at one of the more advanced MPI functions: MPI_Reduce. The use case for MPI_Reduce can be simple: say all processes have some data, and we would like to perform some operation on that data, and reduce it to a single element. For instance, let's say all processes have an integer, and we would like to find the sum of all those integers. This is the signature of the reduce function: MPI_Reduce(void *input, void *output, int count, MPI_Datatype datatype, MPI_Op operation, int dest, MPI_Comm comm). Note that while all processes need to pass a pointer to the output value, only one process will actually get the result - dest. The following minimal program illustrates the use of MPI_Reduce:

#include <stdio.h>
#include <mpi.h>

int main() {
  MPI_Init(NULL, NULL);
  int rank;
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  int number = rank;
  int accumulator = 0;
  MPI_Reduce(&number, &accumulator, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
  if (rank == 0)
    printf("accumulator = %d\n", accumulator);
  MPI_Finalize();
}

Other operators include MAX, MIN, PROD, LOR (logical OR) and BOR (bitwise OR). It is worth knowing that input and output can't point to the same variable. Another variant of the function, MPI_Allreduce is similar, but results in all processes getting the result; naturally, this function does not take a dest argument.

OpenMP

OperMP is an API for multi-platform shared memory multiprocessing. Compiler directives for parallellising seemingly procedural code. Excellent at parallellising (for) loops. Does not expose "low-level" features used, mutexes etc.

#pragma omp parallel
for(int i = 0; i < 10000; i++){
    array[i] = myFunction(i);
}

Different schedules for the parallelizing may be chosen, like this:

#pragma omp parallel for schedule(kind [, chunk_size])

The different kinds of available schedules are

Static

Divides the loop into equal-sized chunks or as equal as possible. The default chunk size is loop_count/number_of_threads.

Dynamic

Use the internal work queue to give a chunk-sized block of loop iterations to each thread. When a thread is finished, it retrieves the next block of loop iterations from the top of the work queue. By default, the chunk size is 1.

Guided

Guided scheduling is similar to dynamic in that not all iterations are allocated at the start. However, threads get a large contiguous chunk to start with, and the chunk size gradually decreases as the program runs, down to the limit set in the chunk_size parameter.

Note the functions, as they may be necessary to know on the exam:

omp_get_num_threads(); // return the total number of threads
omp_get_thread_num();  // return the id of this thread

Pthreads

Basic threading library. Basically a thread spawns other threads that start running a supplied function. No built-in barrier, but access to mutexes etc.

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                   void *(*start_routine) (void *), void *arg);

int pthread_join(pthread_t thread, void **value_ptr);

Why GPUs?

We say GPU, but we really mean GPGPUs, General Purpose GPUs. GPUs have a lower clock speed, but in turn they have a lot more cores. If used correctly, they can speed up computations that apply the same instruction to different data, SIMD. Code run on the GPU are usually small simple program units kalled kernels.

Launching a kernel

1. Create a context
2. Load the kernel source code
3. Compile the kernel
4. Allocate memory on device
5. Copy memory to device
6. Launch kernel
7. Copy back result

These steps are the steps for OpenCL, for CUDA, 1-3 is done ahead of time, and thus only 4-7 is done when launching the kernel.

CUDA vs OpenCL concepts

Use early cases most often in small switches.

Compilers will turn switch statements with few (typically anything less than 3) cases to a chain of if statements. Early cases are faster to find in such cases. In large switches, a slower jump table is used. Jump tables spend the same amount of time jumping regardless of what case is used.

Non-critical race condition

A race condition which only affects some part of the system, while the system as a whole will end up in the same state regardless of input order. The program output is unaffected by such race conditions.

Critical race condition

A critical race condition is a race condition which affects the final state of the program. This will often result in bugs.

How to fix/avoid race condition

Depends on what is causing it, but usually, you are looking for a synchronization mechanism. The ones we care about are

• Semaphore
• Mutex
• Spinlock

The samaphore is a counter that indicates the number of resources available. A thread will decrease the counter to aquire a resource, and increase it when it is finished. A mutex is a semaphore with the counter set to 1.

Amdahl's Law

Amdahl's law is used to find maximum expected improvement to a system when only a part of the system is improved. It is often used in parallel computing to predict the theoretical maximum speedup using multiple processors.

The speedup of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program.

Example: A program needs 20 hours using a single processor core, and a particular portion of the program which takes one hour to execute cannot be parallelized, while the remaining 19 hours (95%) of execution time can be parallelized. No matter how many processors are devoted to a parallelized execution of this program, the minimum execution time cannot be less than the one hour. Hence, the speedup is limited to at most 20×.

The execution time of an algorithm when executed on $n$ threads, where $B$ is the fraction of the algorithm which cannot be parallelized:

$$ T(n) = T(1) \bigg( B + \frac{1}{n}(1-B) \bigg) $$

The theoretical speedup then becomes:

$$ S(n) = \frac{T(1)}{T(n)} = \frac{T(1)}{ T(1) \Big( B + \frac{1}{n}(1-B) \Big) } = \frac{1}{B + \frac{1}{n}(1-B)} $$

Gustafson's Law

Gustafson's law says that computations involving arbitrarily large data sets can be efficiently parallelized.

$$ S(P) = P - \alpha \cdot (P - 1) $$

• $P$, the number of processors
• $S$, the speedup
• $\alpha$, the non-parallelizable fraction

Strong vs weak scaling

Strong scaling describes how a program's execution time is altered when adding processors and keeping the problem size constant.

Weak scaling describes how a program's execution time is altered when adding processors and increasing the problem size linearly.

The Brick Wall

A combination of three other "walls":

The power wall

Consuming exponentially increasing power with increasing operating frequency.

The memory wall

The increasing gap between processor and memory speeds.

The ILP wall

The diminishing returns on finding more ILP.

NUMA

Non-uniform Memory Access

NUMA is a computer memory design which is used in multiprocessing. Because CPUs are so much faster than the memory, sophisticated measures are needed to avoid stalling the CPU. Under NUMA, the memory access time depends on the memory location relative to the processor. Memory which is local to the processor, can be accessed faster than memory which is local to another processor, or memory which is shared between multiple processors.

Replicated vs. Distributed Grids