next up previous
Next: 4.2 Experimental Setup Up: 4 Model the Overlap Previous: 4 Model the Overlap

4.1 Theoretical Model

We base our analysis on the execution model in Fig. 7. It is composed of a compression-transmission loop, where each chunk of data is first processed by a computation procedure before it is sent out,

In our implementation, send() returns as soon as all the application data has been copied into the kernel buffer. So part of the time used for data transmission will overlap with that of COMPRESS(). Assume $t_c$ is the time of compressing one chunk of data, $t_b$ is the socket buffer copying time for the compressed data, and $t_s$ is the corresponding network transmission time. Let us denote the processing time of all the loops as $T$, then this execution model can be expressed as Fig. 12.

Figure 12: Overlap between data transmission and local compression
The grid boxes represent local computation, slashed boxes represent local data copying for data transmission, and the line boxes represent the data transmission. The top box shows the overlap when $t_c \geq t_s - t_b$, and the bottom shows the overlap when $t_c < t_s - t_b$.

Generally, $t_s$ starts somewhat later than the corresponding $t_b$, but the time interval is very difficult to measure. So we simply assume that $t_s$ and $t_b$ start at the same time. From Fig. 12, $T$ can be expressed by the following formula:

T = \left\{
n \cdot t_c + (n-1)t_b + t_s...
t_c + n \cdot t_s & t_c < t_s - t_b
\end{array} \right.
\end{displaymath} (6)

where $n$ is the number of loops in Fig. 7. The relationship between compression time and the total processing time in the above formula is illustrated in Fig. 13

Figure 13: Theoretical model for total execution time, considering the overlap between network processing and local compression
\psfig{figure=formula.eps, width=3.1in}\end{center}\end{figure}

It is easy to see, when computation time is big enough ( $t_c \geq t_s - t_b$), $t_s$ is not the dominating factor in the total execution time. Consequently, the changes of network bandwidth will not affect application performance. The following section shows the experimental result that confirms this claim.

next up previous
Next: 4.2 Experimental Setup Up: 4 Model the Overlap Previous: 4 Model the Overlap
root 2001-10-09