Transcript Pathway Introduction: Information Technology

Parallel Processing
Sharing the load
Inside a Processor
• Primarily Crystalline Silicon
• 1 mm – 25 mm on a side
• 100 million to billions of
transistors
Chip in Package
– current “feature size” (process)
~ 14 nanometers
• Package provides:
– communication with motherboard
– heat dissipation
Circuits
Moore's Law
• Number of transistors in
same area doubles
every 2 years
• Net effects:
Processing power
doubles approximately
every 18 months
Exponential Growth
• Doubling is exponential growth
Year
Speed
0
1.5
3
4.5
6
7.5
1
2
4
8
16
32
Adapted from UC Berkeley "The Beauty and Joy of Computing"
9
10.5
12
64 128 256
Moore's Law
• If Moore's Law applied to
airplanes:
– New York to Paris in 1978
$900 & 7 hours
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Moore's Law
• If Moore's Law applied to
airplanes:
– New York to Paris in 1978
$900 & 7 hours
– Now should be
$0.01 & < 1 second
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Power Density Prediction circa 2000
Power Density (W/cm2)
10000
Sun’s Surface
Rocket Nozzle
1000
Nuclear Reactor
100
Core 2
10
4004
8008
8086
8080 8085
1
1970
286
1980
Hot Plate
386
P6
Pentium® proc
486
1990
2000
Year
Source: S. Borkar (Intel)
Adapted from UC Berkeley "The Beauty and Joy of Computing"
2010
MultiCore
• Multicore : Multiple processing cores on one chip
– Each core can run a different program
Going Multi-core Helps Energy Efficiency
• Speed takes power,
Power = heat
– Can run at 80% speed with
50% power
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Moore's Law Related Curves
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Moore's Law Related Curves
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Issues
• Not every part of a problem scales well
– Parallel : can run at same time
– Serial : must run one at a time in order
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Speedup Issues
• 5 workers can do parallel portion in 1/5th the time
• Can't affect serial part
Time
Parallel portion
Serial portion
1
5
Number of Cores
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Speedup Issues
Time
Parallel portion
Serial portion
1
2
3
4
5
Number of Cores
• Increasing workers provide diminishing
returns
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Amdahl’s Law
• Amdahl’s law :
Predicts how many times faster N workers can
do a task in which P portion is parallel
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Amdahl’s Law
• 60% of a job can be made parallel. We use 2
processors:
• 1.43x faster with 2 than 1
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Amdahl’s Law
• 60% of a job can be made parallel. We use 3
processors:
• 1.67x faster than with 1 worker
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Amdahl’s Law
• Always have to do 40% of the work in serial
• With infinite workers:
𝑆𝑝𝑒𝑒𝑑𝑢𝑝 𝑁 =
1
0.60
1 − .60 +
∞
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Amdahl’s Law
• Always have to do 40% of the work in serial
• With infinite workers:
𝑆𝑝𝑒𝑒𝑑𝑢𝑝 𝑁 =
1
1−.60
0.60
+
∞
=
1
0.40 +0
Only 2.5x faster!
Adapted from UC Berkeley "The Beauty and Joy of Computing"
= 2.5
Limits
• Max speedup limited by parallel portion of
code:
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Speedup Issues : Overhead
• Even assuming no sequential portion, there’s…
–
–
–
–
–
–
–
Time to think how to divide the problem up
Time to hand out small “work units” to workers
All workers may not work equally fast
Some workers may fail
There may be contention for shared resources
Workers could overwriting each others’ answers
You may have to wait until the last worker returns to
proceed (the slowest / weakest link problem)
– There’s time to put the data back together in a way that
looks as if it were done by one
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Concurrency
• Concurrency : two things happening at the
same time
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Concurrency
• Concurrency : two things happening at the
same time
• Many things are hard to share:
– Printers
– Shared memory
Adapted from UC Berkeley "The Beauty and Joy of Computing"
No Synchronization
• Race Condition : unpredictable result based
on timing of concurrent operations
Adapted from UC Berkeley "The Beauty and Joy of Computing"
No Synchronization
• X starts as 5, four possible answers:
Case 1
Case 2
Case 3
Case 4
A runs, x = 15
B runs, x =16
B runs, x = 6
A runs, x = 16
A gets x (5)
B gets x (5)
A adds 10 (has 15)
B adds 1 (has 6)
A stores x = 15
B stores x = 6
A gets x (5)
B gets x (5)
A adds 10 (has 15)
B adds 1 (has 6)
B stores x = 6
A stores x = 15
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Locks
• Can prevent concurrency problems with locks:
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Deadlock
• But if we have…
– Mutual exclusion : can't share resources
– Hold and wait : you can reserve one resource
while waiting on another
– No preemption : can't remove a resource from a
process's control
• Can have deadlock…
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Deadlock
• Workers A and B both want to use locked
resources X and Y:
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Breaking Deadlock
• Must remove one condition
– Mutual Exclusion
• Find a way to share
– Hold and Wait
• If you wait you must give up other resources
– No preemption
• Take back a resource someone has claimed
Adapted from UC Berkeley "The Beauty and Joy of Computing"
Why Parallelism?
• We have no choice!
– Multicore processors are a plan B, not a triumph
for parallelism
• Parallel processing takes new
–
–
–
–
Architectures
Algorithms
Structures
Languages
Adapted from UC Berkeley "The Beauty and Joy of Computing"