2011 | OriginalPaper | Buchkapitel
Upper and Lower I/O Bounds for Pebbling r-Pyramids
verfasst von : Desh Ranjan, John Savage, Mohammad Zubair
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Modern computers have several levels of memory hierarchy. To obtain good performance on these processors it is necessary to design algorithms that minimize I/O traffic to slower memories in the hierarchy. In this paper, we present I/O efficient algorithms to pebble
r
-pyramids and derive lower bounds on the number of I/O steps to do so. The
r
-pyramid graph models financial applications which are of practical interest and where minimizing memory traffic can have a significant impact on cost saving.