Cache-Oblivious VAT-Algorithms

Jurkiewicz, Tomasz; Mehlhorn, Kurt; Nicholson, Patrick

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

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;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

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: https://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.