Terms

Question 1

Race Condition

Answer 1

An error caused by timing

Question 2

Critical Section

Answer 2

A block of code that can be executed by at most one thread at a time

Question 3

P-Complete

Answer 3

A problem C that is solvable in polynomial time and for every other problem L that is solvable in polynomial time, L ≤ log m C

Question 4

≤ log m

Answer 4

This is true iff there exists a function f that can be computed using only log-space s.t x ∈ A ⇔ f(x) ∈ B

Question 5

NC

Answer 5

The set of all problems that can be solved in O((log n)^c) steps using an O(n^k) processors on a PRAM (for some c and k

Question 6

Cache Coherency

Answer 6

The property that when one processor or core changes a cached variable that the value stored by all the other processors in their respective caches is changed to the new value to maintain consistency.

Question 7

Thread Safety

Answer 7

A function has this property if multiple threads are able to simultaneously execute code within the function without leading to errors

Question 8

CRCW PRAM

Answer 8

A PRAM where memory accesses enforce concurrent reads and concurrent writes among the processors

Question 9

EREW PRAM

Answer 9

A PRAM where memory accesses enforce exclusive read and exclusive writes among the processors

Question 10

False Sharing

Answer 10

Performance degradation caused by memory accesses that induce frequent cache updates across multiple core in systems that enforce cache coherency

Question 11

How to debug a running process

Answer 11

1. Run program using mpiexec and open another terminal
2. Use the command:
   gdb -pid 5038
   With all of the pids associated with the mpiexec call
3. Use the command:
   where
   to find where in the code it is hanging

Question 12

Amdahl’s Law

Answer 12

1 / S+ (1-S)/N
where n is the number of processors
and s is the percentage of program executed sequentially

Question 13

The theory of P-Completeness gives a notion of “efficient parallel computation.” What does that mean, precisely?

Answer 13

There is probably no algorithm that can solve a p-complete problem in logarithmic time with a polynomial number of processors.
If P ≠ NC then P-complete is not in NC

Question 14

We know that the circuit value problem (CVP) is P-complete. This tells us that:

Answer 14

It is likely that there is no efficient parallel algorithm for CVP

Question 15

Problems known to be P-complete

Answer 15

1. Breadth First Search
2. Circuit Value Problem
3. Lexicographically First Depth First Search
4. CFG membership
5. Greedy Dominating Set
6. Linear Programming

Question 16

How to compile OpenMP program

Answer 16

g++ -fopenmp filename

Question 17

Why does the second program produce the wrong answer

Answer 17

because the line if (a[i]>a[j]) sum++; causes a race condition

Question 18

Why does the second program run slower than the first even though it is being run on 4 processors?

Answer 18

False Sharing - multiple cores attempt to change sum.

Cache issues.

Question 19

Rewrite it so that it runs faster

Answer 19

#pragma omp parallel for schedule(static,1) reduce(+,sum)
for(int i=0; ia[j]) sum = sum+1;
      }
}
cout<<<endl;
}

Question 20

What is s, the portion of the execution time that must be executed sequentially?

Answer 20

little num/ big num

Question 21

Amdal’s Law

Answer 21

1/ S+ (1-S/N)

Question 22

How long would your code take at maximum speedup using 8 processors

Answer 22

S = sequential / parallel

Question 23

By Amdahl’s law, what is the maximum speedup possible?

Answer 23

1 / S

Question 24

How to run a program using OpenMPI called t3.cc

Answer 24

mpic++ t3.cc

Question 25

How to compile using OpenMPI on the p1 and p2 machines

Answer 25

mpirun -hp 8 -host p1.cs.ohiou.edu, p2.cs,ohiou.edu