Stochastic $p$-Bits for Invertible Logic

Conventional semiconductor-based logic and nanomagnet-based memory devices are built out of stable, deterministic units such as standard metal-oxide semiconductor transistors, or nanomagnets with energy barriers in excess of $\approx 40–60\mathrm{kT}$. In this paper, we show that unstable, stochastic units, which we call “$p$-bits,” can be interconnected to create robust correlations that implement precise Boolean functions with impressive accuracy, comparable to standard digital circuits. At the same time, they are invertible, a unique property that is absent in standard digital circuits. When operated in the direct mode, the input is clamped, and the network provides the correct output. In the inverted mode, the output is clamped, and the network fluctuates among all possible inputs that are consistent with that output. First, we present a detailed implementation of an invertible gate to bring out the key role of a single three-terminal transistorlike building block to enable the construction of correlated $p$-bit networks. The results for this specific, CMOS-assisted nanomagnet-based hardware implementation agree well with those from a universal model for $p$-bits, showing that $p$-bits need not be magnet based: any three-terminal tunable random bit generator should be suitable. We present a general algorithm for designing a Boltzmann machine (BM) with a symmetric connection matrix [$J$] ($J_{ij}=J_{ji}$) that implements a given truth table with $p$-bits. The [$J$] matrices are relatively sparse with a few unique weights for convenient hardware implementation. We then show how BM full adders can be interconnected in a partially directed manner ($J_{ij}\ne J_{ji}$) to implement large logic operations such as 32-bit binary addition. Hundreds of stochastic $p$-bits get precisely correlated such that the correct answer out of $2^{33}$ ($\approx 8\times 10^9$) possibilities can be extracted by looking at the statistical mode or majority vote of a number of time samples. With perfect directivity ($J_{ji}=0$) a small number of samples is enough, while for less directed connections more samples are needed, but even in the former case logical invertibility is largely preserved. This combination of digital accuracy and logical invertibility is enabled by the hybrid design that uses bidirectional BM units to construct circuits with partially directed interunit connections. We establish this key result with extensive examples including a 4-bit multiplier which in inverted mode functions as a factorizer.

Popular Summary

There is increasing interest in probabilistic brainlike logic, which can be far more energy efficient than standard deterministic logic. However, probabilistic logic is generally considered suitable only for operations such as search and optimization rather than precise computation, which seems better suited for deterministic logic. Here, we show that unstable, stochastic units, which we call “$p$-bits,” can be interconnected into “$p$-circuits” to create robust correlations that implement precise Boolean functions with impressive accuracy, comparable to that of deterministic digital circuits.

We show that these $p$-circuits are “invertible,” a unique property that is absent in standard digital circuits. When operated in the direct mode, the input is clamped, and the network provides the correct output. In the inverted mode, the output is clamped, and the network fluctuates among all possible inputs that are consistent with that output. Even large circuits composed of hundreds of $p$-bits can be designed to exhibit this property of invertibility while preserving a striking degree of digital accuracy. A 32-bit adder, for example, rapidly converges to the single correct state out of $2^{33}$ (roughly $8\times 10^9$) possible states with an accuracy similar to digital circuits. However, unlike digital circuits, these circuits can also be operated in the inverse mode to perform subtraction. We also show that spin-current-driven nanomagnets can represent $p$-bits, but the situation is by no means limited: Any three-terminal tunable random bit generator should be suitable.

We expect that our theoretical findings will inspire searches for physical realizations of $p$-bits.

Figure 1

Generic building block for PSL. (a) Generic model for PSL described by Eq. (1) with distinct READ and WRITE units represented by the $R$ and $W$ icon shown in (b). Useful functionalities are obtained by interconnecting $R$ and $W$ units according to Eq. (2), $I_i=I_0(h_i+\sum J_{ij}{m}_j)$, with appropriately designed $\{h\}$ and [$J$]. (c) The blue trace shows the “magnetization” ($m_i$) obtained from Eq. (1) as the current ($I_i$) is ramped. The red trace shows the sigmoid response obtained from a $RC$ circuit which provides a moving average of the time-dependent “magnetization” that agrees very well with the black curve showing $\tanh (I_i)$. The bias terminal could involve a voltage ($V$) instead of a current ($I$), just as the output could involve quantities other than magnetization. (d) The idealized telegraphic behavior of the model is shown at various bias points along with corresponding distributions.

Figure 2

PSL designs discussed in this paper. (a) Basic Boolean elements (AND and OR, full adder) are implemented as Boltzmann machines based on symmetrically coupled networks with $J_{ij}=J_{ji}$. (b) Complex Boolean functions like a 32-bit ripple carry adder or subtractor and 4-bit multiplier or factorizer are implemented by combining the reciprocal Boltzmann machines in a directed fashion.

Figure 3

CMOS-assisted implementation of $p$-bits. (a) A possible CMOS-assisted implementation of $p$-bits that have separate READ-WRITE paths. A GSHE layer provides a spin current is able to pin the magnetization of circular ferromagnets (FM) ($\mathrm{\Delta }\approx 0\mathrm{kT}$). The change in magnetization is sensed by a MTJ and amplified by two CMOS inverters that act as a buffer, providing the necessary isolation and gain. (b) Self-consistent, modular modeling of transport and magnetization dynamics. See “Assumptions of the model” in the text. (c) Equivalent READ circuit. (d) spice-based average output voltage normalized to the $V_{DD}=0.8\mathrm{V}$ of 14-nm Fin Field-Effect Transistor (FinFET) high-performance (HP) inverters [44]. (e) sLLG-based average magnetization of the circular magnet as a function of the spin current (averaged over 500 ns for each bias point with a time step of $\mathrm{\Delta }\mathrm{t}=0.05\mathrm{ps}$, $10\times 10^6$ points per marker), normalized to the GSHE gain and the thermal noise strength $I_s^{\mathrm{th}}$. (f) The time-dependent output voltage at various bias points.

Figure 4

Invertible AND gate. (a) Passive resistor network that is used to obtain the connection terms $J_{ij}$ to correlate $p$-bits. The output impedance $R_{ij}=1/G_{ij}$ is much smaller than the input impedance $R_{\mathrm{GSHE}}$, allowing separate voltages to add at the input of the $i$th $p$-bit. (b) Explicit implementation of an AND gate based on Eq. (10). (c) When $C$ is clamped to 1, $A$ and $B$ spend most of their time in the (11) state, the only combination consistent with $C=1$. (d) The invertible operation of the AND gate when the $C$ gate is clamped to a zero, while $A$ and $B$ are left floating. $A$ and $B$ bits fluctuate between three possible combinations consistent with $C=0$, $(A,B)=(00),(01),(10)$. The time response of $A$, $B$, $C$ voltages are normalized by $V_{DD}$. Histogram is obtained by averaging over 200 ns of thresholded voltages, only the first 20 ns of $A$, $B$, $C$ voltages are shown for clarity.

Figure 5

14-nm Predictive Technology Model, inverter or buffer. dc response of 14-nm HP FinFETs based on Ref. [44] for an inverter and buffer. Sizing the transistors differently allows the switching point to be shifted.

Figure 6

Truth table to $J$ matrix. A given truth table is first transformed from binary to bipolar variables by using the transformation $m=2t-1$, where $m$ and $t$ represent the magnetization and binary values of the truth table. Additional bits are introduced to each line of the truth table to ensure that the resultant $S$ matrix is invertible. The indices $i$, $j$ correspond to the number of lines in the truth table. $u_i$, $u_j$ are column vectors. As an example, we show auxiliary bits that result in an $S$ matrix equal to the identity matrix, since the eigenvectors are orthogonal. The $J$ matrix is then obtained by Eq. (12a), which ensures that the truth table corresponds to the low-energy states of the Boltzmann machines according to Eq. (4). A handle bit of $+1$ is introduced to each line of the truth table, which can be biased to ensure that the complementary truth table does not appear along with the desired one. This bit also allows a truth table to be electrically reconfigured into its complement.

Figure 7

Correlated $p$-bits, AND gate. When the interaction strength ($I_0$) is zero, $p$-bits produce uncorrelated noise, visiting all possible states with equal probability. In this example, the interaction strength (pseudo inverse temperature) is suddenly increased from 0 to 2 as a step function at $t=t_0$, to effectively “quench” the network. This correlates the $p$-bits to produce the truth table of an AND gate (AND: $A\cap B=C$). Note that after this quenching, the $p$-bits visit only the low-energy states corresponding to the truth table of the AND gate, and once the system is in one of the low-energy states, it tends to stay there for a while, until being kicked out by the thermal noise. The time averages of the uncorrelated and the correlated system are well explained by the Boltzmann law stated in Eq. (4). The total simulation uses $T=4\times {10}^6$ steps to compare the results with the Boltzmann distribution, though only a fraction are shown in the upper panel for clarity.

Figure 8

Implementing a Boolean function and its inverse.: The input or output terminals of an appropriately interconnected network of $p$-bits can be “clamped” to perform a specific logic operation or its inverse. In this example, the input bits $(A,B)$ of an OR gate are clamped to be $+1$, forcing the output bit $C$ to be 1, during the first phase of operation ($t<t_0$). In the second phase of operation ($t>t_0$), the output of the OR gate $C$ is clamped to the value $+1$, which is consistent with three different combinations of $(A,B)$. As shown in the time response and the long-time histogram plots, all three possibilities emerge with equal probability, demonstrating the “inverse” OR operation. In each case, the expected probabilities from the Boltzmann law [Eq. (4)] closely match those produced by the generic model, Eqs. (1) and (2), after running the system for $10^6$ steps. Only a fraction are shown in the upper panel for clarity.

Figure 9

Noise tolerance of AND. The probability of a wrong output for an (AND) gate [Eq. (15)] operated with clamped inputs is investigated in the presence of a random noise field which enters Eq. (2) as indicated in the figure. The noise is assumed to be uniformly distributed over all $p$-bits in a given network, and centered around zero with magnitude $\pm {\tilde{h}}_n$, where $(I_0=2,h_i=\pm 1)$. Each gate is simulated 50 000 times for $T=100$ time steps to produce an error probability for a given noise value, and the maximum peak produced by the system is assumed to be an output that can be read with certainty. The system shows robust behavior even in the presence of large levels of noise.

Figure 10

Full adder. Full adder in the truth table mode, where all inputs and outputs are floating, calculated using $J_{\mathrm{FA}}$ from Eq. (16), with $I_0=0.5$. The statistics are collected for $T=10^6$ steps, and each terminal output is then placed in the histogram. The states are numbered using the decimal number corresponding to the binary number $[\begin{array}{ccccc}{C}_i& A& B& S& C_o\end{array}]$. The decimal numbers corresponding to the truth table are shown in the inset, and these match the location of the taller peaks in the histogram. Note that the Boltzmann distribution [Eq. (4)] quantitatively matches the model even for the suppressed peaks.

Figure 11

32-bit ripple carry adder (RCA). (a) 32-bit ripple carry adder is designed using individual full adder units with the carry bit designed as a directed connection from the least significant bit to the most significant bit. The overall $J$ matrix for a 32-bit adder $J$ matrix is shown, and it is quite sparse and quantized. (b) For $t<t_0$, $I_0=0$ and the sum fluctuates randomly. At $t=t_0$, $I_0$ is suddenly increased, and the adder converges on the correct result for two random inputs $A$ and $B$. The distribution of 1000 data points ($t>t_0$) shows a single peak with 24% probability of time spent in the correct state (not including the uncorrelated time points for $t<t_0$). (c) Even though the connections between the full adder units are directed, the system performs the inverse function as well. When the output ($S$) is clamped to a fixed number, the inputs ($A$) and ($B$) fluctuate in a correlated manner to make $A+B=S$ when $I_0=1$. Note the broad distributions of $A$ and $B$ (collected for $t>t_0$) as compared to the extremely sharp distribution of $A+B$.

Figure 12

Ripple carry adder delay. The delay of the RCA as a function of number of bits in the ripple carry adder is shown. The worst-case input combination generates a carry that propagates all the way through bit 1 to bit $N$, and has a linear dependence on the number of bits, exhibiting $O(n)$ complexity. When the inputs are random, the delay increases logarithmically. The delay is defined to be the time it takes for the network to reach the mode of the array for $T=200$ after getting quenched at $t=0$. Each point is an average of 500 trials with random initial conditions for an $I_0=1.5$, and the mode of the array is exactly equal to the arithmetic sum of the inputs in each case. The worst-case inputs are $A=0\dots 000$ and $B=1\dots 111$ with an input carry ($C_{\mathrm{in}})$ of 1. Results show a weak $I_0$ dependence.

Figure 13

Accuracy of 32-bit adder, directed versus bidirectional. The results are shown for the adder operating in a subtractor mode, clamping one (random) 32-bit input ($A$) and a (random) 33-bit output ($C_{\mathrm{out}}+S$), and observing the other 32-bit input $B$, which should provide the difference $S–A$. (a) Color map of the binary state of each of the 448 $p$-bits comprising the directed adder as a function of time with the interaction parameter $I_0$ suddenly increased from 0.25 to 5 at $t_0=50$. For low values of $I_0$ at $t<50$, the collection of $p$-bits is like a molten liquid which is quenched at $t_0=50$ into a solid. (b) Surprisingly, this solid corresponds to a “perfect crystal” in each of the 1000 trial experiments, with $S–A–B$ exactly equal to zero (dark blue). (c) Same as (a) but for a bidirectional adder. Here, too, the “liquid” quenches to a solid at $t_0=50$, but in this case the resulting “solid” is full of defects (with hardly any zeros), with $S–A–B\ne 0$, yielding a different wrong result for each trial as evident from (d). For (c) and (d) the color bar is modified to have a dark blue color corresponding to exactly zero. $S$, $A$, $B$ are taken to be the statistical mode of the $100\times 1$ array obtained at the end of each trial.

Figure 14

Invertibility of 32-bit adder, directed versus bidirectional. An adder that provides the sum $S$ of two 32-bit numbers $A$ and $B$: $S=A+B$. The left-hand panel shows the adder implemented with bidirectional carry bits, while the right-hand panel shows one with carry bits directed from the least significant to the most significant bit. Four different modes are shown with (i) $A$ and $B$ clamped (addition), (ii) $S$ and $A$ clamped (subtraction), (iii) $A$, $B$, and $S$ for the 16 most significant bits (msb) clamped, and (iv) $A$, $B$, and $S$ for the 16 least significant bits (lsb) clamped. Note that the bidirectional implementation shows very large errors for all modes of operation. The directed implementation works perfectly for both the adder and the subtractor modes. It also works if we clamp the least significant bits, but not if we clamp the most significant bits. Correlation parameter $I_0=1$, $T=100$ steps for all trials. $S$, $A$, $B$ are taken to be the mode (most frequent value) of the $100\times 1$ array obtained at the end of each trial. Clamped inputs are random 32-bit words for each trial, for a total of 1000 trials.

Figure 15

Error versus bidirectionality. The degree of bidirectionality $J_{ji}/J_{ij}$ of the carry-out ($j$) to carry-in ($i$) link between the full adders is systematically varied while keeping the sum $J_{ij}+J_{ji}$ constant. In each case the sum is obtained from the statistical mode (or majority vote) of $T$ time samples over 50 trials. The $y$ axis shows the fraction of trials that yield the wrong result. Note that for large $I_0$ and small $T$, error-free operation is obtained only if bidirectionality is close to zero, similar to standard digital circuits. But with $I_0=1.5$ and $T=50000$, error-free operation (at least for 50 trials) is obtained even with $\approx 75\%$ bidirectionality.

Figure 16

Factorization through inverse multiplication. The reversibility of PSL allows the operation of integer factorization using a binary multiplication circuit implemented using the principles of digital logic using AND gates and full adders, as shown in (a). The output nodes of a 4-bit multiplier are clamped to a given integer, and the system produces the only consistent factors of the product at the input terminals, probabilistically. The interaction parameter $I_0$ is suddenly increased to a saturation value of 2, and held constant as shown. (b) The output terminal is clamped to 9 and is factored into $3\times 3$; note that $9\times 1$ is not an achievable solution in this setup since encoding 9 requires 4-bit inputs in binary, whereas inputs are limited to 2-bits. (c) The output terminal is clamped to 6 and after being correlated, the factors cross-oscillate between 2 and 3. In both cases the histogram is obtained by counting outputs after $t>t_{\text{total}}/2=1.25\times 10^4$ time steps to collect statistics after the system is thermalized.