Instruction-level vs thread-level parallelism

6.1.2 · Hardware › Parallelism & Multicore

Overview

Do fundamentally alag approaches hain parallel execution ke liye: ek single instruction stream ke andar instruction-level parallelism (ILP) exploit karna, versus multiple independent instruction streams mein thread-level parallelism (TLP). Yeh distinction hardware design aur software optimization dono ke liye critical hai. (Note: SIMD / vector processing ek teesri, alag category hai — data-level parallelism — aur ise ILP ya TLP kisi se bhi confuse nahi karna chahiye.)

Kaise: Hardware instruction dependencies examine karta hai aur non-dependent instructions ko same program flow ke andar parallel mein execute karta hai.

Key mechanisms:

• Pipelining: Execution stages ko overlap karna (fetch, decode, execute, memory, writeback)
• Superscalar execution: Ek cycle mein multiple instructions issue karna
• Out-of-order execution: Stalls avoid karne ke liye instructions reorder karna
• Speculative execution: Branches predict karke aage execute karna

Scope: Dependency chains ki wajah se typically 2-6 instructions per cycle (IPC)

ILP nahi hai: SIMD/vector instructions (ek instruction jo kai data elements par operate kare) data-level parallelism hai, ek alag category. Ek single SIMD instruction pipeline mein ek hi instruction count hoti hai.

Kaise: Hardware multiple execution contexts (cores, hardware threads) provide karta hai jo alag programs ya same program ke alag parts run karte hain.

Key mechanisms:

• Multicore processors: Ek chip par multiple complete CPU cores
• Simultaneous Multithreading (SMT): Multiple threads ek core ke execution units share karte hain
• Hardware multithreading: Latency hide karne ke liye threads ke beech switch karna

Scope: Dozens ya hundreds of cores tak scale ho sakta hai

Alag kyun hai: SIMD na ILP hai (yeh ek instruction hai, kai independent nahi) na TLP (yeh ek thread hai, kai nahi). Yeh orthogonal hai aur dono ke saath combine ho sakta hai. Teeno categories alag rakhna ek bahut common conceptual error se bachata hai.

Core Differences: Fundamental Tradeoffs

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

Jahaan:

• $f$ = code ka woh fraction jo parallelize ho sakta hai (instruction independence)
• $n$ = average instructions executed per cycle (IPC)

Yeh formula kyun? Yeh Amdahl's Law hai jo instruction streams par apply ki gayi hai. $(1-f)$ term serial dependencies (data hazards, control dependencies) represent karta hai jo parallelize nahi ho sakti. $\frac{f}{n}$ term parallelizable portion ko represent karta hai divided by kitni instructions hum simultaneously execute karte hain.

First principles se derivation:

1. Execution time se shuru karo: $T=T_{serial}+T_{parallel}$

2. Total instructions $I$ ke terms mein express karo:

   • Serial portion: $(1-f)\cdot I$ instructions (sequentially execute honi chahiye)
   • Parallel portion: $f\cdot I$ instructions (simultaneously execute ho sakti hain)

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

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

4. ILP ke saath total time: $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}}$

Jahaan:

• $p$ = program ka woh fraction jo threads mein parallelize ho sakta hai
• $N$ = cores/threads ki sankhya

Yeh formula kyun? Yeh bhi Amdahl's Law hai, lekin ab $p$ algorithmic parallelism represent karta hai (kya problem divide ho sakti hai?), instruction-level independence nahi. $(1-p)$ term inherently sequential kaam hai (jaise initialization, final reduction). $\frac{p}{N}$ term parallelizable kaam hai jo $N$ processors mein divide hota hai.

Key insight: ILP mein typically $f\approx 0.7-0.9$ aur $n\approx 2-4$ hota hai, jo speedup around 1.5-3× deta hai. TLP mein $p\approx 0.95+$ aur $N\approx 16-64$ ho sakta hai, embarrassingly parallel workloads ke liye potentially 10-50× speedup.

Scenario: 1920×1080 image (2.07 million pixels) par blur filter apply karo.

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

Yeh instructions ILP kyun dikhate hain:

• Iteration $i$ aur $i+1$ ka koi data dependency nahi (alag pixels par operate karte hain)
• Ek superscalar processor kar sakta hai:
  • Pixel $i$ ke liye neighbors load karo
  • Saath hi pixel $i+1$ ke liye neighbors load karo
  • Saath hi pixel $i-1$ ka sum compute karo (pehle se loaded)

ILP speedup calculation:

• Maano 70% instructions independent hain ($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\times$

TLP Approach (multi-threaded):

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

TLP ke liye yeh kyun kaam karta hai:

• Har strip bilkul independent hai
• Threads ke beech koi shared data nahi
• Linear speedup possible hai

TLP speedup calculation:

• 99% parallelizable ($p=0.99$, sirf 1% thread spawn/join ke liye)
• 8 cores ($N=8$)
• $S_{TLP}=\frac{1}{0.01+\frac{0.99}{8}}=\frac{1}{0.01+0.124}=7.46\times$

Combined: ILP aur TLP dono use karke: $2.11\times 7.46=15.7\times$ total speedup!

Scenario: 10,000 nodes ki linked list mein values sum karo.

ILP Challenge:

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

ILP yahaan kyun fail hoti hai:

• Load-to-use dependency: Sum mein add karne se pehle current->value load karna zaroori hai
• Pointer chasing: current->next->value tab tak load nahi ho sakta jab tak current->next load na ho
• Har iteration pichli par depend karti hai: serial dependency chain

Calculation:

• Dependencies ki wajah se sirf 10% parallelizable ($f=0.1$)
• 4-wide superscalar ke saath bhi ($n=4$):
• $S_{ILP}=\frac{1}{0.9+\frac{0.1}{4}}=\frac{1}{0.925}=1.08\times$ (naa ke barabar speedup!)

TLP Challenge:

• Linked list easily partition nahi ho sakti (middle dhundhne ke liye traverse karna padta hai)
• Partition bhi ho jaye to poor cache locality (alag threads cache thrash karte hain)
• Algorithm inherently serial hai

TLP attempt:

• Best case: construction ke dauran 8 sub-lists mein partition karo
• Har thread apni sub-list sum kare, phir results combine karo
• $p=0.8$ (20% overhead partitioning + combining ke liye)
• $S_{TLP}=\frac{1}{0.2+\frac{0.8}{8}}=\frac{1}{0.3}=3.33\times$

Lesson: Data structure choice parallelism potential ko dramatically affect karti hai. Arrays dono ILP aur TLP enable karte hain; linked lists dono resist karte hain.

Scenario: Do 1000×1000 matrices multiply karo ($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

ILP yahaan kyun apply hoti hai:

• Alag $k$ values ke liye multiply-add operations independent hain
• Ek superscalar core ek cycle mein kai independent multiply-adds issue kar sakta hai
• Multiple accumulators reduction dependency chain tod dete hain, zyada ILP expose karte hain

ILP speedup: Independent multiply-adds overlap karne se ~2-3×

DLP (SIMD) bonus — alag category:

• Fused multiply-add (FMA) ko SIMD vector instructions ke zariye execute karna ek 256-bit register mein 8 floats process karta hai
• Yeh data-level parallelism hai, ILP nahi — ek SIMD instruction, kai data elements
• Ek aur ~8× add hota hai, ILP se orthogonal

TLP parallelization:

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

TLP kyun excel karta hai:

• Har row computation bilkul independent hai
• Koi synchronization ki zaroorat nahi
• $p=0.999$ (virtually perfect parallelism)

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

Combined (ILP × DLP × TLP): roughly $3\times 8\times 7.94\approx 190\times$ — yeh dikhata hai ki teeno categories multiplicatively stack hoti hain.

Key Architectural Differences

Note: SIMD vectorization (data-level parallelism) ya to compiler automatically expose karta hai (auto-vectorization) ya intrinsics/annotations se — yeh upar ke ILP ya TLP column mein se kisi mein nahi aata.

Galat Idea: "Bas zyada cores lagao — TLP hamesha ILP se behtar hai."

Kyun Sahi Lagta Hai:

• Marketing core counts emphasize karti hai
• Kuch workloads (servers, rendering) cores ke saath beautifully scale karte hain
• ILP improvements ke diminishing returns hote hain

Reality Check: Single-threaded workloads ke liye (abhi bhi kai applications mein common):

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

Fix: Amdahl's Law dominate karta hai: Agar code mein 50% serial portion hai, to 8 cores sirf 1.78× speedup denge, chahe kitne bhi zyada cores lagao. Ek akela faster core better ILP ke saath jeet jaata hai.

Kab kya prioritize karo:

• ILP (kam, faster cores): Gaming, office apps, web browsing (single-thread bottlenecks)
• TLP (zyada, simpler cores): Servers, scientific computing, video encoding (parallel workloads)
• Dono (+ SIMD): Modern CPUs teeno balance karte hain (e.g., 8 cores, 4-6 wide ILP each, with SIMD units)

Galat Idea: "Vector instructions ek cycle mein bahut kaam karte hain, to yeh instruction-level parallelism hai."

Kyun Sahi Lagta Hai:

• SIMD does throughput per cycle increase karta hai
• Yeh ek single thread ke andar hota hai, jaise ILP
• Dono ek core ke andar rehte hain

Reality Check:

• ILP = multiple independent instructions ek saath execute hona (kai distinct ops chahiye)
• SIMD = ek instruction jo multiple data elements par operate kare (data-level parallelism)
• Ek single VFMADD (vector FMA) pipeline mein ek instruction hai — yeh zyada instructions issue karke IPC nahi badhata; yeh data throughput per instruction badhata hai.

Fix: Teeno orthogonal buckets rakh: ILP (kai independent instructions), DLP/SIMD (ek instruction, kai data), TLP (kai threads). Yeh ek saath multiply karte hain lekin alag measure aur enable hote hain.

Galat Idea: "CPU ILP automatically handle karta hai, to mujhe hamesha speedup milegi."

Kyun Sahi Lagta Hai:

• Out-of-order execution transparent hai
• Code rewrite karne ki zaroorat nahi

Reality Check:

// Poor ILP (har iteration pichli par depend karti hai)
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: Modern CPU par 3.2× (dependency chain todne se).

Fix:

• Data dependencies samjho: Hardware program semantics violate nahi kar sakta
• Loop unrolling aur multiple accumulators hardware ko ILP expose karte hain
• Branch prediction: Unpredictable branches avoid karo (branchless techniques use karo)

ILP aise hai jaise apna math homework jaldi karo — sab supplies ready rakh. Jab ek answer likh rahe ho, agla problem pehle se dimag mein soch lo. Teesra problem padh rahe ho jab haath abhi doosra likh raha hai. Ek insaan (tum), lekin EEEK homework ke kai steps ek saath. Lekin yeh tabhi ho sakta hai jab problems ek doosre par depend na karein — problem 5 tab tak solve nahi kar sakte jab tak problem 4 ka answer na aaye.

SIMD ek special stamp ki tarah hai jo ek baar press mein 8 worksheets par ek jaisi answer fill kar deta hai — ek kaam, kai results.

TLP aise hai jaise tum aur teeno dost ek table par alag alag subjects ka homework karo — tum math, dost 1 English, dost 2 science, dost 3 history. Sab ek saath ALAG homework par kaam kar rahe hain. Group mein bahut jaldi hota hai! Lekin agar math homework mein 20 problems hain aur sirf tum math kar sakte ho, dost madad nahi kar sakte — woh ruk ke wait karte hain.

Computer ki choice: Ek student ko super-smart aur fast banao (ILP), use magic stamp do (SIMD), ya zyada students milke kaam karein (TLP)? Best answer: teeno!

Picture: ILP ek chef hai jo kai alag kaam juggle karta hai. SIMD ek chef hai jiske paas ek giant knife hai jo ek baar mein 8 gaajaren kaat deta hai. TLP kai chefs hain, har ek apne station par.

Connections

• Pipelining-Hazards — ILP ki main challenge: data, control, aur structural hazards resolve karna
• Superscalar-Architecture — ILP ka hardware implementation
• Cache-Coherence-Protocols — TLP correctness ke liye zaroori (MESI, MOESI)
• Amdahls-Law — ILP aur TLP dono speedup ki theoretical limit
• Simultaneous-Multithreading — Hybrid: ek single core ke execution units ke andar TLP
• SIMD-Vector-Processing — Data-level parallelism (ILP aur TLP dono se alag)
• Memory-Level-Parallelism — Memory accesses parallelize karna, ILP aur TLP ke beech bridge
• Task-Scheduling-Algorithms — TLP exploit karne mein OS ka role
• Power-Performance-Tradeoffs — Kyun kai simple cores kuch complex cores ko beat kar sakte hain

#flashcards/hardware

Concept Map