Vera and her two siblings are working on decorating holiday cookies for an upcoming holiday party. To save time, Vera and her siblings decide to use Pipelining. Decorating the cookies requires three steps:
I: Ice the cookies (4 min)
W: Trace “JOY!” with icing (4 min)
S: Sprinkle the cookies with blue & white sprinkles (2 min)
Vera decided to map this pipelining process with a table. She makes the following attempts.
For each of the attempts below, denote whether the table is correctly following the pipelining algorithm. If not, state why and how to fix the error.
[20.1] Attempt #1
Person
0:00
2:00
4:00
6:00
8:00
10:00
12:00
Johnson Sibling 1
I
-
I
-
I
-
Johnson Sibling 2
W
-
W
-
Johnson Sibling 3
S
S
Solution:
Correct Attempt: The table follows key pipelining rules, such as assigning each worker one task, starting subsequent tasks only after the previous task has been completed, and correct representation of task time for each task.
Note: Even though the last ‘I’ task starting at time slot 8:00 is not needed or doesn’t contribute to a fully decorated cookie, this is still a correct pipelining table as it doesn’t violate any timing or task rules.
[20.2] Attempt #2
Person
0:00
2:00
4:00
6:00
8:00
10:00
12:00
Johnson Sibling 1
I
-
I
-
Johnson Sibling 2
W
-
W
-
Johnson Sibling 3
S
S
S
Solution:
Incorrect Attempt: Task S, that takes two minutes, has to be initiated only after Task I and W are completed. However, the S is listed in all three slots at 8:00, 10:00, and 12:00, and at slot 10:00, the second round of the two tasks I and W have not been completed. Therefore, this is incorrect pipelining, and to correct the answer, there should be no ‘S’ at timeslot 10:00 to signify that task S cannot be initiated as the previous steps are still finishing.
Note: You should not use task letters or dashes when there is a gap between the two S’s as those signify task initiation & work. Keep it blank to signify the task worker “waiting” as the previous tasks finish.
[20.3] Attempt #3
Person
0:00
2:00
4:00
6:00
8:00
10:00
12:00
Johnson Sibling 1
I
-
I
-
Johnson Sibling 2
-
-
W
-
W
-
Johnson Sibling 3
-
-
-
-
S
S
Solution:
Incorrect Attempt: In making a pipelining table, the dashes signify times when the task at hand is still ongoing. It is not used to denote a wait for the task to start or a wait for a previous task to end, thus all of the beginning dashes before tasks W and S start are incorrect. To correct the error, one can get rid of the dashes in rows W and S before the first instances of these tasks have been started.
Note: You should only use dashes to signify that an initiated task is ongoing at that time slot.
[20.4] Attempt #4
Person
0:00
2:00
4:00
6:00
8:00
10:00
12:00
Johnson Sibling 1
I
-
I
-
Johnson Sibling 2
W
-
W
-
Johnson Sibling 3
S
S
Solution:
Correct Attempt: The table follows key pipelining rules, such as assigning each worker one task, starting subsequent tasks only after the previous task has been completed, and correct representation of task time for each task.
Note: This table is simplified in the fact that even though Task I could have started again, as it would never end up in a final product being produced it is omitted in the table.
[20.5] Attempt #5
Person
0:00
2:00
4:00
6:00
8:00
10:00
12:00
Johnson Sibling 1
I
-
I
-
Johnson Sibling 2
W
-
-
Johnson Sibling 3
S
Solution:
Incorrect Attempt: In this table task ‘W’ is shown to last 6 minutes, when the problem description denotes the amount of time for “W” to be 4 minutes. It shows six because it starts from 4:00, and has dashes at both 6:00, and 8:00, declaring three 2-minute intervals for the task when it should be 2. To correct the error, you would only need one dash after W to signify 4 minutes.
Note: Writing the task letter (I, W, S) symbolizes both the start of the task and represents a time period of completion (ex: placing W at 4:00 states that it starts at 4:00 and by time slot 6:00 would have been worked on for 2 minutes).
[20.6] Attempt #6
Person
0:00
2:00
4:00
6:00
8:00
10:00
12:00
Johnson Sibling 1
I
-
I
-
I
-
Johnson Sibling 2
W
-
W
-
W
-
Johnson Sibling 3
S
S
Solution:
Incorrect Attempt: In pipelining, all the tasks follow in subsequent order. For example, you cannot write the letters on the cookie (W) without icing the cookie (I). In this table, it demonstrates that ‘W’ begins while task ‘I’ is still ongoing (which is denoted by the dash), therefore this wouldn’t be feasible. To correct this error, you would start ‘W’ after ‘I’ has completely finished, for example move the first instance of “W” to the time slot 4:00.
Note: Dashes signify that a task is still ongoing. Therefore, you should not start the subsequent task during a dashed time of a previous work, wait for the previous task to be completely finished (no dashes) to start the next task immediately.
[20.7] Aerie, Bea, and Cady want to wrap presents. To approach the task, they decide to use the Pipelining algorithm.
Wrapping the presents requires three steps:
P: Pick out presents & wrapping paper (2 min)
C: Cut wrapping paper (2 min)
W: Wrap and tape wrapping paper over presents (2 min)
Q1. Fill out the following scheduling table using pipelining:
Person
0:00
1:00
2:00
3:00
4:00
5:00
6:00
7:00
8:00
Aerie
Bea
Cady
Q2. In a 10-minute period, how many presents can the three wrap?
Solution:
Q1:
Person
0:00
1:00
2:00
3:00
4:00
5:00
6:00
7:00
8:00
Aerie
P
-
P
-
Bea
C
-
C
-
Cady
W
-
W
-
Q2: They can wrap 2 presents in 10 minutes.
*Note: This is the most concise representation of the table, other answers can be correct if they don’t violate necessary time and table design rules. We are showing an example below.
Q1: Alternative Correct Table Answers Examples
Person
0:00
1:00
2:00
3:00
4:00
5:00
6:00
7:00
8:00
Aerie
P
-
P
-
P
-
P
-
Bea
C
-
C
-
C
-
Cady
W
-
W
-
[20.8] You and your colleagues at Happy’s Bakery are tasked to bake the signature chocolate cakes.
Your boss suggests a Pipelining approach due to limited resources available at the bakery. Baking the cake requires the following steps:
P: Prepare chocolate cake batter (10 min)
B: Bake cake in oven (20 min)
I: Ice the cake with Happy Bakery’s signature icing (5 min)
T: Top the cake with sprinkles (5 min)
Q1. Fill out the following scheduling table using pipelining:
Worker
0:00
0:05
0:10
0:15
0:20
0:25
0:30
0:35
0:40
0:45
0:50
0:55
Worker 1
Worker 2
Worker 3
Worker 4
Q2. In this 1hr period, how many cakes can you and your colleagues make at Happy’s Bakery? If there were unlimited resources, is this method more efficient than baking the cakes using a parallelization approach?
Q1: Solution (one correct version):
Worker
0:00
0:05
0:10
0:15
0:20
0:25
0:30
0:35
0:40
0:45
0:50
0:55
Worker 1
P
-
P
-
Worker 2
B
-
-
-
B
-
-
-
Worker 3
I
I
Worker 4
T
T
*Note: This is the most concise representation of the table, other answers can be correct if they don’t violate necessary time and table design rules.
Q2: In an 1hr period, they can bake 2 cakes through pipelining. In comparing this to parallelization approach, we can make the following table:
:
Worker
0:00
0:05
0:10
0:15
0:20
0:25
0:30
0:35
0:40
0:45
0:50
0:55
Worker 1
P
-
B
-
-
-
I
T
P
-
B
-
Worker 2
P
-
B
-
-
-
I
T
P
-
B
-
Worker 3
P
-
B
-
-
-
I
T
P
-
B
-
Worker 4
P
-
B
-
-
-
I
T
P
-
B
-
With the table, we can see that in an hour, the workers at Happy’s Bakery can make 4 cakes - which is more than the pipelining approach. As we are assuming unlimited resources and thus each worker can afford to work on their own cake, the parallelization approach would be more efficient.
[20.9] Three workers are involved in making a 3-course meal. The tasks are:
P: Prep ingredients (10 minutes)
C: Cook (30 minutes)
L: Plating (10 min)
If each person does a task at a time (using pipelining), how much time will it take to make 3 meals?
Solution: 1 hr 50 minutes
Worker
0:00
0:10
0:20
0:30
0:40
0:50
1:00
1:10
1:20
1:30
1:40
1:50
Prep
P
P
P
Cook
C
-
-
C
-
-
C
-
-
Plating
L
L
L
Parallel Programming
[20.10] The __________ is a computer component that takes information from the programs that are currently running and decides which
program gets to use the CPU at any given moment.
Solution: Scheduler
[20.11] Explain the difference between multitasking and multiprocessing.
Example Solution:
Multitasking uses a scheduler to alternate between steps of different programs on a single CPU so they appear to run concurrently.
Multiprocessing uses multiple CPUs (or cores) to run multiple actions (processes) at the exact same time on a single computer.
Think of multitasking as you having one brain (CPU) and switching between different tasks (doing homework, scrolling TikTok, etc.) From the outside it may seem you are doing these tasks in parallel, but this is not true parallelism (sometimes we call it fake parallelism).
On the other hand, if you could have 2 brains (2 CPUs), you could truly do homework and scroll TikTok in parallel.
[20.12] Why do we say that parallel programming tends to be more difficult than regular programming? List all reasons.
Solution:
When writing or creating parallel programs, we must take into account many complicated factors including:
Data dependencies
Shared resources
Communication and synchronization between processes
[20.13] For the following statements, determine if they are True or False:
a) A single CPU can only run one action at a time.
b) Multitasking is a form of real simultaneous execution.
c) Multiprocessing allows multiple actions to run at the exact same time.
d) Throughput refers to the number of CPUs in a computer.
e) Increasing the number of transistors in the computer increases efficency.
Solution:
a) True
b) False
c) True
d) False
e) True
[20.14] Match each term below with the definition. There are more definitions than terms.
A. A method where multiple actions run at the exact same time on a single computer using multiple CPUs
B. The amount of work a computer can do during a set length of time
C. A component that decides which program gets to use the CPU
D. Running multiple programs at the same time ( whether it is real or fake)
E. When processes wait forever for resources held by each other
F. A core composed of circuits including a control unit, logic units, and registers
G. Splitting a single program so it runs on multiple CPUs at the same time
H. Increasing the number of transistors on a chip
I. Alternating between actions rapidly on one CPU
J. A storage device that permanently saves data
Solution:
Concurrency - D
Parallel programming - G
CPU - F
Scheduler - C
Throughput - B
Multitasking - I
Multiprocessing - A