Integrated prefetching and caching with read and write requests

Susanne Albers; Markus Büttner

doi:10.1007/978-3-540-45078-8_15

Integrated prefetching and caching with read and write requests

Susanne Albers, Markus Büttner

University of Freiburg

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

1 Scopus citations

Abstract

All previous work on integrated prefetching/caching assumes that memory reference strings consist of read requests only. In this paper we present the first study of integrated prefetching/caching with both read and write requests. For single disk systems we analyze popular algorithms such as Conservative and Aggressive and give tight bounds on their approximation ratios. We also develop a new algorithm that performs better than Conservative and Aggressive. For parallel disk systems we present a general technique to construct feasible schedules. The technique achieves a load balancing among the disks. Finally we show that it is NP-complete to decide if an input can be served with f fetch and w write operations, even in the single disk setting.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Frank Dehne, Jorg-Rudiger Sack, Michiel Smid
Publisher	Springer Verlag
Pages	162-173
Number of pages	12
ISBN (Print)	3540405453
DOIs	https://doi.org/10.1007/978-3-540-45078-8_15
State	Published - 2003
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2748
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-540-45078-8_15

Cite this

Albers, S., & Büttner, M. (2003). Integrated prefetching and caching with read and write requests. In F. Dehne, J.-R. Sack, & M. Smid (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 162-173). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2748). Springer Verlag. https://doi.org/10.1007/978-3-540-45078-8_15

Albers, Susanne ; Büttner, Markus. / Integrated prefetching and caching with read and write requests. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Frank Dehne ; Jorg-Rudiger Sack ; Michiel Smid. Springer Verlag, 2003. pp. 162-173 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{db6ccf5afb2b4c29b3bef211ce6290e5,

title = "Integrated prefetching and caching with read and write requests",

abstract = "All previous work on integrated prefetching/caching assumes that memory reference strings consist of read requests only. In this paper we present the first study of integrated prefetching/caching with both read and write requests. For single disk systems we analyze popular algorithms such as Conservative and Aggressive and give tight bounds on their approximation ratios. We also develop a new algorithm that performs better than Conservative and Aggressive. For parallel disk systems we present a general technique to construct feasible schedules. The technique achieves a load balancing among the disks. Finally we show that it is NP-complete to decide if an input can be served with f fetch and w write operations, even in the single disk setting.",

author = "Susanne Albers and Markus B{\"u}ttner",

year = "2003",

doi = "10.1007/978-3-540-45078-8_15",

language = "English",

isbn = "3540405453",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "162--173",

editor = "Frank Dehne and Jorg-Rudiger Sack and Michiel Smid",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

Albers, S & Büttner, M 2003, Integrated prefetching and caching with read and write requests. in F Dehne, J-R Sack & M Smid (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2748, Springer Verlag, pp. 162-173. https://doi.org/10.1007/978-3-540-45078-8_15

Integrated prefetching and caching with read and write requests. / Albers, Susanne; Büttner, Markus.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Frank Dehne; Jorg-Rudiger Sack; Michiel Smid. Springer Verlag, 2003. p. 162-173 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2748).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Integrated prefetching and caching with read and write requests

AU - Albers, Susanne

AU - Büttner, Markus

PY - 2003

Y1 - 2003

N2 - All previous work on integrated prefetching/caching assumes that memory reference strings consist of read requests only. In this paper we present the first study of integrated prefetching/caching with both read and write requests. For single disk systems we analyze popular algorithms such as Conservative and Aggressive and give tight bounds on their approximation ratios. We also develop a new algorithm that performs better than Conservative and Aggressive. For parallel disk systems we present a general technique to construct feasible schedules. The technique achieves a load balancing among the disks. Finally we show that it is NP-complete to decide if an input can be served with f fetch and w write operations, even in the single disk setting.

AB - All previous work on integrated prefetching/caching assumes that memory reference strings consist of read requests only. In this paper we present the first study of integrated prefetching/caching with both read and write requests. For single disk systems we analyze popular algorithms such as Conservative and Aggressive and give tight bounds on their approximation ratios. We also develop a new algorithm that performs better than Conservative and Aggressive. For parallel disk systems we present a general technique to construct feasible schedules. The technique achieves a load balancing among the disks. Finally we show that it is NP-complete to decide if an input can be served with f fetch and w write operations, even in the single disk setting.

UR - http://www.scopus.com/inward/record.url?scp=35248832609&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-45078-8_15

DO - 10.1007/978-3-540-45078-8_15

M3 - Chapter

AN - SCOPUS:35248832609

SN - 3540405453

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 162

EP - 173

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Smid, Michiel

PB - Springer Verlag

ER -

Albers S, Büttner M. Integrated prefetching and caching with read and write requests. In Dehne F, Sack JR, Smid M, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 162-173. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45078-8_15

Integrated prefetching and caching with read and write requests

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this