English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Accessing Multiple Sequences Through Set Associative Caches

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-358C-1 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-358E-E
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Sanders, Peter1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-021999
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518044
Other: Local-ID: C1256428004B93B8-0616E7BBC9777144C125688E005CB41A-San99c
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Prague, Czech Republic
Start-/End Date: 1999

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP-99)
Source Genre: Proceedings
 Creator(s):
Wiedermann, J., Editor
van Emde Boas, P., Editor
Nielsen, Mogens, Editor
Affiliations:
-
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 655 - 664 Identifier: ISBN: 3-540-66224-3

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 1644 Sequence Number: - Start / End Page: - Identifier: -