Information Technology Reference
In-Depth Information
Similar results can be obtained for the permutation networks defined in Section
7.8.2
(see
Problem
11.18
), the FFT defined in Section
6.7.3
(see Problem
11.19
), and matrix transposi-
tion defined in Section
6.5.4
(see [
9
]).
11.9 The Hierarchical Memory Model
In this section we define the hierarchical memory model and derive bounds on the time to do
matrix multiplication, the FFT and binary search in this model. These results provide another
opportunity to evaluate the performance of memory hierarchies, this time with a single cost
function applied to memory accesses at all levels of a hierarchy. We make use of lower bounds
derived earlier in this chapter.
DEFINITION
11.9.1
The
hierarchical memory model
(HMM) is a serial computer in which a
CPU without registers is attached to a random-access memory of unlimited size for which the time
to access location
a
for reading or writing is the value of a monotone nondecreasing
cost function
ν
(
a
):
→
from the integers
=
{
0, 1, 2, 3,
...
}
to
.The
cost of computing
f
(
n
)
:
n
m
with the HMM
using the cost function
ν
(
a
)
,
A
→A
K
ν
(
f
)
,isdefinedas
x
T
(
)
K
ν
(
f
)=max
x
ν
(
a
j
)
(11.2)
j
=
1
where
a
j
,
1
T
(
x
)
, is the address accessed by the CPU on the
j
th computational step and
T
(
x
)
is the number of steps when the input is
x
.
≤
j
≤
The HMM with cost function
ν
(
a
)=
1 is the standard random-access machine described
in Section
3.4
. While in principle the HMM can model many of the details of the MHG, it
is more difficult to make explicit the dependence of
ν
(
a
)
on the amount of memory at each
level in the hierarchy as well as the time for a memory access in seconds at that level. Even
though the HMM can model programs with branching and looping, following [
7
] we assume
straight-line programs when studying the FFT and matrix-matrix multiplication problems with
this model.
Let
n
(
f
,
x
,
a
)
be the number of times that address
a
is accessed in the HMM for
f
on
input
x
. It follows that the cost
K
ν
(
f
)
can be expressed as follows:
K
ν
(
f
)= max
x
n
(
f
,
x
,
a
)
ν
(
a
)
(11.3)
1
≤a
,
ν
(
a
)=
a
α
,and
ν
(
a
)=
U
m
(
a
)
,where
U
m
(
a
)
is the following threshold function with threshold
m
:
Many cost functions have been studied in the HMM, including
ν
(
a
)=
log
2
a
1
m
0 t r ise
a
≥
U
m
(
a
)=
It follows that
K
U
m
(
f
)=max
n
(
f
,
x
,
a
)
x
m≤a
Search WWH ::
Custom Search