Transcript Parallel processing

Week 8 - Wednesday



What did we talk about last time?
Moore's law
Complex decisions
 Boolean operators not, and, and or
 Multiway decisions with if-elif-else
Even though computers are fast, they are never as
fast as we want
 Parallel processing is the field within CS focused on
solving hard problems with multiple computers
 Often it follows this pattern:





One computer breaks a problem into pieces
It sends the pieces to the other computers
Each computer completes its work independently
The computers send back their results to the master
computer
 It assembles the partial answers into a final answer

Regular (non-parallel) computing is sequential
processing

Sometimes the communication pattern is
more complex than described on the previous
slide
 Multiple computers have to communicate with
each other
 There is back and forth communication


Communication is essentially the enemy of
parallel processing
Time spent on communication is time wasted

Shared memory parallelism
 Different processors can access each other's memory
directly
 Explicit messages don't need to be sent
 Problems happen when two processors manipulate
the same memory in an inconsistent way

Message passing parallelism
 All data is sent as explicit messages
 It's harder to program a message passing system
 But the results are more likely to be correct


The goal of parallel processing is speedup
Speedup is defined as
𝑡𝑖𝑚𝑒𝑠𝑒𝑞𝑢𝑒𝑛𝑡𝑖𝑎𝑙
𝑠𝑝𝑒𝑒𝑑𝑢𝑝 =
𝑡𝑖𝑚𝑒𝑝𝑎𝑟𝑎𝑙𝑙𝑒𝑙



In other words, how many times faster is
doing the job in parallel?
If you have n computers, what's the best
speedup you can hope for?
Is it ever possible to have a speedup less than
1?
Communication time is usually what stops speedup
from being very good
 Another problem is that only part of a problem is
parallelizable
 Amdahl's law states that if p is the fraction (between 0
and 1) of the program that can be parallelized, then
1
𝑠𝑝𝑒𝑒𝑑𝑢𝑝 <
1 −𝑝
 Let's say that 75% of your program can be parallelized

 Your speedup will never be greater than 4, even if you used
1,000,000 computers to solve your problem

Parallel processing used to be something that
only research scientists talked about
 Owning multiple computers was expensive



Now, computers are cheap and virtually all
desktops and laptops have multicore
processors
A multicore processor has several
independent processors inside
Multicore processors bring the possibility of
parallel processing to the common person

Desktop and laptop CPUs commonly have 2, 4,
6, or even 8 cores
 Some expensive, research chips have hundreds


Graphics card GPUs often have 8 or 10 cores
(with as many as 24 stream processors per core)
Not all cores are created equal
 Some can only do special tasks

Architectures that contain two or more different
kinds of cores are sometimes called many core
instead of multicore


You might think that programming in Python is hard
Writing a program that runs in parallel is considered
one of the hardest tasks for a programmer
 Getting multiple computers to talk to each other usually
requires complex instructions
 Some bugs will be unpredictable, happening only when
the timing between different computers is just right
 Even if you do everything right, you might not get any
speedup

No one has a good system for writing parallel
programs




Computers are fast, but you need to process
a lot of data to get a sense of how fast they
are
Python provides us with strings for text data,
which are really a special kind of list
Python also provides general lists that can
hold anything (even other lists)
Since lists can hold many items, it is common
to use loops (especially for loops) to deal
with them

Strings hold text
 They are lists of characters (letters, digits,
punctuation, etc.)

A string literal in Python is text with either
single or double quotes around it
line = "Stop, collaborate, and listen!"
countdown = 'Launching in 5, 4, 3, 2, 1... Blast off!'

It doesn't matter which you use, but you can't
mix them in one string

You can use + to concatenate two strings
together (to get a third string that is both of
them stuck together)
place = "boon" + "docks"
print(place) #prints boondocks

You can use * to get repetitions of a string
comment = "yeah " * 3
print(comment) #prints yeah yeah yeah

You can use the len() function to get the length of a
string
author = "Thomas Pynchon"
print( len(author) ) #prints 14
You can use square brackets to get a particular character
in the string
 Indexes start at 0

 The first character in a string is at 0, the last is at its length - 1
movie = "Dr. Strangelove"
print(movie[4]) #prints S

If you want to get more than one character
from a string, you can use the slice notation
 Two numbers with a colon (:) in between
 The first number is the starting point, the second
number is the location after the ending point
 If you subtract the first from the last, you'll get the
length of the result
adjective = "dysfunctional"
noun = adjective[3:6] #noun contains "fun"
You can think of a string as a list of characters
Python provides a way to make lists of other
things too
 To make a list, you can put a collection of objects
inside square brackets


days = ["Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday", "Sunday"]

They can even be different types
stuff = ["Danger!", 3, True, 1.7]

As with strings, use square brackets and a
number to access an element in the list
days = ["Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday", "Sunday"]
bleh = days[0] #contains "Monday"


Like strings, elements are numbered from 0
to the length – 1
You can use the len() function to get the
length of a list
count = len(days)
#contains 7

You can also change the elements in a list
using the square bracket notation
birds = ["Duck", "Duck", "Duck"]
birds[2] = "Goose"
print(birds) #prints ['Duck', 'Duck', 'Goose']



This is one of the bigger differences between
strings and general lists
You cannot change the characters in a string
You have to make a new string

Just like strings, you can use the slice notation to
get a copy of part of a list
days = ["Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday", "Sunday"]
weekend = days[5:7]
print(weekend) #prints ['Saturday', 'Sunday']

There are shortcuts too
 Python assumes 0 if you leave off the first number
 It assumes the length if you leave off the last number
weekdays = days[:5] #Monday through Friday

A for loop can be used to iterate over all the
elements in a list
days = ["Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday", "Sunday"]
for day in days:
print( day ) #prints each day on a line

Since a string is a special kind of list, you can
iterate over the characters in them too
word = "HEY"
for letter in word:
print( letter ) #H E Y on separate lines



Write a function that takes a list as an argument
and prints out its contents in reverse order
One approach is to access each element with an
index in reverse order
Of course, there's also a built-in reverse()
method that reverses a list (but doesn't work on
strings)
words = ["green", "eggs", "and", "ham"]
words.reverse()
print(words) #['ham', 'and', 'eggs', 'green']




Write a function that takes a string as an
argument and prints out its contents in
reverse order
We could use the function we've already
written
But we could also build a new reversed
version of the string instead
There's a super crazy (but efficient) way to
make a reversed string by slicing the string
backwards, but I'm not going to show it


More list examples
Lab 8



Work on Project 3
Keep reading Python Chapter 5
Think about what you want to do for your
Final Project