TY - GEN
T1 - Markov chain algorithms
T2 - 2013 47th Asilomar Conference on Signals, Systems and Computers
AU - Deka, Biplab
AU - Birklykke, Alex A.
AU - Duwe, Henry
AU - Mansinghka, Vikash K.
AU - Kumar, Rakesh
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84901255945&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84901255945&partnerID=8YFLogxK
U2 - 10.1109/ACSSC.2013.6810242
DO - 10.1109/ACSSC.2013.6810242
M3 - Conference contribution
AN - SCOPUS:84901255945
SN - 9781479923908
T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers
SP - 118
EP - 125
BT - Conference Record of the 47th Asilomar Conference on Signals, Systems and Computers
PB - IEEE Computer Society
Y2 - 3 November 2013 through 6 November 2013
ER -