Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

LIX caching

Hello,
I have a doubt concerning the "broadcast disks and caching" exercise. In question 2, for the LIX part, you are updating the running access probabilities for each page whenever the page appears in the broadcast: p1 is updated at time 1, p2 at time 2, p3 at time 3, p1 at time 4, etc.
In the lecture, however, it is said that the value is updated only when the data item is consumed by the application. This is also shown in the example of slide 25. If we follow this example, we should update p1 at time 1, nobody at time 2, p3 at time 3, etc.
Which convention is the right one?
Thanks a lot.
Posted by Ghid Maatouk on Friday 18 January 2008 at 20:01
Comments
Same Remark indeed... I would believe the slides are right because it makes sense, since pi is a "real-time" estimate... In the solution provided it is shown as some "offline" estimate. Can a TA confirm please?
Posted by Alexandre Imperatori on Sunday 20 January 2008 at 13:24
seems to be a few issues with this exercise.
question 1,
Part1:
the chunks don't seem to match the definition given in the lectures (page 16), that is:
Cij, j=1,...,ci
and ci=cmax/fi
so for example c1=2/2=1 so j is only 1 and there is no 2. why is there a C12 here?!
how many disks are there here, 2 or 3? that is do we group them based on their access probability or based on the square root results.

Part2:
LRU:
the 4th step, when P4 received and cached it should be P1 evicted from the cache and not P3, since P3 was just used in the last step and hence not the LRU. the next line counts for this correctly by saying P1 is dropped and P4, which we cached in the previous step remains in the cache.
the number of steps are quite vague, when a data page is received and dropped, do we count this as a step? second line seems to be considering this when P2 is received and dropped, but not the rest of the solution.
and what happens when E is encountered, does that count as a wait time and hence a step?

LIX:
here it seems like there are 2 disks and disk Pi is updated when any data is received from the disk. but as the other two folks mentioned, why are the Pi of the data pages updated when the page is broadcasted and not when it is consumed?
Posted by Pooya Pakzad on Tuesday 22 January 2008 at 21:30
> question 1,
> Part1:
> the chunks don't seem to match the definition given in the lectures (page 16), that > is: Cij, j=1,...,ci ...
We have 2 disks there, they are spinning with different speeds. You can also group the disks based on their probabilities in which you have 3 disks.

Part2:
LRU:
> the 4th step, when P4 received and cached it should be P1 evicted from the cache > and not P3, since P3 was just used in the last step and hence not the LRU. the next >line counts for this correctly by saying P1 is dropped and P4, which we cached in the > previous step remains in the cache.
> the number of steps are quite vague, when a data page is received and dropped,
> do we count this as a step? second line seems to be considering this when P2 is
> received and dropped, but not the rest of the solution
> and what happens when E is encountered, does that count as a wait time and
> hence a step?

What is the most recently used element there, at step four you have to cache P4 and P1 (step 3) and remove the items used at step 2 [which is p3].
For the steps, How many data items in the broadcast you should visit to answer the query.


LIX:
> here it seems like there are 2 disks and disk Pi is updated when any data is
> received from the disk. but as the other two folks mentioned, why are the Pi of the
> data pages updated when the page is broadcasted and not when it is consumed?
The probability is updated whenever there is a page hit.
See page 20 of :https://drum.umd.edu/dspace/bitstream/1903/671/2/CS-TR-3369.pdf

Best,
AliS
Posted by Ali Salehi on Wednesday 23 January 2008 at 10:43