Q1.

Features of GPU
• GPUs (Graphics Processing Units) are specialized processors for handling graphics and
massively parallel computations.

• SIMD nature: apply the same instruction to multiple data items simultaneously.

• A single GPU may have thousands of cores (CUDA cores for NVIDIA).

• Thread parallelism: GPUs execute groups of threads called warps (typically 32 threads).

• Memory hierarchy:

o Global memory (large but slow).

o Shared memory (faster, accessible to threads of a block).

o Registers (fastest, private to a thread).

• High floating-point performance (important for scientific simulations, ML).

• Hardware multithreading hides memory latency by switching threads quickly.

• Heterogeneous computing: GPUs complement CPUs (GPUs for parallelism, CPUs for
control).

• Energy efficiency: better FLOPs per watt than CPUs.

• Used in AI, ML, image processing, simulations, cryptography, finance.

Q2. GPU Programming

• Involves two parts: host (CPU code) + device (GPU kernel).

• Host responsibilities:

1. Allocate memory on CPU + GPU.

2. Transfer data from CPU → GPU.

3. Launch GPU kernel (program on GPU).

4. Transfer results back to CPU.

• GPU kernel executes thousands of threads in parallel.

• Thread hierarchy:

o Threads → grouped into blocks.

o Blocks → grouped into grids.

• Branch divergence problem:

o If threads in a warp take different branches, execution becomes sequential.

• Scheduler: hardware chooses ready thread groups to hide memory delays.

 • Example: CUDA and OpenCL are popular GPU programming frameworks.

• Real use cases: matrix multiplication, deep learning, physics simulations.

Q3. I/O in MIMD Systems

• Each process/thread may try to write to stdout simultaneously → results become
interleaved.

• Rules to avoid confusion:

o Only process 0 (or master thread) should read from stdin.

o Only one process/thread should handle final output.

o Debug outputs must include rank/ID of the process.

• Files:

o No two processes/threads should write to the same file at the same time.

o Each can use private files.

• Input distribution:

o Sometimes divided among processes, sometimes handled by master only.

• Output order is nondeterministic in parallel runs.

Q4. I/O in GPU Systems

• GPUs normally don’t do I/O → host CPU manages it.

• GPU threads can write to stdout (for debugging), but output order is random.

• GPU threads cannot:

o Read from stdin.

o Write to stderr.

o Access secondary storage (hard disk).

• Host handles all file I/O and user interaction.

• Example: in CUDA, only the CPU program prints results, while GPU kernels perform
computation.

Q5. Speedup in MIMD Systems

• Speedup (S): ratio of serial execution time to parallel execution time.

S=TserialTparallelS = \frac{T_{serial}}{T_{parallel}}S=TparallelTserial
 • Linear speedup: ideally S = p (p processors).

• In reality, S < p due to overheads.

• Overheads include:

o Synchronization delays (mutex, locks).

o Communication costs (network latency).

o Idle processors (load imbalance).

• Example from Table 2.4:

o p=8 → S=6.5 (<8, due to overheads).

• Speedup is the first measure of how effective parallelization is.

Q6. Efficiency in MIMD Systems

• Efficiency (E): measures processor utilization.

E=Sp=Tserialp⋅TparallelE = \frac{S}{p} = \frac{T_{serial}}{p \cdot T_{parallel}}E=pS=p⋅TparallelTserial

• Shows how much of each processor’s time is useful work.

• Ideal efficiency = 1 (100%).

• Drops as processor count increases due to overheads.

• Example:

o p=16, S=10.8 → E=0.68 (68% utilization).

• Larger problem size → better efficiency (overhead becomes smaller fraction).

• Useful for comparing parallel algorithms with different numbers of processors.

Q7. Amdahl’s Law

• States that serial fraction of a program limits overall speedup.

• Formula:

S≤1rS \leq \frac{1}{r}S≤r1

where r = fraction of program that is serial.

• Example:

o 90% parallel (10% serial).

o Even with 1000 cores, max speedup = 10.

• Key insight: diminishing returns when adding more processors.

• Shows importance of minimizing serial parts of code.

 • Practical solution: increase problem size (→ Gustafson’s Law).

Q8. Scalability in MIMD Systems

• Scalability: ability of program to maintain efficiency as processors increase.

• Two types:

1. Strong scalability: Efficiency remains fixed without increasing problem size.

2. Weak scalability: Efficiency remains fixed if problem size increases with processors.

• Example:

o Tserial = n

o Tparallel = n/p + 1

o Efficiency = n / (n+p)

o To keep efficiency constant, increase n with p.

• Scalable systems → better long-term use of large parallel machines.

Q9. GPU Performance

• GPU performance measured differently than CPU:

o GPUs excel in throughput (many tasks per second).

o CPUs excel in latency (single task speed).

• Performance metrics:

o FLOPs (floating point operations per second).

o Memory bandwidth.

• Scalability: larger GPUs (more cores) → better speedup (weak scaling).

• Amdahl’s law still applies: serial parts of GPU program limit speedup.

• Example: deep learning training → GPUs achieve 100x–1000x speedup over CPUs.

• Timings: usually measured by host CPU wall-clock timers.

Q10. Coordinating Processes/Threads (SPMD Programs)

• SPMD = Single Program, Multiple Data.

• Same program runs on all processors, but with different data subsets.

• Steps to parallelize:
 1. Divide work equally (load balancing).

2. Synchronize threads at necessary points.

3. Communicate (via shared memory or message passing).

• Example: vector addition with p processes → each process handles n/p elements.

• Two types of parallelism in SPMD:

o Data parallelism (divide data).

o Task parallelism (different tasks).

Q11. Shared vs Distributed Memory

• Shared Memory Systems:

o All processors access common memory.

o Easy communication (through variables).

o Harder synchronization (need locks).

o UMA: equal access time for all memory.

o NUMA: local memory faster than remote memory.

• Distributed Memory Systems:

o Each processor has private memory.

o Communication via message passing.

o Easier to scale to large systems.

o Example: Clusters, Grids.

• Comparison:

o Shared → easier to program.

o Distributed → more scalable.

Q12. Cache Coherence

• Problem: Multiple cores caching the same variable → inconsistent values.

• Snooping protocol:

o Cores “snoop” a bus for writes.

o When one updates a value, others invalidate their copies.

• Directory-based protocol:

o Directory keeps track of which cores hold which cache line.

 o Only cores with the variable are updated.

• False sharing:

o Different cores update different variables in same cache line.

o Causes unnecessary invalidations.

• Solution:

o Use private temporary variables.

o Then copy results into shared memory.