Three Ways to Organize the Work

The exam draws a sharp line between three models of computing, and the difference is entirely about how the work is organized, not about how fast the hardware is.

• Sequential computing runs steps one after another, one at a time. Step two does not start until step one finishes.
• Parallel computing breaks a single task into parts that run at the same time on multiple processors, then combines the partial results into one answer.
• Distributed computing uses multiple computers or devices connected by a network to work on one problem together, which lets you tackle problems too large or too slow for any single machine.

Speedup: Measuring the Payoff

Parallel computing is only worth it if it actually saves time, and the exam measures that with speedup. The formula is short and you must know it:

speedup = (time to complete sequentially) / (time to complete in parallel)

If a job takes 60 seconds run sequentially and 20 seconds run in parallel, then speedup = 60 / 20 = 3. A speedup of 3 means the parallel solution finished 3 times as fast. Speedup is a ratio, so it has no units; a speedup of 1 would mean parallelizing gained you nothing.

Estimating Parallel Run Time

Most real tasks have a part that must run sequentially and a part that can be split across processors. A useful model for the exam:

parallel time = (sequential part) + (parallelizable part / number of processors)

Suppose a task takes 100 seconds total, of which 20 seconds must run sequentially and the other 80 seconds can be divided evenly. With 4 processors:

parallel time = 20 + (80 / 4)
             = 20 + 20
             = 40 seconds

Now push it: with 8 processors the parallel part becomes 80 / 8 = 10, so the total is 20 + 10 = 30 seconds. Doubling the processors from 4 to 8 did not cut the time in half; it went from 40 to 30, because the 20 second sequential part cannot be sped up at all.

Why Adding Processors Stops Helping

Speedup has a ceiling. Two forces cap it:

• The sequential portion of a task cannot be parallelized. Even with infinite processors, the parallelizable part shrinks toward zero but the sequential part stays fixed, so the total time cannot fall below that sequential floor.
• Splitting the work and combining the partial results adds overhead. At some point the cost of coordinating one more processor outweighs the tiny time it saves.

That is why each extra processor helps less than the one before it, a pattern called diminishing returns. In the run time example, 20 seconds is the hard floor: no number of processors gets the job below 20 seconds.

When Distributed Computing Wins

Some problems are simply too large for one machine, whether because of the amount of data, the memory needed, or the sheer volume of computation. Distributed computing connects many computers over a network so they can each handle a slice of the problem. Searching for signals in astronomy data, training on enormous datasets, and running a web service for millions of users all rely on distributed systems. The trade off is the same limit in a new form: coordinating separate machines across a network adds communication overhead, and any part that cannot be divided still gates the whole job.

How 4.3 Is Tested on the Multiple-Choice Exam

Topic 4.3 shows up on the MCQ section in a few very consistent shapes, so knowing them is worth several fast points.

• Compute a speedup. You are given a sequential time and a parallel time and asked for the speedup. Use speedup = sequential time / parallel time. Given 60 seconds sequential and 20 seconds parallel, the speedup is 60 / 20 = 3.
• Compute a parallel run time. You are given a sequential portion, a parallelizable portion, and a processor count. Use parallel time = sequential part + (parallelizable part / processors). Only the parallelizable part is divided by the processor count.
• Explain the limit. You are asked why adding processors stops helping. The credited reason is that a portion of the task must run sequentially and there is overhead to split and recombine work, so speedup is capped and extra processors give diminishing returns.
• Classify the model. You are asked whether a scenario is sequential, parallel, or distributed. Watch for multiple processors on one machine (parallel) versus multiple networked computers (distributed).

The most common wrong answer treats a task as fully parallelizable, assuming N processors always give an N times speedup or that doubling processors always halves time. Whenever a stem names a sequential portion, that portion is a floor the total time cannot drop below.