Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Mehlhorn, Kurt
Sanders, Peter

dblp
dblp



BibTeX cite key*:

MehSan03j

Title

Title*:

Scanning Multiple Sequences via Cache Memory

Journal

Journal Title*:

Algorithmica

Journal's URL:


Download URL
for the article:

http://www.springerlink.com/content/2g1c9b60yr2h37ak/fulltext.pdf
http://link.springer.de/link/service/journals/00453/contents/02/0993/index.html

Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:


Publisher's
Address:

Berlin, Germany

ISSN:

0178-4617

Vol, No, pp, Date

Volume*:

35

Number:

1

Publishing Date:

2003

Pages*:

75-93

Number of
VG Pages:

46

Page Start:


Page End:


Sequence Number:


DOI:

10.1007/s00453-002-0993-2

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We consider the simple problem of scanning multiple sequences. There are k sequences of total length N which are to be scanned concurrently. One pointer into each sequence is maintained and an adversary specifies which pointer is to be advanced. The concept of scanning multiple sequence is ubiquitous in algorithms designed for hierarchical memory.

In the external memory model of computation with block size B , a memory consisting of m blocks, and at most m sequences the problem is trivially solved with N/B memory misses by reserving one block of memory for each sequence.

However, in a cache memory with associativity a , every access may lead to a cache fault if k > a . For a direct mapped cache (a = 1 ) two sequences suffice. We show that by randomizing the starting addresses of the sequences the number of cache misses can be kept to O(N/B) provided that k = O(m/B1/a) , i.e., the number of sequences that can be supported is decreased by a factor B1/a . We also show a corresponding lower bound.

Our result leads to a general method for converting sequence based algorithms designed for the external memory model of computation to cache memory even for caches with small associativity.


URL for the Abstract:

http://www.springerlink.com/content/2g1c9b60yr2h37ak/?p=4c8bf106f2474a2898e2def3870a9b7a&pi=251

Categories,
Keywords:


HyperLinks / References / URLs:

http://dblp.uni-trier.de/db/journals/algorithmica/algorithmica35.html#MehlhornS03

Copyright Message:


Personal Comments:


Download
Access Level:

Intranet

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{MehSan03j,
AUTHOR = {Mehlhorn, Kurt and Sanders, Peter},
TITLE = {Scanning Multiple Sequences via Cache Memory},
JOURNAL = {Algorithmica},
PUBLISHER = {Springer},
YEAR = {2003},
NUMBER = {1},
VOLUME = {35},
PAGES = {75--93},
ADDRESS = {Berlin, Germany},
ISBN = {0178-4617},
DOI = {10.1007/s00453-002-0993-2},
}


Entry last modified by Anja Becker, 01/21/2008
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Peter Sanders
Created
01/16/2004 11:23:10 AM
Revisions
8.
7.
6.
5.
4.
Editor(s)
Anja Becker
Anja Becker
Tamara Hausmann
Christine Kiesel
Christine Kiesel
Edit Dates
21.01.2008 10:47:09
04.01.2008 15:05:42
09.11.2006 14:39:24
04.10.2006 08:15:21
04.10.2006 08:14:57