TAOCP 1.4.4 Exercise 5

Let T_i be the total time during which I/O device $i$ is actually transferring data, for $1\le i\le n$, and let

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.4.4: Input and Output

Exercise 5. [M21] Generalize the situation of the preceding exercise to the case when the program refers to $n$ I/O devices instead of just one.

Verified: no
Solve time: -

Solution

Let

$$ T_i $$

be the total time during which I/O device $i$ is actually transferring data, for $1\le i\le n$, and let

$$ C $$

be the total computation time exclusive of all waiting for I/O.

With unbuffered I/O, each transfer is initiated and then completed before further useful computation proceeds. Hence the total running time is essentially

$$ R_{\mathrm{unbuf}} = C+\sum_{i=1}^{n}T_i . $$

The computation and I/O activities occur sequentially, so every unit of I/O time contributes directly to the running time.

When buffering is used, computation may proceed simultaneously with the activity of all I/O devices. The running time is then governed by the longest chain of dependent activities. The computation requires time $C$, while device $i$ requires time $T_i$. Since these activities can overlap, the total running time cannot be less than any one of these quantities. In favorable circumstances the running time is therefore

$$ R_{\mathrm{buf}} = \max!\left(C,T_1,\ldots,T_n\right). $$

To compare the two methods, write

$$ M=\max!\left(C,T_1,\ldots,T_n\right). $$

Then

$$ C\le M,\qquad T_i\le M\quad(1\le i\le n), $$

so

$$ R_{\mathrm{unbuf}} = C+\sum_{i=1}^{n}T_i \le (n+1)M. $$

Since

$$ R_{\mathrm{buf}}=M, $$

it follows that

$$ \frac{R_{\mathrm{unbuf}}}{R_{\mathrm{buf}}} \le n+1. $$

Therefore buffering can never decrease the running time by more than a factor of

$$ n+1. $$

This bound is attainable. Take

$$ C=T_1=T_2=\cdots=T_n=M. $$

Then

$$ R_{\mathrm{unbuf}} = (n+1)M, $$

while

$$ R_{\mathrm{buf}} = M. $$

Hence

$$ \frac{R_{\mathrm{unbuf}}}{R_{\mathrm{buf}}} = n+1. $$

Thus, in the most favorable circumstances, buffering can reduce the running time by a factor of $n+1$, and no larger improvement is possible.

The result for Exercise 4 is recovered by setting $n=1$, which yields the maximum factor $2$.

$$ \boxed{\text{Maximum possible speedup from buffering with }n\text{ I/O devices is }n+1.} $$

This completes the proof.

∎