The simplest parallel computation involves only two processes which
exchange messages during execution. Measurement-based profiling will
introduce overhead and intrusion local to each process that carries
between the processes as they interact. To model the intrusion and
determine what information must be shared for overhead compensation,
we consider the following two-process scenarios:
One send | Process P1 sends one message to process P2 | |
Two sends | P1 sends two messages to P2 | |
Handshake | P1 sends one message to P2, then P2 sends one message to P1 | |
General | General message send and receive |
For each scenario, we enumerate all possible cases for overhead relations between the processes (what is called the ``measured execution'' model) and for each case derive a representation of the execution with the overhead removed (what is called the ``approximated execution'' model). We determine the overhead-free approximation using a rational reconstruction of the ``actual'' event timings with the measurement overhead removed.
Both models are presented in diagrammatic form. In addition, we present expressions that relate the overhead, waiting, and timing parameters from the measured execution to those ``corrected'' parameters in the approximated execution. It is important to keep in mind that the goal is to learn from the rational reconstruction of the approximated execution how profile compensation is to be done in the other scenarios, especially the general case.