Parallel Computing Tutorial: Learn Parallelism from Scratch (2026)
For decades, processors gained performance through higher clock speeds, but that era ended — today's performance gains come from parallelism. Having optimized scientific simulations that run on supercomputers with thousands of cores, I have learned that writing correct and fast parallel code requires a fundamentally different mindset than sequential programming. This tutorial covers shared-memory threading, distributed-memory MPI, GPU acceleration with CUDA, and the parallel patterns that unify them.
We will explore the challenges of race conditions, deadlocks, load balancing, and Amdahl's law — which reminds us that the serial portion of any program ultimately limits speedup.
Amdahls Law and Gustafsons Law
Amdahl's Law states that the maximum speedup from parallelization is limited by the serial fraction: Speedup = 1 / (S + (1-S)/P). Even with infinite processors, a program that is 5% serial cannot speed up beyond 20x. Gustafson's Law offers a more optimistic view — as problem sizes scale, the parallel portion dominates, so scaled speedup = S + P*(1-S).
def amdahl_speedup(s, p): return 1.0 / (s + (1-s)/p)
def gustafson_speedup(s, p): return s + p*(1-s)
s,p=0.1,64; print(f"Amdahl: {amdahl_speedup(s,p):.2f}x"); print(f"Gustafson: {gustafson_speedup(s,p):.2f}x")Shared-Memory Parallelism with OpenMP
OpenMP provides a portable API for shared-memory parallel programming using compiler directives. A parallel for loop with #pragma omp parallel for distributes iterations across threads. The reduction clause handles combining partial results without explicit synchronization. False sharing can devastate performance and must be mitigated with padding.
#include
#include
#define N 100000000
int main() {
double sum = 0.0;
#pragma omp parallel for reduction(+:sum) schedule(guided)
for (int i = 0; i < N; i++) { sum += (double)i * i / N; }
printf("Sum = %f\\n", sum); printf("Threads: %d\\n", omp_get_max_threads());
return 0;
} Distributed-Memory with MPI
MPI is the de facto standard for distributed-memory parallel programming. Processes communicate by sending and receiving messages. Point-to-point communication (MPI_Send, MPI_Recv) is the foundation, while collective operations like MPI_Allreduce and MPI_Bcast provide optimized group communication. MPI follows the SPMD model.
#include
#include
int main(int argc, char** argv) {
MPI_Init(&argc, &argv);
int rank, size; MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size);
int local = rank * rank, global = 0;
MPI_Reduce(&local, &global, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);
if (rank == 0) printf("Sum of squares = %d\\n", global);
MPI_Finalize(); return 0;
} GPU Programming with CUDA
CUDA enables general-purpose computing on NVIDIA GPUs. A GPU contains thousands of lightweight cores organized into streaming multiprocessors. Kernels are launched with a grid of thread blocks. Memory hierarchy is critical: global memory (high latency), shared memory (low latency, per-block), and registers. Coalesced memory access is essential for throughput.
__global__ void vector_add(const float* a, const float* b, float* c, int n) {
int idx = blockIdx.x * blockDim.x + threadIdx.x;
if (idx < n) { c[idx] = a[idx] + b[idx]; }
}
int main() {
int n = 1<<20; float *d_a, *d_b, *d_c;
cudaMalloc(&d_a, n*sizeof(float)); cudaMalloc(&d_b, n*sizeof(float)); cudaMalloc(&d_c, n*sizeof(float));
int t=256, b=(n+t-1)/t; vector_add<<>>(d_a,d_b,d_c,n);
cudaDeviceSynchronize(); cudaFree(d_a); cudaFree(d_b); cudaFree(d_c);
return 0;
} Parallel Patterns: Map, Reduce, and Stencil
Common parallel patterns appear across all parallel programming models. The map pattern applies a function to every element independently — embarrassingly parallel. Reduce combines elements using an associative operator in O(log n) time using a tree. Stencil operations update each element based on a fixed neighborhood, benefiting from tiling.
template
T parallel_reduce(const T* data, int n, Op op, T identity) {
extern __shared__ T shared[]; int tid = threadIdx.x;
T local = identity;
for (int i = blockIdx.x*blockDim.x+tid; i < n; i += gridDim.x*blockDim.x)
local = op(local, data[i]);
shared[tid] = local; __syncthreads();
for (int s = blockDim.x/2; s > 0; s >>= 1) {
if (tid < s) { shared[tid] = op(shared[tid], shared[tid+s]); } __syncthreads();
}
if (tid == 0) atomicAdd(&result, shared[0]);
} Race Conditions, Deadlocks, and Synchronization
A race condition occurs when multiple threads access shared data concurrently and the result depends on execution order. Proper synchronization uses locks (mutexes), semaphores, or atomic operations. Deadlocks arise when each thread holds a resource another needs, creating a circular wait. The four Coffman conditions must all hold for a deadlock.
#include
#include
std::atomic counter{0};
void worker(int iters) {
for (int i = 0; i < iters; i++) {
int expected = counter.load();
while (!counter.compare_exchange_weak(expected, expected+1))
std::this_thread::yield();
}
}
int main() {
std::thread t1(worker, 100000); std::thread t2(worker, 100000);
t1.join(); t2.join();
printf("Counter: %d\\n", counter.load());
return 0;
} Frequently Asked Questions
What is the difference between concurrency and parallelism?
Concurrency is about dealing with multiple tasks at once (logical simultaneity), while parallelism is about executing multiple tasks simultaneously (physical simultaneity).
What is false sharing and how do you prevent it?
False sharing occurs when threads on different cores modify variables that reside on the same cache line. Prevention: pad data structures so independent variables are on separate cache lines (typically 64 bytes apart).
Why is the reduction pattern important?
Reduction is the fundamental building block for combining results from parallel workers. It uses a tree structure to achieve O(log P) time instead of O(P).
What is the difference between SIMD and SIMT?
SIMD processes multiple data with one instruction in lockstep. SIMT (NVIDIA) drives multiple threads with one instruction, but threads can diverge and reconverge. SIMT is more flexible.
Originally published on Ayodhyyya. Last updated June 1, 2026.