Information Technology Reference
In-Depth Information
For the FFT graph in the standard MHG, instead of pebbling FFT subgraphs on 2
d
r
inputs, we pebble
b
l
FFT subgraphs on 2
d
r
/b
l
inputs (assuming that
b
l
is a power of 2).
Doing so allows all the data moving back and forth in blocks between memories to be used
and accommodates the transposition mentioned at the beginning of Section
11.5.3
.Ths
provides an upper bound of
O
(
n
log
n/
(
b
l−
1
log(
s
l−
1
/b
l−
1
)))
on t
he I/O time at level
l
.
Clearly, when
b
l−
1
is much smaller than
s
l−
1
,say
b
l−
1
=
O
(
√
s
l−
1
)
, the upper and lower
bounds match to within a multiplicative factor. (This follows because we divide
n
by
b
l−
1
and
log
b
l−
1
=
O
(log
s
l−
1
)
.) These observations apply to the FFT-based problems as well.
11.7 Simulating a Fast Memory in the MHG
In this section we revisit the discussion of Section
11.1.2
, taking into account that a memory
hierarchy may have many levels and that data is moved in blocks.
We ask the question, “How do we assess the effectiveness of a memory hierarchy on a
particular problem?” For several problems we have upper and lower bounds on their number of
computation and I/O steps in memory hierarchies parameterized by block sizes and numbers of
storage locations. If we add to this mix the time to move a block between levels, we can derive
bounds on the time for all computation and I/O steps. We then ask under what conditions
this time is the best possible. Since data must typically be stored and retrieved from archival
memory, we cannot expect the performance to exceed that of a two-level hierarchy (modeled
by the red-blue pebble game) in which all the available storage locations, except for those in
the archival memory, are in first-level storage. For this reason we use the two-level memory
as our reference model. We now define these terms and state a condition for optimality of a
pebbling strategy.
For 1
≤
l
≤
L
−
1welet
t
l
be the time to move one block of
b
l
words between levels
l
−
1
and
l
of a memory hierarchy, measured as a multiple of the time to perform one computation
step. Thus, the time for one computation step is
t
1
=
1.
Let
be a pebbling strategy for a graph
G
in the
L
-level MHG that uses the resource
vector
p
=(
p
1
,
p
2
,
...
,
p
L−
1
)
(
p
l
pebbles are used at the
l
th level) and moves data in blocks
of size specified by
b
=(
b
2
,
b
3
,
...
,
b
L
)
(
b
l
words are moved between levels
(
l
P
−
1
)
and
l
). Let
T
(
L
)
l
(
p
,
b
,
G
)
denote the number of level-
l
I/O operations with
P
on
G
.Wedefinethe
time
P
,
T
(
P
,
G
)
on the graph
G
as
for the pebbling strategy
L
T
(
L
)
l
T
(
P
,
G
)=
t
l
·
(
p
,
b
,
G
)
l
=
1
Thus,
T
(
,
G
)
measures the absolute time expended to pebble a graph relative to the time
to perform one computation step under the assumption that I/O operations cannot be over-
lapped.
From the above discussion, a pebbling is efficient if
T
(
P
,
G
)
is at most some small multiple
of
T
(
2
1
(
s
L−
1
,
G
)
, the normalized time to pebble
G
in the red-blue pebble game when all the
pebbles at level
L
P
−
1orlessintheMHG(thereare
s
L−
1
such pebbles) are used as if they
were red pebbles.
A two-level computation exhibits
locality of reference
if it is likely in the near future
to refer to words currently in its primary memory. Such computations perform fewer I/O
operations than those that don't meet this condition. This idea extends to multiple levels: a
Search WWH ::
Custom Search