Random access memories suffer from transient errors that lead the logical state of some bits to be read differently from how they were last written. Due to technological constraints, caches in the memory hierarchy of modern computer platforms appear to be particularly prone to bit flips. Since algorithms implicitly assume data to be stored in reliable memories, they might easily exhibit unpredictable behaviors even in the presence of a small number of faults. In this paper we investigate the design of dynamic programming algorithms in faulty memory hierarchies. Previous works on resilient algorithms considered a one-level faulty memory model and, with respect to dynamic programming, could address only problems with local dependencies. Our improvement upon these works is two-fold: (1) we significantly extend the class of problems that can be solved resiliently via dynamic programming in the presence of faults, settling challenging non-local problems such as all-pairs shortest paths and matrix multiplication; (2) we investigate the connection between resiliency and cache-efficiency, providing cache-oblivious implementations that incur an (almost) optimal number of cache misses. Our approach yields the first resilient algorithms that can tolerate faults at any level of the memory hierarchy, while maintaining cache-efficiency. All our algorithms are correct with high probability and match the running time and cache misses of their standard non-resilient counterparts while tolerating a large (polynomial) number of faults. Our results also extend to Fast Fourier Transform. © S. Caminiti, I. Finocchi, E.G. Fusco, and F. Silvestri.

Dynamic programming in faulty memory hierarchies (cache-obliviously) / Caminiti, Saverio; Finocchi, Irene; Fusco, EMANUELE GUIDO; F., Silvestri. - Proc. 31st Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011), (2011), pp. 433-444. (31st International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011, Mumbai, December 12-14, 2011). [10.4230/LIPIcs.FSTTCS.2011.433].

Dynamic programming in faulty memory hierarchies (cache-obliviously)

FINOCCHI, Irene;
2011

Abstract

Random access memories suffer from transient errors that lead the logical state of some bits to be read differently from how they were last written. Due to technological constraints, caches in the memory hierarchy of modern computer platforms appear to be particularly prone to bit flips. Since algorithms implicitly assume data to be stored in reliable memories, they might easily exhibit unpredictable behaviors even in the presence of a small number of faults. In this paper we investigate the design of dynamic programming algorithms in faulty memory hierarchies. Previous works on resilient algorithms considered a one-level faulty memory model and, with respect to dynamic programming, could address only problems with local dependencies. Our improvement upon these works is two-fold: (1) we significantly extend the class of problems that can be solved resiliently via dynamic programming in the presence of faults, settling challenging non-local problems such as all-pairs shortest paths and matrix multiplication; (2) we investigate the connection between resiliency and cache-efficiency, providing cache-oblivious implementations that incur an (almost) optimal number of cache misses. Our approach yields the first resilient algorithms that can tolerate faults at any level of the memory hierarchy, while maintaining cache-efficiency. All our algorithms are correct with high probability and match the running time and cache misses of their standard non-resilient counterparts while tolerating a large (polynomial) number of faults. Our results also extend to Fast Fourier Transform. © S. Caminiti, I. Finocchi, E.G. Fusco, and F. Silvestri.
2011
9783939897347
gaussian elimination paradigm; fault-tolerant algorithms; unreliable memories; dynamic programming; cache-oblivious algorithms
File in questo prodotto:
File Dimensione Formato  
FSTTCS2011.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 509.11 kB
Formato Adobe PDF
509.11 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/192673
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact