Question

Robin, Bryan, Finchie, and Dan each have messages to send via carrier pigeon. There are three ordered stages to sending a message via carrier pigeon:: 1. 25 minutes of Writing the message 2. 10 minutes of Fanning the ink dry 3. 15 minutes of Catching and sending a pigeon Notes: There is only one pen to share There is also only one fan (without it the ink will never dry) There are multiple pigeons but only one can be caught at a time (They startle easily) Fanning must happen before catching a pigeon (or it will fly off.. startled) (hint: Draw timeline diagrams to calculate the total times etc)

How long does it take for all to send messages sequentially? How long does it take for all of them to send messages pipelined?

How and why does pipelining help with the throughput of entire workloads?

The workloads involved in sending 4 messages as described above, in comparison to sending 4 messages sequentially?

Can pipelining help reduce the latency of any one step in the 4 people sending a message scenario as described above? Show how the pipeline rate is limited by the slowest pipeline stage.

Answer 1

a)Following symbols are used in the timeline diagrams:

W-Writing,F-Fanning,C-Catching and Sending Pigeon.

Time Required for Sequential execution of the tasks(minutes)	25	10	15	25	10	15	25	10	15	25	10	15	Total Time=200minutes
Robin	W	F	C
Bryan				W	F	C
Finchie							W	F	C
Dan										W	F	C

In pipelined execution of the task, a pipeline stage will take maximum duration of the task executed in that stage.

Time Required for pipelined execution of the task(minutes)	25	25	25	25	15	15	Total Time=130minutes
Robin	W	F	C
Bryan		W	F	C
Finchie			W	F	C
Dan				W	F	C

B)When pipelining is used,throughput increases.This is because pipelining allows the tasks to be executed in parellel,without being wasting the time by sitting idle.For example,in the given case,once Robin has completed writing his message by using the only pen available,Bryan could use the pen while Robin moves on to Fanning the message.By exploiting the parallel execution,pipelining can reduce the total time required for the execution of the combined tasks and thus increase the overall throughput.

This is obvious from the given example.The workloads involved in sending 4 messages take only 130 minutes in comparison to the 200 minutes required in sending 4 messages sequentially.

C)Pipelining will not reduce the latency of any single pipeline stage.In fact,it may increase the latency of a single pipeline stage.This is illustrated in the above mentioned pipelined execution of the task table.

As shown in the timeline diagram given above,Robin requires minimum of 25 minutes for Fanning ,instead of the actual 10minutes required when messages are sent sequentially.Similarly,Robin requires minimum of 25minutes for catching and sending pigeon,instead of the actual 15minutes required when messages are sent sequentially.As it is evident from the example,pipelining will not reduce the latency of a single pipeline stage.

The pipeline rate is always limited by the slowest pipeline stage.As illustrated in the above pipeline stages,Robin takes 25 minutes each for,writing,Fanning and Catching and Sending Pigeon for sending his message for a total of 75 minutes,instead of the 50 minutes required while sending the message in sequential.This happens because the latency of each individual pipeline stages must wait until the slowest pipeline stage is completed before proceeding to the next pipeline stage.