Scribd
Upload
7 views1 page

Parallel Computing in Cake Baking

The document discusses the limitations and possibilities of parallelism in baking cakes and performing binary search. It highlights that certain tasks can be executed in parallel, while others require restructuring to achieve speedup. Additionally, it emphasizes the importance of data-level parallelism and SIMD operations for optimizing computations.

Uploaded by

jujunoidea
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views1 page

Parallel Computing in Cake Baking

The document discusses the limitations and possibilities of parallelism in baking cakes and performing binary search. It highlights that certain tasks can be executed in parallel, while others require restructuring to achieve speedup. Additionally, it emphasizes the importance of data-level parallelism and SIMD operations for optimizing computations.

Uploaded by

jujunoidea
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

S-4 Chapter 6 Solutions

Finish baking Cake 3. Empty cake pan A.


The point here is that we cannot carry out any of these items in parallel
because we either have one person doing the work, or we have limited
capacity in our oven.
6.2.3 Each step can be done in parallel for each cake. The time to bake 1 cake, 2
cakes or 3 cakes is exactly the same.
6.2.4 The loop computation is equivalent to the steps involved to make one
cake. Given that we have multiple processors (or ovens and cooks), we can
execute instructions (or cook multiple cakes) in parallel. The instructions
in the loop (or cooking steps) may have some dependencies on prior
instructions (or cooking steps) in the loop body (cooking a single cake).
Data-level parallelism occurs when loop iterations are independent (i.e., no
loop carried dependencies).
Task-level parallelism includes any instructions that can be computed on
parallel execution units, similar to the independent operations involved in
making multiple cakes.

6.3
6.3.1 While binary search has very good serial performance, it is difficult to
parallelize without modifying the code. So part A asks to compute the
speedup factor, but increasing X beyond 2 or 3 should have no benefits.
While we can perform the comparison of low and high on one core, the
computation for mid on a second core, and the comparison for A[mid] on
a third core, without some restructuring or speculative execution, we will
not obtain any speedup. The answer should include a graph, showing that
no speedup is obtained after the values of 1, 2, or 3 (this value depends
somewhat on the assumption made) for Y.
6.3.2 In this question, we suggest that we can increase the number of cores (to
each of the number of array elements). Again, given the current code, we
really cannot obtain any benefit from these extra cores. But if we create
threads to compare the N elements to the value X and perform these
in parallel, then we can get ideal speedup (Y times speedup), and the
comparison can be completed in the amount of time to perform a single
comparison.

6.4 This problem illustrates that some computations can be done in parallel if
serial code is restructured. But, more importantly, we may want to provide
for SIMD operations in our ISA, and allow for data-level parallelism when
performing the same operation on multiple data items.

You might also like