日本語
 
User Manual Privacy Policy ポリシー/免責事項 連絡先
  詳細検索ブラウズ

アイテム詳細


公開

成果報告書

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;

URL
There are no locators available
フルテキスト (公開)

arXiv:1404.3577.pdf
(プレプリント), 192KB

付随資料 (公開)
There is no public supplementary material available
引用

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


引用: http://hdl.handle.net/11858/00-001M-0000-0024-36C2-4
要旨
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.