next up previous
Next: Summary Up: Three Process Parallel Models Previous: Scenario: Pipeline

Scenario: Two Receive

Unfortunately, it is not hard to find a scenario that raises issues in our ability to correct overhead intrusion under a different set of receive assumptions. These issues are brought on by the effect of intrusion on message sequencing. The Two Receive scenario exposes the problem. Here one process, P2, receives messages from two other processes. There are four cases to consider depending on the relatives sizes of overheads and waiting times. Figure 9 show the first case. We return to looking only at the first messages being sent and received on each process, and consider the initial overheads (not the delays values) in the analysis.

Figure 9: Three-Process, Two Receive - Models and Analysis
\resizebox{.75\columnwidth}{!} {\includegraphics{Figures-new/3-process-2-receive-final.eps}}

The first case is similar in many ways to the other scenarios. We show a two-part approximated execution, with part one (top) showing the state after the first message is processed and part two (bottom) showing the result after the second message is processed. The analysis follows the approach we used before, with new waiting values ($w'$ and $y'$) being calculated and P2's delay value ($x2$) updated. In this case, no waiting time would have occurred. Otherwise, nothing particularly strange stands out in the approximated result.

This is also true of the second case shown in Figure 10. The conditional expression in the analysis of the first message is the same as in the first case, but the opposite condition is found for the second message. Waiting occurs on the second message and will be correctly adjusted based on the analysis expressions we developed before. Case 3, shown in Figure 11, also offers no surprises. Here we see the opposite condition for the first message with the same condition for the second message of Case 2.

Figure 10: Three-Process, Two Receive - Models and Analysis (Case: 2)
\resizebox{.75\columnwidth}{!} {\includegraphics{Figures-new/3-process-2-receive-b-final.eps}}

Figure 11: Three-Process, Two Receive - Models and Analysis (Case: 3)
\resizebox{.75\columnwidth}{!} {\includegraphics{Figures-new/3-process-2-receive-c-final.eps}}

What would be a surprising result? If the overhead analysis resulted in a reordering of send events in time, between the measured execution and the approximated execution, then there would be concerns of performance perturbation. In Figure 12, we see the send events changing order in time in the approximated execution, with P3's send taking place before P1's send. As with the other cases, our analysis reflects a message-by-message processing algorithm.

Figure 12: Three-Process, Two Receive - Models and Analysis (Case: 4)
\resizebox{.75\columnwidth}{!} {\includegraphics{Figures-new/3-process-2-receive-d-final.eps}}

In the rational reconstruction, we assume the message communication is explicit and pairs a particular sender and receiver. Under this assumption, the order of messages received by P2 must be maintained in the approximated execution. In this case, is the time reordering of send messages in Figure 12 a problem? In fact, no. It is certainly possible that a process (P2) will first receive a message from a process (P1) sent after another process (P3) sends a message to the receiving process. This just reflects the strict order of P2 receives. However, if we consider receive operations that can match any send, the send reordering exposes a problem with overhead compensation, since the message from P3 would be received first in the ``real'' execution.

The application of our overhead compensation models to programs using receive operations that can match any send message produces profile analysis results constrained to message orderings as observed in the measured execution. These message orderings are affected by intrusion and, thus, may not be the message orderings that occur in the absence of measurement. However, while it is possible to detect reordering occurrences (i.e., measured versus approximated orderings), it is not possible to correct for reordering during online overhead analysis and compensation. Why? There are two reasons. First, our analysis is unable to determine if it is correct to associate a receive event with a different send event. That is, the analysis does not know why type of receive is being performed, one that is for a specific sender or one that can accept any sender. Second, even if we know the type of receive operation, it is not possible to know whether changing receive order will affect future receive events. Therefore, the models must, in general, enforce message receive ordering. That said, other techniques may be brought to bear on the problem. For instance, the analysis could relax the constraint, allowing measured order to be locally altered, and then apply algorithms developed by Kranzmüller (10) to look for future message event violations.

next up previous
Next: Summary Up: Three Process Parallel Models Previous: Scenario: Pipeline
Scott Biersdorff 2007-02-02