Problem Set Solutions/Synchronization/Problem03

Loop-invariant code motion is an optimization where the compiler identifies a statement that is repeated in a loop but can be moved outside the loop. For example, consider the following code:

  … code that reads the “pi” variable but does not change it…

In this code, the compiler finds that the initialization of “pi” can be moved outside (before) the loop, which reduces execution time because it would be executed once instead of 1000 times. Consider the following code (initially, f is 0 and g is 1):

Thread 0:           Thread 1:

for(i=0;i<1000;i++){        for(j=0;j<1000;j++){
  while(f==0);            while(g==0); 
  printf(“%d\n”,data);    data=…compute some value…;
  f=0;                g=0;
  g=1;                f=1;
}                   }

Note that the inner (while) loop also has an invariant – the variable f (or g) does not change inside the loop, so instead of “while(f==0);” (for Thread 0, the code Thread 1 is affected similarly) we get:

if(f==0) while(1);

How does this affect the parallel execution of the code? What is printed by Thread 0?


If we only apply loop-invariant code motion to inner (while) loops, we get:

for(i=0;i<1000;i++){        for(j=0;j<1000;j++){
  if(f==0)                if(g==0)
    while(1);               while(1);
  printf(“%d\n”,data);        data=…compute some value…;
  f=0;                g=0;
  g=1;                f=1;
}                   }

As a result of this change, we get a program that still may work, but only if every time a thread wants to wait the condition for the wait is already satisfied. This requires the threads to work in perfect synchronicity (without actually synchronizing). If at any time the threads go out of perfect synchronicity, one (and then the other) will enter an infinite loop.

Here is an example of how things can play out perfectly: Thread 1 checks “g”, sees that it is 1 (initially “g” is 1), skips the infinite loop, produces a data item and sets “g” to 0 and “f” to 1. Now Thread 0 checks “f”, sees it is 1 and skips the infinite loop, prints the value, sets “f” to 0 and “g” to 1, then Thread 1 sees that “g” is 1, skips the infinite loop, etc.

Of course, at any point in this “perfect” execution a Thread 0 might check “f” before Thread 1 sets it to 1, in which case Thread 0 gets stuck (causing Thread 1 to get stuck in its next iteration). Conversely, Thread 1 will get stuck first if it checks “g” before Thread 0 sets it to 1, causing Thread 0 to get stuck, too.