MPI-I-97-1-024

Minimizing stall time in single and parallel disk systems

Albers, Susanne and Garg, Naveen and Leonardi, Stefano

MPI-I-97-1-024. November 1997, 16 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We study integrated prefetching and caching problems following
the work of Cao et al. and Kimbrel and Karlin.
Cao et al. and Kimbrel and Karlin gave approximation algorithms
for minimizing the total elapsed time in single and
parallel disk settings. The total elapsed time is the sum of the processor
stall times and the length of the request sequence to be served.

We show that an optimum prefetching/caching schedule for a
single disk problem can be computed in polynomial time,
thereby settling an open question by Kimbrel and Karlin.
For the parallel disk problem we give an approximation algorithm for
minimizing stall time. Stall time is a more realistic and harder to
approximate measure for this problem. All of our algorithms are based on
a new approach which involves formulating the prefetching/caching problems
as integer programs.

Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	181 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-024

BibTeX
@TECHREPORT{AlbersGargLeonardi97, AUTHOR = {Albers, Susanne and Garg, Naveen and Leonardi, Stefano}, TITLE = {Minimizing stall time in single and parallel disk systems}, TYPE = {Research Report}, INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik}, ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany}, NUMBER = {MPI-I-97-1-024}, MONTH = {November}, YEAR = {1997}, ISSN = {0946-011X},}