Markov chain algorithms: a template for building future robust low-power systems.
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.
Department of Electrical and Computer Engineering, University of Illinois at Urbana Champaign, Champaign, IL, USA deka2@illinois.edu.
Biplab
B
Deka
Department of Electrical and Computer Engineering, University of Illinois at Urbana Champaign, Champaign, IL, USA The Technology Platforms Section, Aalborg University, Aalborg, Denmark.
Alex A
AA
Birklykke
Department of Electrical and Computer Engineering, University of Illinois at Urbana Champaign, Champaign, IL, USA.
Henry
H
Duwe
Intelligence Initiative, Massachusetts Institute of Technology, Cambridge, MA, USA.
Vikash K
VK
Mansinghka
Department of Electrical and Computer Engineering, University of Illinois at Urbana Champaign, Champaign, IL, USA.
Rakesh
R
Kumar
Markov chain; algorithmic fault tolerance; error tolerance