Module 2

1). Gpu programming and Programming hybrid systems

2. MIMD systems, GPUs
3. Performance – speed and efficiency

Performance in Parallel Programs (2.6)

The primary goal of parallel programming is to improve performance, mainly
by reducing execution time. Performance evaluation helps us understand how
effectively a parallel program utilizes multiple processors. This section focuses
on homogeneous MIMD systems, where all cores have the same architecture.
GPU performance is treated separately since GPUs are heterogeneous.

Speedup and Efficiency in MIMD Systems (2.6.1)

The ideal case in parallel programming is when the work is divided equally
among all processors and no extra work is introduced. If a serial program takes
time Tserial on one core and the parallel program takes time Tparallel on p
cores, the best possible runtime is:
• Tparallel = Tserial / p
When this happens, the program achieves linear speedup.
Speedup
Speedup (S) is defined as:
• S = Tserial / Tparallel
In the ideal case, S = p. However, perfect linear speedup is rare in practice.
Reasons for Non-linear Speedup
Parallel programs introduce overheads, such as:
• Mutual exclusion (e.g., mutexes) in shared-memory systems
• Communication delays in distributed-memory systems
These overheads increase as the number of processes or threads increases,
causing speedup to fall below the ideal value.
Efficiency
Efficiency (E) measures how well processors are utilized and is defined as:
• E = S / p = Tserial / (p × Tparallel)
Efficiency represents the average fraction of time each processor spends doing
useful work. The remaining time is spent on parallel overhead.
For example:
• If Tserial = 24 ms, p = 8, Tparallel = 4 ms
• E = 24 / (8 × 4) = 0.75
This means each processor spends 75% of its time doing useful computation.
Often, parallel runtime can be written as:
• Tparallel = Tserial / p + Toverhead
Here, efficiency reflects the proportion of time spent solving the original
problem.

Effect of Problem Size

Performance also depends on problem size:
• Increasing problem size usually increases speedup and efficiency
• Decreasing problem size reduces both
This happens because Tserial grows faster than parallel overhead as problem
size increases, making parallel execution more effective.

Measuring Tserial
For reporting performance, Tserial is usually taken as:
• The runtime of the serial version of the same program
• Run on one core of the parallel system
This approach better reflects core utilization and is commonly used in practice.
4. Amdahl’s Law (2.6.2)

Amdahl’s Law, proposed by Gene Amdahl, explains the theoretical limit on

speedup achievable by parallelizing a program. It states that unless almost the
entire program is parallelized, the overall speedup will be limited, no matter
how many processors are used.

Basic Idea
Consider a serial program with runtime Tserial.
Suppose:
• A fraction 0.9 (90%) of the program can be perfectly parallelized
• A fraction 0.1 (10%) remains serial
• The parallelized portion achieves ideal speedup on p processors
Given:
• Tserial = 20 seconds

Parallel Runtime
Parallel part runtime:
𝑇𝑠𝑒𝑟𝑖𝑎𝑙 18
0.9 × =
𝑝 𝑝

Serial part runtime:

0.1 × 𝑇𝑠𝑒𝑟𝑖𝑎𝑙 = 2

Total parallel runtime:

18
𝑇𝑝𝑎𝑟𝑎𝑙𝑙𝑒𝑙 = +2
𝑝
Speedup Formula
Speedup S is defined as:
𝑇𝑠𝑒𝑟𝑖𝑎𝑙 20
𝑆= =
𝑇𝑝𝑎𝑟𝑎𝑙𝑙𝑒𝑙 18 + 2
𝑝

18
As p → ∞, the term → 0, so:
𝑝

𝑇𝑝𝑎𝑟𝑎𝑙𝑙𝑒𝑙 ≥ 2

Thus, the maximum speedup is:

20
𝑆≤ = 10
2

This means that even with infinite processors, the speedup cannot exceed 10.

General Form of Amdahl’s Law

If a fraction r of a program is inherently serial, then:
1
Maximum Speedup =
𝑟

Example:
• If 𝑟 = 0.1, maximum speedup = 10
• If 𝑟 = 0.01, maximum speedup = 100
Even with thousands of cores, speedup is strictly limited by r.

Implications
• Small serial portions severely limit performance gains
• Perfect parallelization of most code is not sufficient
• Adding more processors alone does not guarantee higher speedup
Why Amdahl’s Law Is Not the End
• It does not consider problem size
• For many applications, increasing problem size reduces the serial fraction
• This observation leads to Gustafson’s Law
• Many real-world programs still achieve large speedups
• Even speedups of 5–10× are often practically sufficient

5. Scalability in MIMD systems

Scalability in MIMD Systems

In general, a parallel program is called scalable if increasing the computing
resources, such as the number of processors or threads, results in better
performance. In MIMD systems, scalability is formally defined using efficiency.
A parallel program is said to be scalable if, when the number of
processes/threads is increased, it is possible to increase the problem size at an
appropriate rate so that the efficiency remains constant.
Example
Assume the serial runtime is:
𝑇𝑠𝑒𝑟𝑖𝑎𝑙 = 𝑛

where 𝑛is the problem size.

The parallel runtime is:
𝑛
𝑇𝑝𝑎𝑟𝑎𝑙𝑙𝑒𝑙 = +1
𝑝
The efficiency is:
𝑇𝑠𝑒𝑟𝑖𝑎𝑙 𝑛
𝐸= =
𝑝 ⋅ 𝑇𝑝𝑎𝑟𝑎𝑙𝑙𝑒𝑙 𝑛 + 𝑝

If the number of processes is increased by a factor 𝑘(to 𝑘𝑝) and the problem
size is increased to 𝑥𝑛, efficiency remains unchanged when:
𝑥=𝑘

Thus, increasing the problem size at the same rate as the number of processors
keeps efficiency constant, showing the program is scalable.
Types of Scalability
• Strong scalability: Efficiency remains constant without increasing
problem size.
• Weak scalability: Efficiency remains constant when problem size
increases proportionally with processors.

6. Taking timings of MIMD program

To evaluate the performance of parallel MIMD programs, we need to measure
Tserial and Tparallel accurately. Timing parallel programs is more complex than
serial programs, but some general principles help.

1. Purpose of Taking Timings

There are two reasons for taking timings:
• During program development: to check program behavior, such as time
spent waiting for messages or synchronization.
• After development: to evaluate overall performance, usually reported as
a single execution time.
2. Timing Only the Relevant Code
• We are usually interested in only a part of the program, not the entire
execution.
• Example: In sorting, we time only the sorting phase, not input/output.

3. Wall Clock Time vs CPU Time

• CPU time (from clock()) measures only active execution time.
• It does not include idle time, such as waiting for messages.
• In parallel programs, waiting time is a real cost and must be included.
• Hence, wall clock time is used to measure actual elapsed time.

4. Basic Wall Clock Timing Method

double start, finish;

start = Get_current_time();
/* Code that we want to time */
finish = Get_current_time();

printf("Elapsed time = %e seconds\n", finish - start);

• Get_current_time() is a placeholder.
• Examples:
o MPI → MPI_Wtime()
o OpenMP → omp_get_wtime()
• These return wall clock time, not CPU time.

5. Timer Resolution
• Timer resolution is the smallest measurable time unit.
 • Low-resolution timers may not detect short execution times.
• Programmers must check the timer resolution provided by the API.

6. Timing in Parallel Programs

• Each process/thread measures its own elapsed time.
• However, we want a single execution time for the program.
• This is approximated using synchronization and maximum time.
• A barrier synchronizes all processes.
• The maximum elapsed time represents total program runtime.

7. Variability in Timings
• Execution time varies across runs, even with the same input.
• Instead of mean or median, we usually report the minimum time.
• External factors cannot make a program run faster than its best run.

8. Threads per Core and I/O

• Running more than one thread per core increases scheduling overhead
and variability.
• Hence, parallel programs usually use one thread per core.
• I/O time is excluded from reported performance timings.
7. GPU Performance (10 Marks)
1. GPU program performance is often compared with
serial and MIMD programs, and GPUs usually show
very large speedups over serial execution.
2. In MIMD systems, efficiency assumes that the serial
program runs on the same type of core as the parallel
system, which is not true for GPUs.
3. GPU cores are inherently parallel and fundamentally
different from CPU cores, so comparing GPU efficiency
with serial CPU programs is not meaningful.
4. Due to this architectural difference, traditional MIMD
concepts such as efficiency and linear speedup are
generally not used for GPU performance analysis.
5. The formal definition of scalability used in MIMD
systems cannot be directly applied to GPUs because
efficiency is not well defined.
6. Informally, a GPU program is considered scalable if
increasing the GPU size leads to improved performance
compared to a smaller GPU.
7. Amdahl’s Law can be applied to GPU programs when
the inherently serial portion of the program runs on a
conventional CPU.
8. If a fraction r of the program remains serial, Amdahl’s
Law limits the maximum possible speedup to 1/r,
similar to MIMD systems.
 9. The serial fraction may decrease as problem size
increases, allowing greater speedups, and even small
speedups can be sufficient in practice.
10. GPU program timing is usually done using CPU
timers for total execution time, while GPU-specific API
timers are used when timing only GPU code sections.

Length veriosn

GPU Performance (10 Marks)

1. Performance of parallel programs is commonly evaluated by comparing
them with serial programs.
o GPU programs are often shown to achieve very high speedups.
o These speedups are reported against serial CPU or MIMD program
executions.
2. In MIMD performance analysis, efficiency assumes similar core types.
o The serial program is assumed to run on the same type of core as
the parallel system.
o This assumption becomes invalid in the case of GPUs.
3. GPU cores differ fundamentally from CPU cores.
o GPU cores are inherently parallel in nature.
o CPU cores are optimized for serial or lightly parallel execution.
o Hence, direct efficiency comparison is meaningless.
4. Traditional MIMD performance metrics do not apply well to GPUs.
o Efficiency is not normally discussed for GPU programs.
o Linear speedup relative to a serial CPU program is also not
meaningful.
5. Formal scalability definitions used for MIMD systems cannot be applied
to GPUs.
o Scalability depends on efficiency in MIMD systems.
o Since efficiency is undefined for GPUs, formal scalability is also
undefined.
6. Scalability for GPUs is used in an informal sense.
o A GPU program is said to be scalable if performance improves with
larger GPUs.
o Speedup is measured relative to smaller GPU configurations.
7. Amdahl’s Law can still be applied under specific conditions.
o The inherently serial portion must run on a conventional CPU.
o The parallel portion is executed on the GPU.
8. Amdahl’s Law limits GPU speedup in the same way as MIMD systems.
o If fraction r of the program remains serial, it cannot be
parallelized.
o The maximum possible speedup is bounded by 1/r.
9. The limitations of Amdahl’s Law also apply to GPUs.
o The serial fraction may reduce as problem size increases.
o This allows higher possible speedups.
o Even modest speedups can be practically acceptable.
[Link] of GPU programs follows similar principles to MIMD timing.
o GPU execution is initiated and completed by the CPU.
o CPU timers are used to measure total execution time.
o GPU API timers are required when timing only GPU code sections.