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 reference¹, 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 m_i-1) of the blocks referenced between m_i-1 and m_i. From the block attribute values of those blocks, also as seen from the standpoint of m_i-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.

 

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 m_i are updated for the next detection at m_i+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 m_i is made based on the relationship between the block attribute values and the forward distance at m_i-1).

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 m_i = 50, blocks b₄, b₂, b₆, b₁₂, b₄, b₈, b₁₁, b₆, b₄, and b₆ 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 m_i-1 the backward distance and frequency of the six distinct blocks b₄, b₂, b₆, b₁₂, b₈, b₁₁ 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 m_i-1. From the information about the block attribute values and the forward distance as seen at m_i-1, at m_i 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 sublist^bd_i and sublist^fr_i 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 b_i has a stationary probability p_i and all blocks are independently referenced with the associated probabilities. Under the stationary and independent condition, the expected forward distance of b_i is proportional to 1/p_i. 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.