How it works
Parallel computing divides work across multiple processors; distributed computing divides work across networked computers.
Decide which parts of a task can happen at the same time and which must wait for earlier results.
Common error
Communication overhead can reduce the benefit of dividing work.
Worked example
Compute an idealized parallel speedup while respecting sequential work.
Data / pseudocode
Sequential setup: 2 seconds
Independent tasks: 4 tasks of 3 seconds each
Processors: enough for all four tasks
Communication overhead: ignoredSerial execution takes 2 + 4*3 = 14 seconds. Ideal parallel execution takes 2 + 3 = 5 seconds, giving speedup 14/5 = 2.8. The setup cannot overlap under these assumptions, and real communication costs can increase the parallel time.
Exercises
4.4.1
An application has 4 seconds of sequential work and three independent 2-second tasks. Find serial time and ideal parallel time with three available processors.
Show solution
Serial time is 4 + 3*2 = 10 seconds. Ideal parallel time is 4 + 2 = 6 seconds. The sequential portion remains.
4.4.2
Why might dividing a tiny task among many remote machines be slower than doing it on one machine?
Show solution
Communication, coordination, data transfer, and combining results may cost more than the work saved. Parallelizable work is not automatically faster after distribution.