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. |
Year | Venue | Keywords |
---|---|---|
2014 | CoRR | data structures and algorithms,computer science |
Field | DocType | Volume |
Data structure,Cache-oblivious algorithm,Physical address,Cache,Virtual memory,Computer science,Virtual address space,Algorithm,Theoretical computer science,Flat memory model,Auxiliary memory | Journal | abs/1404.3577 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomasz Jurkiewicz | 1 | 8 | 1.27 |
Kurt Mehlhorn | 2 | 5314 | 853.36 |
Patrick K. Nicholson | 3 | 88 | 14.10 |