Get into groups and grab your blocks.
- Form groups of 3 or 4 students and move to the tables.
- Each group should have a tub of blocks. The blocks come in 9 different shapes.
- Your goal in every challenge is to sort the blocks into 9 neat piles by shape.
- You will run three timed challenges: one person sorts, then two, then your whole group.
Sequential vs. Parallel
Sequential
Steps are performed in order, one at a time. The next step cannot begin until the current one is done.
Parallel
Some steps are performed at the same time, with multiple workers acting simultaneously.
Speedup
Speedup measures how much faster a parallel solution runs compared to a sequential one, using the same amount of work.
Formula
Speedup =
sequential time
parallel time
Example
Sequential
60 seconds
Parallel
40 seconds
60 ÷ 40 = 1.5
The speedup of this parallel solution is 1.5.
Your Group's Speedup
Sequential
Your solo time
Parallel
Your team time
solo time ÷ team time = speedup
Prompt
What was your group's speedup in Challenge 2 (two-person sort)? Divide your best solo time by your best pair time.
Prompt
What was your group's speedup in Challenge 3 (full group)? Is there anything surprising about the result?
Speedup always hits a ceiling.
- Speedup is never equal to the number of processors added.
- Some portions of any algorithm cannot be parallelized and must still run one step at a time.
- Each additional processor helps a little less than the one before it.
- Eventually speedup reaches a hard limit, no matter how many processors you add. This relationship is described by Amdahl's Law.
