In order to determine the number of operations performed by processor during the computation one usually uses the RAM model. However, there are situations where some operations are significantly more expensive than the others. In such a case predicting the running time of computation may require model extension taking it into account. The External Memory model was designed as an extension that captures the disproportionate cost of cache misses in case of memory hierarchy. We propose another extension to the RAM model called VAT. It accounts for process of the virtual address translation, that dominates the running time of algorithms which are very nonlocal in their memory access. (eg. generating a permutation, random access to an array, binary search)
Memory access is a complex multilayer process with a variable cost that in some circumstances can get logarithmic in the input size for each memory access. We believe it would be impractical to model the complete process precisely. The model we present and analyze concentrates on the dominant time consuming factor of the process, namely the memory translation. We believe the approach is simple and elegant, and the experiments confirm its accuracy.
In this talk I will present the model, concept of cache replacement strategies with the initial segment property, and the theoretical groundwork we performed till now together with the relevant experimental results. I will also discuss relation of the model to the cache oblivious approach, and the research perspectives.