next up previous
Next: Three Process Parallel Models Up: Two Process Parallel Models Previous: Scenario: One Send.

General Scenario.

The goal of the two process models is to enumerate the possible cases arising from send/receive message communication. From these cases, we can rationally reconstruct the approximated execution to determine how overhead, waiting, and delay times are to be adjusted. From this reconstruction, we can derive expressions for overhead analysis and correction. The similarity in the case results leads us to propose a general scenario for two processes. This scenario considers an arbitrary message send on one process and corresponding message receive on the other process. Thus, this is a generalization of the One Send scenario above. However, we now use the delay values $x1$ and $x2$ instead of the $o1$ and $o2$ overheads in the analysis. The expressions for the two cases are given below (refer to Figure 1):

Case 1   Case 2
x1 $>$= x2 + w   x1 $<$ x2 + w
o2' = o2 + w   o2' = o2 - (x1-x2 if x1$>$x2)
w' = 0   w' = w + (x2-x1)
x1' = x1   x1' = x1
x2' = min(x1, x2+w) = x2 + w   x2' = min(x1, x2+w) = x1

The importance of the general scenario is the case analysis showing how the delay values are updated and what information is shared between processes during message communication. (Keep in mind that we are arbitrarily designating P1 as the sender and P2 as the receiver. The analysis also applies when P1 is the receiver and P2 the sender, with appropriate reversals of notation in the expressions.) Notice that the overhead values $o1$ (not shown) and $o2$ are accumulated overheads. The $o2$ value is updated here to account for waiting time processing, but whenever any new measurement overhead occurs on P1 or P2, the accumulated overheads $o1$ and $o2$ must be updated accordingly. Similarly, any new measurement overhead must also be added to the delay values $x1$ or $x2$.

Just to be clear, it is the overhead values that are being removed during the profiling calculations. Thus, we want these overhead to be accurately accounted. The conclusion of the two process modeling is that we can handle the parallel overhead compensation for ALL two-process scenarios by applying the general analysis described above on a message-by-message analysis, maintaining the overhead and delay values as the online analysis proceeds.

next up previous
Next: Three Process Parallel Models Up: Two Process Parallel Models Previous: Scenario: One Send.
Sameer Shende 2005-05-30