To address the problem of overhead compensation in parallel execution, we must develop models that describe the effect of measurement overhead on execution intrusion. From these models we can gain insight in how the profiling overheads can then be compensated. However, unlike sequential computation, the models must identify and describe aspects of parallel interaction that may cause different intrusion behavior and, thus, lead to different methods for compensation. We know that the methods will involve the communication of information between parallel threads of execution at the time of their interaction. To be more specific, we will consider parallel compensation in message passing computation. The parallel overhead compensation models we present below allow for information about execution delay to be passed between processes during message communication. The goal is to determine exactly what information needs to be shared and how this information is to be used in compensation analysis. The modeling methodology we develop extends to shared memory parallel computing, but the case for shared memory will not be presented here.
The approach we follow below constructs an understanding of the parallel compensation problem from first principles. We first look at only two processes and then three processes. From this in-depth study, our hope is to gain modeling and analyses understanding that can extend to the general case. We will follow a strategy of rational reconstruction where we take scenario measurement cases and reconstruct an ``actual'' execution as if the measurement overhead were not present. From what we learn, we then derive a model that works for that case and look for consistent properties across the models to formulate a general algorithm for overhead compensation.
The details of overhead removal in the profile calculation are described in our earlier paper [8]. The focus below is on determining the actual overhead value to be removed for each process. These two operations together constitute overhead compensation.