Parallel Programming
Priyadarshini Priya
Supercomputing Section
Computer Division, BARC
Email: pdpriya@[Link]
Sequential Processing
On a Single Processor
Computer
Parallel Processing
Shared Memory Parallel
Processing on a
Multicore/Multiprocessor
system using OpenMP
Distributed Memory
Parallel Processing on a
multi-node system using
MPI
Our Aim is
Distribute the load of compute intensive task among
multiple processors to reduce the computational time
Process v/s threads:
Process: A process is an independent program in execution.
Characteristics:
Has its own memory space
Is isolated from other processes
Heavier to create and manage
Communication with other processes requires IPC mechanisms
Thread: A thread is the smallest unit of execution within a process.
Characteristics:
Shares the same memory space with other threads in the same process
Lightweight and faster to create
Communication is easy (shared variables)
A failure in one thread can affect the entire process
Important components of a parallel computer
Any parallel computer mainly consists of
Compute Node
Processor (e.g. Core i7, Xeon, Athlon, Opteron)
CPU Board (e.g. Intel/Supermicro motherboard)
Full fledged sequential computer (eg. PC, workstation, rackmount
server)
Interconnection Network
Bus (eg. Multibus, VME)
Switch (eg. Crossbar, Omega)
Static network of different topologies
Conventional network (eg. Ethernet, Infiniband)
HPC Architectures
HPC architectures try to maximize performance by
simultaneously employing many Processing Elements
(CPUs) together to solve a given task.
In general these parallel processing machines can
be classified into two main groups based on how the
CPUs view the available memory:
Shared‐Memory machines
Distributed‐Memory machines
Shared Memory Machines
Shared‐memory systems have multiple CPUs, connected
through a fast interconnect on motherboard, all of which
share the same memory and controlled by a single OS.
Supercomputing Section, Computer Division, BARC
Advantages and disadvantages of
shared memory architecture
Advantages:
Easy to program
Data sharing between tasks is both fast and uniform due
to the proximity of memory to the CPUs
Disadvantages:
Lack of scalability – memory CPU link becomes
bottleneck
Programmer responsible for proper synchronization
among the processes to avoid race conditions.
Data Race Condition
Distributed memory machines
Distributed‐memory systems have multiple CPUs each with
their own local memory and own OS, connected through
an external network.
Supercomputing Section, Computer Division, BARC
Advantages and disadvantages of
distributed memory architectures
Advantage: Highly scalable
Disadvantage: Difficult to program
Data sharing among tasks is explicit
DISTRIBUTED MEMORY MODEL SHARED MEMORY MODEL
Suitable for coarse grain parallelism Suitable for fine grain parallelism
Scalable to large number of processors
Limited to small number of
processors due to memory access
problem
Communication delay is larger due to Communication delay is less due to
loose coupling of processors tight coupling of processors
Sequential vs. Parallel Programming
Conventional programs are called sequential (or serial)
programs since they run on one cpu only as in a
conventional (or sequential) computer
Parallel programs are written such that they get divided
into multiple pieces, each running independently and
concurrently on multiple cpus.
Converting a sequential program to a parallel program
is called parallelization.
Example Parallel Program (1)
A B C
0 0 0
+ =
99 99 99
A, B and C are one dimensional arrays
for i = 0 to 99 do
c(i) = a(i) + b(i)
Example Parallel Program (2)
A B C
0-24 0-24 0-24
25-49 25-49 25-49
+ =
50-74 50-74 50-74
75-99 75-99 75-99
It is possible to split the arrays into four pieces
and sum them concurrently on four processors
Terms and Definitions
Speedup of a parallel program:
= Time taken on 1 cpus / Time taken on ‘n’ cpus
Ideally Speedup should be ‘n’
Eg if a program takes 9 hours on 1 cpu and 1 hour
on 10 cpus
Speedup = 9/1 = 9
Ideal speedup should be 10
Terms and Definitions
Efficiency of a parallel program:
= Speedup / No. of processors
Ideally efficiency should be 1 (100 %)
Eg if a program takes 9 hours on 1 cpu and 1
hour on 10 cpus
Speedup = 9/1 = 9
Efficiency = 9/10 = 0.9(90%)
Ideal speedup should be 10
Ideally efficiency should be 1(100%)
Problem areas in parallel programs
Practically, speedup is always less than ‘n’ and
efficiency is always less than 100%
Reason 1: Some portions of the program cannot be
run in parallel (cannot be split)
Reason 2: Data needs to be communicated among
the cpus. This involves time for sending the data and
time in waiting for the data
The challenge in parallel programming is to suitably
split the program into pieces such that speedup and
efficiencies approach the maximum
Challenges in HPC application
development
HPC technologies try to overcome the limitations of single
processor memory size by coordinating many single CPU’s to
work together to solve a task.
HPC Software has to be written to make use of multiple
processors efficiently
Programming Paradigm and algorithm may vary according to
the architecture of the system
Threaded Model : Suitable for shared memory systems
Message Passing Model: For distributed memory systems
Hybrid Model: For combination of shared and distributed
memory systems
Challenges in HPC application
development
Process of parallelization not trivial
Identify portions of the task that can be performed
independently
Data decomposition and dependency
Communication patterns
Scalability issues
Several parallel program development tools
available, but still lots of effort from programmer
is needed
Parallel Program Development
Understand the problem and the algorithm
Whether the problem is parallelizable or not
Identify the program’s hotspots
Places where maximum work is done and time spent
Profilers can help in identifying these hotspots
Concentrate parallelization efforts in these places
Identify bottlenecks in the program
Areas that are slow or unparallelizable
Restructure the program to reduce such areas
Identify inhibitors to parallelization such as data
dependency
Investigate other algorithms with less dependency
Example: Restructuring Code
a[0]=1; a[0]=1;
for(i=1;i<n;i++) for(i=1;i<n;i++)
a[i] = a[i-1]+1; a[i] = i+1;
Code can’t be parallelized Solution: Restructure the code
ith loop is dependent on (i-1)th
loop
Eg Unless value of a[5] is
calculated a[6] can’t be
calculated
Therefore, this loop can’t run in
parallel
Parallel Program Development
Partitioning
Break the problem into discrete "chunks" of work
that can be distributed to multiple tasks. This is
known as decomposition or partitioning.
Domain Decomposition: Partitioning of data
between tasks
Functional Decomposition : Partition of the
algorithm
Parallel Program Development
Dependencies
Main inhibitors to parallelism
A control dependence exists between program
statements when the order of statement execution
affects the results of the program.
Certain events such as I/O operations, need to be ordered
A data dependence results from multiple use of the
same location(s) in storage by different tasks.
One task cannot execute before some data it requires is
generated by another task
Every dependency results in communication or
synchronization between tasks
Parallel Program Development
Communication
Decide when tasks will communicate and how frequently.
Cost of communication
Machine cycles and resources that could be used for computation
are instead used to package and transmit data.
Communications frequently require some type of synchronization
between tasks, which can result in tasks spending time "waiting"
instead of doing work.
Competing communication traffic can saturate the available
network bandwidth, further aggravating performance problems.
Scope of communication
Unicast, Multicast and broadcast
Synchronous/Asynchronous communication
Parallel Program Development
Load Balancing
Load balancing refers to the practice of distributing work
among tasks so that all tasks are kept busy all of the time.
Load balancing is important to parallel programs for
performance reasons. Slowest task decides the overall
performance.
Equal distribution of data among tasks
Dynamic Work Assignment
Parallel Programming Methods
• Automatic Parallelization
• Using vectorization feature of modern compilers
• Simple loops in programs are unrolled and iterations are executed parallelly
over multiple threads
• Parallel Programming using Parallel APIs
• Use ready-made parallel routines from numerical/math libraries, e.g. Intel’s
MKL, AMD’s AOCL
• Incremental Parallelization: Compiler directive based parallelization using
OpenMP
• Explicit Parallelization: Full burden of parallelization on programmer, e.g.
partitioning, synchronization, identifying and resolving dependencies, etc
using MPI
Thank You