TAOCP 5.4.9 Exercise 4
We first recall the standard “square root buffer allocation scheme” described in the text.
Section 5.4.9: Disks and Drums
Exercise 4. ▶ [M21] Consider a modified form of the square root buffer allocation scheme, in which all $P$ of the input buffers have equal length, but the output buffer size should be chosen so as to minimize seek time.
a) Derive a formula corresponding to (2), for the running time of an $L$-character $P$-way merge.
b) Show that the construction in Theorem K can be modified in order to obtain a merge pattern that is optimal according to your formula from part (a).
5.4.9 DISKS AND DRUMS 377
Verified: no
Solve time: 11m05s
Solution
Part (a)
We first recall the standard “square root buffer allocation scheme” described in the text.
A P-way merge reads from P input runs of lengths L₁, …, Lₚ (total length L = ∑ Lᵢ) and writes one output run of length L.
The available internal memory for buffers is M characters.
Let the input buffer sizes be b₁, …, bₚ and the output buffer size be c, with
∑ᵢ bᵢ + c = M.
On a MIXTEC disk the transmission time per character is τ = 5 µs, and the average seek time (including latency when full tracks are used) is σ = 60 ms.
Each time a buffer is exhausted (input) or filled (output) a new disk block must be accessed, incurring one seek.
The number of seeks is therefore approximately
∑ᵢ Lᵢ/bᵢ + L/c = L/b + L/c
when all input buffers have equal size b = b₁ = … = bₚ.
The total running time is
T = τL + σ(L/b + L/c).
Using the memory constraint P b + c = M, we write b = (M − c)/P and obtain
T(c) = τL + σL ( P/(M−c) + 1/c ).
The output buffer size c is to be chosen so as to minimize the seek time, i.e. to minimize
f(c) = P/(M−c) + 1/c , 0 < c < M.
Setting the derivative to zero:
f′(c) = P/(M−c)² − 1/c² = 0 ⇒ √P/(M−c) = 1/c ⇒ c = M/(1+√P).
Then b = (M−c)/P = M/(P+√P).
Substituting these optimal values back gives the minimum number of seeks
L/b + L/c = L(1+√P)²/M.
Hence the minimum running time for an L-character P-way merge under the modified scheme is
[ \boxed{T_{\text{min}}(L,P) = \tau L + \sigma L,\frac{(1+\sqrt{P})^{2}}{M}} \tag{2'} ]
This is the formula corresponding to equation (2) in the text (which gives T = τL + σ(∑√Lᵢ + √L)²/M for the unconstrained square root allocation).
Part (b)
In the text, Theorem K establishes that for a cost function of the form
C(T) = α D(T) + β E(T)
where D(T) is the external path length of the merge tree T and E(T) = ∑ᵥ g(deg v) W(v) (the sum over internal nodes v of a degree‑dependent coefficient g(deg v) times the total weight W(v) of the subtree rooted at v), the optimal merge pattern can be constructed by a generalized Huffman algorithm: repeatedly combine the smallest available runs into a new node, choosing the degree d (subject to the maximum degree Pₘₐₓ allowed by the internal memory) that minimizes the incremental cost per unit weight.
From part (a) the cost of a single P-way merge of total length L is
Tₘᵢₙ(L,P) = L ⋅ w(P),
with w(P) = τ + σ(1+√P)²/M.
Therefore the total cost of a merge tree T is
C(T) = ∑ᵥ w(deg v) W(v)
= τ ∑ᵥ W(v) + (σ/M) ∑ᵥ (1+√{deg v})² W(v)
= τ D(T) + (σ/M) E'(T),
where E'(T) = ∑ᵥ (1+√{deg v})² W(v).
This is exactly of the form required by Theorem K with α = τ, β = σ/M, and g(d) = (1+√d)².
The proof of Theorem K relies only on the linearity of the cost in the subtree weights and the fact that the degree‑dependent coefficients are fixed constants; it does not depend on the specific functional form of g(d). Consequently, the construction given in Theorem K remains optimal for our modified cost function. One simply replaces the coefficients used in that construction with w(d) = τ + σ(1+√d)²/M (or, equivalently, α = τ, β = σ/M, g(d) = (1+√d)²) and observes that the maximum merge order Pₘₐₓ is still determined by the available buffer memory M as in the original theorem.
Thus the optimal merge pattern for the modified square root buffer allocation scheme is obtained by the same algorithmic construction as in Theorem K, with the updated coefficients. ∎