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