In the previous lessons, we looked at the basic I/O model. We saw how to analyze algorithms in that model, and we looked at two particular types of I/O efficient algorithms, cache-aware algorithms that need to know the memory size and the block size, and cache oblivious algorithms. For cache oblivious algorithms, the assumption was that the replacement policy was optimal. So in this lesson, we're going to have a closer look at replacement policies and see that this assumption is maybe not as unrealistic as it seems. So, let's first briefly look again at what a replacement policy actually does. So, remember that in the I/O model what happens is that when an algorithm needs to compute with a certain data elements. If the data element is not present in the internal memory, it needs to read it from the external memory. But before it can do so, if the internal memory is already full, it first needs to write back or evict a block from the internal memory to the external memory, and which block is being evicted to make room for the new block that is needed that is done by what is called the replacement policy. So, there are different types of replacement policies. So, let's first look at the replacement policy that you would actually want to have. So, this is called Longest Forward Distance and it's pretty easy to see what you do is that, you look at all the blocks. Now, you have to decide which one to write back. Well, for instance, if there is a block that you would never need again, well then obviously that would be a good choice to evict because you're not going to use it again. Otherwise, what you do is you look at all your blocks and you see which one you are not going to need for the longest time, and that's the one that you're going to evict. So, this policy intuitively it's clear, but you can also prove it. This is the best you can do. So, this is the optimal policy. That's why it's also called MIN. It performs the minimum possible number of I/O's. But unfortunately, you actually cannot implement this because the operating system does not know when the blocks are going to be needed in the future. So, this is what you would want to have, but it's not possible to implement. So instead, there's lots of different replacement policies that have been suggested. I had two of the most easy ones you could say are First In First Out and Least Recently Used. So, let's have a closer look at these two replacement policies. So, First In First Out is quite simple. So, what you do is you give a time stamp to every block in your internal memory, and then when you have to decide which block to evict when you need to make space, well then, you pick the block where the time stamp is the oldest time stamp. So, when you read a block then you read it at time T. That your time stamp, and then you look at all the blocks that you have when you have to write something back and you pick the one with the oldest time stamp. So, this is First In First Out. A different strategy is Least Recently Used and it's very similar. Again, you give a time stamp to every block and you evict the one with oldest time stamp the only difference is that the definition of time stamp is slightly different. Now, the time stamp of a block is the last time that it was used. So, not when it was read but when it was used. So, if you read something then at that point that's the time stamp, but if its at some later time it's still in internal memory and you use it again you update the time stamp. So, this is Least Recently Used, and this is actually a well known and pretty good replacement strategy. So, what we're going to do in the rest of this lesson is we're going to compare this Least Recently Used to MIN to this optimal replacement strategy. We're going to see that in some sense LRU is a pretty good approximation of MIN. So let's see. We want to look at the I/O efficiency of some algorithm and compare the I/O efficiency for these two different replacement policies. So, let me define LRU of this algorithm for a given memory size M to be well the number of I/Os that the algorithm would do if it would run under Least Recently Used with internal memory size M, and let's look at MIN of ALG, M is again the number of I/Os that the algorithm performs if it were run under this optimal replacement policy again with internal memory size M, and of course the B the block size will also play a role in the analysis. So, the bad news is the following, in some cases the LRU, so the number of I/Os that LRU performs for some given algorithm on memory size M could be much much larger than what you get for MIN. It could even be M divided by B which is a very large number times larger. So, this is really bad, but well, first of all this happens only for very special algorithms with very special memory sizes compared to block size, so in practice it's not really bad at all. To prove that, well, we cannot really prove a good relation between LRU for the algorithm for memory size M and MIN for the same memory size, but we can prove the following which is also very interesting. If you compare LRU to MIN but you give LRU twice as much internal memory size. Then it's almost as good as MIN or stated differently if I compare LRU for memory size M with the number of /IOs of MIN for memory size M divided by two. Then you see that it does at most twice as many I/Os. Actually the theorem is a little bit more general. You can even compare how many I/Os LRU does with memory size M compare to the number of I/Os for min with some memory size M prime. Now, if you plug in M prime is M divided by two in this formula that you see, then, you get the results in the theorem. For concreteness I'm just going to prove the theorem for M prime equals M divided by two but the act should be the same proof would also work in this more general setting. So, let's see if we can prove this theorem. So, I claim that if I run my algorithm under LRU with memory size M it performs at most twice as many IOs as I would get for MIN with memory size M divided by two. So, here's the proof. Let's look at the times at which the algorithm when it run using LRU is going to do an I/O is going to read a block, times t0, t1, t2 and so on. Let me partition time or maybe these time instances where it's going to do an I/O let me partition it into intervals, you could call it, as you see here. So, all intervals have well M divided by B reads in them except maybe for the first one where you have some fewer number of reads. If it's not a multiple of M divided by B the first one is a little bit smaller. All the other intervals are such that LRU does exactly M divided by B read operations. Now, let's try to compare this to the number of read operations being done by MIN with memory size only M divided by two. If you look at this first time interval, well, when you start everything is in the external memory. So, also for MIN. So, it also has to read all these blocks. So, here the number of I/Os is going to be the same. So, let's look at the more interesting part which is the second part. Okay. So, what we're going to show is that in each of these time intervals, where M divided by B read operations take place by LRU, if you look at MIN, then it actually reads at least. Well, you see M divided by 2B plus 1, number of blocks. Right. So, it needs at least half the number of read operations, and if we can prove that, well, that will prove the theorem that you see above. Okay. So, now the only thing that is left is to prove this claim. Okay. So, how can we prove this claim? Well, let's have a look at one such time interval, and let's say that the block that was used by the algorithm just before this time interval started, let's call that block b, and let's define B to be the set of all blocks used by the algorithm during this time interval. Right. Note that this B is the number of blocks that are used, not just the number of blocks that are read. But it could be that at the start of the time interval, there are already some blocks in the internal memory that are used maybe again during this time interval and they're also included in the set B. Okay. What I want to argue is that this set B contains at least M over B blocks, B prime which are not equal to b. Okay. Well, if during that time interval, you need at least or you use at least M divided by B blocks, well, remember MIN only had M divided by 2 size internal memory. So, if you use M over B blocks, well, the only ones where you do not have to read them are the ones that are already in the internal memory at the start of this time interval. Well, that's at most M over 2 divided by B. So, in total, the number of reads is at least M over B minus this M over 2 divided by B. Here you see the minus 1, and that's because the block B, this block was used just before the time interval started. Well, that one should be subtracted from this number. Okay. So, I want to show that this set capital B of all the blocks that are being used, that there are at least M divided by b blocks, not equal to this block b. So, the proof of this has three cases. The first case is that during this time interval, this block b will be evicted by least recently used. Okay. How can that happen? Well, remember that this block b was used just before the time interval started. So, at that point, it's the most recently used block. Well, if at some point it becomes the least recently used block, then in between, there must have been M divided by b are the blocks that have been used. So, in this case, if b is evicted before that can happen, well, you must have used at least M divided by b other blocks, otherwise, it would not be the least recently used. Okay. So, let's look at case 2. Case 2 is that LRU actually reads some block, b prime, which is not equal to b, twice during this time interval. Okay. What does it mean? Well, at some point, this block b prime is being read, then at some other point in time, it's read again. So, in between it will be evicted, but if it's read at some point, because it's used, and then later it's evicted, again similar argument as before. At this point, it was the most recently used block, when it was read. When it's evicted, it's the least recently used block. So, in between, again, there should be M divided by b other blocks that have been used. So, also in case 2, we can conclude that we use at least M divided by b other blocks. So, the only remaining cases were case 3, when case 1 doesn't apply, so b is not evicted, and case 2 doesn't apply, so no block is read twice. Well, if no block is read twice and b is not evicted, that means that b is not read either. Then, well, all the blocks that are read, and there's M divided by B of them in a time interval are distinct and they are not equal to b. So, then obviously my claim holds. So, that means we've now proven the following theorem, that if you look at least recently used on a machine that has memory size M, that the number of I/Os is at most twice the number of I/Os of the optimal strategy if you run the optimal strategy on a machine with a slightly smaller memory, namely only size M divide it by 2. So, this distinction between memory size M and memory size M divided by 2 is maybe not so nice, but at least this gives a justification of why least recently used is actually pretty good, and if you run it in practice, even on a machine with the same memory as MIN, than in practice, it most of the time actually gives really nice results. So, the assumption that a cache-oblivious algorithm that the replacement policy is optimal. Well, if you just run it on least recently used, then this is actually a pretty good reasonable assumption. So, well, that concludes what I wanted to explain to you about replacement policies. In the next lesson, we're going to look at, well, what you could consider as one of the most basic problems in computer science sorting. Probably, you know how to sort efficiently in n log n time in the internal memory model, but what we're going to look at is how to sort a huge dataset that does not fit into the internal memory in I/O-efficient manner.
