TAOCP 1.4.4 Exercise 8

Consider the scenario of Fig.

taocpmathematicsalgorithmsvolume-1simple

Section 1.4.4: Input and Output

Exercise 8. [11] The text describes a hypothetical input scenario that leads from Fig. 23 through parts (a), (b), and (c) of Fig. 24. Interpret the same scenario under the assumption that output to the line printer is being done, instead of input from cards. (For example, what things are happening at the time shown in Fig. 23?)

Verified: yes
Solve time: 47s

Solution

Consider the scenario of Fig. 23 in Section 1.4.4, where $N=6$ buffers are arranged in a circle for anticipated input. At the time depicted in the figure, a single tape unit is feeding data into the first buffer while the program is processing data in another buffer. Let us reinterpret this situation under the assumption that output to a line printer is being performed rather than input from cards or tape.

Let the $N=6$ buffers now represent temporary storage locations for lines of output that are destined for the line printer. Denote the buffers as $B_1, B_2, \dots, B_6$, arranged cyclically. The line printer operates similarly to a tape unit in that it requires non-negligible time to physically print a line, while the CPU can continue other computations in parallel. Suppose that at time $t_0$ the printer is idle, and the program has lines ready in some of the buffers for output.

The analogue of anticipated input is anticipated output: the program can begin placing the next line to be printed into a buffer while the printer is busy printing the previous line. Suppose that buffer $B_1$ currently contains a line being printed, buffer $B_2$ contains a line prepared for imminent printing, and buffers $B_3$ through $B_6$ are either empty or being filled with upcoming lines. The program alternates the active buffer for output in a cyclic manner, analogous to buffer swapping in input.

The sequence of events at the time shown in Fig. 23 is as follows:

  1. The line printer is actively printing the contents of $B_1$. The duration of this operation is the time required for one line, denoted $T$.
  2. The program is simultaneously preparing the contents of $B_2$ for printing. This preparation may include formatting, computation, or moving data into $B_2$ from other memory locations. This preparation time is denoted $C$, analogous to the computation time in the input scenario.
  3. Buffers $B_3$ through $B_6$ are either idle or being filled with lines that will subsequently be printed. The CPU can continue computation on these buffers without interfering with the printer, so the printer remains continuously busy, and no idle cycles occur unless all buffers are empty.
  4. When the printer finishes printing $B_1$, it requests the next line. By the circular arrangement, $B_2$ is immediately available, so the printer begins printing $B_2$ while the program simultaneously prepares $B_3$ for future output. The active buffer rotates through the six positions.

This cyclic overlap of computation and output prevents the printer from idle waiting, analogous to the avoidance of JBUS in the input scenario. The time per printed line is therefore essentially $\max(C, T)$, since the line printer cannot print faster than $T$ per line, and the CPU cannot prepare a buffer faster than $C$. Any MOVE or temporary copy operations are avoided if the program writes directly to the buffer designated for the upcoming line, in accordance with the technique described as buffer swapping.

If the number of buffers $N$ were reduced below the number of lines the CPU can prepare in time $T$, then the printer would occasionally idle while waiting for the next buffer to be filled. Conversely, having $N$ sufficiently large ensures that the printer is continuously fed and that the CPU can compute without interruption.

Thus, the output scenario is structurally identical to the input scenario: the buffers serve as intermediate storage between the CPU and a device with a relatively slow throughput. Fig. 23 now represents the printer actively printing $B_1$, with the CPU preparing subsequent buffers in advance, and anticipated output ensures that the printer operates at full speed without idle time.

This completes the proof.

∎