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.
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).
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:
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.