Parallel Computing

1) a) Define parallel computing. Explain the classifications of parallel computers with neat diagrams. (6 marks)

CLASSIFICATION:

Example: Traditional uniprocessor systems, early Intel 8085/8086 microprocessors.

Single-instruction, multiple-data (SIMD) systems Multiple-instruction, single-data (MISD) systems

Applications:Image processing,neural networks,GPU architectures. Ex: Certain real-time control systems, redundant space

Example: Modern GPUs, Cray vector processors. shuttle computers.

Multiple-instruction, multiple-data (MIMD) systems

b) Compare SIMD and MIMD systems with examples.

Then just write from the above questions and also can draw the diagram.

2) Explain cache coherence problem in multiprocessor systems.

In multiprocessor systems, each processor usually has its own private cache to reduce memory access time. However,
when multiple caches store copies of the same memory block, a cache coherence problem arises because the values of
the shared data may become inconsistent.
Cache coherence refers to the consistency of data values stored in different caches that correspond to the same
memory location.
• If one processor updates a data item in its cache, the same value should be visible to all other processors.
• If not maintained, processors may operate on stale (outdated) data, leading to incorrect results.

Cache Coherence Conditions (must be satisfied):

A coherent system must ensure:

1. Write Propagation: Any write to a variable must eventually be seen by all processors.
2. Transaction Serialization (Write Serialization): Writes to the same location must be performed in the same order for
all processors.

Solutions to Cache Coherence

1. Hardware Protocols (Cache Coherence Protocols):

o Write-Invalidate Protocol: When a processor writes to a cache block, it invalidates the copies in other caches.
o Write-Update (Write-Broadcast) Protocol: When a processor writes, the new value is broadcast to all other caches.
o Example protocols: MSI, MESI, MOESI, Dragon protocol.
2. Software Solutions:
o Compiler or operating system ensures that shared data is updated correctly (less common in practice).
b) Describe cache coherence protocols: Write- through, Write-back,MESI protocol.

1. Write-Through Protocol
• Definition: Every write operation to the cache is also immediately written (updated) to the main memory.
• Advantages:
o Simple to implement.
o Memory always has the latest (updated) data.
• Disadvantages:
o Higher memory traffic → slower performance.
o Reduces system efficiency when many writes occur.
• Use case: Systems prioritizing data consistency over performance.

Diagram (simple sketch):

CPU → Cache → Memory (updated immediately)

2. Write-Back Protocol
• Definition: Data is written to the cache only. Main memory is updated later, only when the cache block is replaced (evicted).
• Advantages:
o Reduces memory traffic (since multiple writes are absorbed in the cache).
o Better performance compared to write-through.
• Disadvantages:
o Main memory may have stale data until write-back occurs.
o Requires extra bits (dirty bit) to track modified blocks.
• Use case: Modern processors where speed is crucial.

Diagram:

CPU → Cache (updated) → Memory (updated only on block replacement)

3. MESI Protocol (Modified, Exclusive, Shared, Invalid)

• A widely used cache coherence protocol for multiprocessors.
• Each cache block can be in one of four states:

1. Modified (M):
o The cache has the only valid copy of the block.
o It is modified (different from main memory).
o Must be written back before eviction.
2. Exclusive (E):
o The cache has the only valid copy, but it matches main memory.
o Can be modified without notifying others.
3. Shared (S):
o The cache block may exist in multiple caches.
o All copies are identical to main memory.
4. Invalid (I):
o The cache block is invalid (not usable).

• Working:
o Processors change block states depending on read/write operations and bus snooping.
o Ensures that all processors see a consistent view of shared data.

State Transition Example:

• If a processor writes to a block in Shared state → it changes to Modified and other caches are invalidated.
• If a processor reads a block not present → it is loaded as Shared or Exclusive depending on other caches.

3)a) What are GPUs? Explain GPU architecture and compare it with CPU architecture. (6 marks)

What are GPUs?

• GPU (Graphics Processing Unit) is a highly parallel processor originally designed for graphics rendering, but now widely
used in scientific computing, AI, machine learning, and big data.
• Unlike CPUs (optimized for sequential operations), GPUs excel at parallel execution of thousands of threads
simultaneously.

GPU Architecture

1. SIMD/SIMT Nature
o CPUs are generally SISD devices (Single Instruction, Single Data) in Flynn’s taxonomy → fetch one
instruction and execute it on small data.
o GPUs, however, are SIMD (Single Instruction, Multiple Data) or SIMT (Single Instruction, Multiple
Threads) systems.
o SIMD model: One control unit broadcasts an instruction to many datapaths (cores). Each datapath
executes it on its own data element.
o Example: For an array x[i], SIMD processors can add +1 to nonnegative values and -2 to negative
values in parallel.
2. Control Unit → [SP1: x[1]] [SP2: x[2]] [SP3: x[3]] ...
3. Streaming Multiprocessors (SMs)
o A GPU contains several Streaming Multiprocessors (SMs).
o Each SM contains many Streaming Processors (SPs) (also called CUDA cores).
o Example: Modern Nvidia GPUs can have 82 SMs × 128 SPs = 10,496 cores.
o SMs operate asynchronously → no penalty if different branches of code execute on different SMs.
4. SIMT (Single Instruction, Multiple Threads)
o Nvidia calls its architecture SIMT.
o Unlike pure SIMD, SIMT allows some threads to block (e.g., waiting for memory) while others
continue, improving performance.
5. Memory Hierarchy
o Registers: Private to each thread.
o Shared Memory: Small, fast memory block inside each SM (shared among SPs).
o Global Memory: Large, but slower memory accessible by all SMs.
o Host vs Device Memory:
▪ CPU (host) has its own memory.
▪ GPU (device) has separate memory.
▪ In modern GPUs (compute capability ≥ 3.0), explicit transfers between CPU and GPU
memory are optimized/automatic.
b) Discuss GPGPU (General Purpose GPU) computing with applications.

Definition

• GPGPU stands for General Purpose computing on Graphics Processing Units.

• It means using a GPU, originally designed for rendering graphics, to perform non-graphics, general-purpose
computational tasks.
• It leverages the parallel processing power of GPUs to speed up scientific, engineering, AI, and data-intensive
computations.

How GPGPU Works

1. Parallelism:
o A GPU has hundreds to thousands of cores that can process multiple data elements in parallel.
2. Programming Models:
o GPGPU uses CUDA (by NVIDIA) or OpenCL frameworks for writing parallel programs.
3. Heterogeneous Computing:
o CPU acts as the host (sequential tasks, system management).
o GPU acts as the device (parallel, compute-intensive tasks).
4. Execution Flow:
o Program runs on CPU → heavy computation kernel is offloaded to GPU → results returned to CPU.

Applications of GPGPU

1. Scientific Computing:
o Weather forecasting, fluid dynamics, molecular simulations.
2. Artificial Intelligence & Machine Learning:
o Deep learning model training (e.g., TensorFlow, PyTorch rely on GPUs).
3. Image & Signal Processing:
o Medical imaging (CT, MRI scans), video processing.
 4. Finance & Business Analytics:
o Risk analysis, stock market prediction, fraud detection.
5. Cryptography & Security:
o Password cracking, blockchain mining.
6. Big Data & High Performance Computing (HPC):
o Data mining, real-time analytics, genome sequencing.

Diagram (for neatness in exam)

┌─────────────┐
│ CPU │ (Sequential tasks, control)
└─────┬───────┘
│
▼
┌─────────────┐
│ GPU │ (Parallel computation)
│ 1000s of │
│ cores │
└─────────────┘
│
▼
Faster Computation

a) Define speedup and efficiency in parallel systems. Derive the formulas. (5 marks)

S = Tserial/Tparallel
 Remarks

1. Ideal case: S=pS = pS=p and E=1E = 1E=1 → linear speedup.

2. In practice, S<pS < pS<p and E<1E < 1E<1 due to overhead, communication, and synchronization delays.
3. Sometimes, superlinear speedup occurs (S>pS > pS>p) due to c ache effects.

b) A parallel program runs in 100 seconds on 1 processor and 25 seconds on 4 processors. Calculate speedup and efficiency.

a) State and explain Amdahl’s law with mathematical derivation.

Amdahl’s Law states that unless nearly all parts of a serial program are parallelized, the overall speedup will be very limited
regardless of the number of processors.
b) If 80% of a program can be parallelized, what is the maximum speedup achievable with 8 processors?

a) What is hybrid programming? Explain programming hybrid systems using MPI+OpenMP.

Definition

• Hybrid programming refers to a parallel programming approach that combines distributed memory and shared
memory models in a single program.
• It leverages both MPI (Message Passing Interface) for communication between nodes (distributed memory) and
OpenMP (Open Multi-Processing) for parallelism within a node (shared memory).
• Useful in modern HPC clusters, where each node has multiple cores, and nodes are connected via a network.

Why Hybrid Programming?

• Efficiency: Combines the benefits of MPI (scaling across nodes) and OpenMP (fast thread-level parallelism within
nodes).
• Flexibility: Can run on clusters with multicore nodes.
 • Reduced communication overhead: Fewer MPI processes per node, since threads within a node communicate via
shared memory.

Programming Hybrid Systems Using MPI + OpenMP

1. MPI for Node-Level Parallelism
o Each node runs an MPI process.
o MPI handles data distribution and communication between nodes.
2. OpenMP for Core-Level Parallelism
o Within each MPI process, OpenMP threads are created to run on multiple cores of the node.
o OpenMP handles loop-level or task-level parallelism using shared memory.
3. Typical Structure of Hybrid Code

#include <mpi.h>
#include <omp.h>
#include <stdio.h>

int main(int argc, char** argv) {

MPI_Init(&argc, &argv); // Initialize MPI
int rank, size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

#pragma omp parallel

{
int tid = omp_get_thread_num();
printf("Hello from thread %d on MPI process %d\n", tid, rank);
}

MPI_Finalize(); // Finalize MPI

return 0;
}

• Explanation:
o MPI_Init and MPI_Finalize manage inter-node communication.
o #pragma omp parallel creates threads within each MPI process.
o Each MPI process may run on a separate node, and each thread runs on a core of that node.

b) Discuss the advantages and challenges of hybrid programming.