Chapter 27, Problem 1P

(a)

Program Plan Intro

To reword the parallel loop in SUM-ARRAYS utilizing nested within the manner of MAT-VEC-MAIN-LOOP.

Explanation of Solution

The implementation of the parallel loop that contains a worth grain-size to be specified is as follows:

SUM − ARRAYS’ (A, B, C)

  $n=A.length$

Grain − Size $=?//$ to be calculated

  $\begin{array}{l}r=ceil(n/grain-size)\\ fork=0tor-1\\ spawnADD-SUBARRAY(A,B,C,k*grain-size+1,min((k+1)*grain-size,n))\\ \end{array}$

Sync

ADD − SUBARRAY (A, B, C, i, j)

  $\begin{array}{l}fork=itoj\\ C[k]=A[k]+B[k]\end{array}$

Observing the algorithm SUM-ARRAYS (A, B, C) the parallelism is $O(n)$ since it’s work is $n\lg n$ and the therefore the span is $\lg n$ .

(b)

Program Plan Intro

To calculate the parallelism of the given implementation if we set grain-size=1.

Explanation of Solution

It can be concluded that each call to $\text{ADD}-\text{SUBARRAY}$ will return a sum of pair of numbers if the grain size = 1.

SUM − ARRAYS’ (A, B, C)

  $\begin{array}{l}n=floor(A.length/2)\\ ifn==0\\ C[1]=A[1]+B[1]\\ else\\ spawnSUM-ARRAYS(A[\mathrm{1..}n],B[\mathrm{1..}n],C[\mathrm{1..}n])\\ SUM-ARRAYS(A[n+\mathrm{1..}A.length],B[n+\mathrm{1..}A\mathrm{..}length],C[n+\mathrm{1..}A.length])\end{array}$

(c)

Program Plan Intro

To formulate the span of SUM-ARRAYS’ in terms of $n$ and grain-size and derived the most effective value worth for grain-size to maximize parallelism.

Explanation of Solution

Assume g be the grain-size. The runtime of the function is $\lceil \frac{n}{g}\rceil$ . The runtime of any spawned task is g. So, we'd like to attenuate

  $\frac{n}{g}+g$ .

To get this we will perform calculus and get a derivative, we have

  $0=1-\frac{n}{g^2}$ .

To further solve this, we set $g=\sqrt{n}$ . This minimizes the amount and makes the span $O(\frac{n}{g}+g)=O(\sqrt{n})$ and hence resulting in parallelism of $O(\sqrt{n})$ .