**Next:** Implementation of the DEAR **Up:**
An Implementation Study of **Previous:** Introduction

Recent research has shown that most applications show regular block reference patterns and that these patterns vary depending on the nature of the application. For example, a large class of scientific applications show a looping reference pattern where blocks are referenced repeatedly with regular intervals [16]. On the other hand, many database applications show a probabilistic reference pattern with different probabilities for index blocks and data blocks [17]. Unix applications tend to show either a sequential or a temporally-clustered reference pattern [12,18]. Applications that deal with continuous media generally show a sequential or a looping reference pattern [19].

From these observations, we classify an application's reference pattern into one of the
following: sequential, looping, temporally-clustered, or probabilistic reference
pattern [20]. In the proposed DEAR scheme, the
detection of an application's reference pattern is made by associating attributes of
blocks with their forward distances, which are defined as the time intervals between the
current time and the times of the next references. An attribute of a block can be anything
that can be obtained from its past reference behavior including backward distance,
frequency, inter-reference gap (IRG) [6], and *k*-th
backward distance [4]. In this paper, we consider
only two block attribute types: backward distance, which is the time interval between the
current time and the time of the last reference^{1}, and frequency, which is the number of past
references to the block.

The detection is performed by a monitoring process that is invoked periodically. At the
time of its *i*-th invocation (we denote this time by *m _{i}*), the
monitoring process calculates the forward distances (as seen from the standpoint of

**Figure 1:** Detection process: two-stage pipeline with
one-level look-behind.

After the detection, the block attributes of the blocks referenced between *m _{i-1}*
and

**Figure 2:** Example of block reference pattern detection.

As an example, consider Figure 2. Assume
that the period of the monitoring process (i.e., detection period) is 10 as measured in
the number of block references made by the associated application. Also assume that
between *m _{i-1}* = 40 and

**Sequential Pattern:**- A sequential reference pattern has the property that all blocks are referenced one after
the other and never referenced again. In this pattern, the average forward distance of all
the sublists is . Therefore,
a reference pattern is sequential if
where
*sublist*and^{bd}_{i}*sublist*are the^{fr}_{i}*i*-th sublist for the backward distance and frequency block attribute types, respectively, and is the average forward distance of blocks in*sublist*. **Looping Pattern:**- A looping reference pattern has the property that blocks are referenced repeatedly with
a regular interval. In this pattern, a block with a larger backward distance has a smaller
forward distance. Therefore, a reference pattern is looping if the following relationship
holds: if
*i*<*j*then . **Temporally-clustered Pattern:**- A temporally-clustered reference pattern has the property that a block referenced more
recently will be referenced sooner in the future. Thus, a block with a smaller backward
distance has a smaller forward distance. Therefore, a reference pattern is
temporally-clustered if the following relationship holds: if
*i*<*j*then . **Probabilistic Pattern:**- A probabilistic reference pattern has a non-uniform block reference behavior that can be
modeled by the Independent Reference Model (IRM) [21].
Each block
*b*has a stationary probability_{i}*p*and all blocks are independently referenced with the associated probabilities. Under the stationary and independent condition, the expected forward distance of_{i}*b*is proportional to 1/_{i}*p*. Thus, a block with a higher frequency has a smaller forward distance. Therefore, a reference pattern is probabilistic if the following relationship holds: if_{i}*i*<*j*then .

In the DEAR scheme, different replacement policies are used for different applications depending on the detected reference pattern. For the sequential and looping reference patterns, the MRU replacement policy is used where the block with the smallest backward distance is always selected for replacement. For the temporally-clustered reference pattern, the LRU replacement policy, which replaces the block with the largest backward distance, is used. Finally, for the probabilistic reference pattern, the LFU replacement policy that replaces the block with the lowest reference frequency is used.

**Next:** Implementation of the DEAR **Up:**
An Implementation Study of **Previous:** Introduction