Video 7-1: External memory model, external sorting

0:04 As the final chapter of advanced data structures, we'll look at external memory data structures and algorithms a bit. Um, so I want to give you a bit of an overview um about this part and let's start a bit with what this is about and uh why we should care. Yeah. First of all, um, as motivation, it's probably fitting that it's towards the end of of today's class. Uh, I don't know if you can read this. Um, these are something um you can find online as well as an illustration how long certain things take in computers. And it goes from one nanocond, which is roughly a well nowadays maybe several clock cycles, right? all the way up to um how long it takes to send something over the internet. And I always think these kind of um these kind of representations are hard to grasp. And so I invite you to do the following little journey. We start with one little black box that's one nancond as I said on the order of individual CPU instructions. take one such tick. Uh indeed reading um one word of memory from the level one cache takes even just half a nancond.

1:28 Incredibly fast. If you cause a branch mispredictions because um uh conditional branch wasn't possible to predict then it already is a 10-fold slowdown. And if you need to go to the next level of cache, similar a slowdown. And if you use uh a lock already um 50fold slowdown. Now a 100 of these little black boxes is one of these blue things and that's one of these is the cost of one memory reference.

2:05 Now, [snorts] uh, that's on the order if if you combine a whole lot of these, that's what a fast zip program needs to zip some some things. If you take a hundred of these, you're at this level of uh, sending one kilobyte over a a gigabit network, right? Which is fast. You think a kilobyte is not much. And here we're at the fast SSD read speeds. Now this is a bit these are all is a bit old outdated. I think this is a factor 100 faster now or maybe more with uh nonvotile memory. This is substantially sped up but still kind of maybe an order of magnitude or two are off. Uh what certainly is not off is um read one megabyte from main memory. This may not be much much faster now. And remember where we came from. Individual CPU instructions all the way down there, right? And then it gets even worse. A 100 of these, that's a disc seek on a hard disk drive. So if you if you zoom in and out a few times, I think this it's the same picture, right? I stole the same picture, but this is exponentials are just not easy to grasp.

3:23 And you can't even see somewhere down here, right? So if you're working on hard disk drives and you do random access, that's what old um paging on computers used to do. If you're waiting for 10 of these red things, you can ignore all all other computation is for free. This is virtually true, right? There's so many orders of magnitude in between. If you do random disk seek means uh the physical readr head of the hard disk drive has to move. So if you jump for each bits all over your hard disk, you're going to wait these 10 red blobs. You're you can do as much computation in between as you want as long as you're not solving a an empty heart problem in each time. So that's the the motivation for um this external memory model which is uh the theoretical answer to um this kind of observation. Right? So uh uh I don't know if if your um your daily commute is dominated by the number of transatlantic flights you take or pick any metaphor that that you like is a a fairly old idea. Um so motivation is to grasp these kind of latency numbers and turn that into a theoretical model that you can design algorithms for without worrying about is this a dis SSD. We don't want to know the details of that. So instead um we'll look at uh this model. Um let me try to draw on the side a bit. So we have our main memory.

5:04 That's the fast main memory. You can also call it cache. I think this um is a bit uh depending what what you feel is more appropriate as a name. The idea of the model will be that you can apply it either between main memory and and hard disk drive or you can apply it between CPU cache and main memory. The same kind of game is played in both cases and it only uh tweaks the parameters. So there's the CPU here with a fat bandwidth connection to main memory. Uh but this is relatively small. And then there's an virtually infinite external memory.

6:12 but there's a a much thinner connection and you can only transfer blocks of memory. Now, um this is also one block. So um in terms of uh B elements and the number of things number of blocks you can fit into memory is M over B. So that the total memory size is capital M. So this is very fast and will ignore everything in on the left side of the picture in terms of the uh approximation for costs and only count how many data transfers you have between external memory and your internal memory. And in particular what's important is there's no way for the CPU to directly access this low memory. It has to go via the main memory. So we have an internal memory or cache an external memory which is unbounded in size. It has data has to be transformed trans transferred in contiguous blocks. Um the input size will denote by capital n in this chapter that's somehow uh the convention and little n is taken for an abbreviation where you divide n by the block size. So uh how many blocks does your input occupies the little n and similar for capital m that's the number of elements that fit in internal memory divided in blocks so little m blocks in internal memory okay and as I said if you're comparing this with random seeks on disk say it's uh justified to say that all that counts is the transfers between disk and internal memory and uh the cost of an algorithm is only that number of communication. We don't care about any other computation.

8:19 I should say that's that's an extreme is an extreme few. Um and sometimes this leads to a bit um I could say uh unrealistic uh assumptions but uh most of the time this is what this is um indicative that to first order you you design the algorithms for the right thing if you follow this.

8:44 Now external memory algorithms there's a lot known and has been studied in in various from various perspectives. Um here I'm going to focus on the data structures part of it but we'll briefly talk about some some basics like sorting and external memory. We'll briefly cover uh this is a table that gives for some simple algorithmic tasks what IO complexity they have. For example scanning n elements that are contiguous. That's important here. Of course, that are continuous in external memory. How would I do this? Well, I load the first B of them into my internal memory. Then I can read them. And then I can load the next block of B elements into internal memory and read them. So I'm only going to load a block one or one out of B elements. So with n / b or theta of little n block io's I can read n elements remember we don't count we don't uh pay for the computation it's only iOS uh sorting elements you can also do um and it turns out it has this slightly awkward complexity um have you ever seen this this four.

10:03 Okay, good. Um, what's that? >> I can't remember. I don't think so. >> So, I'm I'm sure that the the database group would also talk about external memory, but they maybe not from the theoretical side or analyzing things in these parameters. They would probably um present in the database courses, they would certainly use some of the data structures, but maybe from a different angle. And so, uh I hope I'm not um duplicating things there. seems seems not the case. Um, if you write this awkward uh running time with these abbreviations, it looks a bit less awkward. That's mainly the reason why people like these little ns just as an abbreviation of capital n divided b and same for little m capital m divided b. Uh, if you're searching among n keys, I guess this should be uh in sorted in a sorted array. You imagine you have things in sorted order. Um note that here sorting is is sped up substantially. You can this this uh log m uh maybe I should say something about the parameters. Um in most cases b is somewhat moderate maybe 10 to 100 elements. If you think about a cache line, but this m the size of the cache depending on what level the size of the main memory this could be thousands, right?

11:31 So usually having something involved with m gives you a a very substantial speed up and dividing by b is also good but is a little little less extreme in many cases. I guess could be even for main memory. It could be way larger, right? Okay. Uh and the last row is a bit funny. Um this shows you that this external memory has a few peculiarities. Uh permuting an elements. So you know basically it's a sorting without the comparisons. If you already know in what order you want to bring the elements, you're basically still going to pay the same as if you were to sort because the physical real location of elements is what what costs not or comparisons are for free because it's computation. But also even if you count them um it's dominated by the sorting cost. And so as a last thing for today, let me show how you can sort in this model in this optimal time. And it turns out the algorithm is is fairly straightforward.

12:35 Uh it's just an external merge sort variant and the only thing you have to do is do a multi-way merge. And you don't have to be clever about it because we're only counting IO's. So uh it has two stages. The first stage is I'm going to read a a chunk of M elements. I read them in one block at a time, fill my entire memory with m elements and then sort them internally and writing them back. So I'm assuming I don't need extra space for sorting. So maybe this internal step uses some sort of heap sort or quick sort. But you know it's computation is for free. The only cost this has is to read in the m elements.

13:19 So, one of these steps costs uh little m iOS and uh how many such chunks do I have to read? Well, n divided capital m and so overall it's uh linear in in n.

13:49 I think now it wasn't so smart to write this like this. So we have that many chunks. So it's little n capital n divided b total iOS for the first stage. Now I have um my inputs transformed into runs of m elements each and now I'm doing um a multi-way merge where I read k runs at a time but I don't read them into memory. I read only one block of each. So I can make up uh this number of of runs that I use. I can fill my entire memory with one block from each run and one output block. And then I can uh always read from these blocks until they're empty and then replace them. That way I can merge k runs at a time. All of this in the iOS of one scan. So one such merge costs uh scanning times or number of elements divided by b ios [snorts] and then uh you just need to determine how many rounds of such merging you do because we reduce the number of runs by this factor k in each round is a bottomup merge sort.

15:12 um we start with n / m runs and so the number of passes is log to the base k of n / m then I'm left with a single run and then it's sorted and this k you can insert is m over b now here we have n divided m not n divided b from from here or from uh the table but if you look at this uh this is actually does the almost the same. It's just a dividing here by m or dividing by b inside the log is essentially inconsequential is a plus minus one. And so uh each pass costs little n iOS I have that many passes or otherwise known as as that. So multiplying this gives you the sorting complexity. Okay. So a relatively straightforward algorithm and um you can prove that this is also optimal. Uh that's a bit a bit lengthier. Um it's an information theoretic proof. Um so basically uh counting counting that you cannot from loading one block learn too much information and shows that this weird complexity is the truth. That's the the precise bound for sorting.