Markov chain algorithms: A template for building future robust low power systems

Biplab Deka, Alex A. Birklykke, Henry Duwe, Vikash K. Mansinghka, Rakesh Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Although computational systems are looking towards post CMOS devices in the pursuit of lower power, the 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 as such algorithms are both sufficiently general and tolerant to transition errors. We show with four example applications - boolean satisfiability (SAT), sorting, LDPC decoding and clustering - how applications can be cast as Markov Chain 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 Markov Chains as an algorithmic template for future robust low power systems.

Original languageEnglish (US)
Title of host publicationConference Record of the 47th Asilomar Conference on Signals, Systems and Computers
PublisherIEEE Computer Society
Pages118-125
Number of pages8
ISBN (Print)9781479923908
DOIs
StatePublished - Jan 1 2013
Event2013 47th Asilomar Conference on Signals, Systems and Computers - Pacific Grove, CA, United States
Duration: Nov 3 2013Nov 6 2013

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393

Other

Other2013 47th Asilomar Conference on Signals, Systems and Computers
CountryUnited States
CityPacific Grove, CA
Period11/3/1311/6/13

    Fingerprint

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications

Cite this

Deka, B., Birklykke, A. A., Duwe, H., Mansinghka, V. K., & Kumar, R. (2013). Markov chain algorithms: A template for building future robust low power systems. In Conference Record of the 47th Asilomar Conference on Signals, Systems and Computers (pp. 118-125). [6810242] (Conference Record - Asilomar Conference on Signals, Systems and Computers). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2013.6810242