What are some good real-life examples of pipelining, latency, and throughput?

Question

The textbook Computer Organization and Design by Hennessy and Patterson uses a laundry analogy for pipelining, with different stages for:

• washing
• drying
• folding
• putting away

The analogy is a good one for college students (my audience), although the latter two stages are a little questionable.

Latency, of course, is the time for a single load to go through all 4 stages, while throughput is the rate at which loads are completed. Without pipelining or parallelism, throughput is the reciprocal of latency.

I'd like to present additional analogies that might be helpful to my students in understanding latency and throughput. I thought of comparing the latency for one student to go through college (4 years) with the rate at which the college graduates students (many per year) but realize there's parallelism in a college (multiple students in each year) in addition to pipelining (beginning to teach new students before old students have graduated).

What are some good analogies for pipelining and the relationship between throughput and latency?

Answer 1

As usual, useful network analogies are buses:

A bus leaving the central station sets out on route to its first intended stop.
That's the first step. The process of the bus's route from the central station and back to it (the entire route) is a pipeline.

In this analogy, latency is the time it takes the bus to get back to the central station, and throughput would be that maximum number of times a bus completed its route (in a given timeframe - maybe 1 day).

The latency might lengthen due to traffic (literally ;)) or due to packet load - high number of passengers boarding at some stations would cause the bus to be late to the following station, and so also increasing the time it takes to complete the route.

In this example, the throughput is not exactly the reciprocal of the latency. This can also convey the idea that messages can be delayed at the central station (for various reasons - compression etc.), and that counts towards the throughput but not the latency.

Every busride ends exactly where it started; every bus ride starts when the respective bus route is complete (bus number 9 can't start until bus number 9 completes its route). Again, there is some degree of parallelism, because some bus lines have multiple buses going about, but let's ignore that, and focus on bus lines in small cities, or those with short routes.

Answer 2

Production lines in factories, eg. for assembling cars.

In theory, a single person could assemble a whole car from scratch. But they would need to memorize a lot of different steps and it would be hard for them to find an ideal working mode. For example, they might need very different clothes and tools for assembling the engine and painting the body. What is worse, the only way of speeding up production is assembling cars in parallel. Parallelising tasks this way does not scale well in the real world (eg. think of the logistics for getting the parts to every worker as you keep growing the number of parallel workers). In software and hardware design this also applies: (Task-)Parallelism introduces significant additional complexities into a system, so we can't blindly rely on it for scaling up indefinitely.

What factories do instead is, they break the assembly process down into distinct steps and then have each worker specialize in a specific step. This allows them to quickly learn how to complete that singular step as efficiently as possible.

In software and hardware design this is also true: Finding the most efficient design for a single, self-contained step is way easier than optimizing a big system that does everything.

Now, breaking your assembly line into its parts has its caveats: You introduce additional overhead by eg. having to move the car from one assembly station to the next. So a single car might in the end still take longer to move through the assembly line than if one person did the assembly all by themselves. But we can compensate for that by making use of the fact that the steps are independent: As soon as the first car leaves my assembly station, I immediately start working on the next one, even though the previous car still has to reach the end of the assembly line before it's completed. The latency is the total time it takes for a car to pass through the complete assembly line. Throughput is how many cars the assembly line can complete per hour. Once the pipeline is full, this is determined by the time of the slowest assembly step - the clock rate of the line.

The challenge in designing such a system is to find the sweet spot for how much work we can fit into a single step. If a single step gets too big, it again gets difficult to optimize. If it gets too small, the overhead of managing the line might be bigger than the actual work required for the assembly. But we also need to ensure that all tasks are about the same size: If a worker is able to complete a task significantly quicker than the clock rate, they will be forced to idle for the rest of their time until the next car is delivered to their station. All of this applies 1:1 to software/hardware design.

Now, in our production line scenario we have a pretty ideal situation, as the different cars can all be assembled in isolation. If someone makes a mistake in assembling car A, that affects only car A but none of the others (unless the mistake somehow forces you to stop the complete production line). In hardware or software this is often untrue. For instance, deciding whether you take a branch in a CPU instruction pipeline often depends on the result of a previous operation. However, if that operation has not reached the end of the pipeline yet, we might not have that information available. So we have to delay the execution of the branch until that information becomes available (stall the pipeline). If we have a lot of those dependencies (often referred to as hazards), we might lose all our pipeline parallelism again and our throughput approaches the latency of the pipeline.

Answer 3

I like the image of a flute player for illustrating parallel processing of several simultaneous flows:

• reading the score ("buffering" enough notes before playing them)
• moving fingers (planning a few notes ahead while following a set rhythm)
• managing breath (refilling the lungs regularly while not interfering with the music)

They all occur in parallel, each with its own set of constraints, and are all interdependent.

I find the notions of latency (reading enough notes and breathing in enough air to keep playing), pipelining (finger positioning requires score reading) and throughput (following the tempo) quite intuitive.

Answer 4

I think that, in order to not overcomplicate the issue, a good clarifying example would be satellite TV. STV broadcasting can transmit quite a lot of information at once, which means it has high throughput, and you see that in the fact that STV services like Dish offer a lot of channels.

On the other hand, beaming the information to a satellite in orbit and back creates a certain level of interference (which must be corrected) and travel delay, which means that this technology suffers from high latency. This leads to the notorious jumpiness and screen artifacts (delay in correcting data) that STV often suffers from.

This is a pure example, in which the throughput does not itself create a limit that increases latency, or vice versa, so the two can be seen completely separately.

If you want a case where the two interact, then the movement of cars in high traffic would be a suitable example instead. Its interesting to note that, when road usage is saturated, traffic moves more slowly before a merge and more quickly after it. That is simply because the throughput before and after is the same, but before the merge, that throughput is divided by more lanes, so each individual lane gets less movement per second - ie, each lane has a higher latency.

Likewise, in clear traffic, latency (speed limit) can limit the number of cars that pass a given line per second, so latency can also limit throughput.

Answer 5

One which most of your students are likely to have seen, and some of them may have participated in: production of an order in a fast food restaurant.

• Cashier takes order
• Burger is prepared and placed in the rack
• Drink is prepared, brought to the counter, and placed on the tray
• Chips* are bagged, brought to the counter, and placed on the tray
• Burger is fetched from the rack, brought to the counter, and placed on the tray
• Payment is collected
• Customer collects tray

There's pipelining, parallelisation, maybe even branch prediction (cashier fetches tray before asking whether it's to eat in or take away).

* Speakers of en-US: read "fries".