Effectiveness of Software Trace Recovery Techniques for Current Parallel Architectures

This paper extends results concerning the recovery of accurate parallel program traces from corrupted traces initially gathered with software monitoring. Earlier work developed an approach that functioned for idealized machines. Here, we explain how this approach can be modified to track the temporal uncertainties due to the software monitoring mechanisms, and to halt when the recovered order can no longer be guaranteed. By quantifying certain system and application parameters, we are able to compute both worst-case and average-case estimates of the number of trace events that our modified trace-recovery algorithm will be able to recover before it can no longer guarantee the recovered order of events. We also report the values of these key parameters for some current parallel machines and compute typical expected trace lengths for a variety of application types on these machines