Module-2

1
Syllabus
• GPU programming, Programming hybrid systems, MIMD systems, GPUs,
Performance – Speedup and efficiency in MIMD systems, Amdahl’s law,
Scalability in MIMD systems, Taking timings of MIMD programs, GPU
performance.

2
GPU programming
• GPUs are usually not “standalone” processors.
•They don’t ordinarily run an operating system and system services, such as
direct access to secondary storage.
•Programming a GPU also involves writing code for the CPU “host”
system, which runs on an ordinary CPU.
• The memory for the CPU host and the GPU memory are usually separate.
• The code that runs on the host typically allocates and initializes storage
on both the CPU and the GPU.
• It will start the program on the GPU, and it is responsible for the output of
the results of the GPU program.
• Thus GPU programming is really heterogeneous programming, since it
involves programming two different types of processors
3
GPU programming
• Processors on the GPU
• A GPU is made up of several processors, usually called Streaming
Multiprocessors (SMs).
• Each SM can run hundreds or even thousands of threads at the same
time.
• Threads are grouped into warps (typically 32 threads), and warps are
scheduled together.
• Shared Large Memory
• All SMs can access a large block of memory (called global memory or
VRAM).
• This memory is big (GBs) but slow (hundreds of cycles to access).
• Every thread on the GPU can read and write here. 4
• Per-Processor Fast Memory
• Each SM also has a small, very fast memory block (usually 48–100
KB).
• Only threads running on that SM can access it.
• This is called shared memory in CUDA.
• It acts like a programmer-managed cache:
• You decide what data to put there.
• Often used to store values that will be reused by multiple threads in a block.
• Access is much faster than global memory.

5
• The threads running on a processor are typically divided into groups:
1. the threads within a group use the SIMD model
2. two threads in different groups can run independently.
• The threads in a SIMD group may not run in lockstep.
• That is, they may not all execute the same instruction at the same time
• No thread in the group will execute the next instruction until all the
threads in the group have completed executing the current instruction.
• If the threads in a group are executing a branch, it may be necessary to
idle some of the threads.

6
Example
• / Thread private variables
int rank_in_gp, my_x;

if (rank_in_gp < 16)

my_x += 1; // Threads 0–15 execute, 16–31 idle
else
my_x -= 1; // Threads 16–31 execute, 0–15 idle
•With 32 threads in the group:
• First, threads 0–15 increment my_x while 16–31 wait.
• Then, threads 16–31 decrement my_x while 0–15 wait.
•Efficiency lost: only 50% of threads active at a time
• it’s up to the programmer to minimize branching, where the threads
within a SIMD group take different branches. 7
• Another issue in GPU programming that’s different from CPU
programming is how the threads are scheduled to execute.
• GPUs use a hardware scheduler and this hardware scheduler uses very
little overhead.
• the scheduler will choose to execute an instruction when all the
threads in the SIMD group are ready.
Each thread must have rank_in_gp stored in a register before execution.
Threads execute the instruction together, and none can proceed to the
next instruction until all are done

8
• Maximizing Hardware Utilization
• Programmers usually launch many SIMD groups (warps).
• While some warps are waiting for memory or prior instructions:
• The scheduler selects a ready warp to execute.
• This keeps the GPU’s compute units busy.
• This strategy hides latency (like waiting for memory) and improves
throughput.

9
Programming hybrid systems
Hybrid Programming
• Definition: Combines shared-memory programming (e.g., OpenMP)
within a node and distributed-memory programming (e.g., MPI) between
nodes.
• Use Case: High-performance applications where maximum performance is
required.
• Challenges:
• Much more complex to develop.
• Requires careful management of both intra-node and inter-node communication.
• Programmer must handle thread-level parallelism inside nodes and message
passing between nodes.
10
Distributed-Memory Programming
• Definition: Uses a single distributed-memory API (like MPI) for both
intra-node and inter-node communication.
• Advantages:
• Simpler programming model.
• Easier to reason about data movement.
• Trade-off: May not fully exploit shared-memory parallelism within
nodes, but development is much easy

11
• When to Use Which
• Hybrid (MPI + OpenMP):
• Needed for extreme performance on clusters of multicore nodes.
• Good when nodes have many cores and inter-node communication is a
bottleneck.
• Pure MPI (Distributed memory):
• Easier and more common in practice.
• Works well for many applications that don’t need fine-grained optimization.

12
 Input and output
MIMD systems

Why We Avoid Parallel I/O?

• Parallel I/O is very complex – managing multiple cores writing to
multiple disks efficiently requires specialized strategies
• In most of our parallel programs, I/O demand is small, so we can rely
on simple standard C I/O functions : printf, fprintf, scanf, fscanf.
• The Challenge with Standard C I/O functions are serial by design –
they do not define behavior when multiple processes call them
simultaneously.
• This means: If different processes call printf at the same time →
results are undefined/nondeterministic
13
Threads vs. Processes
• Threads (forked from one process):
• Share stdin, stdout, stderr.
• But if multiple threads write at once → outputs get interleaved, corrupted, or
unpredictable.
• Processes (separate):
• Each has its own I/O streams, but combining outputs requires coordinating

• Parallel I/O is hard because ordering, consistency, and correctness of output aren’t
guaranteed.
• In practice: For small I/O → use serial C I/O cautiously.
• For large-scale parallel apps → use specialized parallel I/O libraries (e.g., MPI-IO, HDF5,
NetCDF).

14
 Output with printf
• Developers expect all output to appear on the starting system's
console
• Most systems provide this, but with processes there's no
guarantee
• Possibilities: only one process has access to stdout/stderr, or
none do

15
 Input with scanf
• Unclear whether input should be divided among
processes/threads
• Typically: process 0 can call scanf, multiple threads may also be
allowed
• Some systems don’t allow any process to call scanf

16
 Nondeterminism in Parallel I/O
• When multiple processes/threads access stdin/stdout/stderr:
• Output may appear in different order on each run
• Output may be interleaved or corrupted across
processes/threads
• Input distribution may vary between runs, even with the same
input

17
 Key Takeaway
• Standard C I/O in parallel contexts is unpredictable and
nondeterministic
• Use specialized I/O libraries for reliable parallel input/output
• Examples: MPI-IO, HDF5, NetCDF

18
 Input and Output
• In distributed memory programs, only process 0 will access
stdin. In shared memory programs, only the master thread or
thread 0 will access stdin.

• In both distributed memory and shared memory programs all

the processes/threads can access stdout and stderr.

19
 Input and Output
• However, because of the indeterminacy of the order of output
to stdout, in most cases only a single process/thread will be
used for all output to stdout other than debugging output.

• Debug output should always include the rank or id of the

process/thread that’s generating the output.

20
 Input and Output
• Only a single process/thread will attempt to access any single
file other than stdin, stdout, or stderr. So, for example, each
process/thread can open its own, private file for reading or
writing, but no two processes/threads will open the same file.

21
 Speedup and efficiency in MIMD systems
• The best parallel program can do is to divide the work equally among the cores while
at the same time introducing no additional work for the cores.
• If succeed in doing this, program runs with p cores, one thread or process on each core,
then parallel program will run p times faster than the serial program runs on a single
core of the same design.
• serial run-time ->Tserial
• parallel run-time ->Tparallel
• Number of cores ->p
• the best possible run-time of parallel program is Tparallel = Tserial/p
• This is called Linear Speedup

22
 Speedups and Efficiencies
p (No. of Cores) S (Speedup) E (Efficiency)

1 1.0 1.0

2 1.9 0.95

4 3.6 0.90

8 6.5 0.81

16 10.8 0.68
• It is not possible to get perfect linear speedup
Problems
1. Because the use of multiple processes/threads almost invariably introduces some
overhead.
• Shared-memory programs often have critical sections.
• These require a mutual exclusion mechanism (e.g., a mutex) to ensure only one
thread accesses the critical section at a time.
• Mutex function calls introduce overhead that does not exist in the serial program.
• The use of a mutex also forces parts of the program to serialize execution,
reducing potential speedup.

24
2. Distributed-memory programs will almost always need to transmit data across the
network, which is usually much slower than local memory access.
• The overheads will increase as we increase the number of processes or
threads.
• More threads will probably mean more threads need to access a critical
section .
• More processes will probably mean more data needs to be transmitted
across the network.
• Speedup measures how much faster a parallel program executes on
multiple processors compared to a single processor
S=Tserial/Tparallel
• Then linear speedup has S = p
25
Parallel Overhead and Efficiency
• As the number of processors (p) increases, parallel
overhead (e.g., synchronization, communication,
critical section delays) also increases.
• Because of this, the actual speedup (S) becomes a
smaller fraction of the ideal linear speedup (p).

26
 Parallel Overhead and Efficiency
• As p increases, parallel overhead increases
• Actual speedup S becomes a smaller fraction of ideal speedup p
• Efficiency = S/p usually decreases as p increases
• Efficiency shows how effectively we are using all processors in a
parallel system
 Formula for Efficiency
• Speedup: S = T_serial / T_parallel
• Efficiency:
E=S/p
• Substituting S:
E = T_serial / (p × T_parallel)
• Efficiency decreases when parallel overhead increases
• Many parallprocesses/threads and adding in the necessary
“parallel overhead,” such as mutual exclusion or
communication.
• Therefore if Toverhead denotes this parallel overhead, it’s often
the case that
Tparallel = Tserial/p + Toverhead.
• Tparallel, S, and E depend on p, the number of processes or
threads.
• Tparallel, S, E, and Tserial all depend on the problem size
• el programs are developed by explicitly dividing the work of
the serial program among the
Speedups and efficiencies of
parallel program on different
problem sizes
Real-World Factors Affecting Speedup & Efficiency in MIMD Factor Impact on Speedup & Efficiency

Communication overhead Slows down execution when

processors exchange data

Load imbalance Some processors finish earlier and stay

idle

Task granularity Finer tasks may incur more overhead

Synchronization Time spent waiting for other processors

Memory access latency Shared memory delays can reduce

performance
Contention on resources When multiple processors access
shared data/memory
Ideal vs Actual Speedup

The gap widens with more processors

Reflects Amdahl's Law and overheads
MIMD-Specific Considerations
• Since MIMD allows different instructions/data per processor:
1. Speedup is not always predictable
2. Heterogeneous tasks → performance depends on task
scheduling •
• If a task is not divisible evenly among processors, some will be
underutilized.
Example (Matrix Multiplication on MIMD): Each processor
handles a different part of a matrix. If:
• Processor 1 has a small submatrix (finishes early)
• Processor 2 has a large submatrix (takes longer)
Even though they’re in parallel, efficiency drops due to load
imbalance.
Ideal Case (Best Scenario)
If all the following are true:
• Tasks are perfectly divisible
• No communication required
• Processors don’t interfere with each other
Then:
• Speedup ≈ p
• Efficiency ≈ 1 (100%)
But in practice, this is rare.
 Amdahl’s Law
Amdahl’s Law describes the theoretical maximum speedup of a
program when only part of it can be parallelized.
It shows how the non-parallelizable (serial) portion limits the overall
performance improvement, no matter how many processors are used.

Amdahl’s Law formula

 Practical Example
Suppose: • A program takes 100 seconds
• 70% of it can be parallelized (P=0.7)
• You use 4 processors

Calculate speedup:

New execution time:

 Example
 We can parallelize 90% of a serial
program.
 Parallelization is “perfect” regardless of the
number of cores p we use.
 Tserial = 20 seconds
 Runtime of parallelizable part is 0.9 x Tserial / p = 18 / p
Scalability in MIMD Systems
What is Scalability?
Scalability is the ability of a parallel system (like
MIMD) to effectively utilize increasing numbers of
processors to solve larger problems or solve the
same problem faster.
In MIMD systems, where each processor executes
different instructions on different data, scalability
measures how well performance improves as more
processors are added.
Why is Scalability Important?
 In real-world MIMD systems (e.g., clusters, multi-core processors,

cloud VMs), we want performance to grow with hardware. If we

double the number of processors, ideally:
 Execution time should reduce by half (strong scaling), or

 We should solve a problem twice as large in the same time (weak

scaling)
 But this depends on:

 Communication costs

 Synchronization Task distribution (load balancing)

Types of Scalability
A. Strong Scalability
 Problem size is fixed

 Increase number of processors to reduce execution time

 Ideal when the same task needs to be completed faster

 Example:

 Sorting 1 million elements using 2 processors takes 5s

 Using 4 processors: time becomes 2.5s → strong scaling

Weak Scalability
 Problem size grows with number of processors

 Execution time stays constant

 Ideal when data grows (e.g., climate simulation, big

 data analytics)
 Example:

1 processor handles 1 GB data in 10s

4 processors handle 4 GB data in 10s → weak scaling