next up previous
Next: Scenario: Pipeline Up: Models of Parallel Overhead Previous: General Scenario

Three Process Parallel Models

The question at this point is whether that conclusion applies to three or more processes. That is, can the general two-process analysis be applied on a message-by-message basis to all send/receive messages between any two processes in a multi-process computation and, more importantly, give the desired overhead compensation result? In this section, we look at two scenarios with three processes to get a sense of the answer. These scenarios are:

Pipeline   Process P1 sends a message to P2, then P2 sends to P3
Two Receive   Process P1 and P3 sends a message each to process P2

We then argue that these two scenarios are enough to elucidate all similar cases regardless of the number of processes. Again, we follow a rational reconstruction approach to determine approximated executions and then derive expressions for updating overhead, waiting time, and delay variables to match the reconstructed executions.


Scott Biersdorff 2007-02-02