Basics of Parallel Programming: Unit-1
Basics of Parallel Programming: Unit-1
Basics of Parallel Programming: Unit-1
Basics of Parallel
Programming
Syllabus-Parallel & Distributed Computing
Syllabus-Parallel & Distributed
Computing
Syllabus-Parallel & Distributed
Computing
TEXT BOOKS:
1. Parallel Programming in C with MPI and OpenMP by M.J. Quinn, McGraw-Hill Science/Engineering/
Math.
2. Introduction to Parallel Computing, Ananth Grama, Anshul Gupta, George Karypis, Vipin
Kumar, By Pearson Publication
3. Distributed Computing, Sunita Mahajan and Seema Shah, Oxford University Press.
4. Distributed Systems: Concepts and Design, By G. Coulouris, J. Dollimore, and T. Kindberg, Pearson
Education.
5. Mastering Cloud Computing foundation and application Programming, Rajkumar Buyya,
Christan Vecchiola, S. Thamarai Selvi, MK
Reference Books:
Memory Input-Output
Control Unit
ALU
Communicate
Store data and
with
program
"outside world",
Execute
e.g.
program
Do arithmetic/logic • Screen
operations • Keyboard
requested by program • Storage
What is Parallel Computing?
• Traditionally, software has been written for serial
computation:
• To be run on a single computer having a single Central Processing
Unit (CPU);
• A problem is broken into a discrete series of instructions.
• Instructions are executed one after another.
• Only one instruction may execute at any moment in time.
Limitations of Serial Computing
• Limits to serial computing - both physical and practical reasons
pose significant constraints to simply building ever faster serial
computers.
– Advantages of Flynn
» Universally accepted
» Compact Notation
» Easy to classify a system (?)
– Disadvantages of Flynn
» Very coarse-grain differentiation among
machine systems
» Comparison of different systems is limited
» Interconnections, I/O, memory not
considered in the scheme
Classification based on memory arrangement
• Shared Memory
• Distributed Memory
Shared memory
Interconnection
I/O1 network
Interconnection
network
I/On
PE1 PEn
PE1 PEn M1 Mn
Processor P P
s 1 n
Shared memory -
Message passing -
multiprocessors
multicomputers
Shared Memory
• Shared memory parallel computers vary widely, but generally have
in common the ability for all processors to access all memory as
global address space.
• Disadvantages:
• Static networks
• Dynamic networks
Interconnection Networks for Parallel
Computers
• Interconnection networks carry data between processors
and to memory.
• Interconnects are made of switches and links (wires,
fiber).
• Interconnects are classified as static or dynamic.
• Static networks consist of point-to-point communication
links among processing nodes and are also referred to as
direct networks.
• Dynamic networks are built using switches and
communication links. Dynamic networks are also referred
to as indirect networks.
Static and Dynamic
Interconnection Networks
• The network interface may hang off the I/O bus or the
memory bus.
Data-parallel Function-parallel
architectures architectures
DP
s ILP MIMD
S s
• 1. e = a + b (Independent)
• 2. f = c + d (independent)
• 3. m = e * f (dependent)
if CPU = "a"
lower_limit := 1
upper_limit := round(d.length/2)
else if CPU = "b"
lower_limit := round(d.length/2) + 1
upper_limit := d.length
• The if clause differentiates between the CPUs. CPU "a" will read true
on the if; and CPU "b" will read true on the else if, thus having their
own values of lower_limit and upper_limit.
• Now, both CPUs execute foo(d[i]), but since each CPU has different
values of the limits, they operate on different parts of d simultaneously,
thereby distributing the task among themselves.
Data Level parallelism-Speedup
•
Data Level parallelism-Speedup
•
Task Level Parallelism
• Task parallelism is the characteristic of a parallel program
that "entirely different calculations can be performed on
either the same or different sets of data“.
• program:
if CPU="a" then
do task "A"
else if CPU="b" then
do task "B“
end if ...
end program
Process Coordination
Shared Memory v. Message Passing
Canonical syntax: