hpca/Problem Set Solutions/Synchronization/Problem01

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:

``````for(i=0;i<1000;i++){
pi=3.14159265;
… 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;
}                   }
``````

What does this code do (what is printed by Thread 0)?

Solution:

This code is intended to use Thread 1 as a producer thread that compute a value and puts it in “data”, and Thread 0 as a consumer thread that takes values from “data” and prints them out. If the compiler and the hardware both provide sequential consistency, this code actually works and Thread 0 prints out 1,000 integers computed by Thread 1.

The way the code works is as follows: Thread 0 spins until f becomes non-zero, which will not happen until Thread 1 is done placing a value in the “data” variable and chaned g to 0. Thread 1 then spins until g becomes non-zero, which will only happen after Thread 0 is done printing the data item and changing f back to 0, then Thread 0 again waits until Thread 1 produces another data item, etc.