CS 229r: Algorithms for Big Data Fall 2015

Last time we talked about disk access model (as known as DAM, or external memory model). Our goal is to minimize I/Os, where we assume that the size of the disk is unbounded, while the memory is bounded and has size M. In particular, the memory is divided into MB pages, each of which is a block of size B. Today we are going to continue trying to minimize I/Os, but we are going to look at a new model called cache-oblivious model introduced in [FLPR99] (you can also refer to the survey [Dem02] for more detail). The new model is similar to DAM, but with two differences (we further refer them as two assumptions): 1. Algorithms are not allowed to know M or B. 2. Algorithms do not control cache replacement policy. Operating system handles cache replace-ment, and we assume it makes optimal choices. (So in our analysis, we assume that we evict what we want to evict.) Why do we have cache-oblivious model? First, it makes programs easily portable across different machines. You do not have to find parameters in your code for a specific machine. Note that the block size B is chosen to amortize against the expensive cost of seeking on the disk. In really, B is not fixed, because even on a given disk, there are multiple levels of memory hierarchy (L1/L2 cache