Derive the best value for grain-size to maximize parallelism

Assignment Help Basic Computer Science

Reference no: EM131030904

Implementing parallel loops using nested parallelism

Consider the following multithreaded algorithm for performing pairwise addition on n-element arrays A[1 .. n] and B[1.. n], storing the sums in C[1.. n]:

SUM-ARRAYS(A,B,C)

1 parallel for i = 1 to A. length

2 C[i] = A[i] + B[i]

a. Rewrite the parallel loop in SUM-ARRAYS using nested parallelism (spawn and sync) in the manner of MAT-VEC-MAIN-LOOP.

Analyze the parallelism of your implementation.

Consider the following alternative implementation of the parallel loop, which contains a value grain-size to be specified:
SUM-ARRAYS'(A,B,C)

1 n = A. length

2 grain-size = ? // to be determined

3 r = [n/grain-size]

4 for k = 0 to r - 1

5 spawn ADD-SUBARRAY(A,B,C, k . grain-size + 1, min((k + 1) . grain-size, n))

6 sync

ADD-SUBARRAY(A,B,C, I, j )

1 for k = i to j

2 C[k]= A[k]+ B[k]|

b. Suppose that we set grain-size = 1. What is the parallelism of this implementation?

c. Give a formula for the span of SUM-ARRAYS0 in terms of n and grain-size.

Derive the best value for grain-size to maximize parallelism.

Reference no: EM131030904

Questions Cloud

Discuss the performance differences between fhss and dsss : Discuss the performance differences between FHSS and DSSS - What considerations should be used when determining the chipping rate?

How much fabric does jessi need to buy : Jessi has 9 feet of blue fabric. To finish making her costume she needs one third of that amount of red fabric. The fabric store selld fabric by the yard. How much fabric does Jessi need to buy

Explain why differences between state constitutions : Explain why differences between state Constitutions and the U.S. Constitution made it more controversial for the national government to require all citizens to buy health insurance.

What is the area of the rug : The perimeter of a rectangular rigid 24 fee. The length of the rug is 1 2/5 it's width. What is the area of the rug

Derive the best value for grain-size to maximize parallelism : Suppose that we set grain-size = 1. What is the parallelism of this implementation?

Using media to advocate and influence : The Session Long Project entails you going through the process of influencing policymakers. Under the Connecticut Health Policy toolbox resource, read the section on "Writing to Policymakers." You will notice toward the bottom of that page, "sampl..

Major equipment breakdowns and excessive loss : Studies have shown that DU5 can operate only 3 1/2 years without major equipment breakdowns and excessive loss of efficiency. Therefore, DU5 is shut down every 3 1/2 years for cleaning, inspection, and repairs.

What the aged-payables and aged-receivables reports are : How they might be used to make management decisions from both the view of internal and external users - What the aged-payables & aged-receivables reports are.

What is the value of the chi-square statistic : What were the actual percentages of local high school students in each category? (Round answer to two decimal places) State an appropriate null hypothesis for this analysis. What is the value of the chi-square statistic

User Account

All Pages