Information Technology Reference
In-Depth Information
clock time (i.e., it has only one timestamp),
and the case that their non-recent time
stamps have a difference larger than 1.
The current sequence size reaches 128,
bottom. In this way, only block misses could trig-
ger sequencing and the eviction section refilling
operations. While being compared with the miss
penalty, these costs are very small.
The second issue is how the sequences in the
eviction section are ordered for replacement ac-
cording to their temporal and spatial locality. We
adopt an algorithm similar to
GreedyDual-Size
used in Web file caching (Cao et al. 2007). It
makes its replacement decision by considering the
recency, size, and fetching cost of cached files. In
our case, file size is equivalent to sequence size, and
file fetching cost is equivalent to the I/O operation
cost for a sequence access. For sequences whose
sizes are distributed in a reasonable range, which
is limited by bank size, we currently assume their
fetching cost is the same. Our algorithm can be
modified to accommodate cost variance if neces-
sary in the future.
The DULO algorithm associates each sequence
with a value
H
, where a relatively small value
indicates the sequence should be evicted first. The
algorithm has a global inflation value
L
, which
records the H value of the most recent evicted
sequence. When a new sequence
s
is admitted into
the eviction section, its
H
value is set as
H(s) =
L + 1/size(s)
, where
size(s)
is the number of the
blocks contained in
s
. The sequences in the eviction
section are sorted by their H values with sequences
of small
H
values at the LRU stack bottom. In the
algorithm a sequence of large size tends to stay at
the stack bottom and to be evicted first. However,
if a sequence of small size is not accessed for a
relatively long time, it will be replaced. This is
because a newly admitted long sequence could
have a larger H value due to the L value, which is
continuously being inflated by the evicted blocks.
When all sequences are random blocks (i.e., their
sizes are 1), the algorithm degenerates into the
LRU replacement algorithm.
As we have mentioned before, once a bank
size of blocks are replaced from the eviction sec-
tion, we take the blocks in the sequencing bank to
form sequences and order the sequences by their
•
which is the maximal allowed sequence
size and we deem to be sufficient to amor-
tize a disk operation cost.
If any one of the conditions is met, a complete
sequence has been formed and a new sequence
starts to be formed. Otherwise, block B becomes
part of the sequence, the following blocks will be
tested continuously.
the dulo replacement algorithm
There are two challenging issues to be addressed in
the design of the DULO replacement algorithm.
The first issue is the potentially prohibitive
overhead associated with the DULO scheme. In
the strict LRU algorithm, both missed blocks and
hit blocks are required to move to the stack top.
This means that a hit on a block in the eviction
section is associated with a bank sequencing cost
and a cost for sequence ordering in the eviction
section. These additional costs that can incur in a
system with few memory misses are unacceptable.
In fact, the strict LRU algorithm is seldom used
in real systems because of its overhead associated
with every memory reference (Jiang et al. 2005).
Instead, its variant, the CLOCK replacement
algorithm, has been widely used in practice. In
CLOCK, when a block is hit, it is only flagged
as
young
block without being moved to the stack
top. When a block has to be replaced, the block
at the stack bottom is examined. If it is a young
block, it is moved to the stack top and its ``young
block'' status is revoked. Otherwise, the block
is replaced. It is known that CLOCK simulates
LRU behaviors very closely and its hit ratios are
very close to those of LRU. For this reason, we
build the DULO replacement algorithm based
on the CLOCK algorithm. That is, it delays the
movement of a hit block until it reaches the stack
Search WWH ::
Custom Search