On a Model of Virtual Address Translation
Tomasz Jurkiewicz, Kurt Mehlhorn · ACM Journal of Experimental Algorithmics · 2015
Modern computers are not Random Access Machines (RAMs). They have a memory hierarchy, multiple cores, and a virtual memory. We address the computational cost of the address translation in the virtual memory. The starting point for our work on virtual memory is the observation that the analysis of some simple algorithms (random scan of an array, binary search, heapsort) in either the RAM model or the External Memory (EM) model does not correctly predict growth rates of actual running times. We propose the Virtual Address Translation (VAT) model to account for the cost of address translations and analyze the algorithms mentioned and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms.