Parallel Processing & Distributed Systems - Chapter 1: Introduction

ThoaiNam
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Introduction
– What is parallel processing?
– Why do we use parallel processing?

 Applications

 Parallelism
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 1 CPU

 Simple

 Big problems???
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Modeling
SimulationAnalysis
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 A grand challenge problem is one that cannot be 
solved in a reasonable amount of time with today’s 
computers

 Ex: 
– Modeling large DNA structures
– Global weather forecasting
– Modeling motion of astronomical bodies
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Power processor
– 50 Hz -> 100 Hz -> 1 GHz -> 4 Ghz -> ... -> Upper bound?

 Smart worker
– Better algorithms

 Parallel processing
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 The N2 algorithm:
– N bodies
– N-1 forces to calculate for each bodies
– N2 calculations in total
– After the new positions of the bodies are determined, the 
calculations must be repeated

 A galaxy: 
– 107 stars and so 1014 calculations have to be repeated
– Each calculation could be done in 1µs (10-6s)
– It would take 10 years for one iteration
– But it only takes 1 day for one iteration with 3650 processors
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Parallel Processing Terminology

 Parallel processing

 Parallel computer
– Multi-processor computer capable of parallel processing

 Throughput:
– The throughput of a device is the number of results it produces per 
unit time.

 Speedup
S = Time(the most efficient sequential algorithm) / Time(parallel
algorithm)

 Parallelism: 
– Pipeline
– Data parallelism
– Control parallelism
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 A number of steps called segments or stages

 The output of one segment is the input of other segment
Stage 1 Stage 2 Stage 3
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Applying the same operation simultaneously to 
elements of a data set
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
A B C
w4w3w2w1A B C w5
w2 w1
A B C w5 w2
A B C w4 w1
A B C w6 w3
1. Sequential execution
2. Pipeline
3. Data Parallelism
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Pipeline is a special case of control parallelism

 T(s): Sequential execution time
T(p): Pipeline execution time (with 3 stages)
T(dp): Data-parallelism execution time (with 3 processors)
S(p): Speedup of pipeline
S(dp): Speedup of data parallelism
2+1/232+2/32+1/332+1/22321S(dp)
2+1/22+5/112+2/52+1/32+1/42+1/721+4/51+1/21S(p)
12999666333T(dp)
1211109876543T(p)
30272421181512963T(s)
10987654321widget
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
0
0.5
1
1.5
2
2.5
3
3.5
1 2 3 4 5 6 7 8 9 10
S(p)
S(dp)
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 Applying different 
operations to different 
data elements 
simultaneously
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM

 An algorithm is scalable if the level of parallelism increases 
at least linearly with the problem size.

 An architecture is scalable if it continues to yield the same 
performance per processor, albeit used in large problem 
size, as the number of processors increases.

 Data-parallelism algorithms are more scalable than control-
parallelism algorithms