Module-2

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.
GPU programming
• GPUs are not standalone processors

• No operating system or direct access to secondary storage

• Programming a GPU also involves writing code for the CPU “host” system, which runs on an
ordinary CPU
• Programming a GPU always involves both:

➢ Host (CPU) → allocates/initializes memory, launches GPU tasks, handles output

➢ Device (GPU) → executes massively parallel computations

• This is called heterogeneous programming

• The separate memory for the CPU host and the GPU.
1. CPU Host's Role:

• The CPU host is responsible for the overall control and coordination.

• It allocates and initializes memory on both the CPU (host memory) and the GPU (device
memory), which are usually separate.

• It initiates the execution of programs on the GPU.

• It handles the output and retrieval of results from the GPU program.

2. GPU Architecture:

• A GPU contains one or more processors.

• Each of these processors is designed to run hundreds or thousands of threads

concurrently

• Critically, each individual processor also has a small block of much faster memory, often
referred to as a programmer-managed cache. This faster memory is only accessible by
threads running on that specific processor.
[Link] Organization and Execution (SIMD Groups):

• Threads running on a GPU processor are typically organized into groups, often called
SIMD (Single Instruction, Multiple Data) groups.

• Within a SIMD group: Threads generally operate under the SIMD model and two threads in
different groups can run independently.

• Thread in SIMD may not execute in strict "lockstep" (i.e., not all execute the exact same
instruction at the precise same time), no thread in the group will move to the next instruction
until all threads in the group have completed the current instruction.

[Link] and Idling Threads:

• A significant challenge in SIMD execution is branching (e.g., if-else statements) where threads
within the same group take different execution paths.
• For example: suppose there are 32 threads in a SIMD group, and each thread has a private
variable rank_in_gp that ranges from 0 to 31. Suppose also that the threads are executing the
following code:

• Threads are divided based on their rank (ID).

• Threads with rank < 16 execute the first assignment, while others remain idle.

• Threads with rank ≥ 16 execute the second assignment, Threads with rank < 16 stay idle.

• This process results in half of the threads being idle at any time.

• Such idling leads to inefficient use of resources.

• Therefore, programmers should minimize branching ,where threads in the same SIMD group
take different execution paths.
[Link] Scheduling and Maximizing Resource Use:

• GPU scheduling differs from CPU scheduling:

• CPUs use software-based schedulers.

• GPUs use a hardware scheduler with very low overhead.

• Execution rule:The hardware scheduler executes an instruction only when all threads in
a SIMD group are ready.

• To maximize hardware utilization, it's common practice to create a large number of SIMD
groups, This provides the scheduler with more options:

• This ensures that while some groups are waiting (e.g., for memory or previous
instructions), other groups can be executed.
 Programming hybrid systems
• When programming systems composed of clusters of multicore processors, a common approach for
achieving high performance is to combine different programming models:

• Shared-memory API: Used for communication and data sharing within a single node (i.e., among
the cores of a single multicore processor).

• Distributed-memory API: Used for communication and data exchange between different nodes in
the cluster.

• This combination is often referred to as a "hybrid" API programming model.

• Why use a hybrid API?

• The primary motivation for employing a hybrid API is to achieve the highest possible levels of
performance.

• By utilizing the shared-memory model within a node, programs can exploit faster communication paths
(e.g., directly accessing shared memory) compared to the overheads of inter-node communication
• Challenges of Hybrid API Programming:

• Despite the performance benefits, hybrid API programming introduces significant

complexity, making program development much more difficult. This increased
complexity arises from:

• Managing two distinct programming models: Developers must understand and

effectively integrate both shared-memory and distributed-memory paradigms.

• Data placement and movement: Carefully orchestrating data movement

between shared memory within a node and distributed memory across nodes
becomes crucial for performance.

• Synchronization: Ensuring correct synchronization both within and across nodes

adds layers of complexity.
• Alternative Approach:

• Given the challenges, such system communication.

• While this might not always yield the performance, are often programmed using a
single, unified distributed-memory API for both inter-node and intra-node
communication.

• While this might not always yield the absolute peak performance achievable with
a finely-tuned hybrid approach, it significantly reduces program development
complexity by providing a consistent communication model across the entire
cluster.
 MIMD systems
• MIMD Systems: Input/Output Challenges

• Parallel I/O means multiple execution entities (cores / threads / processes) reading from
and/or writing to one or more devices (terminals, disks, network filesystems, etc.) at the
same time.

• When discussing MIMD (Multiple Instruction, Multiple Data) systems, the topic of
input/output (I/O) often presents unique challenges compared to serial
programming.

• Most parallel programs use little I/O:

• Data read/write is usually small.

• Managed with standard C, I/O functions (printf, fprintf, scanf, fscanf).

• I/O Challenges in MIMD Systems:

[Link] C's Ambiguity for Processes: C is a serial language, so it does not define behavior
when multiple processes call I/O functions simultaneously.

[Link] Outcomes for Threads: While threads forked by a single process do share
stdin, stdout, and stderr, simultaneous access by multiple threads to these shared resources
leads to nondeterministic outcomes.

• Output from one thread/process can get interleaved with another’s, producing mixed or
corrupted text.

Possible outputs:

Thread A: ABCDE Thread A: ABThread B: 12C3D45 Thread B: 12345

Thread B: 12345 Thread A: ABCDE

[Link] to Console (printf, fprintf):

➢ Developer Expectation: Developers usually want all output to appear on the console
of the single system where the program was initiated.

➢ System Behavior: Most systems indeed combining multiple output to a single console.
However, there's no guarantee. Some systems might restrict stdout or stderr access to
only one process, or even none.

➢ Nondeterminism: When multiple processes/threads can access stdout, the sequence of

output is usually nondeterministic. Data from different processes/threads might
interleave unexpectedly, making it hard to read or debug.
4. Input from Console (scanf, fscanf):

➢ Ambiguity: It's less obvious how scanf should behave with multiple processes/threads.
Should input be divided? Should only one be allowed to read?.

➢ System Behavior: The majority of systems allow at least one process (commonly process
0) to call scanf, and most allow multiple threads to call scanf. However, some systems
might not allow any processes to call scanf.

➢ Nondeterminism: When multiple processes/threads read from stdin, the data read by
each can vary on different runs, even with identical input, due to race conditions.
Assumptions and Rules for I/O in Parallel
Programs:
To manage these potential issues and ensure predictable (or at least understandable) I/O
behavior in parallel programs, the following conventions are often adopted:

➢ Standard Input (stdin) Access: Distributed-Memory Programs: Only process 0 will

access [Link]-Memory Programs: Only the master thread or thread 0 will access
stdin

➢ Standard Output (stdout) and Standard Error (stderr) Access: Both Distributed and
Shared-Memory Programs: All processes/threads can access stdout and stderr.

➢ Debug Output Best Practice: Debug output should always include the rank or ID of
the process/thread generating the output.

➢ File I/O (other than stdin, stdout, stderr): Only a single process/thread will attempt
to access any specific file.
GPU
• GPU programs have two parts:

• Host code → runs on the CPU.

• Device code → runs on the GPU (many threads in parallel).

GPUs and I/O: Host-Centric Approach with Debugging Exceptions

• In GPU programming, the CPU host code is generally responsible for all input/output (I/O)
operations. This simplifies I/O management significantly for a few key reasons:

➢ Single Host Process/Thread:

• Typically, only one process or thread runs on the CPU host to manage the GPU computations.

• This means that the standard C I/O functions (like printf, scanf, fprintf, fscanf) behave exactly as
they would in a regular serial C program.
GPU Limitations:

GPUs are specialized for parallel computation and generally do not have direct access to
standard I/O streams or secondary storage (like hard drives). This offloads I/O responsibilities
entirely to the host.

Exception for Debugging:

• While the rule is to use the host for all I/O, there's a crucial exception for debugging GPU code:

• stdout for GPU Threads: In the systems commonly used for GPU programming, individual
GPU threads can write to stdout.

• Nondeterministic Output: Similar to MIMD programs running on CPUs, when multiple GPU
threads write to stdout concurrently, the order of the output is nondeterministic. This means
the interleaved output can vary from one run to the next.

• No Access to Other Streams/Storage: Crucially, GPU threads typically do not have access to
stderr, stdin, or secondary storage. This reinforces the host's role for all but very specific
debugging output.
Performance – Speedup and efficiency in
MIMD systems
• The primary goal of writing parallel programs is to achieve
increased performance.

• When evaluating the performance of homogeneous MIMD

systems (where all cores have the same architecture, unlike
GPUs), we use metrics like speedup and efficiency.
Speedup and Efficiency in MIMD Systems
▪ Ideally, a parallel program divides work equally among cores with no
added overhead.
▪ If a program runs on p cores (one process or thread per core), the best
possible runtime, Tparallel, would be Tserial /p, where Tserial is the
runtime of the equivalent serial program on a single core of the same
design.
▪ When this ideal is achieved, we say the program has linear speedup.
▪ Speedup (S) is formally defined as:
• E = Efficiency, i.e., how well the processors are being utilized.
• Efficiency is the ratio of speedup to the number of processors, measures average utilization of
the cores.
• Interpretation:If 𝑬 = 𝟏: all cores are working perfectly, no overhead.
• If 𝑬 < 𝟏: some time is wasted on overheads like communication, synchronization, or idle time.
• Example: If 𝐸 = 0.8, then on average each core spends 80% of its time doing useful work and
20% of time is wasted on overhead.
• Parallel Overhead:

• Parallel overhead tells how much extra time is spent compared to the
ideal case.
Dependence on Problem Size

Tparallel, S, and E are not only dependent on p but also significantly on the problem size.
• Observation:
• In many parallel programs, as the problem size increases
(with p fixed), speedups and efficiencies generally increase (as
illustrated in Tables 2.4 and 2.5 and Figures 2.18 and 2.19).
Conversely, they decrease when the problem size is reduced.
• When you increase the problem size (say, processing a bigger dataset or solving a
larger matrix), the serial work 𝑇𝑠𝑒𝑟𝑖𝑎𝑙 (the total amount of actual computation) grows
rapidly.

• Meanwhile, the parallel overhead 𝑇𝑜𝑣𝑒𝑟ℎ𝑒𝑎𝑑 (extra time due to communication,

synchronization, thread management, etc.) usually grows much more slowly.

Tserial≫Toverhead

• For small problem sizes, overhead dominates → efficiency is poor (processors idle or
spend too much time communicating).

• For large problem sizes, computation dominates → efficiency improves because

overhead is negligible compared to useful work.

• parallel computing is most beneficial for large-scale problems.

The question: Which 𝑻𝒔𝒆𝒓𝒊𝒂𝒍 should we use?

• When reporting speedup or efficiency, we always compare the parallel run time against a serial
run time (𝑇𝑠𝑒𝑟𝑖𝑎𝑙 ).

• But — there’s more than one way to define that serial time.

2. Two possible choices

Approach 1: Fastest possible serial program on the fastest processor

• Here, we take the best serial algorithm and run it on the fastest available processor (not
necessarily the same machine as the parallel system).

• This gives a "best-case baseline" — the absolute fastest possible time to solve the problem serially.

• Then, the parallel program is compared against this.

Approach 2: Serial version of the parallel program on one core of the parallel system

• we take the same program that was parallelized, but run it with a single processor/core on the
parallel machine.
• Approach 1 (fastest algorithm, fastest machine) → gives a best-case
but can make parallel results look artificially bad.

• Approach 2 (same algorithm, same system, 1 core) → fairer and

more widely used, since it directly measures how well parallelization
improves that program.
• Problem Size (Gustafson's Law):

• Amdahl's Law assumes a fixed problem size. However, for many

problems, as the problem size increases, the "inherently serial"
fraction (r) often decreases proportionally to the total work.

• This means that larger problems can exhibit much better

speedups on many cores, a concept formalized by Gustafson's
Law.

• In essence, as you scale up the problem, the parallelizable work

often grows much faster than the serial work.
Scalability in MIMD systems
The Example:
Checking scalability:
 Taking timings of MIMD programs
• Taking timings of MIMD programs is about how to measure execution time
for parallel programs

There are generally two main reasons for timing parallel programs

1. During Program Development (Detailed Analysis):

• Example: In a distributed-memory program (MPI), you may want to know how

much time processes spend waiting for messages.

• If waiting is high, the program design/implementation may be inefficient.

2. After development (performance evaluation):

• Goal: Measure how good the program’s performance is.

• What we measure the total time for the important computation part.

• This is the value used to calculate things like:

𝑇𝑠𝑒𝑟𝑖𝑎𝑙
• Speedup: 𝑆 =
𝑇𝑝𝑎𝑟𝑎𝑙𝑙𝑒𝑙

𝑆
• Efficiency: 𝐸 = (where 𝑃= number of processors).
𝑃

When writing a parallel program, you may want timings for two purposes:

1. Debugging/Optimization → measure time spent in different sections (communication,

computation, waiting, etc.).

2. Final Performance Measurement → measure only the core computation part, usually
as a single value.
Key Considerations for Performance Timings

1. Timing Specific Code Sections, Not Entire Program:

• We are usually interested in the time taken by the core computational

part of the program, not the total execution time from start to finish
(which includes setup, I/O, etc.).

• Therefore, standard shell commands like time (Unix) are often

insufficient as they report total program execution time.

• So we need to insert timers inside the program, around only the

important section (the computation part).
2. Wall Clock Time vs. CPU Time:
• We are generally not interested in "CPU time" (time spent actively
executing instructions or system calls initiated by the program). The
standard C clock() function reports CPU time.
• Problem with CPU time: In parallel programs, processes/threads might
spend significant time idle (e.g., waiting for other processes/threads to
send data, or waiting for a mutex to be released).
• Solution: Wall Clock Time: The reported time for parallel programs is
almost always "wall clock time" (also known as elapsed time or real
time). This measures the total time that elapses from the beginning to the
end of the timed section, as if measured by a stopwatch.
For parallel programs, CPU time underestimates the actual runtime
because it ignores waiting/idle time.
What we usually want instead is wall-clock time (real elapsed time between
start and end of computation).
A typical structure for measuring wall clock time is:

double start, finish;

// ...
start = Get_current_time(); // Hypothetical function// It returns the
number of seconds elapsed since some fixed reference point
/* Code that we want to time */
// ...
finish = Get_current_time();
printf("The elapsed time = %e seconds\n", finish - start);
Issue with Timer Resolution:

• Definition: Timer resolution is the smallest unit of measurement the timer

can report (e.g., milliseconds, microseconds, nanoseconds).

• Issue: If the resolution is too coarse (e.g., milliseconds) and the timed code
section executes very quickly (e.g., less than a millisecond), the timer might
report zero or an inaccurate value.

• Ex: Modern CPUs can execute an instruction in < 1 nanosecond (10⁻⁹ s), so a
coarse timer may not capture very short program segments.

• Verification: Many APIs provide functions to query the timer's resolution,

or they specify a minimum required resolution. Programmers must check
these values.
Timing in parallel programs – the tricky part:

• When the code being timed is executed by multiple processes or threads, each will
record its own my_start and my_finish times, resulting in p individual elapsed
times.

• Ex: If you have 8 processes running in parallel, each will output its own time ,
resulting in 8 different elapsed times.

• However, what's usually desired is a single overall time: the duration from when the
first

• process/thread began the timed section to when the last process/thread finished it.

• Challenge: Due to potentially unsynchronized clocks across different nodes (in

distributed memory), obtaining this exact "global" start and end time is often difficult.
 how to measure parallel program run-times correctly.
• A barrier ensures that all processes/threads reach the same point before
starting the measurement.

• While it doesn't guarantee simultaneous return, it provides a crucial

synchronization point.

• Global Maximum:

• Each process/thread calculates its my_elapsed time. A global reduction

operation (like Global_max or MPI_Reduce with MPI_MAX) is then used to
find the maximum of all these individual elapsed times.

• This maximum represents the time it took for the slowest process/thread to
complete its portion of the work, effectively capturing the total time.
Why timings vary between runs?
• Even if the Same hardware and Same number of threads
Run-times will vary slightly. Reasons:
• OS scheduling: The operating system may schedule/deschedule threads
differently.
• Background processes: Other programs (e.g., system services) compete for
CPU, memory, or cache.
• Memory/cache effects: Cache hits/misses and NUMA placement can differ.
 Variability in Timings and Reporting
Minimum Time:
• Running a program multiple times will almost certainly yield slightly different elapsed
times, even with identical inputs and systems.

• While reporting the mean or median might seem intuitive, it's generally unlikely for external
factors to make a program run faster than its best possible time. External interference (OS
activity, network jitter, etc.)

• Therefore, it's common practice to report the minimum time observed across multiple
runs.

Threads per Core:

• Running more than one thread per physical core can significantly increase timing
variability and introduce extra overhead due to system scheduling and descheduling.

• For this reason, it's generally recommended to run no more than one thread per physical
core when aiming for optimal performance and consistent timings.
Excluding I/O from Reported Timings:
• Since most parallel programs (unless specifically designed for high-performance I/O) do not
optimize for I/O operations, it's common practice to exclude I/O time (reading inputs,
printing final results) from the reported performance timings.

• The focus remains on the core computation time.

Key Points:
• Use a barrier → synchronize all processes before timing.
• Each process measures its time → take the maximum (slowest).
• Timings vary → report the minimum over multiple runs
• Avoid >1 thread per core → reduces variability and overhead
• Exclude I/O → focus on true computation performance.
GPU performance
Comparing performance: MIMD vs GPU
Scalability for GPUs
• MIMD scalability definition doesn’t apply to GPUs.
• A GPU program is scalable if a bigger GPU (with more cores, memory, etc.)
makes it run faster than on a smaller GPU.
• Amdahl’s Law for GPUs
• Amdahl’s Law can still apply if part of the program is inherently serial
and runs on a CPU.
• If fraction r of the code is serial, then:

• The serial fraction often depends on problem size

• So achievable speedup can increase as problem size grows.
• Even a small speedup on GPUs can be useful in practice, but often GPUs
achieve very large speedups
• Timing GPU programs