next up previous
Next: Comparison with Application-controlled File Up: Sensitivity Analysis Previous: Cache Size


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.


next up previous
Next: Comparison with Application-controlled File Up: Sensitivity Analysis Previous: Cache Size

Jongmoo Choi
1999-04-22