# Parallel computing homework | parallel computing

1. For each of the following code segments, use OpenMP pragmas to make the loop parallel, or

explain why the code segment is not suitable for parallel execution.

a. for (i = 0; i < (int) sqrt(x); i++) {

a[i] = i + 12;

if (i < 10) b[i] = a[i];

}

b. flag = 0;

for (i = 0; (i < n) & (!flag); i++) {

a[i] = 2.8 * i;

if (a[i] < b[i]) flag = 1;

}

c. for (i = 0; i < n; i++) {

a[i] = fun(i);

}

d. for (i = 0; i < n; i++) {

a[i] = fun(i);

if (a[i] < b[i]) b[i] = a[i];

}

e. for (i = 0; i < n; i++) {

a[i] = fun(i);

if (a[i] < b[i]) break;

}

f. product = 0;

for (i = 0; i < n; i++) {

product += a[i] * b[i];

}

g. for (i = j; i < 3 * j; i++) {

a[i] = a[i] + a[i-j];

}

h. for (i = j; i < n; i++) {

a[i] = c * a[i-j];

}

2. Suppose a parallel program completes execution on 32 processors in 348 seconds, and it has

been found that this program spends 21 seconds in initialization and cleanup on one processor, and for

the remaining time all 32 processors are active. What is the scaled speedup of this parallel program?

3. Suppose a parallel program executing on 20 processors spends 98% of its time inside parallel

code. What is the scaled speedup of this parallel program?

4. The table below shows the speedups observed for six different parallel programs A, B, C, D,

E, F as the number of processors is increased from 1 through 8.

Processors

Speedup

A

B

C

D

E

F

1

1.00

1.00

1.00

1.00

1.00

1.00

2

1.60

1.92

1.92

1.96

1.74

1.94

3

2.00

2.73

2.78

2.88

2.30

2.82

4

2.29

3.39

3.57

3.67

2.74

3.65

5

2.50

3.91

4.31

4.46

3.09

4.42

6

2.67

4.29

5.00

5.22

3.38

5.15

7

2.80

4.55

5.65

5.93

3.62

5.84

8

2.91

4.71

6.25

6.25

3.81

6.50

Using the Karp-Flatt metric as the basis, choose the statement that best describes the expected speedup

for each program with 16 processors.

I. The speedup achieved on 16 processors will probably be at least 40% higher than the speedup

achieved on eight processors.

II. The speedup achieved on 16 processors will probably be less than 40% higher than the speedup

achieved on eight processors, due to the increase in overhead as processors are added.

III. The speedup achieved on 16 processors will probably be less than 40% higher than the speedup

achieved on eight processors, due to the large serial component of the computation.

5. Let n ≥ f(p) denote the isoefficiency relation of a parallel system and let M(n) denote the

amount of memory required to store a problem of size n. Use the scalability function to rank the

parallel systems shown below from the most scalable to the least scalable:

a. f(p) = Cp, M(n) = n2.

b. f(p) = C√p, M(n) = n2.

c. f(p) = C√plog p, M(n) = n2.

d. f(p) = Cplog p, M(n) = n2.

e. f(p) = Cp, M(n) = n.

f. f(p) = Cp√p, M(n) = n.

g. f(p) = Cp2√p, M(n) = n.

6. Suppose a problem of size 100,000 can be solved in 15 hours on a computer today. Assuming

that the execution time is solely determined by the CPU speed, determine how large a problem can be

solved in 15 hours time by a computer that is 100 times as fast as today’s computer, if the algorithm

used to solve the problem has a time complexity given by (for a problem size of n):

a. Θ(n2)

b. Θ(nlog2n)

c. Θ(n3)

## Calculate the price of your order

550 words
We'll send you the first draft for approval by September 11, 2018 at 10:52 AM
Total price:
\$26
The price is based on these factors:
Number of pages
Urgency
Basic features
• Free title page and bibliography
• Unlimited revisions
• Plagiarism-free guarantee
• Money-back guarantee
On-demand options
• Writer’s samples
• Part-by-part delivery
• Overnight delivery
• Copies of used sources
Paper format
• 275 words per page
• 12 pt Arial/Times New Roman
• Double line spacing
• Any citation style (APA, MLA, Chicago/Turabian, Harvard)

# Our guarantees

Delivering a high-quality product at a reasonable price is not enough anymore.
That’s why we have developed 5 beneficial guarantees that will make your experience with our service enjoyable, easy, and safe.

### Money-back guarantee

You have to be 100% sure of the quality of your product to give a money-back guarantee. This describes us perfectly. Make sure that this guarantee is totally transparent.

### Zero-plagiarism guarantee

Each paper is composed from scratch, according to your instructions. It is then checked by our plagiarism-detection software. There is no gap where plagiarism could squeeze in.

### Free-revision policy

Thanks to our free revisions, there is no way for you to be unsatisfied. We will work on your paper until you are completely happy with the result.

Your email is safe, as we store it according to international data protection rules. Your bank details are secure, as we use only reliable payment systems.

### Fair-cooperation guarantee

By sending us your money, you buy the service we provide. Check out our terms and conditions if you prefer business talks to be laid out in official language.