TAOCP 5.4.4 Exercise 21

Section 5.4.4: Reading Tape Backwards

Exercise 21. [18] Draw the tree representation for the read-forwards merge pattern defined by the vectors in exercise 7. Is this tree strongly 3-fifo?

Verified: no
Solve time: 14m43s

Solution

Vectors from Exercise 7

Exercise 7 gives the vector representation for the polyphase merge on three tapes with 13 initial runs. The final output is on tape 1, so
[ \mathbf{y}^{(0)} = (1,0,0). ] The twelve merge vectors (\mathbf{y}^{(1)},\dots,\mathbf{y}^{(12)}) (with (\mathbf{y}^{(1)}) the last merge) are:

[ \begin{array}{ccl} \mathbf{y}^{(1)} &=& (-1,,+1,,+1) \ \mathbf{y}^{(2)} &=& (+1,,+1,,-1) \ \mathbf{y}^{(3)} &=& (+1,,-1,,+1) \ \mathbf{y}^{(4)} &=& (+1,,-1,,+1) \ \mathbf{y}^{(5)} &=& (-1,,+1,,+1) \ \mathbf{y}^{(6)} &=& (-1,,+1,,+1) \ \mathbf{y}^{(7)} &=& (-1,,+1,,+1) \ \mathbf{y}^{(8)} &=& (+1,,+1,,-1) \ \mathbf{y}^{(9)} &=& (+1,,+1,,-1) \ \mathbf{y}^{(10)} &=& (+1,,+1,,-1) \ \mathbf{y}^{(11)} &=& (+1,,+1,,-1) \ \mathbf{y}^{(12)} &=& (+1,,+1,,-1) \end{array} ]

These vectors satisfy (\mathbf{v}^{(12)} = \sum_{i=1}^{12}\mathbf{y}^{(i)}+\mathbf{y}^{(0)} = (5,8,0)), the initial distribution.

Tree Construction for Read‑Forwards (FIFO)

For read‑forwards the tapes behave as queues. The tree is built from the vectors by starting with the root (the final run on tape 1) and processing (\mathbf{y}^{(1)},\mathbf{y}^{(2)},\dots,\mathbf{y}^{(12)}) in this order. At step (i) we expand the oldest leaf on the output tape indicated by the (-1) component of (\mathbf{y}^{(i)}); the two new children receive the labels of the input tapes (the (+1) components). This implements the “first formed, first grown on” rule.

Carrying out the twelve steps yields the following ordered tree (internal nodes are labelled with the step at which they were created; leaves are the initial runs).

T1 (N1)
├── T2 (N3)
│   ├── T1 (N6)
│   │   ├── T2 (leaf)
│   │   └── T3 (N11)
│   │       ├── T1 (leaf)
│   │       └── T2 (leaf)
│   └── T3 (N8)
│       ├── T1 (leaf)
│       └── T2 (leaf)
└── T3 (N2)
    ├── T1 (N5)
    │   ├── T2 (leaf)
    │   └── T3 (N10)
    │       ├── T1 (leaf)
    │       └── T2 (leaf)
    └── T2 (N4)
        ├── T1 (N7)
        │   ├── T2 (leaf)
        │   └── T3 (N12)
        │       ├── T1 (leaf)
        │       └── T2 (leaf)
        └── T3 (N9)
            ├── T1 (leaf)
            └── T2 (leaf)

The tree has 13 leaves: five labelled T1 and eight labelled T2, matching the initial distribution ((5,8,0)).

Strongly 3‑FIFO Test

A tree is strongly (T)-fifo (Exercise 20) iff it can be labelled so that the corresponding merge pattern obeys the strict queue discipline “write, rewind, read all, rewind; write, rewind, read all, rewind; …”. Equivalently, every write phase on a tape must be completely consumed in a single subsequent read phase; no write phase may be split across two read phases.

In the polyphase pattern above, the chronological merge phases (reverse of the vector order) are:

Phase A (5 merges): output T3
Phase B (3 merges): output T1 ← write phase on T1 producing three runs
Phase C (2 merges): output T2, input T1 and T3 ← read phase on T1 consuming two runs
Phase D (1 merge): output T3, input T1 and T2 ← read phase on T1 consuming the remaining run
Phase E (1 merge): output T1

The three runs created on T1 during Phase B are not all read in one read phase; two are consumed in Phase C and the third in Phase D. This splits one write phase over two read phases, violating the “read all” requirement of the strong FIFO discipline.

In the tree, the three internal nodes labelled T1 that belong to Phase B are N5, N6, N7 (created at unmerge steps 5, 6, 7). N5 and N6 become inputs to N10 and N11 (which correspond to Phase C), while N7 becomes an input to N12 (which corresponds to Phase D). Hence the write phase is split.

Therefore the tree is not strongly 3‑fifo.

\boxed{\text{The tree is not strongly 3-fifo.}} ∎