Information Technology Reference
In-Depth Information
Chapter Notes
Hong and Kung [ 137 ] introduced the first formal model for the I/O complexity of problems,
the red-blue pebble game, an extension of the pebble game introduced by Paterson and Hewitt
[ 239 ]. The analysis of Section 11.1.2 is due to Kung [ 178 ]. Hong and Kung derived lower
bounds on the number of I/O operations needed for specific graphs for matrix multiplication
(Theorem 11.5.2 ), the FFT (Theorem 11.5.4 ), odd-even transposition sort and a number of
other problems. Savage [ 295 ] generalized the red-blue pebble game to the memory-hierarchy
game, simplified the proof of Theorem 11.4.1 , and obtained Theorems 11.5.3 and 11.5.5 and
the results of Section 11.3 . Lemma 11.5.2 is implicit in the work of Hong and Kung [ 137 ];
the simplified proof given here is due to Agrawal and Vitter [ 9 ]. The results of Section 11.5.4
are due to Savage [ 295 ].
The two-level contiguous block-transfer model of Section 11.8.1 was introduced by Savage
and Vitter [ 296 ] in the context of parallel space-time tradeoffs. The analysis of sorting of
Section 11.8.1 is due to Agrawal and Vitter [ 9 ]. In this paper they also derive similar bounds
on the I/O time to realize the FFT, permutation networks and matrix transposition.
The hierarchical memory model of Section 11.9 was introduced by Aggarwal, Alpern,
Chandra, and Snir [ 7 ]. They studied a number of problems including matrix multiplication,
the FFT, sorting and circuit simulation, and examined logarithmic, linear, and polynomial
cost functions. The two-level bounds of Section 11.10 are due to Sleator and Tarjan [ 311 ].
Aggarwal, Alpern, Chandra, and Snir [7] extended this model to multiple levels. The MIN
page-replacement algorithm described in Section 11.10 is due to Belady [ 35 ].
Two other I/O models of interest are the BT model and the uniform memory hierarchy.
Aggarwal, Chandra, and Snir [ 8 ] introduced the BT model , an extension of the HMM model
supporting block transfers in which a block of size b ending at location x is allowed to move
in time f ( x )+ b . They establish tight bounds on computation time for problems including
matrix transpose, FFT, and sorting using the cost functions
, x ,and x α for 1
1.
Alpern, Carter, and Feig [ 18 ] introduced the uniform memory hierarchy in which the
u th memory has capacity αρ 2 u , block size ρ u , and time ρ u ( u ) to move a block between
levels; β ( u ) is a bandwidth function. They allow I/O overlap between levels and determine
conditions under which matrix transposition, matrix multiplication, and Fourier transforms
can and cannot be done efficiently.
Vitter and Shriver [ 354 ] have examined three parallel memory systems in which the mem-
ories are disks with block transfer, of the HMM type, or of the BT type. They present a
randomized version of distribution sort that meets the lower bounds for these models of com-
putation. Nodine and Vitter [ 232 ] give an optimal deterministic sorting algorithm for these
memory models.
log x
α
Search WWH ::




Custom Search