de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

New on-line algorithms for the page replication problem

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43989

Albers,  Susanne
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Koga,  Joachim
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-94-106.pdf
(beliebiger Volltext), 11MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Albers, S., & Koga, J.(1994). New on-line algorithms for the page replication problem (MPI-I-94-106). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B788-B
Zusammenfassung
The page replication problem arises in the memory management of large multiprocessor systems. Given a network of processors, each of which has its local memory, the problem consists of deciding which local memories should contain copies of pages of data so that a sequence of memory accesses can be accomplished efficiently. We present new competitive on-line algorithms for the page replication problem and concentrate on important network topologies for which algorithms with a constant competitive factor can be given. We develop the first optimal randomized on-line replication algorithm for trees and uniform networks; its competitive factor is approximately 1.58. Furthermore we consider on-line replication algorithms for rings and present general techniques that transform large classes of $c$-competitive algorithms for trees into $2c$-competitive algorithms for rings. As a result we obtain a randomized on-line algorithm for rings that is 3.16-competitive. We also derive two 4-competitive on-line algorithms for rings which are either deterministic or memoryless. All our algorithms improve the previously best competitive factors for the respective topologies.