Heterogeneous computing concepts

What Makes Computing "Heterogeneous"?

Key characteristics:

1. Different processor types (CPU + GPU, CPU + FPGA, CPU + DSP, etc.)
2. Asymetric capabilities (not just different speeds, but different strengths)
3. Task partitioning (dividing work based on processor strengths)
4. Explicit data movement between processor memories (often the bottleneck)

WHAT distinguishes it from homogeneous multicore?

• Homogeneous:8 identical CPU cores, all run same instruction set
• Heterogeneous: 4 CPU cores + 1 GPU with2048 CUDA cores + 1 Neural Processing Unit

The Hardware Architecture

CPU: The Control Master

Design philosophy: Optimize for latency of individual tasks

HOW it achieves this:

• Large caches (MB range) → reduce memory access time
• Complex out-of-order execution → hide instruction dependencies
• Branch prediction → speculate on control flow
• Few powerful cores (4-64 typically)

Best for:

• Sequential algorithms
• Irregular memory access patterns
• Complex control flow (many if/else, function calls)
• Operating system tasks, coordination

GPU: The Throughput Engine

Design philosophy: Optimize for throughput of many parallel tasks

HOW it achieves this:

• Thousands of simple cores (ALUs)
• Small caches per core
• SIMT execution model (Single Instruction, Multiple Threads)
• Massive memory bandwidth (hundreds of GB/s)

Best for:

• Data-parallel operations (same operation on millions of data points)
• Regular memory access patterns (coalesced reads/writes)
• Graphics rendering, matrix operations, simulations

Specialized Accelerators

Accelerators are fixed-function or configurable hardware designed for one class of problems.

Types:

1. TPU (Tensor Processing Unit): Matrix multiply-accumulate operations for neural networks
2. FPGA (Field-Programmable Gate Array): Reconfigurable logic blocks for custom datapaths
3. DSP (Digital Signal Processor): Optimized for filtering, FFT, convolution
4. Crypto accelerators: AES encryption, SHA hashing

WHY they exist: For narrow domains, hardwired logic is 10-100x more energy-efficient than general-purpose cores.

The Programming Model Challenge

Memory Hierarchy Mismatch

Total execution time: $T_{total} = T_{CPU \rightarrow GPU} + T_{compute\_GPU} + T_{GPU \rightarrow CPU}$

WHY this matters: If $T_{compute\_GPU}$ is small, data transfer dominates!

Derivation of the break-even point:

Let:

• $B$ = PCIe bandwidth (GB/s)
• $D$ = data size (GB)
• $F_{CPU}$ = CPU FLOPS
• $F_{GPU}$ = GPU FLOPS
• $W$ = work (total FLOPS needed)

Time on CPU alone: $T_{CPU} = \frac{W}{F_{CPU}}$

Time on heterogeneous system: $T_{hetero} = \frac{2D}{B} + \frac{W}{F_{GPU}}$

(Factor of 2 because data goes CPU→GPU→CPU)

Break-even when $T_{hetero} < T_{CPU}$: $\frac{2D}{B} + \frac{W}{F_{GPU}} < \frac{W}{F_{CPU}}$

$\frac{2D}{B} < W \left(\frac{1}{F_{CPU}} - \frac{1}{F_{GPU}}\right)$

WHY THIS STEP? We isolate the data movement cost on the left. The right side is the computational advantage of GPU.

$W > \frac{2D \cdot F_{CPU} \cdot F_{GPU}}{B(F_{GPU} - F_{CPU})}$

Interpretation: You need enough work (W) relative to data size (D) to overcome transfer overhead. This is called arithmetic intensity.

Transfer1 GB of data: $T_{transfer} = \frac{2 \times 1}{32} = 0.0625 \text{ seconds}$

To break even, GPU compute time must save at least 0.0625s:

Work needed: $W > \frac{2 \times 1 \times 10}{32(10-1)} = \frac{20}{288} \approx 0.069 \text{ TFLOPS}$

$W > 69 \text{ GFLOPS}$

WHY? If the task requires 69 billion floating-point operations, GPU saves enough time to justify the transfer cost.

Arithmetic intensity: $\frac{W}{D} = \frac{69 \text{ GFLOPS}}{1 \text{ GB}} = 69 \text{ FLOP/byte}$

Practical insight: Matrix-matrix multiply (O(n³) work, O(n²) data) is great for GPUs. Vector addition (O(n) work, O(n) data) is terrible.

Task Partitioning Strategies

Three models:

1. Offload model: CPU does setup/control, GPU does compute kernels, CPU does post-processing
2. Pipelined model: CPU stage 1 → GPU stage 2 → CPU stage 3, overlapping different data
3. Collaborative model: CPU and GPU work on different parts of the same problem simultaneously

Step-by-step with WHY:

1. CPU reads image1 from disk → CPU has file system access
2. CPU transfers image 1 to GPU → GPU needs data in VRAM
3. GPU applies filters to image 1 → Massively parallel pixel operations
4. CPU reads image 2 (overlapped with step 3) → Hide transfer latency
5. GPU returns processed image 1to CPU → CPU will write to disk
6. CPU writes image 1 to disk (overlapped with GPU processing image 2)

WHY pipelined? Each stage overlaps with others. Total time ≈ max(read, transfer, compute, write) ×1000, not their sum.

Formula for pipeline efficiency:

If stages take time $t_1, t_2, .., t_k$ and we process $n$ items:

Sequential time: $n \times (t_1 + t_2 + ... + t_k)$

Pipelined time: $(t_1 + t_2 + ... + t_k) + (n-1) \times \max(t_1, .., t_k)$

WHY? First item pays full latency, then we sustain at the rate of the slowest stage.

Speedup: $S = \frac{n \times \sum t_i}{(\sum t_i) + (n-1) \times \max(t_i)} \approx \frac{\sum t_i}{\max(t_i)} \text{ as } n \rightarrow \infty$

Amdahl's Law in Heterogeneous Systems

Original Amdahl's Law assumes homogeneous speedup. We need to extend it.

Let:

• $f_s$ = fraction of code that's serial (CPU-only)
• $f_p$ = fraction that's paralelizable (can use GPU)
• $S_{GPU}$ = speedup of GPU over CPU for parallel work
• $f_s + f_p = 1$

Derivation from scratch:

Original execution time (CPU only): $T_0 = 1$ (normalized)

New execution time:

• Serial part: $f_s \times 1 = f_s$ (no speedup)
• Parallel part: $\frac{f_p}{S_{GPU}}$ (runs $S_{GPU}$ times faster)
• Data transfer overhead: $t_{xfer}$ per kernel launch

$T_{hetero} = f_s + \frac{f_p}{S_{GPU}} + t_{xfer}$

WHY THIS STEP? Serial work is unaffected. Parallel work benefits from GPU. But we pay transfer tax.

Overall speedup: $S_{overall} = \frac{1}{f_s + \frac{f_p}{S_{GPU}} + t_{xfer}}$

Critical insight: Even if $S_{GPU} = \infty$, speedup is bounded by $\frac{1}{f_s + t_{xfer}}$

$S_{overall} = \frac{1}{0.05 + \frac{0.95}{50} + 0.02} = \frac{1}{0.05 + 0.019 + 0.02} = \frac{1}{0.089} \approx 11.2\times$

WHY only 11x when GPU is 50x faster?

• 5% serial bottleneck
• 2% transfer overhead
• These fixed costs dominate!

What if we eliminate transfer overhead (unified memory)? $S_{new} = \frac{1}{0.05 + 0.019} = 14.5\times$

Only 3.3x improvement from eliminating transfers! The5% serial code is the real killer.

Common Heterogeneous Patterns

Map Pattern (Embarrassingly Parallel)

Definition: Apply same function to every element independently.

CPU code:

for (int i = 0; i < N; i++) {
    output[i] = f(input[i]);
}

Why GPU wins: Each iteration is independent, perfect for thousands of threads.

Arithmetic intensity: Low (O(1) work per byte unless f is complex.

Reduce Pattern (Parallel with Coordination)

Definition: Combine array elements with associative operator (sum, max, etc.)

Sequential: $result = a_0 \oplus a_1 \oplus ... \oplus a_n$

Parallel tree reduction:

Derivation of work/span:

Work (total operations): Still $n-1$ operations (can't reduce this)

Span (critical path):

• Level 1: $n/2$ pairs combine in parallel → depth 1
• Level 2: $n/4$ pairs combine → depth 2
• ...
• Level $\log_2 n$: final combine

$\text{Span} = \log_2 n$

WHY? Each level halves the data, takes one step.

Speedup with $p$ processors: $S = \frac{n}{\log_2 n + \text{overhead}}$

On GPU: Overhead is high due to synchronization between levels. Better to use warp-level primitives.

GPU (tree reduction):

• Launch kernel with 1024 threads per block, 976 blocks
• Each thread sums 1024 elements → 976 partial sums
• Reduce976 sums on CPU (small enough)
• Time: ~0.5ms GPU compute + 0.5ms transfer = 1ms total

Speedup: 3x (not great because low arithmetic intensity)

WHY not faster? Each element read once, added once. Ratio of 1 FLOP per 4 bytes (assuming float). PCIe transfer time dominates.

Scan Pattern (Prefix Sum)

Definition: Output[i] = input[0] ⊕ input[1] ⊕ ... ⊕ input[i]

Applications: Stream compaction, radix sort, resource allocation

Parallel algorithm (work-efficient):

Step 1 - Upsweep (build tree):

for d = 0 to log₂(n) - 1:
    for each k = 0 to n/(2^(d+1)) - 1 in parallel:
        idx = (k+1) * 2^(d+1) - 1
        a[idx] = a[idx - 2^d] + a[idx]

WHY THIS STEP? Build a binary tree of partial sums, moving up levels.

Step 2 - Downswep (propagate sums):

a[n-1] = 0  // identity
for d = log₂(n) - 1 down to 0:
    for each k in parallel:
        idx = (k+1) * 2^(d+1) - 1
        temp = a[idx - 2^d]
        a[idx - 2^d] = a[idx]
        a[idx] = a[idx] + temp

WHY THIS STEP? Propagate the accumulated sum down, maintaining the inclusive scan property.

Work: $O(n)$ - same as sequential! Span: $O(\log n)$ - logarithmic depth GPU advantage: Exploits paralelism without extra work.

Programming Models & APIs

Popular models:

1. CUDA/HIP: Low-level, explicit control (NVIDIA/AMD GPUs)
2. OpenCL: Cross-platform, vendor-neutral
3. OpenMP offload: Pragma-based, implicit transfers
4. SYCL: C++ template-based, single-source
5. Vulkan Compute: Graphics API with compute shaders

Step 2 - Copy data to device:

cudaMemcpy(d_input, h_input, N*sizeof(float), 
           cudaMemcpyHostToDevice);

WHY? Transfer over PCIe bus.

Step 3 - Launch kernel:

int threads_per_block = 256;
int blocks = (N + 255) / 256;
kernel<<<blocks, threads_per_block>>>(d_input, d_output, N);

WHY THIS SYNTAX? <<<blocks, threads>>> specifies grid dimensions. GPU schedules these threads.

Step 4 - Copy result back:

cudaMemcpy(h_output, d_output, N*sizeof(float),
           cudaMemcpyDeviceToHost);

Step 5 - Free memory:

cudaFree(d_input);
cudaFree(d_output);

Total overhead: Allocations + 2 transfers + kernel launch latency. This is why arithmetic intensity matters!

Power Efficiency: The Real Win

Derivation of energy advantage:

Let

• $P_{CPU}$ = CPU power (watts)
• $P_{GPU}$ = GPU power when active (watts)
• $P_{idle}$ = GPU idle power (watts)
• $T_{CPU}$ = time on CPU
• $T_{GPU}$ = time on GPU (compute only)
• $T_{xfer}$ = transfer time

Energy on CPU: $E_{CPU} = P_{CPU} \times T_{CPU}$

Energy on heterogeneous system: $E_{hetero} = P_{CPU} \times (T_{xfer} + T_{CPU\_serial}) + P_{GPU} \times T_{GPU} + P_{idle} \times T_{xfer}$

WHY THIS FORM? CPU is active during transfers and serial code. GPU is active during compute. GPU idles during transfers.

For pure parallel workload ($T_{CPU\_serial} = 0$):

If $T_{GPU} = \frac{T_{CPU}}{S_{GPU}}$ (speedup $S_{GPU}$):

$E_{hetero} = P_{CPU} \times T_{xfer} + P_{GPU} \times \frac{T_{CPU}}{S_{GPU}} + P_{idle} \times T_{xfer}$

Energy efficiency gain: $\eta = \frac{E_{CPU}}{E_{hetero}} = \frac{P_{CPU} \times T_{CPU}}{(P_{CPU} + P_{idle}) \times T_{xfer} + P_{GPU} \times \frac{T_{CPU}}{S_{GPU}}}$

WHY IMPORTANT? For data centers, energy cost dominates over hardware cost!

GPU Setup:

• NVIDIA A100, 400W TDP, 10 TFLOPS (20× faster)
• Time: 0.5 hours + 5 min overhead
• Energy: 400W × 2100s = 0.84 MJ = 0.23 kWh

Energy saving: 85%!

WHY? Even though GPU uses more power, it finishes 20× faster, spending most time idle. Total energy is 6.5× lower.

Cost: At $0.12/kWh, CPU costs$0.18, GPU costs $0.03per epoch. Over 1000 epochs, save$150.

Advanced Concepts

Cache Coherence in Heterogeneous Systems

Problem: CPU and GPU have separate memory spaces (disagregated memory). If both access the same data, copies can diverge.

Solutions:

1. Manual coherence: Programmer ensures transfers after writes
2. Unified memory: Hardware/driver maintains coherence (CUDA unified memory)
3. Cache-coherent interconnect: AMD Infinity Fabric, Intel CXL

Trade-off: Automatic coherence adds latency (coherence protocol traffic).

Dynamic Task Scheduling

Challenge: How to decide CPU vs GPU at runtime when workload is unknown?

Approach - Work stealing:

1. Both CPU and GPU pull tasks from a shared queue
2. GPU takes tasks if queue is large (amortize overhead)
3. CPU takes tasks if queue is small (low latency)

Formula for threshold:

Execute on GPU if: $\text{Queue size} > \frac{T_{xfer} \times F_{GPU}}{S_{GPU} -1}$

WHY? Need enough work to overcome transfer cost.

FPGA vs GPU Trade-offs

Example: High-frequency trading uses FPGAs (10μs latency matters). AI training uses GPUs (throughput matters).

Mistakes & Misconceptions

Why it feels right: GPUs have more cores and higher FLOPS.

The fix: GPUs excel at specific patterns (data parallelism, high arithmetic intensity). For serial code, complex control flow, or small datasets, CPU is faster. The transfer overhead can make GPU slower even for parallel work if the dataset is small.

Litmus test: Is your workload:

• Massively parallel? (Yes needed)
• Regular memory access? (Yes needed)
• High arithmetic intensity (>10 FLOP/byte)? (Yes needed)
• Large dataset (>10MB)? (Yes needed)

All four must be true for guaranteed GPU win.

Why it feels right: More paralelism should mean more speed.

The fix:

1. Amdahl's Law: Serial portions limit speedup
2. Memory bandwidth: If memory-bound, cores sit idle waiting for data
3. Occupancy: GPU needs many threads per core to hide latency (need 10,000+ threads for full utilization, not 2048)
4. Coordination overhead: Synchronization between threads adds cost

Reality: 10-100× speedup is typical for well-suited problems, not 1000×.

Why it feels right: Unified memory abstracts away explicit transfers.

The fix: Unified memory still moves data over PCIe, just automatically. You still pay the latency! Worse, page faults (when GPU touches CPU page) can be slower than explicit batched transfers. Unified memory is convenient, not free.

Best practice: Prefetch large blocks with cudaMemPrefetchAsync to retain control.

Why it feels right: FPGAs have lower power and can be optimized per-algorithm.

The fix:

1. Development time: FPGA design takes months (RTL coding). GPU kernel takes days.
2. Flexibility: Changing FPGA logic requires resynthesis (minutes-hours). GPU recompiles instantly.
3. Peak performance: Modern GPUs have higher throughput for data-parallel tasks.

Use FPGAs when: Latency is critical, power is scarce, and the algorithm is stable (won't change often).

Connections

• CPU Architecture and Pipeline: Understanding CPU design motivates why GPUs are architected differently
• Memory Hierarchy and Caching: Explains why data movement dominates in heterogeneous systems
• Parallel Programming Models: Thread-level parallelism concepts extend to GPU thread blocks
• Amdahl's Law and Scalability: Directly applies to heterogeneous speedup analysis
• Power and Energy Optimization: Heterogeneous computing's primary advantage
• SIMD and Vector Processing: GPU SIMT is an evolution of SIMD principles
• DMA and I/O Controllers: Similar asynchronous data transfer concepts
• Rofline Performance Model: Tool for analyzing if workload is compute- or memory-bound on accelerators

Flashcards

#flashcards/hardware

What is heterogeneous computing? :: A computing architecture that uses two or more different types of processors (e.g., CPU + GPU, CPU + FPGA) with distinct capabilities, working together by partitioning tasks based on each processor's strengths.

Derive the heterogeneous Amdahl's Law speedup formula :: For serial fraction $f_s$, parallel fraction $f_p$, GPU speedup $S_{GPU}$, and transfer overhead $t_{xfer}$: Original time =1. New time = $f_s + \frac{f_p}{S_{GPU}} + t_{xfer}$. Therefore, $S_{overall} = \frac{1}{f_s + \frac{f_p}{S_{GPU}} + t_{xfer}}$. This shows serial code and transfer overhead limit speedup even with infinite GPU performance.

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)

Hinglish (regional understanding)