TAOCP 1.4.4 Exercise 4

Section 1.4.4: Input and Output

Exercise 4. [M20] Show that if a program refers to a single I/O device, we might be able to cut the running time in half by buffering the I/O, in favorable circumstances; but we can never decrease the running time by more than a factor of two, with respect to the time taken by unbuffered I/O.

Verified: no
Solve time: -

---

Solution

Let $T$ denote the time required for one input-output operation on the device, and let $C$ denote the computation time performed between successive input-output requests. Since the program refers to a single I/O device, each cycle of execution consists of one I/O operation together with the intervening computation.

For unbuffered input-output, the program waits for the device to complete its work before computation begins. Thus the computation and I/O do not overlap. By the discussion preceding the exercise, the time per cycle is essentially

$$ T+C. $$

Let $U=T+C$ denote the running time per cycle for unbuffered I/O.

For buffered input-output, computation and I/O are overlapped. While the device is performing one transfer, the processor executes the computation associated with the previous transfer. Hence the running time per cycle is governed by the slower of the two concurrent activities. Ignoring the comparatively small overhead of buffer management, the time per cycle is

$$ \max(T,C). $$

Let $B=\max(T,C)$ denote the running time per cycle for buffered I/O.

We compare the two methods by considering the ratio

$$ \frac{U}{B} = \frac{T+C}{\max(T,C)}. $$

If $T\ge C$, then $\max(T,C)=T$, and

$$ \frac{U}{B} = \frac{T+C}{T} = 1+\frac{C}{T} \le 2, $$

since $C\le T$.

If $C\ge T$, then $\max(T,C)=C$, and

$$ \frac{U}{B} = \frac{T+C}{C} = 1+\frac{T}{C} \le 2, $$

since $T\le C$.

Therefore

$$ \frac{U}{B}\le 2, $$

so buffering can never decrease the running time by more than a factor of two.

Equality is attained in the favorable circumstance

$$ T=C. $$

In this case,

$$ U=T+C=2T, \qquad B=\max(T,C)=T, $$

hence

$$ \frac{U}{B}=2. $$

Thus buffering may cut the running time in half, but no greater improvement is possible.

$$ \boxed{\text{Maximum possible speedup factor }=2} $$