...Carnival
This research was supported by NSF grant CCR-9510173. Wagner Meira, Jr. is supported by CNPq-Brazil, Grant 200.862/93-6.
.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  
...multiprogramming. 
Multiprogramming that occurs while a process is waiting is counted as waiting time.
.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  
...time. 
Our discussion is in terms of pair-wise synchronization, but the techniques extend to the analysis of waiting time for synchronization operations between many processors. In particular, we characterize waiting time in barriers as a set of pair-wise synchronization operations between each waiting processor and the last processor to enter the barrier.
.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  
...speed. 
We are currently investigating the use of waiting time analysis in analyzing memory reference behavior by instrumenting a software coherence protocol.
.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  
...time. 
We chose 95% as our initial level of tolerance for this algorithm, so we remove blocks only as long as the remaining blocks account for 95% of the actual waiting time.
.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  
...class.
The representative for an equivalence class is never changed, ensuring that the equivalence relation is independent of the order in which paths are processed. The characterization for a class is updated each time a new path matches the representative for that class, reflecting the time spent in the new path.
.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  
...path. 
We compute the relative duration to avoid relying on the exact duration of steps or the precise number of iterations in a loop in determining equivalence of execution paths.
.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  
...Cholesky. 
The implementations of Cholesky on the SGI and SP2 are slightly different, and cannot be compared directly.
.
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  .
  

Wagner Meira
Tue Mar 19 14:59:26 EST 1996