English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Cache-Oblivious VAT-Algorithms

MPS-Authors
/persons/resource/persons45021

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

/persons/resource/persons101850

Nicholson,  Patrick
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1404.3577.pdf
(Preprint), 192KB

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

Jurkiewicz, T., Mehlhorn, K., & Nicholson, P. (2014). Cache-Oblivious VAT-Algorithms. Retrieved from http://arxiv.org/abs/1404.3577.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-36C2-4
Abstract
The VAT-model (virtual address translation model) extends the EM-model (external memory model) and takes the cost of address translation in virtual memories into account. In this model, the cost of a single memory access may be logarithmic in the largest address used. We show that the VAT-cost of cache-oblivious algorithms is only by a constant factor larger than their EM-cost; this requires a somewhat more stringent tall cache assumption as for the EM-model.