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. From the discussion above, 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 focused in our discussion, 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 begin with only two processes and then consider 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 scenarios measurement cases and reconstruct an ``actual'' execution as if the measurement overhead were not present. From what we learn, we derive a model that works for that case and look for consistent properties across the models to formulate a general algorithm.