Question

Question Title: Q2E

Question:You are trying to bake 3 blueberry pound cakes. Cake ingredients are as follows:

1 cup butter, softened

1 cup sugar

4 large eggs

1 teaspoon vanilla extract

1/2 teaspoon salt

1/4 teaspoon nutmeg

1 1/2 cups flour

1 cup blueberries

The recipe for a single cake is as follows:

Step 1: Preheat oven to 325°F (160°C). Grease and flour your cake pan.

Step 2: In large bowl, beat together with a mixer of butter and sugar at medium speed until light and fluffy. Add eggs, vanilla, salt, and nutmeg. Beat until thoroughly blended. Reduce mixer speed to low and add flour, 1/2 cup at a time, beating just until blended.

Step 3: Gently fold in blueberries. Spread evenly in a prepared baking pan. Bake for 60 minutes.

6.2.1 Your job is to cook 3 cakes as efficiently as possible. Assuming that you only have one oven large enough to hold one cake, one large bowl, one cake pan, and one mixer, come up with a schedule to make three cakes as quickly as possible. Identify the bottlenecks in completing this task.

6.2.2 Assume now that you have three bowls, 3 cake pans, and 3 mixers. How much faster is the process now that you have additional resources?

6.2.3 Assume now that you have two friends that will help you cook, and that you have a large oven that can accommodate all three cakes. How will this change the schedule you arrived at in Exercise 6.2.1 above?

6.2.4 Compare the cake-making task to computing 3 iterations of a loop on a parallel computer. Identify data-level parallelism and task-level parallelism in the cake-making loop.

Short answer

6.2.1 The schedule for making three cakes as quickly as possible:

• Preheat the Oven

• Mix ingredients in a bowl for Cake 1

• Fill the cake pan with the contents of the bowl and bake Cake 1. Meanwhile, mix the ingredients for Cake 2 in a bowl.

• After cake 1 is baked, empty the cake pan. Fill the cake pan with the ingredients for cake 2 and bake cake 2. Meanwhile, mix the ingredients for Cake 3 in a bowl.

• After cake 2 is baked, empty the cake pan. Fill the cake pan with the ingredients for cake 3 and bake cake 3.

• Finish baking cake 3 and empty the cake pan.

The bottleneck of this task is having one oven with the capacity of baking only one at a time.

6.2.2 With 3 bowls, 3 cake pans, and 3 mixers, naming them as 1, 2, and 3 schedules are as follows:

• Preheat Oven

• Mix ingredients in bowl 1 for cake 1 and fill the cake pan 1 with the ingredients in bowl 1 and bake cake 1.

• Mix ingredients in bowl 1 for cake 2 and fill the cake pan 1 with the ingredients in bowl 1 and bake cake 2.

• Mix ingredients in bowl 1 for cake 3 and fill the cake pan 1 with the ingredients in bowl 1 and bake cake 3.

• Finish baking cake 3 and empty the pan 1

6.2.3 In the given case, all three cakes can be baked parallelly. Time is taken to bake all the cakes will be the same.

6.2.4 The loop computation is compared to the steps involved to make one cake. Multiple processors are given so that the instructions can be executed parallelly.

Data level parallelism occurs when loop iterations are independent.

Task level parallelism includes any instructions that can be computed on parallel execution units, are similar to the independent operations involved in making multiple cakes.

Step-by-step solution

Determine parallelism and its types.

In multicore and multiprocessors, parallel computing will allow several processors simultaneously execute multiple processes. The primary purpose of the parallel processing system is to enhance the processing capability and increase throughput. There are four types of parallelism bit-level parallelism, instruction level, task parallelism, and data-level parallelism.

Determine the schedule to make three cakes as quickly as possible.

6.2.1 The schedule for making three cakes as quickly as possible:

• Preheat the Oven

• Mix ingredients in a bowl for Cake 1

• Fill the cake pan with the contents of the bowl and bake Cake 1. Meanwhile, mix the ingredients for Cake 2 in a bowl.

• After cake 1 is baked, empty the cake pan. Fill the cake pan with the ingredients for cake 2 and bake cake 2. Meanwhile, mix the ingredients for Cake 3 in a bowl.

• After cake 2 is baked, empty the cake pan. Fill the cake pan with the ingredients for cake 3 and bake cake 3.

• Finish baking cake 3 and empty the cake pan.

The bottleneck of this task is having one oven with the capacity of baking only one at a time.

Determine the schedule to make three cakes as quickly as possible with additional resources.

6.2.2 With 3 bowls, 3 cake pans, and 3 mixers, naming them as 1, 2, and 3 schedules are as follows:

• Preheat Oven

• Mix ingredients in bowl 1 for cake 1 and fill the cake pan 1 with the ingredients in bowl 1 and bake cake 1.

• Mix ingredients in bowl 1 for cake 2 and fill the cake pan 1 with the ingredients in bowl 1 and bake cake 2.

• Mix ingredients in bowl 1 for cake 3 and fill the cake pan 1 with the ingredients in bowl 1 and bake cake 3.

• Finish baking cake 3 and empty the pan 1

Here all the additional resources are involving preparation alone. Since we have only one oven with limited capacity. So additional resources will not provide any better performance.

Determine the schedule to make three cakes as quickly as possible with a large oven that can accommodate all three cakes

6.2.3 In the given case, all three cakes can be baked parallelly. Time is taken to bake all the cakes will be the same.

The schedule will be rewritten as,

• Preheat Oven

• Mix ingredients in bowl 1 for cake 1 and fill the cake pan 1 with the ingredients in bowl 1 and bake cake 1

• Mix ingredients in bowl 2 for cake 2 and fill the cake pan 2 with the ingredients in bowl 2 and bake cake 2.

• Mix ingredients in bowl 3 for cake 3 and fill the cake pan 3 with the ingredients in bowl 3 and bake cake 3.

• Finish baking three cakes and empty all the pans parallelly.

Determine data-level parallelism and task-level parallelism in the cake-making loop.

6.2.4

The loop computation is compared to the steps involved to make one cake. Multiple processors are given so that the instructions can be executed parallelly.

For three cakes it takes three separate loops to bake and each step is dependent on the other. Likewise, in loop computation, the instructions may have dependencies on prior instructions in the loop body.

Data level parallelism occurs when loop iterations are independent.

Task level parallelism includes any instructions that can be computed on parallel execution units, are similar to the independent operations involved in making multiple cakes