Visible to the public Markov Chain Algorithms: A Template for Building Future Robust Low-power SystemsConflict Detection Enabled

TitleMarkov Chain Algorithms: A Template for Building Future Robust Low-power Systems
Publication TypeJournal Article
Year of Publication2014
AuthorsBiplab Deka, University of Illinois at Urbana-Champaign, Alex A. Birklykke, Aalborg University, Henry Duwe, University of Illinois at Urbana-Champaign, Vikash K. Mansinghka, Massachusetts Institute of Technology, Rakesh Kumar, University of Illinois at Urbana-Champaign
JournalPhilosophical Transactions of the Royal Society A Mathematical, Physical and Engineering Sciences
Date Published06/2014
Keywordsalgorithmic fault tolerance, error tolerance, Markov chain, NSA SoS Lablets Materials, science of security, Secure Platforms via Stochastic Computing, UIUC

Although computational systems are looking towards post CMOS devices in the pursuit of lower power, the expected inherent unreliability of such devices makes it difficult to design robust systems without additional power overheads for guaranteeing robustness. As such, algorithmic structures with inherent ability to tolerate computational errors are of significant interest. We propose to cast applications as stochastic algorithms based on Markov chains (MCs) as such algorithms are both sufficiently general and tolerant to transition errors. We show with four example applications--Boolean satisfiability, sorting, low-density parity-check decoding and clustering--how applications can be cast as MC algorithms. Using algorithmic fault injection techniques, we demonstrate the robustness of these implementations to transition errors with high error rates. Based on these results, we make a case for using MCs as an algorithmic template for future robust low-power systems.

Citation Keynode-32609

Other available formats:

Markov Chain Algorithms A Template for Building Future Robust Low-power Systems