C58 · Topic 4.3 · 40 minutes · CSN-2.A, CSN-2.B
Account for serial work and communication
By the end you can:
- Include an unavoidable serial portion in a runtime model.
- Distinguish parallel from distributed computing.
- Explain why communication and dependencies limit speedup.
Before this lesson: topics 3.17, 4.1.
- Sequential
- Tasks run one after another.
- Parallel
- Multiple processing units perform work at the same time.
- Distributed
- Multiple networked computing devices work on parts of a task.
- Speedup
- Sequential time divided by the parallel time for the same task under stated assumptions.
Understand
If part of a task must run sequentially, adding more processors cannot remove that part. With serial time S and perfectly divisible parallel work P, the ideal time on k processors is S + P/k, before communication overhead. This is a model assumption, not a universal measured runtime formula.
Distributed systems can combine machines and data from many locations, supporting scale and availability. Networks also introduce latency, partial failures and coordination needs. More machines can make a small task slower if communication dominates.
Worked example
An analysis has 4 seconds of unavoidable serial work and 12 seconds of ideally divisible independent work. Communication overhead is ignored first.
- Oneprocessor:4+12=16 seconds.
- Twoprocessors:4+6=10 seconds;speedup 1.6.
- Fourprocessors:4+3=7 seconds;speedup 16/7≈2.29.
- Even unlimited processors cannot remove the 4-second serial part. Adding 3 seconds of overhead to the four-processor run makes it 10 seconds.
Explore each concept
Choose a concept, change its inputs and follow the explanation. Each example models the stated rule or scenario; completing it is practice rather than evidence of mastery.
- Sequential, parallel and distributed
- Unavoidable serial portion
- Communication overhead and capacity
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Serial seconds (0–100)4Waiting
- Divisible parallel-work seconds (0–100)12Waiting
- Workers (1–8)4Waiting
- Communication overhead seconds (0–10)0Waiting
Ready to explore: Serial work limits parallel speedup
Why: Change an input, predict the first effect, then advance one step.
Try this: Change one input or choose another listed case. Predict the effect, reset and compare the states and governing rule.
Step through and experiment
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Input 16,4,3,3Waiting
- Input 20,1,0,1Waiting
- Input 30Waiting
Ready to experiment
Why: Predict the first change, then advance one step.
Try this: Put every task on one worker, then balance the loads and add overhead.
Check a misconception
Claim: Distributed and parallel mean exactly the same thing.
Distributed describes work across networked devices; parallel describes simultaneous processing. They can overlap but neither label alone specifies the other.
Guided practice
Under the ideal modelS 4,P 12, predict time on 3 processors and speedup.
Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.
Independent transfer
Explain why sending a tiny calculation across several networked machines may be slower than doing it on one device.
Exit check
What prevents unlimited speedup in this ideal model?
Write your reasoning before comparing with a classmate. If your teacher assigned this task, submit it through My classes to save your work and receive feedback.
Check yourself
Your practice so far
Check an answer to see its rationale.