Check out the new USENIX Web site.

next up previous
Next: Implementation of the DEAR Up: An Implementation Study of Previous: Introduction


The DEAR Scheme


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 reference1, 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 mi), the monitoring process calculates the forward distances (as seen from the standpoint of mi-1) of the blocks referenced between mi-1 and mi. From the block attribute values of those blocks, also as seen from the standpoint of mi-1, the monitoring process builds two ordered lists using those blocks, one according to backward distance and the other according to frequency. Each ordered list is divided into a fixed number of sublists of equal size. Based on the relationship between the attribute value of each sublist and the average forward distance of blocks in the sublist, the block reference pattern of the application is deduced.

 

\begin{figure}
\begin{center}
\epsfbox{pipeline1.eps}\leavevmode
\end{center}\end{figure}

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

 

After the detection, the block attributes of the blocks referenced between mi-1 and mi are updated for the next detection at mi+1. As shown in Figure 1, the detection process is essentially a two-stage pipeline with one-level look-behind (i.e., the detection at mi is made based on the relationship between the block attribute values and the forward distance at mi-1).


\begin{figure}
\begin{center}
\epsfbox{example.eps}\leavevmode
\end{center}\end{figure}

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 mi-1 = 40 and mi = 50, blocks b4, b2, b6, b12, b4, b8, b11, b6, b4, and b6 were referenced in the given order (see Figure 2-(b)). Note that there are 10 block references since the detection period is 10. Finally, assume that at mi-1 the backward distance and frequency of the six distinct blocks b4, b2, b6, b12, b8, b11 were 15, 12, 25, 4, 20, 9 and 6, 4, 5, 2, 1, 1, respectively (see Figure 2-(a)). Note that these distinct blocks have forward distances of 1, 2, 3, 4, 6, 7, respectively as seen at mi-1. From the information about the block attribute values and the forward distance as seen at mi-1, at mi the DEAR scheme constructs two ordered lists, one according to backward distance and the other according to frequency (see Figure 2-(c)). Each list is divided into a number of sublists of equal size (3 sublists of size 2, in this example). Then various rules for detecting reference patterns, which are explained below, are applied to the two lists. In this particular example, blocks with higher frequency have smaller forward distance, which allows us to deduce that the block reference pattern of the given application follows a probabilistic reference pattern. The detection rules for all the reference patterns we consider are as follows:

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 $\infty$. Therefore, a reference pattern is sequential if ${\bf Avg\_fd}(sublist^{bd}_{1}) = {\bf Avg\_fd}(sublist^{bd}_{2}) =
\cdots = {\bf Avg\_fd}(sublist^{fr}_{1}) = {\bf Avg\_fd}(sublist^{fr}_{2})$ $= \cdots = \infty$ where sublistbdi and sublistfri are the i-th sublist for the backward distance and frequency block attribute types, respectively, and ${\bf Avg\_fd}(sublist)$ 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 ${\bf Avg\_fd}(sublist^{bd}_{i}) >
{\bf Avg\_fd}(sublist^{bd}_{j})$.
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 ${\bf Avg\_fd}(sublist^{bd}_{i}) < {\bf Avg\_fd}(sublist^{bd}_{j})$.
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 bi has a stationary probability pi and all blocks are independently referenced with the associated probabilities. Under the stationary and independent condition, the expected forward distance of bi is proportional to 1/pi. 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 < j then ${\bf Avg\_fd}(sublist^{fr}_{i}) > {\bf Avg\_fd}(sublist^{fr}_{j})$.

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 up previous
Next: Implementation of the DEAR Up: An Implementation Study of Previous: Introduction

Jongmoo Choi
1999-04-22