Instruction-level vs thread-level parallelism

Overview

Two fundamentally different approaches to parallel execution: exploiting instruction-level paralelism (ILP) within a single instruction stream versus thread-level parallelism (TLP) across multiple independent instruction streams. Understanding the distinction is critical for hardware design and software optimization. (Note: SIMD / vector processing is a third, separate category — data-level parallelism — and should not be confused with either ILP or TLP.)

How: Hardware examines instruction dependencies and executes non-dependent instructions in parallel within the same program flow.

Key mechanisms:

• Pipelining: Overlapping execution stages (fetch, decode, execute, memory, writeback)
• Superscalar execution: Multiple instructions issued per cycle
• Out-of-order execution: Reordering instructions to avoid stalls
• Speculative execution: Predicting branches and executing ahead

Scope: Typically 2-6 instructions per cycle (IPC) due to dependency chains

Not ILP: SIMD/vector instructions (one instruction operating on many data elements) are data-level parallelism, a distinct category. A single SIMD instruction still counts as one instruction in the pipeline.

How: Hardware provides multiple execution contexts (cores, hardware threads) that run different programs or different parts of the same program.

Key mechanisms:

• Multicore processors: Multiple complete CPU cores on one chip
• Simultaneous Multithreading (SMT): Multiple threads share one core's execution units
• Hardware multithreading: Switching between threads to hide latency

Scope: Can scale to dozens or hundreds of cores

Why it's separate: SIMD is neither ILP (it's one instruction, not many independent ones) nor TLP (it's one thread, not many). It is orthogonal and can combine with both. Keeping these three categories distinct avoids a very common conceptual error.

Core Differences: The Fundamental Tradeoffs

ILP Speedup (within single thread): $S_{ILP} = \frac{1}{(1-f) + \frac{f}{n}}$

Where:

• $f$ = fraction of code that can be paralelized (instruction independence)
• $n$ = average instructions executed per cycle (IPC)

Why this formula? It's Amdahl's Law applied to instruction streams. The $(1-f)$ term represents serial dependencies (data hazards, control dependencies) that cannot be paralelized. The $\frac{f}{n}$ term represents the paralelizable portion divided by how many instructions we execute simultaneously.

Derivation from first principles:

1. Start with execution time: $T = T_{serial} + T_{parallel}$

2. Express in terms of total instructions $I$:

   • Serial portion: $(1-f) \cdot I$ instructions (must execute sequentially)
   • Parallel portion: $f \cdot I$ instructions (can execute simultaneously)

3. With ILP factor $n$ (instructions per cycle):

   • Serial time: $(1-f) \cdot I$ cycles (1 instruction/cycle for dependencies)
   • Parallel time: $\frac{f \cdot I}{n}$ cycles (n instructions/cycle when independent)

4. Total time with ILP: $T_{ILP} = (1-f) \cdot I + \frac{f \cdot I}{n}$

5. Speedup: $S_{ILP} = \frac{T_{original}}{T_{ILP}} = \frac{I}{(1-f) \cdot I + \frac{f \cdot I}{n}} = \frac{1}{(1-f) + \frac{f}{n}}$

TLP Speedup (multiple threads): $S_{TLP} = \frac{1}{(1-p) + \frac{p}{N}}$

Where:

• $p$ = fraction of program that can be parallelized across threads
• $N$ = number of cores/threads

Why this formula? This is also Amdahl's Law, but now $p$ represents algorithmic parallelism (can the problem be divided?), not instruction-level independence. The $(1-p)$ term is inherently sequential work (like initialization, final reduction). The $\frac{p}{N}$ term is paralelizable work divided across $N$ processors.

Key insight: ILP typically has $f \approx 0.7-0.9$ with $n \approx 2-4$, giving speedup around 1.5-3×. TLP can have $p \approx 0.95+$ with $N \approx 16-64$, potentially yielding 10-50× speedup for embarrassingly parallel workloads.

Scenario: Apply a blur filter to a 1920×1080 image (2.07 million pixels).

ILP Approach (single-threaded):

for each pixel (i):
    load neighbors[i-1], neighbors[i], neighbors[i+1]
    sum = neighbors[i-1] + neighbors[i] + neighbors[i+1]
    result[i] = sum / 3

Why these instructions show ILP:

• Iteration $i$ and $i+1$ have no data dependency (operate on different pixels)
• A superscalar processor can:
  • Load neighbors for pixel $i$
  • While simultaneously loading neighbors for pixel $i+1$
  • While computing sum for pixel $i-1$ (already loaded)

ILP speedup calculation:

• Assume 70% of instructions are independent ($f = 0.7$)
• 4-wide superscalar processor ($n = 4$)
• $S_{ILP} = \frac{1}{0.3 + \frac{0.7}{4}} = \frac{1}{0.3 + 0.175} = 2.11×$

TLP Approach (multi-threaded):

Divide image into 8 horizontal strips (one per core)
Each core processes its strip independently
No synchronization needed (embarrassingly parallel)

Why this works for TLP:

• Each strip is completely independent
• No shared data between threads
• Linear speedup possible

TLP speedup calculation:

• 99% paralelizable ($p = 0.99$, only 1% for thread spawn/join)
• 8 cores ($N = 8$)
• $S_{TLP} = \frac{1}{0.01 + \frac{0.99}{8}} = \frac{1}{0.01 + 0.124} = 7.46×$

Combined: Using both ILP and TLP: $2.11 × 7.46 = 15.7×$ total speedup!

Scenario: Sum values in a linked list of 10,000 nodes.

ILP Challenge:

Node* current = head;
int sum = 0;
while (current != nullptr) {
    sum += current->value;      // Load dependency!
    current = current->next;    // Pointer chasing!
}

Why ILP fails here:

• Load-to-use dependency: Must load current->value before adding to sum
• Pointer chasing: Cannot load current->next->value until current->next is loaded
• Each iteration depends on previous: serial dependency chain

Calculation:

• Only 10% paralelizable due to dependencies ($f = 0.1$)
• Even with 4-wide superscalar ($n = 4$):
• $S_{ILP} = \frac{1}{0.9 + \frac{0.1}{4}} = \frac{1}{0.925} = 1.08×$ (barely any speedup!)

TLP Challenge:

• Cannot easily partition linked list (must traverse to find middle)
• Even if partitioned, poor cache locality (different threads thrash cache)
• Algorithm is inherently serial

TLP attempt:

• Best case: partition during construction into 8 sub-lists
• Each thread sums its sub-list, then combine results
• $p = 0.8$ (20% overhead for partitioning + combining)
• $S_{TLP} = \frac{1}{0.2 + \frac{0.8}{8}} = \frac{1}{0.3} = 3.33×$

Lesson: Data structure choice dramatically affects parallelism potential. Arrays enable both ILP and TLP; linked lists resist both.

Scenario: Multiply two 1000×1000 matrices ($A \times B = C$).

ILP inner loop:

for i in rows:
    for j in cols:
        sum = 0
        for k in range(1000):
            sum += A[i][k] * B[k][j]  // Each k iteration is independent!
        C[i][j] = sum

Why ILP applies here:

• Multiply-add operations for different $k$ values are independent
• A superscalar core can issue several independent multiply-adds per cycle
• Multiple accumulators break the reduction dependency chain, exposing more ILP

ILP speedup: ~2-3× from overlapping independent multiply-adds

DLP (SIMD) bonus — separate category:

• Fused multiply-add (FMA) executed via SIMD vector instructions processes 8 floats per 256-bit register
• This is data-level parallelism, not ILP — one SIMD instruction, many data elements
• Adds another ~8× on top, orthogonal to ILP

TLP paralelization:

Assign rows to different threads
Thread 1: computes rows 0-124
Thread 2: computes rows 125-249
...
Thread 8: computes rows 875-999

Why TLP excels:

• Each row computation is completely independent
• No synchronization needed
• $p = 0.999$ (virtually perfect parallelism)

TLP speedup: $S_{TLP} = \frac{1}{0.001 + \frac{0.999}{8}} = 7.94×$ (near-linear on 8 cores)

Combined (ILP × DLP × TLP): roughly $3 × 8 × 7.94 \approx 190×$ — showing all three categories stack multiplicatively.

Key Architectural Differences

Note: SIMD vectorization (data-level parallelism) is exposed either automatically by the compiler (auto-vectorization) or via intrinsics/annotations — it belongs to neither the ILP nor TLP column above.

The Wrong Idea: "Just throw more cores at it—TLP is always better than ILP."

Why It Feels Right:

• Marketing emphasizes core counts
• Some workloads (servers, rendering) scale beautifully with cores
• ILP improvements have diminishing returns

The Reality Check: For single-threaded workloads (still common in many applications):

• A 4-core CPU at 4.0 GHz with 4-wide ILP: strong per-program throughput
• An 8-core CPU at 2.0 GHz with 2-wide ILP: weak per-program throughput

The Fix: Amdahl's Law dominates: If your code has 50% serial portion, 8 cores give only 1.78× speedup, no matter how many cores you add. A single faster core with better ILP wins.

When to prioritize what:

• ILP (fewer, faster cores): Gaming, office apps, web browsing (single-thread bottlenecks)
• TLP (more, simpler cores): Servers, scientific computing, video encoding (parallel workloads)
• Both (+ SIMD): Modern CPUs balance all three (e.g., 8 cores, 4-6 wide ILP each, with SIMD units)

The Wrong Idea: "Vector instructions execute lots of work per cycle, so that's instruction-level parallelism."

Why It Feels Right:

• SIMD does increase throughput per cycle
• It happens within a single thread, like ILP
• Both live inside one core

The Reality Check:

• ILP = multiple independent instructions executing together (needs several distinct ops)
• SIMD = one instruction operating on multiple data elements (data-level parallelism)
• A single VFMADD (vector FMA) is one instruction in the pipeline — it doesn't raise IPC by issuing more instructions; it raises data throughput per instruction.

The Fix: Keep three orthogonal buckets: ILP (many independent instructions), DLP/SIMD (one instruction, many data), TLP (many threads). They multiply together but are measured and enabled differently.

The Wrong Idea: "The CPU handles ILP automatically, so I'll always get the speedup."

Why It Feels Right:

• Out-of-order execution is transparent
• Don't need to rewrite code

The Reality Check:

// Poor ILP (each iteration depends on previous)
int sum = 0;
for (int i = 0; i < n; i++) {
    sum = sum + array[i];  // Cannot start iteration+1 until i completes!
}
 
// Better ILP (multiple independent accumulators)
int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
for (int i = 0; i < n; i += 4) {
    sum1 += array[i];      // All four can execute in parallel!
    sum2 += array[i+1];
    sum3 += array[i+2];
    sum4 += array[i+3];
}
int sum = sum1 + sum2 + sum3 + sum4;

Measured speedup: 3.2× on modern CPU (from breaking dependency chain).

The Fix:

• Understand data dependencies: Hardware can't violate program semantics
• Loop unrolling and multiple accumulators expose ILP to hardware
• Branch prediction: Avoid unpredictable branches (use branchless techniques)

ILP is like doing your math homework faster by having all your supplies ready. While you're writing one answer, you're already thinking about the next problem in your head. You're reading the third problem while your hand is still writing problem two. One person (you), but doing multiple steps of the SAME homework at once. But you can only do this if the problems don't depend on each other—you can't solve problem 5 if it says "use your answer from problem 4."

SIMD is like a special stamp that fills in the same kind of answer on 8 worksheets at once with a single press — one action, many results.

TLP is like you and your three friends each doing a different subject's homework at the same table. You do math, friend 1 does English, friend 2 does science, friend 3 does history. You're all working at the same time on DIFFERENT homeworks. You can work much faster as a group! But if the math homework has 20 problems and only you can do math, your friends can't help—they're stuck waiting.

The computer's choice: Should I make one student super-smart and fast (ILP), give them a magic stamp (SIMD), or get more students to work together (TLP)? Best answer: all three!

Picture: ILP is a chef juggling many different tasks. SIMD is a chef with one giant knife slicing 8 carrots in one chop. TLP is many chefs, each at their own station.

Connections

• Pipelining-Hazards — ILP's main challenge: resolving data, control, and structural hazards
• Superscalar-Architecture — Hardware implementation of ILP
• Cache-Coherence-Protocols — Required for TLP correctness (MESI, MOESI)
• Amdahls-Law — Theoretical limit for both ILP and TLP speedup
• Simultaneous-Multithreading — Hybrid: TLP within a single core's execution units
• SIMD-Vector-Processing — Data-level parallelism (distinct from both ILP and TLP)
• Memory-Level-Parallelism — Paralelizing memory accesses, bridges ILP and TLP
• Task-Scheduling-Algorithms — OS role in exploiting TLP
• Power-Performance-Tradeoffs — Why many simple cores can beat few complex cores

#flashcards/hardware

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)