TAOCP 1.4.4 Exercise 13

The COMPUTE coroutine, as described in Section 1.

taocpmathematicsalgorithmsvolume-1medium

Section 1.4.4: Input and Output

Exercise 13. [20] What instructions should be included at the end of the COMPUTE coroutine in the text, if the buffering algorithms are being applied to output, to ensure that all information has been output from the buffers?

Verified: no
Solve time: -

Solution

The COMPUTE coroutine, as described in Section 1.4.2 and extended in Section 1.4.4 for buffered input, can be adapted to handle buffered output using the same principles. Let the output buffers occupy consecutive memory locations OUTBUF1 and OUTBUF2 (or more generally, two buffers of size $B$ each), and let index register 6 keep track of the current word within the active buffer, analogously to the WORDIN subroutine. Let SENTINEL denote a special value marking the end of the buffer. The key idea is to ensure that any partially filled buffer is completely output before the coroutine terminates, so that no data remains in memory untransmitted.

Let the output unit be denoted by U. Suppose that the COMPUTE coroutine alternates between the two buffers, writing data into the current buffer and initiating an OUT instruction when the buffer is full. Then, at the end of the COMPUTE routine, some buffer may contain unwritten words. The following steps guarantee that all buffered data is written to the output device:

  1. Complete the current buffer. If the current buffer contains fewer than $B$ words, write a sentinel in the next location to mark the logical end of the buffer. Then execute OUT to transfer all words of the buffer to unit U. The program must wait until the output is complete, which can be done using JBUS *(U).
  2. If multiple buffers are in use and some are already filled but not yet output, issue OUT commands for these buffers in order, using JBUS *(U) after each to ensure completion.
  3. No further computation should reference these buffers until the OUT instructions complete. After all buffers have been emptied, the coroutine can return or terminate.

In MIXAL notation, assuming two buffers OUTBUF1 and OUTBUF2 each of size B, and that index register 6 points to the current word within the active buffer, the instructions to flush all output at the end of the COMPUTE coroutine are:

STJ 1F                Store return address
LDA 0,6                Load address of next word in current buffer
CMPA =SENTINEL=        Compare to sentinel
JNE 1H                 If not at sentinel, continue filling buffer
OUT -100,6(U)          Output current buffer to unit U
JBUS *(U)              Wait until output is complete
LD6 1,6                Switch to other buffer if necessary
OUT -100,6(U)          Output second buffer
JBUS *(U)              Wait until output completes
JMP 1F                 Return to caller

Here the -100,6(U) addressing is symbolic for the starting address of the buffer; the actual offset depends on buffer placement in memory. Each OUT instruction initiates the transmission of one buffer's worth of data, and the subsequent JBUS instruction ensures that the program waits until the output completes, preserving the invariant that no data remains in memory untransmitted. If more than two buffers are used, the procedure can be extended by iterating over all buffers, issuing OUT and JBUS in turn.

The correctness of this sequence follows from the buffer-swapping principle: every word written to an output buffer is eventually transmitted to the output unit, and the JBUS instruction guarantees that the unit is idle only after the transfer completes. Therefore, after executing these instructions, no information remains in any buffer, ensuring that the output is complete.

This completes the proof.

∎