Analog computing: Bayesian probability based NAND gates

"A DARPA-funded processor start-up has made bold claims about a new kind of processor that computes using probabilities, rather than the traditional ones and zeroes of conventional processors. Lyric Semiconductor, an MIT spin-off, claims that its probabilistic processors could speed up some kinds of computation by a factor of a thousand, allowing racks of servers to be replaced with small processing appliances.

Calculations involving probabilities have a wide range of applications. Many spam filters, for example, work on the basis of probability; if an e-mail contains the word "Viagra" it's more likely to be spam than one which doesn't, and with enough of these likely-to-be-spam words, the filter can flag the mail as being spam with a high degree of confidence. Probabilities are represented as numbers between 0, impossible, and 1, certain. A fair coin toss has a probability of 0.5 of coming up heads.

Traditional computers are based on digital logic. The signals used inside processors are either 0 volts, for a zero, or the full voltage of the circuit (V_DD, in integrated circuit jargon) for a one. This has some nice properties: because the circuits only need to be fully on or fully off, they're quite robust against noise; a signal that momentarily goes a little bit above 0 V or drops a bit below V_DD won't affect the interpretation; it'll still be a zero or a one. The nice, simple, zero-or-one nature of the circuit also makes it easier to reason about how it works, which makes building processors—and the software to run on them—easy.

The big trade-off this causes is that most of the time, we want to manipulate numbers other than zero or one. There are infinite possible voltages between 0 and V_DD, which could be used to represent all the numbers we actually care about in a nice compact way. With binary circuits, however, we're stuck with just two possible values—one binary digit. To represent all the other numbers we want to use, we have to use multiple digital signals—multiple bits—and binary arithmetic.

This works very well—the computer revolution is testament to that—but it carries with it a certain level of complexity. Processors now have to manipulate dozens of signals together in order to work with simple concepts like "42" or "0.5", typically 32 or 64 at a time.

Which brings us back to the probability computations. Normal computers use 32- or 64-bit floating point arithmetic to calculate probabilities. For computers that need to compute probabilities very quickly, this means that they need a lot of circuitry to handle all these bits, and indeed, that's why today's processors have billions of transistors.

Lyric's innovation is to use analogue signals instead of digital ones, to allow probabilities to be encoded directly as voltages. Their probability gates represent zero probability as 0 V, and certainty as V_DD. But unlike digital logic, for which these are the only options, Lyric's technology allows probabilities between 0 and 1 to use voltages between 0 and V_DD. Each probabilistic bit ("pbit") stores not an exact value, but rather, the probability that the value is 1. The technology allows a resolution of about 8 bits; that is, they can discriminate between about 2⁸ = 256 different values (different probabilities) between 0 and V_DD.

By creating circuits that can operate directly on probabilities, much of the extra complexity of digital circuits can be eliminated. Probabilistic processors can perform useful computations with just a handful of pbits, with a drastic reduction in the number of transistors and circuit complexity as a result.

To do something useful with these pbits requires suitable logic gates, the building blocks of integrated circuits. The most important of these is the NAND gate. This is a gate with two inputs, with an output that is 1 as long as at least one of the inputs is 0, and 0 if they are both 1. NAND gates are important because any other gate can be constructed from one or more NAND gates. For example, a NOT gate, which outputs a 1 if the input is 0 and a 0 if the input is 1, can be constructed by sending the same value to both inputs of a NAND gate.

Lyric Semiconductor has developed NAND gates that operate on probabilities rather than binary values. The input probabilities are combined using Bayesian logic rather than the binary logic of conventional processors.

The company plans to build a processor dubbed GP5 that uses this technology to accelerate probability-heavy workloads, with applications such as spam filtering, shopping pattern analysis, and fraudulent transaction discovery being possible candidates. PCIe-based GP5 accelerator cards will give machines a thousand-fold improvement in probability computing performance. As well as the processor, the company is also creating a programming language, Probability Synthesis to Bayesian Logic, for programming the device. GP5 is still in the design stage, and the company plans to show it off in 2013.

The GP5's logic gates will be interconnected to enable complex probabilistic calculations to be performed in an inherently parallel way. This will give a further improvement over traditional computers, as they must perform their probability calculations in a serial manner.

More immediately, Lyric has devised a probability-based circuit for error-correction in flash memory. Flash memory produces something around one error in every 1,000 bits read. This is transparent to users, because the memory also includes circuitry to detect and correct these errors. This, however, adds complexity and takes up space, and as flash storage densities increase, the error rate is likely to worsen. Lyric Error Correction uses the same probabilistic logic to perform equivalent error detection and correction with about 3 percent of the circuitry, and 8 percent of the power, compared to conventional error correction. LEC is available to use today, with chips manufactured by TSMC.

Lyric Semiconductor hopes that this technology will eventually become mainstream. It claims that GP5 is a fifth generation of processor, following on from CPUs, DSPs, FPGAs, and GPUs. The first customers will likely be DARPA and unspecified three-letter agencies, and the initial devices will be expensive, but this is a technology that the company believes will one day be found in every computer."