TAOCP 5.4.6 Exercise 12
Six tapes are partitioned into three logical pairs.
Section 5.4.6: Practical Considerations for Tape Merging
Exercise 12. [40] [40] Consider partitioning six tapes into three pairs of tapes, with each pair playing the role of a single tape in a polyphase merge with T = 3. One tape of each pair will contains blocks 1,3,5,... and the other tape will contain blocks 2, 4,6,...; in this way we can essentially have two input tapes and two output tapes active at all times while merging, effectively doubling the merging speed. a) Find an appropriate way to extend Algorithm F to this situation. How many buffers should there be? b) Estimate the total running time that would be obtained if this method were used to sort 100,000 100-character records, considering both the read-forward and readbackward cases.
Verified: no
Solve time: 1m22s
Setup
Six tapes are partitioned into three logical pairs. Each pair represents one logical tape in a 3-way polyphase merge with $T = 3$. Let the logical tapes be $L_1, L_2, L_3$. Each $L_i$ is implemented by two physical tapes, one carrying blocks $1,3,5,\dots$ and the other carrying blocks $2,4,6,\dots$.
Algorithm F (Forecasting with floating buffers) for a $P$-way merge uses $2P$ input buffers and $2$ output buffers. The merge here operates logically with $P = 3$, but each logical tape is split into two physical streams that must be read and written independently while preserving alternation and overlap.
The task is to extend Algorithm F to exploit simultaneous activity of both tapes in each pair and to estimate running time for sorting $100{,}000$ records of $100$ characters.
Solution
(a) Extension of Algorithm F and buffer count
Algorithm F assigns one input buffer $I[j]$ to each active input stream and uses forecasting to determine the next stream to refill. In the present configuration each logical tape $L_i$ is realized by two physical tapes, denoted $L_i^{(0)}$ and $L_i^{(1)}$, carrying alternating blocks.
To preserve continuous I/O on each logical tape, each physical stream requires its own input buffer, since a read operation on $L_i^{(0)}$ cannot be overlapped with a read operation on $L_i^{(1)}$ unless separate buffering is available. The forecasting rule is applied independently across the two substreams of each logical tape, selecting the next physical stream whose current buffer empties first.
Thus each logical input stream contributes two input buffers instead of one, giving $2 \cdot 2P = 4P$ input buffers. With $P = 3$, this yields $12$ input buffers.
The output side is also doubled because the output tape is implemented as a pair of physical tapes used in alternation. Algorithm F uses two output buffers $O[0]$ and $O[1]$ to maintain overlap between computation and writing. Each of these must be duplicated so that each physical output tape can be written continuously without waiting for buffer turnover from its partner. This yields $4$ output buffers.
Therefore the total number of buffers is
$$ 12 + 4 = 16. $$
The modified algorithm proceeds exactly as Algorithm F, except that all indexing over input streams is replaced by indexing over physical substreams, and forecasting selects the next physical tape buffer pair $(L_i^{(0)}, L_i^{(1)})$ whose terminal key indicates earliest depletion.
(b) Running time estimate for $100{,}000$ records
Each record has $100$ characters, so the total data volume is
$$ 100{,}000 \cdot 100 = 10^7 \text{ characters}. $$
The MIXT transfer rate is approximately $800$ characters per inch at $75$ inches per second, giving a nominal rate of
$$ 800 \cdot 75 = 60{,}000 \text{ characters per second}, $$
so the pure transfer time per character is approximately
$$ \frac{1}{60{,}000} \approx 1.67 \cdot 10^{-5} \text{ seconds}. $$
A block of $100$ characters therefore requires
$$ 100 \cdot 1.67 \cdot 10^{-5} = 1.67 \cdot 10^{-3} \text{ seconds}. $$
Each block incurs an interblock gap of $480$ characters, contributing
$$ 480 \cdot 1.67 \cdot 10^{-5} \approx 8.0 \cdot 10^{-3} \text{ seconds}. $$
Assuming continuous operation so that stop/start penalty is avoided, the forward-transfer time per block is approximately
$$ (100 + 480)\cdot 1.67 \cdot 10^{-5} \approx 9.7 \cdot 10^{-3} \text{ seconds}. $$
The number of blocks equals $100{,}000$, so one full linear scan costs approximately
$$ 100{,}000 \cdot 9.7 \cdot 10^{-3} \approx 9.7 \cdot 10^{2} \text{ seconds}. $$
This gives about $970$ seconds per full pass.
In a 3-way polyphase merge, the number of passes is reduced compared to 2-way merging, but the dominant cost remains proportional to the number of full tape traversals. The doubling of physical tapes per logical stream does not reduce total data volume; it only increases overlap, so the main comparison is between forward and backward operation costs.
In forward mode, the estimate remains approximately $970$ seconds per full pass because continuous streaming keeps the gap cost amortized.
In backward mode, each reversal of direction introduces an additional overhead of $32$ ms per operation boundary. With $100{,}000$ blocks, each block boundary contributes an extra
$$ 3.2 \cdot 10^{-2} \text{ seconds}, $$
so the added overhead is
$$ 100{,}000 \cdot 3.2 \cdot 10^{-2} = 3.2 \cdot 10^{3} \text{ seconds}. $$
Thus a backward-access pass requires approximately
$$ 970 + 3200 = 4170 \text{ seconds}. $$
The paired-tape organization does not change this conclusion because direction changes occur per physical operation boundary, not per logical stream.
Hence forward operation is about four times faster than backward operation for this workload under the given tape model.
$$ \boxed{\text{(a) 16 buffers;\quad (b) forward } \approx 970\text{ s/pass, backward } \approx 4170\text{ s/pass}} $$
Verification
Each logical tape in a 3-way merge is split into two physical streams, and independent buffering is required to maintain simultaneous readiness of both streams, producing $4P = 12$ input buffers. The output mechanism mirrors the same duplication for continuous writing, producing $4$ output buffers.
The time estimate is consistent with the linear model of tape I/O in Section 5.4.6, where block transfer time is dominated by interblock gaps. The backward penalty is applied once per operation boundary and therefore scales linearly with the number of blocks, producing the stated additive overhead.
This completes the verification. ∎