SAFETY and LIVENESS in a parallel program.

A SAFETY feature is a feature that prevents a bad thing from happening.  A program is SAFE is nothing bad ever happens (or could happen).

A LIVENESS feature is one that guarantees that a certain good thing will happen every time.  A program is LIVE if the good stuff always happens.

For example,

PARTIAL CORRECTNESS is a SAFETY feature.

"Partial correctness" is whenever the program terminates, the answer is always correct.  Of course, it might not terminate.

GUARANTEED TERMINATION is a LIVENESS feature.  However, GUARANTEED TERMINATION doesn't necessarily mean the answer is right when it terminates.  You need both PARTIAL CORRECTNESS and GUARANTEED TERMINATION to infer TOTAL CORRECNTNESS of a program.  In other words, that the program is both SAFE and LIVE.

int x;
cin >> x;
if (x < 1) return;
while (!Prime (x))
 x++;

The above will terminate every time.

int x;
cin >> x;
if (x < 1) return;
while (!(Prime (x) && Prime (x+2)))
 x++;

This terminates if the Twin Primes conjecture is true, but if it is false, then there are inputs for x that will result in nontermination.  The Twin Primes Conjecture is as yet unsolved.  So, whether the above program is guaranteed to terminate is also an unsolved problem.  We have here a VERY SHORT program, and we don't whether it is guaranteed to terminate.

So, to analyze parallel programs, we make use of something called ATOMIC STATEMENTS.  Atomic statements are a theoretical tool and might really be implemented in your parallel language or on your parallel platform.

<x = x+y>;

In this notation, with the angle brackets, we interpret this as an atomic statement.  This means that while this statement is executing, nothing else is happening.

This is NOT the same thing as:

pthread_mutex_lock (&lock);
x = x+y;
pthread_mutex_unlock (&lock);

Using locks, prevents another from going in there and also trying to execute x = x+y;  But other threads might be out there doing something else.  With an atomic statement <x = x+y>; nothing is happening at all EXCEPT this statement.

We tend to assume that variable reads and writes are always atomic even if we don't say so explicitly.  In other words, no thread is changing a variable while someone else is reading it.

0:    0
1:    1
2:   11
3:   10
4:  110
5:  111
6:  101
7:  100
8: 1100

In Gray Code, which looks sort of like binary, but isn't.  You increment a variable by flipping a single bit.


Also, for the purpose of theoretical analysis we introduce the "co" block (which is not part of any actual language).

co { // means run these statements in parallel

 x++ %%  The %% is what we use to separate blocks of parallel code
 x *= 2
}

If x starts out as 5, what might x be after this block is run?

We also have a co-loop:

co (int i=0; i < sz; i++)
 Stuff (i)

This causes sz threads to run in parallel, each running the stuff method with its own value of i.

int max = A[0];
for (int i=1; i < sz; i++)
 if (A[i] > max)
  max = A[i];  //Easily finds the max of an array of ints

int max = A[0];
co (int i=1; i < sz; i++)
 if (A[i] > max)
  max = A[i];

Suppose A is [1,2,3,4,5];
max gets set to 1, and then four threads with i ranging from 1 to 4.  Supposing all the tests happen before all the writes, then all four threads test true, since all of their A[i]'s are greater than 1.

Then they all write.  And the thread that happens to write last gets to have its value immortalized in the max variable (whether it's really the maximum or not.)

This is called a "race condition."

int max = A[0];
co (int i=1; i < sz; i++)
 if (A[i] > max)
  <max = A[i];>

How does making the assignment statement atomic make any difference?  It does not.  Reading and writing variables are already atomic and so we still have the same race condition.

int max = A[0];
co (int i=1; i < sz; i++)
 <if (A[i] > max)
  max = A[i];>

 How does making the if statement atomic make a difference?
The answer will now be correct.  We no longer have a race condition.  The loop will not necessarily file in sequential order, but all iterations of the loop will fire sooner or later, and the max will contain the correct answer when it's done.

However, this isn't actually running in parallel anymore.  Since all the work is now done atomically, nothing is happening simultaneously.

How could you find the max of an array of numbers faster with a parallel algorithm?  Normally if there n items in the array, you can find the max in O(n) time with a regular sequential algorithm.  How can you find the max much faster in parallel?

Like, is O (lg n) time.


3 8 4 7 6 2 1 5

Break it up into four threads:
1.  Max (3,8) : 8
2.  Max (4,7) : 7
3.  Max (6,2) : 6
4.  Max (1,5) : 5

Break it up into threads

1.  Max (8,7) : 8
2.  Max (6,5) : 6

Finally, find Max (8,6) : 8

if (A.size <= 2) find Max manually.
else
 co {
  a = Max (first half of A) %%
  b = Max (second half of A)
 }
 return Max (a,b)

In the end, this will run in O(lg n) in parallel.

AT-MOST-ONCE property (of assignment statements):

A "critical reference" to a variable is when you REFERENCE a variable that is MODIFIED by another thread.