de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Accessing Multiple Sequences Through Set Associative Caches

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45344

Sanders,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Sanders, P. (1999). Accessing Multiple Sequences Through Set Associative Caches. In J. Wiedermann, P. van Emde Boas, & M. Nielsen (Eds.), Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP-99) (pp. 655-664). Berlin: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-358C-1
Zusammenfassung
The cache hierarchy prevalent in todays high performance processors has to be taken into account in order to design algorithms which perform well in practice. We start from the empirical observation that external memory algorithms often turn out to be good algorithms for cached memory. This is not self evident since caches have a fixed and quite restrictive algorithm choosing the content of the cache. We investigate the impact of this restriction for the frequently occurring case of access to multiple sequences. We show that any access pattern to $k=\Th{M/B^{1+1/a}}$ sequential data streams can be efficiently supported on an $a$-way set associative cache with capacity $M$ and line size $B$. The bounds are tight up to lower order terms.