TY - GEN

T1 - The synthesis of combinational logic to generate probabilities

AU - Qian, Weikang

AU - Riedel, Marc

AU - Bazargan, Kia

AU - Lilja, David J

PY - 2009

Y1 - 2009

N2 - As CMOS devices are scaled down into the nanometer regime, concerns about reliability are mounting. Instead of viewing nanoscale characteristics as an impediment, technologies such as PCMOS exploit them as a source of randomness. The technology generates random numbers that are used in probabilistic algorithms. With the PCMOS approach, different voltage levels are used to generate different probability values. If many different probability values are required, this approach becomes prohibitively expensive. In this work, we demonstrate a novel technique for synthesizing logic that generates new probabilities from a given set of probabilities. Three different scenarios are considered in terms of whether the given probabilities can be duplicated and whether there is freedom to choose them. In the case that the given probabilities cannot be duplicated and are predetermined, we provide a solution that is FPGA-mappable. In the case that the given probabilities cannot be duplicated but can be freely chosen, we provide an optimal choice. In the case that the given probabilities can be duplicated and can be freely chosen, we demonstrate how to generate arbitrary decimal probabilities from small sets - a single probability or a pair of probabilities - through combinational logic.

AB - As CMOS devices are scaled down into the nanometer regime, concerns about reliability are mounting. Instead of viewing nanoscale characteristics as an impediment, technologies such as PCMOS exploit them as a source of randomness. The technology generates random numbers that are used in probabilistic algorithms. With the PCMOS approach, different voltage levels are used to generate different probability values. If many different probability values are required, this approach becomes prohibitively expensive. In this work, we demonstrate a novel technique for synthesizing logic that generates new probabilities from a given set of probabilities. Three different scenarios are considered in terms of whether the given probabilities can be duplicated and whether there is freedom to choose them. In the case that the given probabilities cannot be duplicated and are predetermined, we provide a solution that is FPGA-mappable. In the case that the given probabilities cannot be duplicated but can be freely chosen, we provide an optimal choice. In the case that the given probabilities can be duplicated and can be freely chosen, we demonstrate how to generate arbitrary decimal probabilities from small sets - a single probability or a pair of probabilities - through combinational logic.

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

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

U2 - 10.1145/1687399.1687470

DO - 10.1145/1687399.1687470

M3 - Conference contribution

AN - SCOPUS:76349102306

SN - 9781605588001

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD

SP - 367

EP - 374

BT - Proceedings of the 2009 IEEE/ACM International Conference on Computer-Aided Design - Digest of Technical Papers, ICCAD 2009

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2009 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2009

Y2 - 2 November 2009 through 5 November 2009

ER -