# 23. Cache-Oblivious Algorithms: Medians & Matrices

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=CSqbjfCCLrU
**Transcript page:** https://www.withtranscript.ai/video/CSqbjfCCLrU

## Chapters

- 0:00 — Chapter 1 (0:00)
- 5:06 — Chapter 2 (5:06)
- 7:20 — Chapter 3 (7:20)
- 8:53 — Chapter 4 (8:53)
- 11:03 — Chapter 5 (11:03)
- 15:49 — Chapter 6 (15:49)
- 18:32 — Chapter 7 (18:32)
- 20:31 — Chapter 8 (20:31)
- 23:55 — Chapter 9 (23:55)
- 24:46 — Chapter 10 (24:46)
- 27:23 — Chapter 11 (27:23)
- 32:29 — Chapter 12 (32:29)
- 35:01 — Chapter 13 (35:01)
- 36:51 — Chapter 14 (36:51)
- 42:10 — Chapter 15 (42:10)
- 45:21 — Chapter 16 (45:21)
- 47:39 — Chapter 17 (47:39)
- 49:28 — Chapter 18 (49:28)
- 56:00 — Chapter 19 (56:00)
- 1:01:17 — Chapter 20 (61:17)
- 1:02:41 — Chapter 21 (62:41)
- 1:06:28 — Chapter 22 (66:28)
- 1:06:52 — Chapter 23 (66:52)
- 1:15:11 — Chapter 24 (75:11)
- 1:16:15 — Chapter 25 (76:15)

## Transcript

**[0:00]:** the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit mitop courseware at ocw.mit.edu all right welcome to the final week of 6046 are you excited yeah today well and sad I know it's tough but we've got two more lectures they're on one topic which is cache oblivious algorithms and this is uh a really cool concept it was actually originally developed in the context of 6046 as a sort of an interesting way to teach cache efficient algorithms but it turned into a whole research program in the late 90s and uh and now it's it's its own thing so it's kind of funny to bring it back to 6046 um the whole idea is in all of the algorithms we have seen uh except maybe distributed algorithms we've had this

**[1:07]:** view that um all of the data that we can access is the same cost if we have an array like a hash table accessing anything in the hash table is equally costly uh if we have a binary search tree every node costs the same to access but this is not real let me give you some idea of what a real computer looks like you probably know this but we've not yet thought about it in uh an algorithmic

**[1:40]:** context uh these are caches what are typically called caches in your computer uh then you have what we've mostly been thinking about which is main memory your

**[1:58]:** RAM okay okay uh and then there's probably more stuff these days you probably have some big flash if you have a fancier computer you have flash which is maybe caching your disc which is huge okay and then maybe there's the internet at the end if you like uh so the point is all the data in the world is not on your CPU and there's this big thing which is called the memory hierarchy uh which dictates which things are fast and which things are slow not exactly which data items that's up to you but the idea is that on board your CPU you have uh probably these days up to four levels of cash uh they're as I've tried to draw them they get increasingly big uh typical values at level one cach is something on the order of 10 32k whatever uh level four cach these days as introduced by like Haswell architectures has about

**[2:57]:** 100 megabytes uh main memory you know this is the thing you usually think about it's in the gigabytes these days you can buy computers with a terabyte of Ram uh it's not crazy flash you know gets bigger disc uh these days you can buy a four terabyte single disc but if you have a whole raid of discs you can have pedabytes of data on one computer so uh things are getting bigger as we go farther to the right but they're also getting slower and the point of cach efficient algorithms is to deal with the fact that things get slow when they get far away and this makes sense from a physics standpoint if you think about how much data can you store in a cubic inch or something and how much could possibly be near your CPU uh at some point you're just going to run out of space and you've got to go farther

**[3:43]:** away and to go farther away is going to take more time okay so you can think of it I mean there's the speed of light argument that things that are farther away in your computer are going to take longer uh typical computers are not anywhere near the speed of light so there's a more real issue which is how long your traces and then when you have physical moving Parts like a disc I don't know if you know but discs actually Spin and there's a head and it has to move around that that's called seek time moving the head around on the disc is really slow on the order of milliseconds whereas reading from on chip cache that's on the order of nanoseconds whatever your clock rate is so few billion times a second so there's a there's a big spread of like a factor of a million or 10 million from level one cash to

**[4:30]:** dis speed that sucks and so you might think well if your data is Big you're just screwed you've got to deal with disk and dis is slow but that's not true life is not so bad uh so in general uh

**[5:06]:** there's two Notions of speed and I've been kind of vague on them one notion is latency which is if right now I have the the idea that I really need to fetch memory location 2 billion 73 uh how long does it take for that data say one word of data to come back that's latency uh but there's another issue which is bandwidth uh how fast are these pipes how much uh what's my rate of information that I could pump if I said please give me all of main memory in order how fast could it pump it back and that's actually really

**[5:55]:** good so latency is like your startup cost when I ask for something how long does it take for for that one thing to come but uh then there's a data rate and bandwidth you can generally make really large uh for example in disk bandwidth of a disc is pretty big but uh even if it weren't big you could just add 100 more discs and then when you ask for some data all 100 diss could give you data at the same speed uh and provided you don't overload your bus so you've got to also make more buses and so on uh you can actually read a huge amount of data per second but still the time to get there and the time for all the discs to seek their heads that's slow it doesn't add up actually because they're all doing it in parallel uh so you can't reduce latency but you can increase bandwidth and

**[6:42]:** let's say it's not physically doesn't match physics but we can get pretty close to arbitrarily high bandwidth and so in a well-designed computer the the fatness of these pipes are going to increase or could increase if you want uh so you can move lots of data around but latency we can't get rid of and this is annoying because from an algorithmic standpoint when we ask for something we'd like it immediately we can't do in a sequential algorithm we can't do anything until that data arrives so cache efficiency is going to fix this uh by

**[7:20]:** blocking this is an old idea I mean since caches were introduced

**[7:30]:** there's the idea of blocking so when you ask for a single word in main memory you don't get one word you get maybe 32 kilobytes of information not just uh four bytes or eight bytes okay so uh

**[8:09]:** and we're kind of free to choose these block sizes however we want when we design the system uh so we can set them in a certain sense to hide latency so if you uh if you think of amortizing

**[8:29]:** the cost over the block then you have something like uh advertised cost over block this is per word is g to essentially we divide the latency by the block

**[8:53]:** size uh and we have to pay one over bandwidth bandwidth is how many words a second you can read say from your memory so one over bandwidth uh is going to be your cost so this we can't change but uh by adding enough discs or adding enough things at at making these pipes fat enough you can basically make this big um latency is the thing we can't control but if you think of if if this block is sort of useful then we're paying the initial startup time say hey give me this block and then waiting for the response that latency we only pay once for the entire block so if there block size words in that block we're per item we're effectively dividing latency by block size this is kind of rough but uh this is the idea of how to reduce latency now for this to actually work uh we need better algorithms

**[10:00]:** pretty much every algorithm you've seen in the class so far Works horribly in this model so that's the point of today and next class is to fix

**[10:12]:** that for this kind of amortization to work

**[10:19]:** uh I'm using use in a vague sense so far we'll make it formal in a moment when I fetch an entire block all of the elements in that block should be useful uh we should be able to compute something on them that we needed to compute otherwise I mean if I just if I only needed the one item that I read out of the block uh that's not going to help me so much so uh I really want to structure my data in such a way that when I access one element I'm also going to access the elements nearby it uh then this blocking will actually be useful this is a property normally called spatial locality

**[11:03]:** uh and the other thing we'd like um these caches have some size so I can store more than just one block it's not like I read one block and I just finish processing it and then I read the next block and go on uh these C some of these caches are actually pretty big if you think of main memory as a cache to your dis uh that can be really big so um ideally the blocks that I'm using here relate to each other in some way or when I access a block I'm going to access it for a while along with other blocks so the way this is usually said is that uh we'd like to reuse the existing blocks in the cache as much as possible and this you can think of as temporal

**[11:49]:** locality when I access a particular block I'm going to access it again fairly soon that way it's actually useful to bring it into my cache and then I use it many times that would be even better I don't have to have both of these and exactly to what extent I have them is going to dictate what the overall time it's going to take to run my algorithm but these are sort of the ideal properties you want in a very informal sense now uh in the rest of today we're going to make this formal and then we're going to develop some algorithms for this model but this is the the motivation in reality you typically you were free to choose block size in the system though in a moment I'm going to assume that it's given to us you'd normally set the block size so that these two terms come out roughly equal uh because if

**[12:33]:** you're spending the latency time to go and get something you might as well get uh a whole chunk of something so that uh I mean according to whatever your bandwidth is if it only costs you say twice as much to fetch an entire block than to fetch one word that seems like a pretty good block size so for something like disk uh that block size is on the order of megabytes maybe even bigger hundreds of megabytes so think of the block sizes as really big we really want all that data to be useful in some way now uh it's really hard to think about a memory hierarchy with so many levels uh so we're going to focus on two levels at a time the sort of the cheap and small cache versus the huge thing which I'll call dis just for

**[13:25]:** emphasis so I'm going to call this twole model the external memory model was originally introduced as a model for main memory versus Disk but you could apply it to any pair of levels in general you you have your problem size n choose the smallest level that fits n typically that's main memory maybe it's disk and just think of the the level between that and the previous okay so uh the last level and the next to last level often that's what matters like if you run a program and you run out of RAM and you start swapping a disc that's when everything just flows to a crawl uh but you can see that difference at each of these levels but it's probably most dramatic at disc just because it's so slow million times slower than Ram or at least a thousand times slower than Ram I should say anyway uh so we have just two levels

**[14:23]:** so let me draw a more precise picture we have the CPU this is where all of our operations are doing this is where we add numbers and so on we'll think of it as having a constant number of registers each register is one word uh and then we have a really fat pipe low latency pipe to the

**[14:47]:** cache cach is going to be divided into blocks so uh let's say there's B words per blocks instead of of writing block size I'll just write capital B and the number of blocks I'm going to call M over B so the total size of your cache is capital M uh and then there's a relatively thin and slow connection so this one's fast this one's slow to your dis dis will'll think of as huge essentially infinite size it's also divided into blocks of size B so the same block

**[15:49]:** size uh so this is the picture and so initially all of your the input is over here all of your n data items whatever say you want to sort those items and uh in order to access those items you first have to bring them into cache that's going to be slow but it's done in a blocked manner so when I uh I can't access uh an individual item here I have to request the entire block when I request that block it gets sent over here it takes a while um then I get to choose where to store it maybe I'll put it here uh and then maybe I'll grab this uh block and then store it here and so on each of those is a block read so these are new instructions the CPU can do um and eventually this cache will get full and then before I bring in a new block I have

**[16:41]:** to kick out an old block meaning I need to take one of these blocks and write it to some position maybe to the same place uh I think in fact we will always assume that you write to the same place overwrite what was on the dis you made some changes here send it back and in general what we're going to do is count how many times we read and write blocks question when you talk about how fast the connection is you're just talking about lat yes sorry this is latency so disconnection right this could have huge bandwidth and uh so in this model we're assuming the block size is fixed and then the latency versus bandwidth is not uh we're not going to think about bandwidth we're assuming the block size has been chosen in some reasonable way and then we all we need to do is count the number of blocks but underneath yeah

**[17:30]:** you have uh some kind of bandwidth you've set presumably you set the block size to make these two things roughly equal and so then latency and bandwith are kind of the same thing that's the the idea but really we're just going to think about counting latency which is how many times do I have to request a block and wait for it to come over and how much does it cost to write a block how many times do I write a block I'm not going to worry about how much physical time it takes me to do either of those things I'm just going to count them and assume that that that is what I need to minimize so I'm going to count uh we call these memory transfers transfers of blocks between levels between these two levels this the number of blocks read from are written to disk

**[18:32]:** we're going to view uh accesses to the cash as free not going to count

**[18:44]:** those uh you don't need to worry about that so much because we can still uh we can still count the number of operations that we do on the computer on the CPU

**[18:59]:** okay we still can think about how much time regular time it takes to do the computation how many comparisons how many additions things like that and that would include things like reading and writing elements from Cache individual things but we're going to view this this connection let's say these are on the same ship So reading cach is just as fast as reading from registers so we're not going to worry about that time what we're focusing on for the purpose of this model is between these two levels so these are essentially one level combined I'll change that in a little bit but for now just think about the two levels and we're counting how many memory transfers do we have between uh these two levels cache and disk okay so we want to minimize that now just like before we want to minimize the running time and the usual traditional measure but and we want to

**[19:49]:** minimize space and all the usual things we minimize but now we have a new measure which is number of memory transfers and we want our algorithm to minimize that to for a given block size and for a given cache size okay uh and at this point I'm going to change this in a moment um the algorithm that that we would write in such a in this external memory model uh explicitly manages the blocks it has to explicitly uh read and write blocks

**[20:31]:** and there's a software system that implements this model particularly for disk and lets you do this in a nice controlled way maintain your memory maintain reading and writing disk the operating system tries to do this but it usually does a really bad job with swapping uh but there are software systems that let you take control and do much better so that's a good model external memory model is especially good for disk

**[21:01]:** uh it's not going to capture the Finesse of all these other levels uh and it's a little bit annoying to write algorithms in this way explicitly reading and writing blocks today I will not write any such algorithms um although you could think about them I personally uh love this other model just cach obliviousness

**[21:29]:** it's going to lead to in some sense cleaner algorithms although it's more of a magic trick to get them to work uh but writing the algorithms is very simple analyzing them is more work uh and it will capture in some sense all of these levels but in fact it is basically exactly this model almost the same we're going to change one thing uh which is where the oblivious comes from uh we're going to say that the algorithm doesn't know the cache parameters it doesn't know b or M so this is a little weird where I have to make some other changes to make it work but I want to model from an analysis perspective I want to count memory transfers and analyze my algorithm with respect to this memory hierarchy but the algorithm itself isn't allowed to know what the memory hierarchy looks like another way to say this is that the algorithm has to work

**[22:27]:** simultaneously for all values of B and all values of M uh as you might imagine this is not so easy but there are some simple things that where this is easy and more complicated things where this is possible and it gives you all sorts of cool things um let me first formalize the model a little bit the other nice thing about cach oblivious algorithms is it's uh much it corresponds much more closely to how these caches work uh when you write code on your CPU you may have noticed you don't usually do block reads and block wrs unless you're dealing with flash or disk all of this is taken care of for you it's all done internal to the processor when you access a word behind the scenes magically uh the system the the computer finds which word to read uh which block to read it moves the entire block into a higher level cache

**[23:19]:** and then it's just serving you words out of that block and you you don't have explicit control over that so the way that works is when you access a word in memory and I'm going to think of memory as everything this is what's stored in the disk say this is your entire uh this is the entire memory system the entire memory hierarchy and as usual in this class we're going to think of the entire memory as a giant

**[23:55]:** array of words each of these squares is one word

**[24:01]:** uh but then also the memory is now divided into blocks so let's say every four let's say b equals 4 every four words is a block boundary just for sake of drawing a figure so this is Bal 4 when you access a single word like this one you get the entire block containing the word

**[24:30]:** let's say to emphasize it's not you personally the system somehow fetches uh the block containing that

**[24:46]:** word it has to do this automatically we can't explicitly read and write blocks in this model because we don't know how big the blocks are so we couldn't even name them okay but internally uh you can on the real system and in your analysis you're going to think of whenever you touch something you actually get all of this into the cache so you hope that you will use things nearby because you've already read them in ideally they're useful but you don't know how many you've read in you've read in B and you don't know what B is from the algorithm doesn't know okay uh one more detail the cash is going to get full pretty quickly and So then whenever you read something you have to kick something out in stady State uh cash might as well always stay full no reason to leave anything empty uh so which block do you kick out uh

**[25:34]:** any suggestions which block uh should I kick out if I've been reading and writing some blocks reading and writing to words within these blocks yeah the block that was fetched farthest in the past yeah that was is usually called First in first out that's fifo and that is a good good strategy uh any other suggestions yeah the block that has been least recently used so maybe you fetched it a long time ago but you use it every clock cycle that would also be uh uh that one you should probably not throw away because you use a lot that's called lru and that is also uh good strategy are there suggestions those are two good ones if you go beyond that I'm worried I won't know but there are some bad strategies yeah random random yeah random H random is probably pretty good I don't know off hand there are some randomized strategies that beat both of those uh but from this perspective both are good we've got lots of Frisbees to go through so uh but that that's a good

**[26:43]:** answer random is definitely a good idea I know there's a randomized strategy called bit that in certain sense is a little bit better but from my perspective I think all of those are good random I have to double check whether you lose a log Factor an expectation should be fine uh cool so all of the strategies will work I'm going to Define you could Define this model with any of them I think it would work fine except randomized you get an expectation bound uh okay so the system uh evicts let's say the least recently used

**[27:23]:** page the least recently loaded page would also work fine that's fifo um sorry I'm switching to page but I've been calling them blocks blocks and pages are the same thing for this lecture uh and at the end uh either end of this lecture or beginning of next I'll tell you why that's an okay thing uh but let's not worry about it at this point uh

**[27:50]:** cool so now we have a model Cas we have two models actually but I think now the cach bious model is complete uh we're going to analyze again we're still counting the number of memory transfers in this thing the algorithm is just not allowed to know B and M and so we had to change the model to make the reading and writing of of blocks automatic because the algorithm is not allowed to do it so someone's got to cool thing about the cach oblivious model is every algorithm you've seen in this class or you know most of the algorithms you've seen in this class are in a certain sense cach oblivious algorithm they weren't aware of B&M before still not uh what changes is now you can analyze them in this new way in this new model now all as I said all the algorithms we've seen are not going to perform well in this

**[28:41]:** model almost all uh but that makes things interesting that's why we have some work to do all right I have some reasons why cache obliviousness why would you tie your hands behind your back and not know b or M reason one it's cool uh I think it's pretty amazing you can actually do this I guess that's reason too is you can actually do it for a lot of problems we care about cash oblivious algorithms exist that are just as good so I mean of course they exist but they ones that are optimal they're within a constant factor of the best algorithm when you know b or M so that's surprising that's the cool part um in general the algorithms are easier to write down because it's our regular we can use pseudo code just like before we don't need to worry about blocking in the algorithm the analysis is going to be harder but that's

**[29:33]:** unavoidable uh in some sense it makes it easier to write code uh and it's also a little easier to distribute your code um because every computer has different block sizes that matter also as you change your value of n a different level in the memory hierarchy is going to matter and so it's annoying to have to each of these levels I didn't mention has a different block size and of course has a different cache size so tuning your code every time to a different V or M is annoying the big the big gain here though I think is that you capture the entire hierarchy in a sense so in in the real world right each of these pipes has its own latency and let's just think about latency and you'd like to minimize the number of block transfers between here and here you'd like to minimize the number of block transfers here and here well

**[30:21]:** okay I can't minimize all of them that's a multi-dimensional problem what I'd like to minimize is some weighted average of those things the lat latency times number of blocks here plus the latency times number of blocks here plus latency times number of blocks here and so on uh if you can find an optimal cache oblivious algorithm and analyze it just with respect to two levels because the algorithm is not allowed to know B&M it has to work for all levels it has to minimize the number of block transfers between all of these levels and so in particular it will minimize the weighted sum of them that require it's a bit handwavy you have to prove something there but you can prove it uh I didn't mention uh so there's a paper about this from 1999 by fro lerson procop ramachandran um it's old enough I remember all the names after about 2001 when I became

**[31:19]:** a professor I can't remember anything but before that I can remember everything um so fro we've talked about him in the context of fft f w that was the fastest 48 transform in the west so he was a student here and uh fftw uses a cach oblivious fast 48 transform algor though uh lerson you've probably seen on the cover of your textbook or walking around sta Professor lerson here in M uh and procop uh this was actually his M thesis so pretty awesome M thesis all right so cool I think I've said all the things I wanted to say uh so if you want to see the proof that you can you solve the entire memory hierarchy you can read their paper you have to make a couple of assumptions but it's intuitive cach oblivious has to work for all B&M so it's going to optimize all the levels simultaneously doing that explicitly with all

**[32:14]:** the different BS and M's that would be really messy code probably also slower cash oblivious is just going to do it for free with the same code all right let's do some algorithms

**[32:29]:** there's one easy algorithm which works great from a cach oblivious perspective uh which is scanning let me give you some python

**[32:46]:** code uh for historical reasons uh in this field n is written with a capital letter don't ask or don't worry about it so here's some very simple codes suppose you want to accumulate an array you want to add up all of the items in the array or multiply them or take them in or whatever this is a typical kind of thing uh again an array we're going to think of so here was here was my memory we're going to think of the array is being stored uh as some contiguous uh segment of that array let's say this segment so this is important uh assume

**[33:30]:** array is stored uh continuously no holes relative to how it's mapped onto memory and this is a realistic assumption when you do when you allocate a block of memory The Promise by the system is that it's essentially a contiguous chunk of memory or dis or whatever um so uh and when python makes an array it it it does this it guarantees that the uh these things will be stored continuously if you use a dictionary this would not be true but for regular raised lists this is true so um I'm accessing the items in the array in order and so I start here at item zero I end up with item n minus one uh that seems good because I read this one I get the whole block then I read this one I already had that block it's free this one's free this one's free here I have to read a new block but then

**[34:25]:** this one's free so the first item I access in each block costs one but as long as my cash size as long as my cash stores at least one block uh that's enough and let's say the sum is a register uh that's enough to remember that block so that the next operation I do uh will be free so the cost is going to be uh actually be a little more precise ceiling of n/ B

**[35:01]:** almost uh without a big O here this can be this is right in the external memory

**[35:12]:** model but not quite right in the C oblivious model can someone tell me why yeah if is two you could have good n could be two but it could span a block boundary remember the algorithm has no idea where the block boundaries are and again in reality there are block boundaries all over the place and you can't there's no way to know you can't you can't request that when you allocate an array it always begins in a block boundary so great uh you can have you can span block boundaries in a way off I just spanned a block boundary sorry um so uh it's going to be at most ceiling of n overb uh plus one cachee obliviously so it's just going to hurt you by one but I wanted to point out there is a slight difference between the two models even with this very simple algorithm okay in general I'm just going to

**[36:10]:** think of this as Big O n/ B plus one okay there's some additive constant uh I guess you could even say it's n / B plus Big O of one but uh we won't worry about constant factors today so that's scanning cach oblivious external memory both great uh slightly more

**[36:51]:** interesting uh yeah SOC in the external memory algorithm because you're explicitly controlling the blocks you're explicitly reading and writing them and you know where the block boundaries are you could if you wanted to you don't have to but you could choose the array to be aligned to be starting at a block boundary so that's that's the distinction in the cache oblivious you can't control that so you have to worry about the worst case uh external memory you could control it and you could do better maybe you'd want to it will hurt you by a constant Factor so uh and in diss for example you want things to be track aligned because tracks or if you have to go to an adjacent track it's a lot more expensive you got to move the the head track is a circle what you can read without moving the head okay so great so slightly more interesting is you

**[37:44]:** can do a constant number of parallel scans so that was one scan uh here's an example of two scans

**[38:02]:** again we have one array uh of size n python notation that would be the whole thing uh and what I want to do is swap AI with this is not python but I think textbook notation but you know what swap means uh what does this do assuming I got my minus ones right yeah rever it reverses the array good we'll just burn through these PHS uh so this is a very simple algorithm for reversing the array it's originally by John Bentley who was Charles lon's advisor PhD adviser back in the day uh so very simple uh but what's cool about it if you think about the array and the order in which you're accessing things it's like I have two fingers and I should have made this smaller uh so here we'll go down here I I start at the very beginning of the array and the very end of the array then I go

**[39:11]:** to the second element next to Second next to last element and I Advanced like this okay so as long as your cache M uh the number blocks in the cach is at least two which is totally reasonable you can assume this is uh at least 100 typically you've got at least 100 blocks say so for any fixed constant we're going to assume MB is bigger than a constant we'll only need like two or three or four for the algorithms we cover uh then great uh when I access this item I will load in the block that contains it I don't know how it's aligned okay but don't care so much and then I load in the block that contains this item and then the next aises are free until I advance to the next block but once I advance advance to the next block on the left or the right I'll never have to access

**[39:57]:** the old ones and so again the the the cost here is just going to be equal to the number of blocks which is Big O of n over B+ one okay so constant number of parallel scans is going to be basically the number of blocks in the array so if n is smaller than b this is a bad idea or not so hot but when n is bigger than b this is just n over B that's how much it takes to read in the data okay big deal so these are boring cach oblivious algorithms let's do interesting ones and I would say the central idea in cach oblivious algorithms is to use divide and conquer this goes back to the first few lectures in this class and so we will go back to examples from there uh today we're going to do median finding in particular which we did in lecture two so really blast

**[40:54]:** from the past but it's good review because the final covers everything so got to remember that U matrix multiplication we've talked about but not usually as a uh well I guess we did actually use divide and conquer for stren's algorithm we're going to use divide and conquer even for the boring algorithm today and then next class we're going to go back to vom deas but in a a completely different way so if you don't like vom deas don't worry it's much simpler okay so let's do median finding or actually sorry let me first talk about divide and conquer in general okay you know what divide and conquer is you take your problem you split it into non-overlapping sub problems recursively solve them combine them um but what I want to stress here is what it's going to look like in a cach oblivious context so the algorithm is going to look like a regular divide

**[41:50]:** and conquer algorithm so in particular the algorithm will recurse all all the way to let's say constant size problems uh whatever the base case

**[42:10]:** is okay so same as usual but what's different is the analysis okay when we analyze a cache oblivious algorithm we get to uh then we get to know what B&M are in some sense we're analyzing for all B&M but let's suppose B&M is given to us then we'll tell you how many memory transfers you need this kind of bound you need to know what B is to just know what the value of this bound is but you learn it as a function of B and in general a function of B and M and that's the best you could hope for as a complete characterization so in the analysis let's just look at one value of B and one value of M so analysis knows b& M and and it's going to look at uh let's say the recursive

**[43:10]:** level where one of two things happens either

**[43:20]:** uh the problem the problem size fits in order one blocks so meaning uh it's order B size that's an interesting level another interesting level as you the more obvious one probably is that it fits in cach so that means that the size is less than equal to capital M okay we everything here is counted in terms of words okay this is the more obvious one for a lot of problems uh the cache size Isn't So Rel what really matters is the block size for example scanning uh you're only looking through the data once so it doesn't matter how big your cache is as long as it's not super tiny as long as it has a few blocks um then it's just a function of B and N no M involved okay uh so for that kind of problem this would be more useful uh constant number of blocks uh because I think of the cash

**[44:21]:** m is being larger than any constant times B um this is strictly smaller or this is smaller or equal to uh problem fitting in cach so when m is relevant we'll look at this level and maybe the adjacent levels in the recursion okay so the algorithm doesn't know what B and M are so it's got to recurse all the way down Turtles all the way down uh but the analysis because we're only thinking about one value b& M at a time we can afford to just consider that one level and that will be like the critical place where all the cost is because once things fit in cash and you've loaded things in the cost will be zero so below that that the base case is kind of trivial so basically what this is going to do is make our base cases larger instead of our base case being constant it's going to be order

**[45:06]:** b or M all right uh what don't I need

**[45:21]:** that's so now let's go to median finding

**[45:45]:** median finding you're given an unsorted array you want to find the median uh and in lecture two we had a linear time uh worst case algorithm for this and so my goal today is to make it this running time this is what you might call linear time in the cach oblivious model uh because that's how long it takes just to read the data okay turns out basically the same algorithm works first you've got to remember the algorithm so let me write it down quickly uh this is the sort of 5 byn array so we think of the array as being partitioned uh into I'll call them five

**[46:34]:** columns right so uh this was this picture of five dots by n over five dots uh this is dot dot dot um so this was five now uh we didn't talk about it then and there's a few different ways you could actually implement it but uh let's say these the actual array is onedimensional let's say these are the first five items these are the next five items so in other words this Matrix is stored column by column okay that this is just a conceptual view so we can Define it either way however we want so I'm going to view it that way and then uh what the rest of the algorithm did was first sort each column there's only five items so you can sort it in constant Time Each one uh but in particular what we care about is the median of those five items uh then we recursively found the median of the

**[47:31]:** medians this is the step we're going to have to change a little

**[47:39]:** bit uh then we leave a little bit of space then we partition the array by X meaning we split the array into items less than or equal to X and things is greater than x we probably assumed there was only one value equal to X but doesn't matter uh and finally we recurse on one of those two

**[48:12]:** halves so this is a pretty crazy divide and conquer algorithm one of the more sophisticated ones um you don't need to know all the details here just that it worked and it ran in linear time um what's crazy about it is there are two recursive calls usually like merge sort when you do two recursive calls and spend linear time to do the stuff like this partition uh you get n log n time like merge sort here because this array is a lot smaller this is a size n over five and this one was reasonably small it was like at 710 n uh because 7/10 plus uh plus 1/5 is strictly less than one this uh ends up being linear time instead of n log n okay that's just review now what I'd like to do is the same thing same analysis or same algorithm but now I want to analyze it in this twole model

**[49:10]:** so actually uh I will race this board

**[49:28]:** so now my array has been partitioned into blocks of size B like this picture in fact it's quite similar here we're partitioning things into blocks but they're size five that's different now someone has partition my array into blocks of size B I need to count how many things I access well let's just look line by line at this code and see what we do step one we do absolutely nothing this is a conceptual picture so zero cost great step one zero my favorite answer uh step two we sort each column how long does this take what am I

**[50:11]:** doing it's right above

**[50:17]:** me n over B because this is a scan okay it's a little bit weird of a scan we look at five items uh and then we look at the next five items and then the next five items but it's basically a scan you could think of it as at most five parallel scans I suppose or you could just break into the case where maybe B if B is a constant then it doesn't matter what you do okay but if B is bigger than a constant then uh reading five items those are all probably going to be in one block except the ones that straddle the block boundaries okay so in all cases for step two maybe I should rewrite step one zero cost step two uh is order n/ B plus one to be careful okay that's a scan actually it's two parallel scans because we have to write out these medians somewhere or I

**[51:09]:** yeah so we'll have to step three is recursively find the medians now uh before we had you know T of n is uh T of n over 5 plus T of 710 n Plus linear okay in this new world that was the old this is regular running time in this new world I'm going to use a different notation for the recurrence Mt of n for memory transfers okay this is a good old fashioned time and this is our new modern notion of Time how many block transfers do I need to do for problem size n so this is a recursion and should be Mt of n over5 but uh and this is important for this to for this to be a same problem of the same type I need to know that the array that I'm recursing on is stored contiguously okay before I didn't need to do that I could say well let's put

**[52:11]:** the medians in the middle okay so now every fifth item in this array is my new subarray and so I could recursively call this thing and say okay here's my array but really only think about every fifth item that's like a stride in the array and then the next recursive level oh only worry about every 25th item and every five cubed item I'm going to stop Computing um and so on and that would be fine for regular running time but when I my strike gets bigger and bigger at some point every item is going to be in a different block that's bad I don't want to do that so when I find these medians or when I recurse I need that the medians that I'm recursing on are stored in a contiguous array now this is easy to do but we didn't have to do it before that's the key difference uh make sure they

**[52:58]:** are stored uh

**[53:05]:** continuously okay I can do that because when I sort each column uh in one scan I can have a second scan which is the output which is the array of medians so as I'm scanning through the input I'm going to Output the median it's going to be 1/5 the size but then I've got all the medians nicely stored in a contiguous array okay so with order one parallel scan same time here uh this is actually a legitimate recursive call okay uh then we partition partition again is a bunch of parallel scans I think three uh you've got one reading scan which is you're reading through the array and you've got two writing scans you're writing out the elements less than or equal to X and you're writing out the elements greater than x but again all of those are scans you're always writing the next element right after the previous one so if you already

**[53:57]:** have that block in memory and if you assume that the number of blocks in Cache is at least three then three parallel scans is fine okay it's different from the crrs partition algorithm that one was fancy to be in place we're not trying to be in place or fancy at all let's just do it with a bunch of scans okay so now we have two arrays the elements less than x elements greater than x then we recurse on one of them and those elements are consecutive already so good this is a regular recursive call again we're maintaining the invariant that the array is stored continuously and by the old analysis that array is size at most 7/10 n okay so I get a new recurrence which is Mt of n is Mt of n over5 Plus Mt so analis feels very empty uh plus n over B sorry bad joke uh n over B plus

**[54:55]:** one okay so basically the same recurrence but now n / B+ one for what we're doing here okay but I I had to change the algorithm a little bit for this recurrence to be correct to for it to correctly reflect number of memory transfers now all we need to do is solve the recurrence uh and actually in some sense more importantly we need to figure out what the base case is okay because we could say all right uh let's here's usual base case if I have a constant size problem well that's going to be constant this is our base case for every recurrence we've ever done and that's enough usually it's going to give us a really bad answer here so let's uh let's go off to the side here and solve that recurrence

**[56:00]:** uh so if that's my base case well in particular so this is some recursion tree it's very uneven so it's kind of annoying to draw uh but what I know with this base case uh this overall Mt of n is going to be at least the number of leaves in the recursion tree so say Mt of n is at least L of n number of leaves in the recursion so this is really if I run the algorithm how many base cases of constant size do I get uh and that satisfies so it's not obvious what that is uh this is some there's no plus here number of leaves is just how many leaves are over here how many leaves are over here and L of one equals 1 say or some constant equals constant uh I happen to know because I Sol lots of recurrences uh this solves to Su n to the alpha okay I claim that L of n is n the alpha for some constant Alpha uh y I'll just prove that it

**[57:10]:** works uh so this is now n over 5 to the alpha and this is 710 n to the alpha if it's going to work this recurrence should be satisfied okay uh and now if you look at this equation there's a lot of n to the alphas and they all cancel so I get 1al 1 to the alpha plus 710 to the alpha it's confusing because I was just watching the TV show at Alphas but no relation uh so this is now something purely in terms of alpha you just need to check that there is a real solution there is one you plug it into from alpha or something nope nope pun intended wow they're just coming out today uh and then Alpha is next page I I can't do this by hand something like uh 83 978 so we get L of n is is let's say at least n to the 0.8 it's bigger okay it's sublinear and that was enough when we just cared about time but now it's bad news because n over

**[58:23]:** B our goal was to get uh n / B + 1 if B is huge if B is bigger than n the 0.2 uh then we're not achieving this bound right we always are paying at least n to the 0.8 and for example B is roughly n we're way off but that's just because we use the wrong base case turns out if you use a better base case things just work so let's do that I think it's going to be smaller uh so the next B I mean when you're doing cachas analysis you never use this pace case the first one you should think about is this one if you have a problem of size that fits in a constant number of blocks well of course that's going to take once they're read into the cach you're not going to pay anything How long does it take to read a constant number of blocks into

**[59:14]:** cache constant number of memory transfers okay so this is obviously a strictly better base case than this one uh because we have this the same thing on the right hand side it's a constant but we've solved a larger problem so clearly you should cut here instead of there then uh the number of leaves in this recursion so same recurrence uh different base case so we just stop recursing conceptually in the analysis the algorithm goes all the way down but in the analysis we stop recursing when we reach a problem of size B the number of leaves in that new recursion tree will be uh n / B to the alpha that's that's good that's sub that's smaller than n overb okay now I'm going to wave my hands a little bit and say Mt of n is order n / B + 1 uh I guess to do that you want to prove it the

**[1:00:13]:** same way we did before uh when we solve this recurrence which is by substitution you assume this is true you plug it in verify it can actually be done with some constants the intuition of what's going on is in general this recurrence is dominated by the root the root cost for this recursion is n / B+ 1 so this is the root cost I claim that up to constant factors that is the overall cost roughly because as you go down the recursion tree the cost is decreasing geometrically okay but that's not obvious for this recurrence because it's so uneven but it's kind of like the master method a little fancier intuitively this should be obvious um there's the root cost and then there's the other ones but to actually prove it you should substitution method I want to go to more interesting algorithms instead but any questions before we continue all right so uh next algorithm that was median now we're going to do matrix

**[1:01:17]:** multiplication via divide and conquer

**[1:01:32]:** so uh what we just saw was an example where in divide and conquer we stop in the analysis we think about the case where things fit in a constant number of blocks that was sort of case one the next example matrix multiplication will be the other case so you get to see both

**[1:01:52]:** types so multiplying matrices something we've done many times uh for example in the fft lecture uh and in the sten's algorithm just remind you uh I'm just thinking about the square case although this generalizes we have two square matrices n byn uh normally I would say C equals a * B but I realize uh we use B for Block size so this is going to be z = x * y hopefully that doesn't conflict with anything else uh but no B's all right so standard Matrix let's start with the standard

**[1:02:41]:** algorithm let's start by analyzing that uh because uh if you're reasonably clever this this standard algorithm is not so bad um so in general uh this won't matter too much let's suppose we're doing z uh row by row and let's say we're currently Computing uh this product cell so that product C is the dot product this uh Z J here is the dot product of this row with this column how do I compute dot products two parallel scans right I scan through this row and a parallel scan through this column now uh it depends the order in which you store X and Y but let's suppose we can store X in row major order meaning row by row and we store Y in column major order meaning column by column then this will be an honest to goodness scan of a contiguous array again the order we store things in memory really matters so let's

**[1:03:41]:** let's make our life ideal let's say that this is uh row by row and this one is column by column then hey uh this is two parallel scans so order n/ B to compute this cell okay I claim that uh Computing Z J C N / B and so maybe plus one again these are n byn matrices so total size is n s uh which means the total cost is what uh uh n q cubed over B + n^2 I guess seems pretty good I mean we had a running time of n cubed at before and we divided by B how could you possibly do better well by being smarter uh this is not optimal you can do better it's not obvious but um let me just uh spend a little more time convincing you this is the right answer not only is this big O but for appropriate uh settings this in the worst case this

**[1:04:57]:** is going to be Theta uh because if you think of the order in which we're see we look at these rows several times um and if you look at you know when I compute this cell and this cell and this cell of the Z Matrix of the product Matrix each of them uses the same row of X so um maybe you could reuse that you could reuse that row of X that might actually be free depending on how B and N relate but uh The Columns of Y those are different every time when I compute this one I use the First Column of y when I compute this one I use the second column of Y unless the cache is so big that it can store all of Y which is like you can store the entire problem in Cache that's unrealistic um so unless m is bigger than N2 uh in this algorithm at

**[1:05:49]:** least you have to read a new column of Y every single time so that's why it's Theta n/ B+ + 1 you need to spend n / B assuming uh m is less than n^2 okay and I claim this is not the best you can do because we're going to do better and we're going to do better by divide and conquer

**[1:06:28]:** now you've already seen divide and conquer used for matrix multiplication to get sten's

**[1:06:35]:** algorithm uh and the idea there is to use

**[1:06:43]:** blocks so this is sort of an algorithm you've already seen I'm going to

**[1:06:52]:** divide the Matrix Z into n /2 by n two submatrices so each of these Z JS is an n/2 by n/2 matrix and uh you know I do the same thing for X and

**[1:07:14]:** Y get the numbers right one two Y 2 one and so on and you can write this out explicitly I prefer not to do all of it uh but let's do one of them you can just think of these as 2 x two matrices because uh matrix multiplication is associative and good things happen I can just take these two elements but they're actually matrices uh sorry take these two and Dot product with these two uh and I get X11 y11 plus X12 y 21 and that's what I should set z11 to so this is a Formula but it's also a recursive algorithm it says if I want to compute Z I'm going to say well there are four sub problems the first one is to compute z11 and I'm going to do that by recursively Computing the product of X11 and y11 recursively Computing the product of X12 y21 and then adding them together this

**[1:08:10]:** is not recursive addition is easy okay and there's two products here two products here two products here two products here total of eight products so we're going to have eight recursive calls in size n/ two uh yeah so so we look at the number of memory transfers this is 8 * recursive call on N /2 by n /2 submatrices and then plus the cost of addition and I claim the cost of addition is at most n^2 over B plus one uh because addition is is basically parallel scans okay I can scan through x uh scan through y as long as they're stored in the same order I just am adding them ele element by element and there's a third scan which is writing out the Z Vector so uh once things are linearized now for this to work for this to be a true recursion I need that say X11 and y11 are stored as

**[1:09:10]:** contiguous things in memory so this means that the layout of a matrix let's call let's consider the Matrix Z is going to be like the following I'm going to recursively layout one one so when I say layout I mean what order do I store the elements in memory what order do I store the cells in memory and what I'm going to say is recursively layout the pieces there's four pieces recursively call layout of those and then concatenate them together that's my layout so I'm going to store all of these items then I'm going to store all of these items then all of these items then all of these items uh how do I how do I store these items in what order recursively so I'm going to divide them like this store these before these before these before these how do I store these recursively okay it's same recursion so it's a really weird order

**[1:10:04]:** it's a divide and conquer order there's only four things here in what order should I combine the four things doesn't matter all that matters is that this is consecutive this is consecutive and this is consecutive so that when I recurse I'm recursing on consecutive chunks of memory otherwise the analysis just won't work so for this to be right got to have this layout okay now we just need to solve the recurrence and we're done uh I already told you the base case we're going to use is this one we're going to use this one because it's stronger and better uh and and we'll need it in this case to get a better analysis um you could solve it using the weaker base cases you'll get larger numbers but if you use the strongest base case Mt of uh it's not M got to be a little careful uh because n here is is actually just

**[1:10:55]:** one side length this is an N byn Matrix so the total size here is n s actually the total size is 3 n^ 2 so this is going to be square < TK of M over3 H some constant times square root of M okay it doesn't actually doesn't matter what the constant is but this is the size of this is the value of n for which all three matrices will fit in Cache so uh I claim we know this costs at most M overb memory transfers because uh because uh we I forgot a stroke here um because we know that all of these guys fit in cash and because we know that they are stored consecutively in memory well in three consecutive chunks okay once no matter what I do there are only M overb blocks there and so at worst I read them all in but once the cach is filled with them I

**[1:11:49]:** will never C for the duration of this recursion I won't be reading any other blocks and so the cach will just stay full with the problem and so I never pay more than this okay so that's the base case kind of easy but you have to think about it for a second uh cool now we have a recurrence and a base case and now we have a good oldfashioned recursion tree this one I can actually draw because it's well partly because it's nice and uniform uh it's just explodes rather fast so at the top we have a cost of n^2 over B + 1 um and we have eight recursive calls and the recursive calls are to something of size n/ 2^ squar over B also known as n^2 over 4B okay so if I add up everything on this level I get n^2 over B if I add up everything on this level I'm

**[1:12:46]:** going to get 8 * n over 4 uh is that right yeah so two * n^2 B okay I did that in order to verify that the cost per level is increasing geometrically so all that will matter is the leaf level okay this is the the proof of the master theorem um when things are doubling at every step and you can this was just a special case but every level will look the same every recursive level level of recursion if you add them all up you're getting twice as much as you had at the previous level so all that will matter is the leaf level okay the leaf level uh actually maybe I'll do it over here first question is how many leaves are there the leaves are this thing so the way I would think about this is uh because everything's nice and uniform is 8 to the power of the number of levels

**[1:13:44]:** what's the number of levels uh well we're dividing by two each time so it's going to be log of something uh but it's no longer log n because we're stopping early we're stopping when n reaches this value so it turns out that is n ided that value we take this is how many times do I have to multiply by two before I get to this which is the same thing as how many times do I have to divide n by two before I get that think about it okay but 8 to the log this is 2 to the 3 * log 2 to the log is just the thing so this is uh n over root M over B so many overs uh to the thir power okay this is starting to look familiar this is n cubed that should appear somewhere divided by square root of M over B this is the number of leaves now for each

**[1:14:52]:** Leaf we're paying this cost so the overall cost of Mt of n is going to be this times this so let's do that and

**[1:15:11]:** simplify uh so Mt of n is going to be Big O uh because we're taking the leaf level but there's some other things that's just going to lose us a factor of two uh we have this thing divided multiply by this thing so we' got n cubed over Square < TK of M overb times M over

**[1:15:41]:** B I made a mistake yeah thank you this is supposed to be cubed so this was M over B to the2 so now we have down here M over B to the three halves thank you thought that looked weird

**[1:16:00]:** all right uh M over B to the three halves okay

**[1:16:15]:** H uh yeah what was I doing here this is supposed to be M over3 that's I was not missing a stroke thank you m over3 this is supposed to be M over3 wow okay so this is M over3 uh I'm just GNA drop the well I'll put it here but then I'm just going to write Theta so I can forget about the three because that's just a square root of three Factor so now this is going to be m to the three halves That's Makes Me much happier did I get it right this time uh double check so this is Square < TK of M to the 3 power so that's m to the 12 Cub m to the 3es I think that's good this base case was Square Ro of M okay get it right so now this is m to the 3es there is a square root that's going to come back because

**[1:17:12]:** m to the three Hales and there's an M upstairs so the one cancels we're going to be left with n cubed over < TK of M * B okay there was a lower order term because I dropped this plus one but uh let's not worry about that right now here we had n Cub / by B that was the standard algorithm now we've got n Cub divid B divid root of M that's big it's Bas I mean this is basically you're dividing by well square root of your cache size wow so who knows how big that is but say between main memory and disk we're talking gigabytes so this is like billions square root of a billion is still pretty big uh like 10 100 thousand so this is a huge amount faster than the standard algorithm you can do way better than scans basically because we're reusing the same rows and columns over and

**[1:18:08]:** over now this is standard matrix multiplication you might ask what about stren's algorithm well same thing works you can do the same analysis Sten of course you get a similar improvement over stasen uh you can do this for nons square matrices and all those good things I have one minute left and it's going to be enough I think to cover lru block replacement so uh here's what I want to say about lru block replacement so in the beginning we said the model is lru or it could have been fifo remember that and this algorithm will work just fine from an lru perspective or fifo perspective if you think about it but why how do we know that lru is as good as anything I claim if you uh look at some sequence of block axises so suppose you know what B is and you count uh for a cach of size M

**[1:19:03]:** how many uh memory transfers does lru do it's going to be within a factor of two of the optimal but not the optimal for a c for size M the optimal for a c of size M over two this is a bit of a weird statement I have a factor of two here and a factor of two here this is a cool idea called resource augmentation uh

**[1:19:27]:** fancy word uh for a simple idea this we're used to this is approximation algorithms okay but this is an approximation in cost here we're approximating the resources available to the algorithm we're changing the Machine model dividing M by two and we get uh a nice result why is this okay because if you look at a bound like this if you change M by a factor of two it will not change the Bound by more than a factor of square root of two so as long as you have it most say a linear or polinomial dependence on M changing M by a constant Factor will not change the overall running time The cach oblivious algorith this is why we can assume it's lru the same is true for fifo it's probably true in expectation for random uh sequences and uh I will leave it at that if you want to see the do you want to

**[1:20:17]:** see the proof of this theorem tomorrow or Thursday yes okay we'll cover it on Thursday
