Minimizing stall time in single and parallel disk systems using multicommodity network flows

Susanne Albers; Carsten Witt

Minimizing stall time in single and parallel disk systems using multicommodity network flows

pro3dure medical GmbH

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

Abstract

We study integrated prefetching and caching in single and parallel disk systems. Arecen t approach used linear programming to solve the problem. We show that integrated prefetching and caching can also be formulated as a min-cost multicommodity flow problem and, exploiting special properties of our network, can be solved using combinatorial techniques. Moreover, for parallel disk systems, we develop improved approximation algorithms, trading performance guarantee for running time. If the number of disks is constant, we achieve a 2-approximation.

Original language	English
Title of host publication	Approximation, Randomization, and Combinatorial Optimization
Subtitle of host publication	Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings
Editors	Luca Trevisan, Klaus Jansen, Michel Goemans, Jose D. P. Rolim
Publisher	Springer Verlag
Pages	12-24
Number of pages	13
ISBN (Electronic)	3540424709
State	Published - 2015
Externally published	Yes
Event	4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 - Berkeley, United States Duration: 18 Aug 2001 → 20 Aug 2001

Publication series

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

Conference

Conference	4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001
Country/Territory	United States
City	Berkeley
Period	18/08/01 → 20/08/01

Cite this

Albers, S., & Witt, C. (2015). Minimizing stall time in single and parallel disk systems using multicommodity network flows. In L. Trevisan, K. Jansen, M. Goemans, & J. D. P. Rolim (Eds.), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings (pp. 12-24). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2129). Springer Verlag.

Albers, Susanne ; Witt, Carsten. / Minimizing stall time in single and parallel disk systems using multicommodity network flows. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. editor / Luca Trevisan ; Klaus Jansen ; Michel Goemans ; Jose D. P. Rolim. Springer Verlag, 2015. pp. 12-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4bff7ea46c2d43e2bee5b7b7943be32f,

title = "Minimizing stall time in single and parallel disk systems using multicommodity network flows",

abstract = "We study integrated prefetching and caching in single and parallel disk systems. Arecen t approach used linear programming to solve the problem. We show that integrated prefetching and caching can also be formulated as a min-cost multicommodity flow problem and, exploiting special properties of our network, can be solved using combinatorial techniques. Moreover, for parallel disk systems, we develop improved approximation algorithms, trading performance guarantee for running time. If the number of disks is constant, we achieve a 2-approximation.",

author = "Susanne Albers and Carsten Witt",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001; 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 ; Conference date: 18-08-2001 Through 20-08-2001",

year = "2015",

language = "English",

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

publisher = "Springer Verlag",

pages = "12--24",

editor = "Luca Trevisan and Klaus Jansen and Michel Goemans and Rolim, {Jose D. P.}",

booktitle = "Approximation, Randomization, and Combinatorial Optimization",

}

Albers, S & Witt, C 2015, Minimizing stall time in single and parallel disk systems using multicommodity network flows. in L Trevisan, K Jansen, M Goemans & JDP Rolim (eds), Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2129, Springer Verlag, pp. 12-24, 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Berkeley, United States, 18/08/01.

Minimizing stall time in single and parallel disk systems using multicommodity network flows. / Albers, Susanne; Witt, Carsten.
Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. ed. / Luca Trevisan; Klaus Jansen; Michel Goemans; Jose D. P. Rolim. Springer Verlag, 2015. p. 12-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2129).

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

TY - GEN

T1 - Minimizing stall time in single and parallel disk systems using multicommodity network flows

AU - Albers, Susanne

AU - Witt, Carsten

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001

PY - 2015

Y1 - 2015

N2 - We study integrated prefetching and caching in single and parallel disk systems. Arecen t approach used linear programming to solve the problem. We show that integrated prefetching and caching can also be formulated as a min-cost multicommodity flow problem and, exploiting special properties of our network, can be solved using combinatorial techniques. Moreover, for parallel disk systems, we develop improved approximation algorithms, trading performance guarantee for running time. If the number of disks is constant, we achieve a 2-approximation.

AB - We study integrated prefetching and caching in single and parallel disk systems. Arecen t approach used linear programming to solve the problem. We show that integrated prefetching and caching can also be formulated as a min-cost multicommodity flow problem and, exploiting special properties of our network, can be solved using combinatorial techniques. Moreover, for parallel disk systems, we develop improved approximation algorithms, trading performance guarantee for running time. If the number of disks is constant, we achieve a 2-approximation.

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

M3 - Conference contribution

AN - SCOPUS:84923080853

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

SP - 12

EP - 24

BT - Approximation, Randomization, and Combinatorial Optimization

A2 - Trevisan, Luca

A2 - Jansen, Klaus

A2 - Goemans, Michel

A2 - Rolim, Jose D. P.

PB - Springer Verlag

T2 - 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001

Y2 - 18 August 2001 through 20 August 2001

ER -

Albers S, Witt C. Minimizing stall time in single and parallel disk systems using multicommodity network flows. In Trevisan L, Jansen K, Goemans M, Rolim JDP, editors, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 4th International Workshop on Approximation, Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001, Proceedings. Springer Verlag. 2015. p. 12-24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Minimizing stall time in single and parallel disk systems using multicommodity network flows

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this