Dynamic programming in faulty memory hierarchies (cache-obliviously)

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