Online paging for flash memory devices

  • We propose a variation of online paging in two-level memory systems where pages in the fast cache get modified and therefore have to be explicitly written back to the slow memory upon evictions. For increased performance, up to alpha arbitrary pages can be moved from the cache to the slow memory within a single joint eviction, whereas fetching pages from the slow memory is still performed on a one-by-one basis. The main objective in this new alpha-paging scenario is to bound the number of evictions. After providing experimental evidence that alpha-paging can adequately model flash-memory devices in the context of translation layers we turn to the theoretical connections between alpha-paging and standard paging. We give lower bounds for deterministic and randomized alpha-paging algorithms. For deterministic algorithms, we show that an adaptation of LRU is strongly competitive, while for the randomized case we show that by adapting the classical Mark algorithm we get an algorithm with a competitive ratio larger than the lower bound by a multiplicative factor of approximately 1.7.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Annamária Kovács, Ulrich MeyerORCiDGND, Gabriel Moruz, Andrei Laurian NegoescuGND
URN:urn:nbn:de:hebis:30-71163
ISSN:1868-8330
Parent Title (German):Frankfurter Informatik-Berichte ; [Nr. 09,2]
Series (Serial Number):Frankfurter Informatik-Berichte (09,2)
Document Type:Working Paper
Language:English
Date of Publication (online):2009/09/23
Year of first Publication:2009
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2009/09/23
Tag:Flash Memories; Online Algorithms; Paging Algorithms
GND Keyword:Algorithmus; Seitenersetzungsstrategie
Note:
Partially supported by the DFG grant ME 3250/1-1, and MADALGO
HeBIS-PPN:219461856
Institutes:Informatik und Mathematik / Informatik
CCS-Classification:F. Theory of Computation / F.1 COMPUTATION BY ABSTRACT DEVICES / F.1.2 Modes of Computation
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht