Parallelism
Table of Contents
1. Measuring Runtime
To measure time, most systems use epoch time, defined as the number of seconds since some historical event. The most common epoch is UNIX time, which starts on January 1, 1970 at 00:00:00 GMT. C has several functions for this in the <time.h> library.
Generally, to measure runtime, we use the clock() function, which gives us a timestamp in terms of the number of CPU clock ticks. We can get the runtime by taking the difference and dividing by the constant CLOCKS_PER_SEC, which will give us runtime rounded to the nearest millisecond.
1.1. Amdahl’s Law
If half of our original runtime is at 1x speed, we have to speedup the second half of the code by infinity to achieve a 2x speedup. This observation is Amdahl’s Law: the maximum speedup we can attain is limited by the fraction that cannot be sped up.
2. SIMD Instructions
Instead of doing math on one number at a time, we can instead do math on several numbers at a time, in a single clock cycle. Instructions that do this are known as SIMD instructions, or single-instruction, multiple data instructions. These use specialized “vector” registers which store 128, 256, or even 512 bits; processors must support these instructions at the hardware-level, and act as extensions to the base instruction set.
Generally speaking, most of the speedup comes not from doing math operations at the same time, but instead from doing less memory accesses.
2.1. Intel Intrinsics
RISC-V doesn’t have a standard vector library, so we will be using x86 vector operations instead. Intel Intrinsics are C functions that allow access to the x86 SIMD instructions that may be present on a machine. These instructions belong to one of several libraries that were developed over the years:
- SSE (Streaming SIMD Extensions)
- 64-bit and 128-bit registers (4 32-bit integers at a time or 2 doubles at a time)
- AVX (Advanced Vector Extensions)
- successor of SSE, 256-bit registers
- AVX-2
- extension of AVX with more supported instructions
- AVX-512
- 512-bit registers, has various performance and compatibility issues
- AVX10
- successor to AVX-512, introduced in 2023 to solve the complexity of AVX-512
2.1.1. Types
The following types are used to store variables:
| Type | Description |
|---|---|
__m256 |
256-bit register for storing floats |
__m256d |
256-bit register for storing doubles |
__m256i |
256-bit register for storing integers |
__m128, __m128d, __m128i |
128-bit register for the respective data |
Each type corresponds directly to a type of SIMD register (note that x86 has different sets of registers for floats, doubles, or integers). Each register can pack multiple pieces of data at once so we can operate on them at the same time — for example, __m128 can store 4 32-bit floats.
2.1.2. Instructions
SIMD instructions (functions) are generally of the format:
_<register size>_<instruction>_<component type>()
For example, _mm256_add_epi32() adds two 256-bit vectors, treating the vectors as arrays of 32-bit integers. There exists a full list of Intel Intrinsics instructions.
When working with these instructions, avoid these common mistakes:
- trying to directly access a 32-bit chunk of a SIMD vector (such as through typecasting)
- need to do an explicit load/store, since registers are different from memory
- trying to
_mm_loador_mm_storewith unaligned addresses- if you must, use
_mm_loaduor_mm_storeuinstead - use
aligned_alloc()instead ofmalloc()to get aligned heap memory - force a stack/local variable by using compiler attributes, e.g.
float arr[4] __attribute__((aligned(16)));
- if you must, use
- forgetting the tail case
- some data at the end may not be a multiple of your vector size, so these must be handled one at a time
- using too many vectors
- ends up slowing down since the compiler tries to load/store many SIMD vectors to the stack a bunch of times
When parallelizing using SIMD instructions, it usually comes down to these following steps:
- Broadcast any constants and initialize any vectors/registers you will use.
- Loop over your input one vector-width chunk at a time.
- Perform operations across all lanes in parallel.
- Reduce or store the vector result as needed.
- Handle the remaining elements.
Example: Dot product
Here, we will use the above 5 steps to write SIMD code to perform a dot product operation on two arrays. The main idea is that we can use the _mm_fmadd_ps(a, b, c) instruction, which multiplies packed elements in a and b, adds it to the elements in c, and stores the result in the destination:
#include <immintrin.h>
#include <stdio.h>
int main() {
// the two vectors we are doing the dot product on
int length = 10;
float arr1[10] __attribute__((aligned(32))) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
float arr2[10] __attribute__((aligned(32))) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
// STEP 1: broadcast 0 over vec3
__m128 vec3 = _mm_set_ps1(0);
// STEP 2: loop over our arrays by chunks of 4
int i = 0;
while (i + 4 < length) {
__m128 vec1 = _mm_load_ps(arr1 + i);
__m128 vec2 = _mm_load_ps(arr2 + i);
// STEP 3: perform operations across all lanes in parallel
vec3 = _mm_fmadd_ps(vec1, vec2, vec3);
i += 4;
}
// STEP 4: store the vector result on the stack
float sum[4] __attribute__((aligned(32)));
_mm_store_ps(sum, vec3);
// STEP 5: handle our remaining elements
while (i < length) {
sum[0] += arr1[i] * arr2[i];
i++;
}
printf("%f\n", sum[0] + sum[1] + sum[2] + sum[3]);
return 0;
}
3. Multithreading
A program is a sequence of instructions to run. A process is the actual execution of a program: each process is a largely separate entity, with its own memory space. Each process is composed of threads, which are independently running instruction sequences that share most memory. The datapath we’ve discussed so far is a CPU core, which can run one thread at any given time. A CPU can be composed of multiple cores, which thus allows multiple threads to be run simultaneously.
A single-threaded program is a program that only runs one thread. Multi-threaded and multi-process programs are programs that use multiple threads or processes. The operating system is responsible for managing which threads get run on which CPUs.
On most modern computers, the number of active threads is way larger than the number of available cores, so most threads are idle at any given time. This is one of the big reasons why runtime can vary, even when running the same program.
In multithreading, each thread has its own registers, its own PC, and its own stack. Each thread shares the same heap, and communication is done through shared memory. Since threads run simultaneously, we have no control over the order in which threads do their work.
The fork-join model involves a master thread then can be forked into multiple threads to do some parallel work, and then join back together to coordinate again. Forks and joins take a while, so our goal is to minimize the number of forks/joins, and minimize the serial parts.
3.1. OpenMP
OpenMP is an extension of C used for multi-threaded code which generally fllows the fork-join framework. Include the header file <omp.h> and is generally uses pragmas to define multithreaded code.
In order to create a parallel section, write:
#pragma omp parallel
{
// parallel code
}
The code in the parallel section gets run on all threads, so we need some way to distinguish threads. In a parallel segment, we can run:
omp_get_num_threads()returns the number of threads runningomp_get_thread_num()returns a unique number from 0 to the number of threads per thread
By default, any variable declared outside the parallel segment is shared, and any variable declared inside the parallel segment is private. You can also explicitly scope variables by writing #pragma omp parallel private(private_var) shared(shared_var).
Example: Parallel hello world
#include <stdio.h>
#include <omp.h>
int main() {
int x = 0; // shared variable
#pragma omp parallel
{
int tid = omp_get_thread_num(); // private variable
x++;
printf("Hello World from thread %d, x = %d\n", tid, x);
if (tid == 0) {
printf("Number of threads = %d\n", omp_get_num_threads());
}
}
printf("Done with parallel segment\n");
}
3.1.1. Multithreaded For Loops
Say we want to write a multithreaded for loop over an array of 1 million integers. We have two options here:
- Interweaving:
for (int i = tid; i < 1000000; i+=4) - Blocking:
for (int i = tid * 250000; i < (tid + 1) * 250000; i++)
With standard multithreading, option 1 is actually as slow as the serial version of the code due to cache coherency issues. Cache coherency ensures that all the caches share the same view of memory. Since cores have their own L1 and L2 caches, whenever a thread updates data in their cache, if another cache has that data, that cache must first evict that block before our thread can modify it. Therefore, we must ensure that only one thread’s cache has the data to be modified.
You can also just use #pragma omp parallel for before a for loop to parallelize it correctly. Note that this must be done within an existing parallel block. This also only works if the loop bounds are known beforehand, and with no break statements in the loop.
3.2. Race Conditions
Recall that the operating system can choose whichever threads it wants to run, and in what order. This is one of the biggest downsides to multithreading: a multithreaded program is no longer deterministic in terms of the execution order. Formally, a multithreaded program is correct only when any execution order yields the same result.
For example, the following code contains a race condition:
int x = 0;
#pragma omp parallel
{
x = x + 1;
}
The problem is that some threads might read before other threads have written, so it is possible for x to end up becoming 1, instead of 4. In practice, most times you run this code, the result will be 4; however, there is a 0.01% chance you get the wrong result. Therefore, race condition bugs are extremely hard to debug since they are usually silent-failing and non-deterministic.
3.3. Atomic Operations
Regardless of how we do some things, multithreading will never work if the instructions happen to be perfectly interleaved. Our solution is to create an instruction that checks a value and writes to memory at the same time. These are known as atomic instructions.
3.3.1. Locks
A lock is an object that helps with synchronization. Essentially, each thread can try to acquire a “lock” on an object, but only one thread can have the lock at a given time. Formally, locks have two operations: acquire and release.
Code surrounded by a lock is called a critical section, because only one thread is allowed to run that section at a time. OpenMP has several commands for this:
#pragma omp barrier- forces all threads to wait until all threads have hit the barrier
#pragma omp critical- creates a critical segment in parallel code: only one thread can run a critical segment at a time
4. Multiprocess Programs
While a multithreaded program is fundamentally one program, individual processes are essentially distinct program instances entirely. In a multithreaded program, the entire process crashes if any single thread crashes. In a multiprocess program, each process runs independently.°
Because you don’t share memory, you can’t use locks or concurrency primitives. This effectively restricts multiprocess programs to problems that can be split entirely into independent tasks.
Inter-process communication is done by sending messages between nodes. Generally, messages take a lot of time to transmit/communicate. In any exchange, the sender should be ready to send a message, and the receiver should be ready to receive a message.
A very common framework is the manager-worker system: you have a manager, whose job is to assign work to processes, and workers, who receives work from the manager and does work.