Detection Period and the number of Sublists

Determining the length of the detection period is an important design issue that requires a trade-off. If the detection period is too long, the scheme will not be adaptive to possible changes of the reference pattern within a detection period. On the other hand, if the period is too short, the scheme would incur too much overhead to be practical. Moreover, if the period is too short, a short burst of references may mislead the detection. For example, a probabilistic reference pattern may be mistaken for a looping reference pattern when a small number of blocks are repeatedly accessed over two detection periods while satisfying the detection condition for a looping reference pattern.

 

Table 5: The effect of the detection period on the performance of the DEAR scheme for the single application case.

Scheme	Detection	Response Time (seconds)
	Period	cscope	glimpse	sort	cpp	gnuplot	postgres1	postgres2
	100	12.85	33.70	13.72	98.81	40.92	34.62	76.56
	250	12.79	33.68	13.30	91.54	40.93	34.13	72.30
DEAR	500	12.87	33.73	13.60	91.61	41.39	34.22	71.15
	1000	13.52	36.26	13.88	91.78	41.66	34.53	72.41
	2000	15.20	36.45	15.77	91.99	42.36	34.84	72.53
LRU	N/A	19.77	39.55	16.59	93.39	44.30	38.82	74.75

 

The above trade-off relationship is evident in Table 5 that gives the response time of all but the link application as the detection period varies from 100 to 2000. We exclude the link application since as we mentioned earlier all of its blocks fit into the buffer cache. Thus different detection periods do not make any difference. For most applications, the best performance was obtained when the detection period is either 250 or 500. The results also show that even with detection periods that are considerably smaller or larger than these optimal values, the DEAR scheme performs better than the LRU scheme in FreeBSD. The exceptions are with the cpp and postgres2 applications when the detection period is 100. In the two cases, the performance degradation is considerably larger than the others at the detection period of 100. A careful inspection of the results revealed that when the detection period is 100 the DEAR scheme mistakenly detects both applications to have a looping reference pattern when in reality it was part of a probabilistic reference pattern. The multiple application case shows a similar effect of the detection period on the performance as we can see in Table 6.

Table 6: The effect of the detection period on the performance of the DEAR scheme for the multiple application case.

Scheme	Detection	Response Time (seconds)
	Period	cs+sort	gli+link	cpp+ps1	gli+ps2	cs+sort+link	gli+sort+cpp
	100	66.68	73.54	236.29	144.67	108.86	251.54
	250	65.84	73.41	216.62	136.86	108.62	230.61
DEAR	500	66.61	74.29	216.73	139.88	112.73	235.56
	1000	67.34	74.99	216.91	139.24	116.30	238.70
	2000	68.70	81.69	219.38	139.34	116.84	241.41
LRU	N/A	70.96	89.87	229.99	155.27	118.03	245.34

Table 7: The effect of the number of sublists on the detection results of the DEAR scheme.

Application	Detection Results
	Number of sublists = 3	Number of sublists = 5	Number of sublists = 7
cscope	seq[3],loop[8]	seq[3],loop[8]	seq[3],loop[8]
glimpse	seq[4],loop[8]	seq[4],loop[8]	seq[3],loop[9]
sort	seq[3],loop[3]	seq[3],loop[2],undetect[1]	seq[3],loop[2],undetect[1]
link	seq[3],loop[5]	seq[3],loop[5]	seq[3],loop[5]
cpp	prob[18]	prob[18]	prob[13],undetect[5]
gnuplot	seq[1],loop[6]	seq[1],loop[6]	seq[1],loop[6]
postgres1	seq[5],loop[16]	seq[5],loop[16]	seq[5],loop[16]
postgres2	prob[13],loop[5],seq[2],undetect[1]	prob[12],loop[4],seq[2],undetect[3]	prob[11],loop[3],seq[2],undetect[5]

The number of sublists used in the detection process can also affect the detection results of the DEAR scheme. Table 7 gives the detection results of the DEAR scheme as the number of sublists increases from three to seven. From the results, we can notice that the number of sublists hardly affects the detection results although there is a slight increase in the number of undetected cases as the number of sublists increases due to a more strict detection rule. Remember that to detect a reference pattern the associated detection rule should be held for all the sublists.