Parallel Architecture

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 — Interconnection Networks

A1. Why communication dominates

A modern processor performs an arithmetic operation in well under a nanosecond, while moving a word between two processors may take hundreds of nanoseconds or more. Beyond a modest number of processors, therefore, communication — not computation — determines performance. The interconnect is one of the most consequential architectural decisions in a parallel machine.

A good network provides low latency, high bandwidth, uniform access, fault tolerance and scalability at acceptable cost. No topology achieves all of these at once, which is why several families exist.

A2. Classification: static vs dynamic

                    INTERCONNECTION NETWORKS
                              |
              +---------------+---------------+
              |                               |
        STATIC (Direct)                 DYNAMIC (Switched)
     fixed point-to-point links       paths built on demand
              |                          through switches
              |                               |
   +----------+----------+          +---------+---------+
   |     |    |    |     |          |         |         |
 Linear Ring Mesh Torus Hypercube  Bus    Crossbar  Multistage
        Tree / Star / Fully-connected                 (Omega)

One-line answer: static = wires between nodes; dynamic = switches between nodes.

A3. The dynamic networks

(a) Bus

A single shared line to which all processors and memory modules attach. Only one transmitter may drive it at a time; a bus arbiter resolves simultaneous requests using fixed priority, round robin or daisy chaining. Because all devices observe every transfer, the bus naturally supports broadcast — the property that makes snooping cache coherence possible (B6).

    P0      P1      P2      P3
    |       |       |       |
====+=======+=======+=======+====   SHARED BUS
    |               |
    M0              M1

The scalability limit. Total bus bandwidth is a fixed constant, independent of how many processors attach. If the bus supports B transfers/sec and each of N processors needs r, it saturates once N·r > B. Beyond that, adding processors increases queueing delay without increasing throughput.

Worked example. Bus sustains 4 GB/s; each processor demands 500 MB/s.

A bus stops being effective at roughly 8–16 processors. Merits: minimal hardware, lowest cost, simple, supports broadcast. Demerits: bisection width 1, does not scale, single point of failure, arbitration latency.

(b) Crossbar

A grid placing a switch at every intersection of an input line and an output line, so any input can reach any output.

            M0      M1      M2      M3
             |       |       |       |
    P0 ------X-------X-------X-------X
             |       |       |       |
    P1 ------X-------X-------X-------X
             |       |       |       |
    P2 ------X-------X-------X-------X
             |       |       |       |
    P3 ------X-------X-------X-------X

    X = crosspoint switch.   N x N -> N^2 crosspoints.

To connect P_i to M_j, close the crosspoint at row i, column j. Since every pair has a dedicated crosspoint the crossbar is non-blocking — an existing connection never prevents a new one between two free endpoints. Contention arises only when two sources address the same destination, which is unavoidable in any network.

The cost problem. Crosspoints grow as N², so doubling ports quadruples hardware:

   N =    8  ->        64 crosspoints
   N =   16  ->       256
   N =   64  ->     4,096
   N =  256  ->    65,536
   N = 1024  -> 1,048,576   (over a million)

A 1024-port crossbar would need over a million crosspoints plus control logic, wiring, area and power — physically unroutable. Crossbars are therefore used only at small port counts: inside a switch chip, as a processor's internal fabric, or as the 2×2 building blocks of a multistage network. Merits: non-blocking, diameter 1, bisection N/2, uniform latency. Demerits: N² cost, high power and pin count, poor scalability.

(c) Multistage interconnection network — Omega

The engineering compromise between the two. Instead of one enormous switch, several stages of small switches, so cost grows as N log N rather than N². For N inputs, the Omega network has log₂N stages of N/2 switches of size 2×2, i.e. (N/2)·log₂N switching elements, joined by a fixed perfect shuffle permutation.

   8 x 8 OMEGA:  log2(8) = 3 stages, 8/2 = 4 switches per stage

        Stage 0        Stage 1        Stage 2
   0 --[ S ]--\    /--[ S ]--\    /--[ S ]-- 0
   1 --[   ]--  \/   [   ]--  \/   [   ]-- 1
                 \/            \/
   2 --[ S ]--  /\   [ S ]--  /\   [ S ]-- 2
   3 --[   ]--/    \--[   ]--/    \--[   ]-- 3
      ... lower half identical ...

   Total switches = (8/2) x 3 = 12    (a crossbar would need 64)
   Each [ S ] is a 2x2 switch: STRAIGHT or CROSS

Destination-tag routing. Write the destination in binary. At stage i, read bit i counting from the most significant: 0 → take the switch's upper output, 1 → take the lower output. After log₂N stages the message has arrived. No routing tables anywhere in the network — the address itself steers the message.

Worked example. Route to destination 5 in an 8×8 Omega. 5 = 101. Stage 0 reads 1 → lower. Stage 1 reads 0 → upper. Stage 2 reads 1 → lower. The message emerges at output 5.

Blocking. Exactly one path exists between any input and output, so two messages with entirely distinct sources and destinations may still need the same internal link and one must wait. This is the price of reducing cost from N² to (N/2)log₂N. Merits: N log N cost, many simultaneous transfers, self-routing, regular structure. Demerits: blocking, log₂N stages of latency, one path per pair so poor fault tolerance.

A4. The static topologies

Linear array

   0 --- 1 --- 2 --- 3 --- 4 --- 5

Degree 1–2; diameter N − 1; bisection 1; links N − 1. Cheapest possible, but diameter grows linearly.

Ring

        0 --- 1 --- 2
        |             |
        7             3
        |             |
        6 --- 5 --- 4

Degree 2; diameter ⌊N/2⌋; bisection 2; links N. One extra link halves the diameter and doubles bisection versus a linear array.

Mesh

   4 x 4 MESH                    Route 0 -> 15 (worst case):
   0 -- 1 -- 2 -- 3              0 -> 1 -> 2 -> 3 -> 7 -> 11 -> 15
   |    |    |    |              = 3 hops across + 3 hops down
   4 -- 5 -- 6 -- 7                = 6 hops = the diameter
   |    |    |    |
   8 -- 9 --10 --11              Diameter = 2(sqrt(N) - 1)
   |    |    |    |                       = 2(4 - 1) = 6
  12 --13 --14 --15

A √N × √N grid; interior nodes degree 4, edges 3, corners 2. Diameter 2(√N − 1); bisection √N; links 2(N − √N). Attractive because it maps directly onto a flat chip or board with short uniform wires, and its degree stays constant however large the machine grows.

Torus

   4 x 4 TORUS  (dotted links wrap around)

        .----.----.----.
        |    |    |    |
     ..-0 -- 1 -- 2 -- 3-..
        |    |    |    |
     ..-4 -- 5 -- 6 -- 7-..
        |    |    |    |
     ..-8 -- 9 --10 --11-..
        |    |    |    |
     ..12 --13 --14 --15-..
        |    |    |    |
        '----'----'----'

   Diameter  = 2 * floor(sqrt(N)/2) = 4     (was 6 in the mesh)
   Bisection = 2 * sqrt(N)          = 8     (was 4 in the mesh)

A mesh with wrap-around links on every row and column. Every node now has degree exactly 4 and the topology is fully symmetric — no edges or corners. Diameter 2·⌊√N/2⌋; bisection 2√N; links 2N. Adding wrap-around cuts the diameter by about a third and doubles bisection, which is why nearly all large supercomputers use a torus rather than a plain mesh.

Tree and fat tree

              (root)              A plain tree has bisection 1:
             /      \             cutting the single root link
          ( )        ( )          separates the two halves.
         /   \      /   \
        P0   P1    P2   P3        A FAT TREE makes links thicker
                                  nearer the root, restoring
                                  bisection bandwidth.

Diameter 2·log₂N; bisection 1 for a plain tree, whose root is a severe bottleneck. The fat tree corrects this by increasing link bandwidth at each level towards the root, and is the standard topology in data centres and InfiniBand clusters.

Hypercube

   n=1        n=2              n=3  (8 nodes, degree 3)

   0---1    00----01           110--------111
            |     |           /|          /|
            |     |        100--------101  |
            10----11         |  010------|-011
                             | /         | /
                            000--------001

   Neighbours differ in EXACTLY ONE BIT.
   000's neighbours: 001, 010, 100.

An n-dimensional cube with N = 2ⁿ nodes, n = log₂N. Each node carries an n-bit address, and two nodes are connected exactly when their addresses differ in one bit. Degree log₂N; diameter log₂N; bisection N/2; links (N·log₂N)/2. Outstanding diameter and bisection, but node degree grows with N, so enlarging the machine requires rewiring every node — the reason hypercubes lost favour at the very largest scales.

A5. The evaluation metrics

These goals conflict, and every topology is a particular compromise between them.

A6. Master comparison, and N = 16 worked out

For N nodes; mesh and torus as √N × √N grids; hypercube with n = log₂N.

Worked example — N = 16 (√N = 4, log₂N = 4). Always show the substitution:

4x4 MESH
  Degree    = 4 (interior), 3 (edge), 2 (corner)
  Diameter  = 2(sqrt(N) - 1)       = 2(4 - 1)  = 6
  Bisection = sqrt(N)              = 4
  Links     = 2(N - sqrt(N))       = 2(16 - 4) = 24

4x4 TORUS
  Degree    = 4 (uniform)
  Diameter  = 2 * floor(sqrt(N)/2) = 2 * 2     = 4
  Bisection = 2 * sqrt(N)          = 8
  Links     = 2N                   = 32

HYPERCUBE, n = log2(16) = 4
  Degree    = log2(N)              = 4
  Diameter  = log2(N)              = 4
  Bisection = N/2                  = 8
  Links     = N*log2(N)/2          = 32

A7. Hypercube XOR routing

EXAMPLE 1 — 3D hypercube, route 000 -> 111

   000 XOR 111 = 111    -> three 1s -> three hops
   Path A:  000 -> 001 -> 011 -> 111   (flip bit 0, 1, 2)
   Path B:  000 -> 100 -> 110 -> 111   (flip bit 2, 1, 0)
   Both valid, both 3 hops.

EXAMPLE 2 — 4D hypercube, route 0110 -> 1011

   0110 XOR 1011 = 1101 -> three 1s -> three hops
   Bits to flip: positions 0, 2 and 3
   0110 -> 0111 -> 0011 -> 1011
          (bit 0) (bit 2) (bit 3)

The algorithm needs no routing tables, no global knowledge and no computation beyond an XOR and a bit scan — every node routes independently from the destination address alone. Because the bits may be flipped in any order, there are as many shortest paths as there are orderings of the differing bits, which gives the hypercube excellent fault tolerance and natural load spreading.

A8. Where these appear in real systems

IBM's Blue Gene used a 3D and later 5D torus; Japan's Fugaku uses the 6D Tofu interconnect. Data centres are built almost universally on fat trees, because web and analytics workloads generate traffic that cannot be predicted in advance and therefore demand uniform bisection bandwidth.

Part B — Memory Hierarchy & Cache Coherence

B1. The memory wall

A core executes several instructions per nanosecond; main memory (DRAM) takes about 100 ns to answer. If the CPU waited for RAM on every access it would sit idle roughly 99% of the time. This widening gap between fast processors and slow memory is the memory wall. The remedy is a hierarchy of caches — a few tiny fast memories near the core, backed by progressively larger and slower ones.

If an L1 hit were 1 SECOND, then to human scale...

  L1 cache   1 second     (the pen in your hand)
  L2 cache   ~4 seconds   (the desk drawer)
  RAM        ~2 minutes   (the library downstairs)
  SSD read   over a DAY   (a book shipped from another city)

The CPU will do almost anything to avoid the long trips.

B2. The memory hierarchy

Each level acts as a cache for the level below. L1 to RAM is a 100× jump; RAM to SSD is another 1000×. Almost all performance engineering consists of turning misses into hits.

B3. Locality and the 64-byte cache line

Caches work only because real programs exhibit locality of reference:

• Temporal locality — if a location was used recently, it is likely to be used again soon.
• Spatial locality — if a location was used, nearby locations are likely to be used soon.

Hardware exploits spatial locality by moving memory in fixed blocks called cache lines, typically 64 bytes, never single bytes. This single fact explains both the row-major example below and false sharing in B8.

Worked example — two loops, one line swapped. Sum every element of a 4096×4096 matrix of doubles. Both loops perform exactly 16,777,216 additions.

A — row by row                    B — column by column
for (i = 0; i < N; i++)           for (j = 0; j < N; j++)
  for (j = 0; j < N; j++)           for (i = 0; i < N; i++)
    sum += a[i][j];                   sum += a[i][j];

Walks memory in a straight line.  Jumps 32 KB between accesses.
~40 ms                            ~400 ms   -> 10x SLOWER

WHY — entirely about the cache line.
A cache line is 64 bytes = 8 doubles. C stores a matrix ROW BY ROW.

LOOP A: reads a[0][0] -> miss, hardware fetches a[0][0..7] in one line
        reads a[0][1] -> HIT,  a[0][2] -> HIT ... a[0][7] -> HIT
        1 miss buys 8 useful values.       miss rate = 12.5%

LOOP B: reads a[0][0] -> miss, fetches a[0][0..7]  (uses ONE of them)
        reads a[1][0] -> miss, fetches a[1][0..7]  (uses ONE of them)
        every access is a new line, and by the time it returns to
        a[0][1] that line was evicted long ago.
        1 miss buys 1 useful value.        miss rate ~ 100%

Identical arithmetic, identical output, 10× difference in runtime. No profiler that counts operations can explain it. On modern hardware, where the data is beats how much work you do.

B4. AMAT — what one cache miss costs

Average Memory Access Time  =  hit time  +  (miss rate  x  miss penalty)

                            =    1 ns    +  (miss rate  x    80 ns   )

Varying only the hit rate, for a program making 1 billion memory accesses:

Losing four percentage points of hit rate — 99% down to 95% — makes the program 2.8× slower with identical code and identical instruction count. An algorithm doing twice the arithmetic with good locality will comfortably beat a "smarter" one that misses cache.

B5. The cache coherence problem

WATCH TWO CACHES DISAGREE       x lives in RAM, initial value 5

  Step  Action                  Core 1 cache  Core 2 cache  RAM
   1    Core 1 reads x               5              -         5
   2    Core 2 reads x               5              5         5
   3    Core 1 writes x = 42        42              5         5   <- C2 STALE
   4    Core 2 reads x               42             5         5   <- reads 5!

  Core 2 is not wrong to trust its cache — it has no way to know.
  Without a coherence protocol, step 4 silently returns the old value.

Note this is a hardware problem with a hardware solution, and it is invisible in the source code. It is also the reason shared-memory systems stop scaling: the machinery that keeps caches coherent generates traffic that grows with the number of cores.

B6. Coherence protocols: snooping vs directory

This is the same bus-versus-fabric trade-off as the interconnects in Part A, appearing one level down. Small chips snoop; big systems use directories.

B7. MESI — the four states

TRACE — two cores, one variable x

                                Core 1     Core 2
  1. Core 1 reads x               E          I
  2. Core 2 reads x               S          S
  3. Core 1 writes x = 42         M          I     <- invalidate!
  4. Core 2 reads x               S          S     <- coherence miss:
                                                      C1 writes back,
                                                      then both share

B8. False sharing

BAD  — both counters on the SAME cache line:
  struct { long a; long b; } counter;   // 8 bytes apart -> same line
  Thread 0 writes a -> invalidates Thread 1's line
  Thread 1 writes b -> invalidates Thread 0's line   ... forever.

GOOD — pad each onto its OWN line:
  struct Padded { long value; char pad[56]; };  // 8 + 56 = 64 bytes
  Padded counter[2];   // different lines — no invalidations

Measured effect: up to 20x slower in the bad version.

Why it is so hard to find: it is completely invisible in the source code, because the source code shares nothing. Two threads increment two separate variables — logically correct, apparently independent — and the program still slows down when you add threads.

Two fixes: (1) pad hot variables so each occupies its own cache line; (2) accumulate into a thread-local variable and write the shared result once — which is exactly what an OpenMP reduction does. Note the callback to Unit I: accumulate locally, combine once solves the race condition and false sharing, for two entirely different reasons.

B9. SMP vs AMP

SMP with a handful of fat, equal cores is one end of a spectrum; Part C pushes to the other end — thousands of tiny GPU cores — and asks why both exist.

Part C — Multicore Processors & GPUs

C1. Single-core → multicore → many-core

   Single-core          Multicore              Many-core (GPU)
   ---------            ---------              ---------------
   +-------+            +---++---+             +-+-+-+-+-+-+-+-+
   |       |            | C || C |             +-+-+-+-+-+-+-+-+
   |  ONE  |            +---++---+             +-+-+-+-+-+-+-+-+
   |  big  |            +---++---+             +-+-+-+-+-+-+-+-+
   | core  |            | C || C |             +-+-+-+-+-+-+-+-+
   +-------+            +---++---+             +-+-+-+-+-+-+-+-+
   1 fast core          4-16 fat cores         1000s of tiny cores
   latency              latency, but wider     pure throughput

• Single-core (until ~2005) — one core, one instruction stream. Ended at the power wall (Unit I).
• Multicore (~2005 onwards) — a few full, powerful cores: 4, 8, 16. Your laptop. MIMD.
• Many-core (GPU) — thousands of simple cores. Weak individually, formidable together. SIMT.

C2. Homogeneous vs heterogeneous multicore

Heterogeneous designs dominate wherever energy matters — every smartphone is heterogeneous — and increasingly in servers too, since a GPU-equipped node is by definition heterogeneous.

C3. CPU vs GPU: two philosophies of "fast"

A CPU is optimised for latency: a few powerful cores with big caches and branch prediction, spending silicon on being smart so one thread finishes as fast as possible. A GPU is optimised for throughput: thousands of simple cores with enormous bandwidth, spending silicon on being wide so a million tasks finish per second.

C4. SIMT and warps

SIMT is how a GPU obtains SIMD efficiency while letting the programmer write ordinary-looking scalar code for a single thread. The hardware schedules warps, and when one warp stalls on memory another is swapped in — which is how a GPU hides latency without the large caches a CPU needs.

C5. Warp divergence

If the 32 threads of a warp reach an if/else and want to take different paths, they cannot — the warp shares one instruction stream. The hardware therefore serialises the branch, running each path in turn with the non-participating threads idle.

Warp hits an if/else — threads diverge

  Step 1: run doA()     T0  __  T2  __  T4  __  ...   (odd threads idle)
  Step 2: run doB()     __  T1  __  T3  __  T5  ...   (even threads idle)

  Both paths run one after the other -> up to 2x slower, half wasted.
  Instead of 32 threads working, you get 16, then 16.

Warp divergence is a leading reason real GPU code falls short of peak performance, and it worsens with nested branches. The lesson: keep threads within a warp doing the same thing. Branchy, decision-heavy code belongs on the CPU. Note the contrast — the same if costs a CPU almost nothing, because a CPU core runs one thread and simply predicts the branch.

C6. Memory bandwidth, arithmetic intensity and the roofline

A GPU's thousands of arithmetic units are useless if they cannot be fed. Its real advantage is memory bandwidth — roughly 30× a CPU's. Performance is capped by whichever ceiling is reached first:

• Compute ceiling — how many operations per second the chip can perform.
• Bandwidth ceiling — how fast it can move data in and out of memory.

Arithmetic intensity is operations performed per byte moved. The ridge point of the roofline is where the two ceilings meet:

                  peak compute      60,000 GFLOP/s
   ridge point =  --------------  =  --------------  =  20 FLOPs per byte
                 peak bandwidth       3,000 GB/s

    GFLOP/s
    60,000 |            ...............................   <-- compute roof
           |          /   :
           |        /     :  above 20: COMPUTE bound
           |      /       :  below 20: MEMORY bound (starved)
           |    /         :
         0 +------------------------------------------
           0.1     1     20      100    1000   FLOPs/byte
                       ^ ridge

A vector add on a 60-teraflop GPU achieves 0.4% of the machine, and every one of these kernels is perfectly parallel. Buying a GPU twice as fast at arithmetic would take that figure to 0.2%. You cannot optimise your way out of a bandwidth limit by adding compute.

C7. When the GPU wins, and when it loses

Worked example. Two jobs, both perfectly parallel. Same GPU, same data volume, same 32 ms of PCIe transfer.

One job loses by 2×, the other wins by 51×. The difference is not parallelism — both are perfectly parallel. It is arithmetic intensity: vector add does 0.08 operations per byte moved, matrix multiply does 32.

Quick recall

Mesh      diameter 2(sqrt(N)-1)   bisection sqrt(N)   links 2(N-sqrt(N))
Torus     diameter 2*floor(sqrt(N)/2)  bisection 2*sqrt(N)  links 2N
Hypercube degree/diameter log2(N)  bisection N/2   links N*log2(N)/2
Ring      diameter floor(N/2)      bisection 2     links N
Crossbar  N^2 crosspoints          Omega  (N/2)*log2(N) switches, log2(N) stages
Hypercube hops = number of 1s in (src XOR dst)  = Hamming distance

AMAT      = hit time + (miss rate x miss penalty)
Cache line = 64 bytes = 8 doubles
Ridge point = peak compute / peak bandwidth   (FLOPs per byte)
Warp = 32 threads

Self-check

Answer each out loud before opening it.