de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

The Cost of Address Translation

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44713

Jurkiewicz,  Tomasz
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1212.0703.pdf
(Preprint), 530KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Jurkiewicz, T., & Mehlhorn, K. (2012). The Cost of Address Translation. Retrieved from http://arxiv.org/abs/1212.0703.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0015-8653-C
Abstract
Modern computers are not random access machines (RAMs). They have a memory hierarchy, multiple cores, and virtual memory. In this paper, we address the computational cost of address translation in virtual memory. Starting point for our work 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 EM model (external memory model) does not correctly predict growth rates of actual running times. We propose the VAT model (virtual address translation) to account for the cost of address translations and analyze the algorithms mentioned above and others in the model. The predictions agree with the measurements. We also analyze the VAT-cost of cache-oblivious algorithms.