Introduction to Parallel Processing

Complete revision notes. Everything in this unit, organised by topic — definitions, diagrams, formulas, comparison tables and worked examples. Revise from this alone and you have the whole unit.

Part A — Why Parallelism?

A1. The free lunch is over

For roughly forty years, programs got faster every year without programmers doing anything. Clock speeds rose, and the same binary simply ran quicker on next year's processor. That era ended around 2005.

It ended because of the power wall. The dynamic power a chip consumes is approximately

P  =  C x V^2 x f

   C = capacitance,  V = voltage,  f = clock frequency

Raising the clock frequency requires raising the voltage to keep the transistors switching reliably, and because power depends on the square of voltage, the power consumed rises far faster than the performance gained. Past roughly 4 GHz the heat generated could no longer be removed economically. The related memory wall (Unit II) and instruction-level parallelism wall compounded the problem.

This is the single fact that motivates the entire subject: hardware is now parallel by default, so software must be parallel to use it.

A2. Concurrency vs parallelism vs multitasking

Three terms that are constantly confused. The distinction is examinable and worth stating precisely.

THE CHEF ANALOGY  (remember this — it answers the question by itself)

  1 chef, 1 dish                 -> sequential.  No concurrency, no parallelism.
  1 chef, 3 dishes, juggling     -> CONCURRENCY. One core, progress on many
                                    tasks by switching cleverly.
  3 chefs, 3 dishes, at once     -> PARALLELISM. Real simultaneous work.
                                    Needs 3 chefs = 3 cores.

The one-line summary: concurrency is about structure; parallelism is about execution. A concurrent program can run on a single core; a parallel program cannot achieve parallelism without multiple processing units. Concurrency makes parallelism possible, but does not guarantee it.

A3. Latency vs throughput

These are independent quantities and improving one need not improve the other. Opening more toll booths does not make any individual car pass through faster, but far more cars get through per minute.

Worked example — the canteen counter. One counter serves a student in 2 minutes; 120 students are waiting.

The latency column never changes. No individual student is served faster, yet the queue clears eight times sooner. The same holds in a real system: an API taking 200 ms per request and handling 5 requests/sec will, behind a load balancer with four servers, handle 20 requests/sec — while every single request still takes 200 ms.

A4. Data parallelism vs task parallelism

Most real systems mix both. Data parallelism generally offers far more scope for scaling, because the amount of data typically grows without bound while the number of distinct tasks in a program does not.

A5. Speedup, and the ceiling

                 time on 1 core          T(1)
   Speedup  S  =  ----------------   =   ------
                 time on N cores         T(N)

   Perfect (linear) speedup = N on N cores.  Rarely achieved.
   100 s on 1 core -> 25 s on 4 cores  =  4x   (perfect)
   100 s on 1 core -> 40 s on 4 cores  =  2.5x (real life)

Speedup falls short of linear because some work is inherently sequential — step 2 requires the result of step 1 — and because parallelism introduces coordination overhead. Reading input, distributing work and combining results generally cannot be split.

Worked example — the ceiling is real. A job takes 10 hours, of which 1 hour is setup that cannot be split. The remaining 9 hours split perfectly.

Going from 100 cores to a million takes the speedup from 9.2× to 9.99×. Adding 999,900 cores gains almost nothing. That single un-splittable hour caps the program at 10× forever. The sequential fraction, not the core count, decides the outcome. This is Amdahl's Law, formalised in Unit III. As a preview: if a fraction f of the work is parallelisable, maximum speedup is 1/(1 − f).

A6. The new classes of bug

Parallelism introduces failure modes that simply do not exist in sequential code.

Worked example — a race condition, step by step. A bank balance is ₹1000. Two people withdraw ₹600 each from two ATMs at the same instant.

₹1200 was dispensed and the balance reads ₹400. The bank lost ₹600. Every individual step was arithmetically correct — the bug lives entirely in the interleaving. Change the timing by a microsecond and it works. This is exactly the same bug, in the same shape, as two threads executing sum += a[i] (see C4).

Part B — Flynn's Taxonomy & Memory Models

B1. Flynn's taxonomy

Proposed by Michael Flynn in 1966, this is the standard classification of computer architectures. It classifies a machine along two axes: the number of concurrent instruction streams and the number of concurrent data streams. Two binary choices give four categories.

                      |  SINGLE DATA   |  MULTIPLE DATA
   -------------------+----------------+------------------
   SINGLE INSTRUCTION |     SISD       |      SIMD
   -------------------+----------------+------------------
   MULTIPLE INSTRUCTN |     MISD       |      MIMD

   Do not memorise — decode. SIMD = Single Instruction, Multiple Data.
   Say the letters and the meaning follows.

MIMD is by far the most common class in general-purpose computing; SIMD dominates wherever the same operation must be applied to large regular data, which is why GPUs are SIMD-like. MISD is largely of theoretical interest, though it is genuinely used in safety-critical redundant systems.

B2. SPMD — what real programs actually do

if (my_rank == 0):
    read the file, hand out the chunks
else:
    wait for my chunk, then process it

# ONE program. Rank 0 takes a different path from rank 7.

Nobody hand-writes a separate program for each processor, so SPMD is the pattern nearly all real parallel code follows — both MPI and OpenMP programs are SPMD. Note carefully: SPMD is not a fifth Flynn category. It is a practical special case of MIMD. Flynn classifies the hardware; SPMD describes how we write software for that hardware.

B3. Shared memory

The second way to classify a parallel system is by how processors share data. In a shared-memory architecture, all processors access one common pool of RAM. If core 3 writes x = 5, core 7 can simply read x and see it. Communication happens implicitly, through ordinary variables.

   SHARED MEMORY

   +----+  +----+  +----+  +----+
   | P0 |  | P1 |  | P2 |  | P3 |
   +----+  +----+  +----+  +----+
      |       |       |       |
   ===+=======+=======+=======+===   interconnect
                  |
          +---------------+
          |  SHARED RAM   |
          +---------------+

Analogy: roommates sharing one fridge. Taking food is easy because it is all right there, but you bump into each other, and two people reaching for the last egg simultaneously is a collision — a race condition.

Advantages: a simple mental model, no explicit data movement, and easy programming with threads or OpenMP. Disadvantages: it does not scale past tens of cores, it requires hardware cache coherence (Unit II), and it is vulnerable to race conditions and contention.

B4. UMA vs NUMA

Shared memory subdivides according to whether all memory is equally distant from all cores.

Worked example — what NUMA actually costs. A two-socket server, 32 cores and 256 GB per socket. Local access ≈ 80 ns; remote access across the interconnect ≈ 140 ns, i.e. 1.75× slower.

Same binary, same input, same core count — a 75% difference in runtime determined solely by where the data physically sits. Nothing in the source code reveals which row you are in. NUMA is the underlying reason that simply adding more CPUs to one machine eventually stops helping: it is the physics behind the ceiling on vertical scaling.

B5. Distributed memory

In a distributed-memory architecture each processor has its own private memory and no processor can directly address another's. The only way to share data is to send a message across a network. This is precisely the model MPI implements.

   DISTRIBUTED MEMORY

   +----+ +-----+     +----+ +-----+     +----+ +-----+
   | P0 |-| RAM |     | P1 |-| RAM |     | P2 |-| RAM |
   +----+ +-----+     +----+ +-----+     +----+ +-----+
      |                  |                  |
      +==================+==================+
                     NETWORK
        (the ONLY path between nodes: messages)

Analogy: everyone has their own fridge in their own house. To share food you must phone and deliver. More coordination is required, but you can keep adding houses indefinitely.

The trade-off in one line: shared memory is easy to program and hard to scale; distributed memory is hard to program and scales without limit.

B6. Hybrid architectures

Every modern supercomputer is hybrid: a cluster of nodes connected by a fast network (distributed memory), where each node is itself a shared-memory multicore machine, usually with one or more GPUs attached.

   NODE 0                          NODE 1
   +---------------------+         +---------------------+
   | core core core core |         | core core core core |   <- OpenMP
   |     shared RAM      |         |     shared RAM      |      inside
   |        [GPU]        |         |        [GPU]        |   <- CUDA
   +---------------------+         +---------------------+
              |                              |
              +==============================+
                         NETWORK                          <- MPI between

Three tools appear in one program: MPI moves data between nodes, OpenMP uses the many cores within a node, and CUDA drives the GPU. The analogy is a neighbourhood of shared houses: inside each house roommates share one fridge, and between houses you phone and deliver.

Part C — Parallel Programming Models

C1. Three ways to split work

Why a pipeline feels faster. Suppose a job has 3 stages of 10 minutes each, and there are 6 jobs to process.

SEQUENTIAL:   6 jobs x 30 min                 = 180 min

PIPELINE:     fill the pipe (2 stages)         =  20 min
              then one job completes every      =  10 min
              -> 20 + (6 x 10)                  =  80 min

Latency per job is STILL 30 minutes — no single job got faster.
Throughput rose from 1 job / 30 min to 1 job / 10 min.

Speedup approaches the number of stages, but only once the
pipeline is full — and only if the stages take equal time.
The slowest stage sets the rate for everybody.

This is the same latency-versus-throughput distinction from A3, and the same reason a pipeline with one slow stage performs badly — a form of load imbalance.

C2. The programming-models landscape

The model follows the memory architecture, not personal preference. Shared memory implies OpenMP or threads; distributed memory implies MPI; a GPU implies CUDA. Hybrid machines use several at once (B6).

C3. OpenMP and the fork-join model

OpenMP (Open Multi-Processing) is an API for shared-memory parallel programming in C, C++ and Fortran. It consists of compiler directives (#pragma omp ...), a runtime library and environment variables. Its defining characteristic is that parallelism is expressed by annotating existing serial code rather than rewriting it: compile without the -fopenmp flag and the pragmas are ignored, leaving a valid serial program.

OpenMP follows the fork-join execution model:

   master thread
        |
        |                    #pragma omp parallel
     FORK ------+-----+-----+-----+
        |       |     |     |     |     team of threads
        |      T0    T1    T2    T3     runs the region
        |       |     |     |     |
     JOIN ------+-----+-----+-----+     implicit barrier
        |
        |    (serial again)
        v

The program begins as a single master thread. At a parallel region it forks a team of threads that execute the region concurrently; at the end of the region the threads join at an implicit barrier and execution returns to serial. A program may fork and join many times.

The core toolkit.

#include <omp.h>

#pragma omp parallel              // fork a team of threads
#pragma omp parallel for          // fork + split loop iterations
#pragma omp critical              // only one thread at a time here
#pragma omp barrier               // all threads wait here

omp_get_thread_num()              // my thread ID (0 .. n-1)
omp_get_num_threads()             // size of the current team
omp_set_num_threads(4)            // request a team size

compile with:  gcc -fopenmp prog.c -o prog

Non-determinism. The order in which threads execute is not defined. A parallel loop printing thread IDs will print them in a different order on different runs, and both orders are correct. This is the first lesson of parallel programming: you do not own the order. Correctness must never depend on it.

C4. Race conditions and critical sections

THE WRONG WAY

double sum = 0.0;
#pragma omp parallel for
for (i = 0; i < N; i++)
    sum += a[i];          // <-- every thread writes the SAME variable

Run it 5 times on the same input and you get 5 different answers.

Why. sum += a[i] is not one instruction. It is three:

   1. READ   sum from memory into a register
   2. ADD    a[i] to that register
   3. WRITE  the register back to sum

TRACE — two threads, sum starts at 100, T0 adds 5, T1 adds 3:

   Time   Thread 0              Thread 1              sum in memory
   t1     reads sum -> 100                             100
   t2                           reads sum -> 100       100
   t3     100 + 5 = 105                                100
   t4                           100 + 3 = 103          100
   t5     writes 105                                   105
   t6                           writes 103             103   <-- WRONG

Expected 108. Got 103. Thread 0's update vanished completely.
This is called a LOST UPDATE, and it is exactly the ATM trace in A6.

The window between reading and writing is where another thread can interfere. An operation that cannot be interrupted in this way is called atomic; sum += a[i] is not atomic.

A critical section is a region of code that must be executed by at most one thread at a time. OpenMP provides #pragma omp critical and #pragma omp atomic:

#pragma omp parallel for
for (i = 0; i < N; i++) {
    #pragma omp critical
    sum += a[i];          // correct — but now effectively SERIAL
}

This is correct but usually terrible: every iteration now waits for the lock, so the parallel version can be slower than the serial one. Correctness has been bought by destroying the parallelism. The right answer is a reduction.

C5. Reduction — the right fix

THE RIGHT WAY — one word

double sum = 0.0;
#pragma omp parallel for reduction(+:sum)
for (i = 0; i < N; i++)
    sum += a[i];

What reduction actually does. The compiler gives every thread a private copy of sum, initialised to the identity element of the operator (0 for +, 1 for *). Each thread accumulates into its own copy with no sharing whatsoever, and therefore no contention. At the end of the region the runtime combines the private copies into the original variable, using the same operator, once per thread.

   Thread 0: private sum = 0  ->  accumulates a[0..249]   -> 1200
   Thread 1: private sum = 0  ->  accumulates a[250..499] -> 1350
   Thread 2: private sum = 0  ->  accumulates a[500..749] -> 1180
   Thread 3: private sum = 0  ->  accumulates a[750..999] -> 1270
                                                             ----
   COMBINE at the join:  1200 + 1350 + 1180 + 1270    =     5000

   N shared writes became 4 combines. No lock in the hot loop.

Valid reduction operators include +   *   -   &   |   ^   &&   ||   max   min.

Note the general principle, which recurs throughout the course: accumulate locally, combine once. The same idea reappears as the fix for false sharing (Unit II), as the parallel reduction tree in CUDA (Unit IV), and as the combiner in MapReduce (Unit V).

C6. Data scoping, and which loops parallelise

SHARED BY ACCIDENT — the classic bug

int i, j, temp;                       int i, j, temp;
#pragma omp parallel for              #pragma omp parallel for private(j, temp)
for (i = 0; i < N; i++)               for (i = 0; i < N; i++)
  for (j = 0; j < N; j++) {             for (j = 0; j < N; j++) {
    temp = a[i][j] * 2;                   temp = a[i][j] * 2;
    b[i][j] = temp;                       b[i][j] = temp;
  }                                     }

  i is private (loop counter).          j and temp are now private.
  j and temp are SHARED — threads       Correct.
  overwrite each other's values.
  Garbage output, different each run.

Will this loop parallelise? A loop is safe to parallelise if its iterations are independent — no iteration reads a value another iteration writes.

A loop-carried dependence is the single most common reason a loop cannot be parallelised, and recognising one is a standard exam task.

Quick recall

Everything above, compressed. If you can reconstruct this page you know Unit I.

Power                P = C x V^2 x f          (why the clock stopped rising)
Speedup              S = T(1) / T(N)
Perfect speedup      S = N   on N cores
Amdahl ceiling       S_max = 1 / (1 - f)      f = parallel fraction
Pipeline time        fill + (jobs x slowest stage)

Self-check

Answer each out loud before opening it. Anything you have to peek at is your revision priority.