MPI-INF D1 Publications: Journal Article: Real-time prefetching and caching

Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

Options:

Library locked

Goto entry point

Author, Editor(s)

Author(s):

Sanders, Peter
Singler, Johannes
van Stee, Rob

dblp
dblp
dblp

Not MPG Author(s):

Sanders, Peter
Singler, Johannes

BibTeX cite key*:

SaSiSt13

Title

Title*:

Real-time prefetching and caching

Journal

Journal Title*:	Journal of Scheduling	Journal's URL:	http://www.springer.com/business+%26+management/operations+research/journal/10951
Download URL for the article:		Language:	English

Publisher

Publisher's Name:	Springer	Publisher's URL:	http://www.springer-ny.com/
Publisher's Address:	New York	ISSN:	1094-6136

Vol, No, pp, Date

Volume*:	16	Number:	1
Publishing Date:	February 2013
Pages*:	47-58	Number of VG Pages:	12
Page Start:		Page End:
Sequence Number:		DOI:

Note:
(LaTeX) Abstract:	The high latencies for access to background memory like hard disks or flash memory can be reduced by caching or hidden by prefetching. We consider the problem of scheduling the resulting I/Os when the available fast cache memory is limited and when we have real-time constraints where for each requested data block we are given a time interval during which this block needs to be in main memory. We give a near linear time algorithm for this problem which produces a feasible schedule whenever one exists. Another algorithm additionally minimizes I/Os and still runs in polynomial-time. For the online variant of the problem, we give a competitive algorithm that uses lookahead and augmented disk speed. We show a tight relationship between the amount of lookahead and the speed required to get a competitive algorithm.
URL for the Abstract:
Categories, Keywords:	Prefetching, online algorithms
HyperLinks / References / URLs:
Copyright Message:
Personal Comments:
Download Access Level:	MPG

Correlation

MPG Unit:	Max-Planck-Institut für Informatik

MPG Subunit:	Algorithms and Complexity Group
Audience:	experts only
Appearance:	MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{SaSiSt13,
AUTHOR = {Sanders, Peter and Singler, Johannes and van Stee, Rob},
TITLE = {Real-time prefetching and caching},
JOURNAL = {Journal of Scheduling},
PUBLISHER = {Springer},
YEAR = {2013},
NUMBER = {1},
VOLUME = {16},
PAGES = {47--58},
ADDRESS = {New York},
MONTH = {February},
ISBN = {1094-6136},
}

Entry last modified by Rob van Stee, 02/17/2014

Edit History (please click the blue arrow to see the details)

	Editor(s) [Library]	Created 02/28/2013 03:39:07 PM
Revision 0.	Editor Rob van Stee	Edit Date 02/28/2013 03:39:07 PM