Question

Task 5 - Pipelining
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)

a) (4 + 7 = 11 marks) How long does it take for all to send messages sequentially?
How long does it take for all of them to send messages pipelined?

b) 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?

c) (2+3 marks) 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) How long does it take for all to send messages sequentially?
    How long does it take for all of them to send messages pipelined?

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

Time (minutes)

25

10

15

25

10

15

25

10

15

25

10

15

Total Time = 200 minutes

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 tasks

Time (minutes)

25

25

25

25

15

15

Total Time = 130 minutes

Robin

W

F

C

Bryan

W

F

C

Finchie

W

F

C

Dan

W

F

C

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

When pipelining is used, throughput increases. This is because, the pipelining allows the tasks to be executed in parallel, 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) 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.

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 following pipelined execution of the tasks:

Time required for pipelined execution of the tasks

Time (minutes)

25

25

25

25

15

15

Total Time = 130 minutes

Robin

W

F

C

Bryan

W

F

C

Finchie

W

F

C

Dan

W

F

C

As shown in the timeline diagram given above, Robin requires minimum of 25 minutes for Fanning, instead of the actual 10 minutes required when messages are send sequentially. Similarly, Robin requires minimum of 25 minutes for Catching and Sending Pigeon, instead of the actual 15 minutes required when messages are send 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.