Campus Event Calendar

Event Entry

What and Who

Computational Complexity of the Virtual Address Translation

Tomasz Jurkiewicz
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
Public Audience

Date, Time and Location

Friday, 27 April 2012
30 Minutes
E1 4


The role of models of computation in algorithmics is abstraction of real machines that can be used for problems and algorithms analysis. A good model is mathematically pleasing and has predictive value. Both aspects are essential. If analysis has no predictive value, it becomes a mathematical game. If model is not clean and simple, researchers will not use it.

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.


Tomasz Jurkiewicz
--email hidden
passcode not visible
logged in users only

Tomasz Jurkiewicz, 04/25/2012 05:10 -- Created document.