Information Technology Reference
In-Depth Information
THE HIERARCHICAL MEMORY MODEL
11.20 Derive the following lower bounds on the cost of computing the following functions
when the cost function is
ν
(
a
)=
a
α
:
⎧
⎨
Ω(
n
2
α
+
2
)
if
α>
1
/
2
K
ν
(
f
(
n
)
Ω(
n
3
log
n
)
if
α
=
1
/
2
Matrix multiplication:
B
)=
A
×
⎩
Ω(
n
3
)
if
α<
1
/
2
(
n
)
c
(
F
(
d
)
)=Ω(
n
α
+
1
)
Fast Fourier transform:
K
K
ν
(
f
(
n
)
BS
)=Ω(
n
α
)
Binary search:
Hint:
Use the following identity to recast expressions for the computation time:
n
n−
1
Δ
g
(
k
)
h
(
k
)=
−
Δ
h
(
k
)
g
(
k
+
1
)+
g
(
n
+
1
)
h
(
n
)
−
g
(
1
)
h
(
1
)
k
=
1
k
=
1
11.21 A cost function
ν
(
a
)
is
polynomially bounded
if for some
K>
1andall
a
≥
1.
ν
(
2
a
)
Kν
(
a
)
.Letthecostfunction
ν
(
a
)
be polynomially bounded. Show that
there are positive constants
c
and
d
such that
ν
(
a
)
≤
ca
d
.
11.22 Derive a good upper bound on the cost to sort in the HMM with the logarithmic cost
function
≤
log
a
.
COMPETITIVE MEMORY MANAGEMENT
11.23 By analogy with the proof for FIFO in the proof of Theorem
11.10.1
,considerany
memory-address sequence
s
and a contiguous subsequence
t
of
s
that immediately
follows a page fault under LRU and during which LRU makes
φ
LRU
=
f
≤
n
LRU
page faults. Show that at least
f
different pages are accessed by LRU during
t
.
11.24 Let A be any online page-replacement algorithm that uses
n
A
pages of primary memory.
Show that there are arbitrarily long memory-address sequences
s
such that the number
of page faults with A,
F
A
(
s
)
, satisfies the following lower bound, where
n
MIN
is the
number of pages used by the optimal algorithm MIN:
n
A
F
A
(
s
)
≥
n
MIN
+
1
F
MIN
(
s
)
n
A
−
Hint:
Design a memory-address sequence
s
of length
n
A
with the property that the
first
n
A
−
n
MIN
+
1 accesses by A are to pages that are neither in A's or MIN's primary
memory. Let
be the
n
A
+
1 pages that are either in MIN's primary memory initially
or those accessed by A during the first
n
A
−
S
n
MIN
+
1 accesses. Let the next
n
MIN
−
1
page accesses by A be to pages not in
S
.
Search WWH ::
Custom Search