TY - GEN

T1 - On the theory of stochastic processors

AU - Duggirala, Parasara Sridhar

AU - Mitra, Sayan

AU - Kumar, Rakesh

AU - Glazeski, Dean

PY - 2010

Y1 - 2010

N2 - Traditional architecture design approaches hide hardware uncertainties from the software stack through overdesign, which is often expensive in terms of power consumption. The recently proposed quantitative alternative of stochastic computing requires circuits and processors to be correct only probabilistically and use less power. In this paper, we present the first step towards a theory of stochastic computing. Specifically, a formal model of a device which computes a deterministic function with stochastic delays is presented; the semantics of a stochastic circuit is obtained by composing such devices; finally, a quantitative notion of stochastic correctness, called correctness factor (CF), is introduced. For random data sources, a closed form expression is derived for CF of devices, which shows that there are two probabilities that contribute positively, namely, the probability of being timely with current inputs and the probability of being lucky with past inputs. Finally, we show the characteristic graphs obtained from the analytical expressions for the variation of correctness factor with clock period, for several simple circuits and sources.

AB - Traditional architecture design approaches hide hardware uncertainties from the software stack through overdesign, which is often expensive in terms of power consumption. The recently proposed quantitative alternative of stochastic computing requires circuits and processors to be correct only probabilistically and use less power. In this paper, we present the first step towards a theory of stochastic computing. Specifically, a formal model of a device which computes a deterministic function with stochastic delays is presented; the semantics of a stochastic circuit is obtained by composing such devices; finally, a quantitative notion of stochastic correctness, called correctness factor (CF), is introduced. For random data sources, a closed form expression is derived for CF of devices, which shows that there are two probabilities that contribute positively, namely, the probability of being timely with current inputs and the probability of being lucky with past inputs. Finally, we show the characteristic graphs obtained from the analytical expressions for the variation of correctness factor with clock period, for several simple circuits and sources.

KW - Formal models of computation

KW - Probabilistic circuits

KW - Probabilistic computing

UR - http://www.scopus.com/inward/record.url?scp=78649467733&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78649467733&partnerID=8YFLogxK

U2 - 10.1109/QEST.2010.43

DO - 10.1109/QEST.2010.43

M3 - Conference contribution

AN - SCOPUS:78649467733

SN - 9780769541884

T3 - Proceedings - 7th International Conference on the Quantitative Evaluation of Systems, QEST 2010

SP - 292

EP - 301

BT - Proceedings - 7th International Conference on the Quantitative Evaluation of Systems, QEST 2010

T2 - 7th International Conference on the Quantitative Evaluation of Systems, QEST 2010

Y2 - 15 September 2010 through 18 September 2010

ER -