Voltage-driven Building Block for Hardware Belief Networks
Orchi Hassan Kerem Y. Camsari Supriyo Datta
cs.ET



School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA

School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA

School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA



Probabilistic spin logic (PSL) based on networks of binary stochastic neurons (or p-bits) has been shown to provide a viable framework for many functionalities including Ising computing, Bayesian inference, invertible Boolean logic and image recognition. This paper presents a hardware building block for the PSL architecture, consisting of an embedded MTJ and a capacitive voltage adder of the type used in neuMOS. We use SPICE simulations to show how identical copies of these building blocks (or weighted p-bits) can be interconnected with wires to design and solve a small instance of the NP-complete Subset Sum Problem fully in hardware.
 Keywords - Probabilistic computing, Embedded MTJ, p-bits, p-circuits, Invertible Boolean logic, Subset Sum Problem



Voltage-driven Building Block for Hardware Belief Networks
    Supriyo Datta
    December 30, 2023
==========================================================



§ INTRODUCTION


Probabilistic spin logic (PSL) has been shown to  provide a viable framework for Ising computing <cit.>, Bayesian inference <cit.>, invertible Boolean logic  <cit.>, and image recognition <cit.>. The PSL model is defined by two equations  <cit.> loosely analogous to a neuron and a synapse. The former  is what we call the p-bit whose output m_i is related to its dimensionless input I_i by the relation



    m_i(t+Δ t) = sgn{rand(-1,1) + tanh(I_i(t))}



where rand(-1,+1) is a random number uniformly distributed between -1 and +1, and t is the normalized time unit. The synapse generates the input I_i from a weighted sum of the states of other p-bits according to the relation

    I_i(t) = I_0( h_i(t)+∑_jJ_ijm_j)




where, h_i is the on-site bias and J_ij is the weight of the coupling from j^th p-bit to i^th p-bit and I_0 is a dimensionless constant. These two equations constitute the behavioral model of PSL. The objective of this paper is to present a voltage-driven hardware building block using present day device technologies such as embedded MRAM <cit.> and Floating-Gate MOS transistors, such that identical copies of the same block can be interconnected with wires to implement Eqs. <ref>. 


The paper is organized as follows: We first show a complete hardware mapping for the weighted p-bit by augmenting a recently introduced Magnetoresistive Random Access Memory (MRAM) type stochastic unit <cit.> with a floating gate MOS-based capacitive network <cit.>. We then show how the results of a fully interconnected ^Wp-bit circuit closely approximate the the ideal equations using an example of an “invertible” Full Adder that can perform 1-bit addition and subtraction. Finally, we show how such invertible Full Adders can be interconnected to solve a simple instance of the NP-complete Subset Sum Problem. 


Each example in this paper has been obtained using full SPICE models which simply uses transistors, capacitors and resistors without any additional complex circuitry or processing.




§ BUILDING BLOCK





Our building block has two components corresponding to the two Eqs. <ref>a,b. Eq. <ref>a is implemented by the p-bit in Fig.<ref>a which consists of an embedded low-barrier unstable MTJ coupled to two CMOS inverters which provides a stochastic output whose average value is controlled by the input voltage:


    V_out,i= V_DD/2sgn(rand(-1,+1) + tanhV_in,i/V_0)

where ± V_DD/2 are the supply voltages, and V_0 is a parameter (∼22  mV) describing the width of the sigmoidal response.



The value of V_0 depends on the details of the 1T/1MTJ  in the embedded MRAM structure <cit.> and the transistor characteristics. The conductance, G_0 of the MTJ is chosen to match the MTJ switching characteristics to the transistors in the ^Wp-bit so that the overall transfer characteristics is centered at zero as shown in Fig. <ref>e. To do that, an input voltage of V_i=0V is applied at the input of T1 and T2 transistors turning both of them ON (| V_GS| = 0.4V) and G_0 is swept to observe the outputs. The G_0 value for which V^+_OUT=V^-_OUT=0V is the value chosen to be the MTJ conductance. For minimum sized 14nm HP-FinFET transistors models with V_DD=0.8V, 1/G_0≈ 62 kΩ  and it seems reasonable considering the RA-products of modern MTJs <cit.>.

Eqs. <ref>b is implemented by the weighted synapse portion of Fig. <ref>a , which is a capacitive voltage adder just like those used in neuMOS devices <cit.>. We can write

    V_i= V_bias,i C_b,i + ∑_jV_out,j C_ij/C_g+C_z,i+C_b,i + ∑_jC_ij


Note that the capacitive voltage divider typically attenuates the voltage V_i at its output, and the inverter scales it up to V_in,i as shown in Fig. <ref>c, the two being related approximately by 

    V_in,i≈V_DD/2tanhV_i/ν_0




    ≈V_DD/2 ν_0 V_i   if   V_i≪ν_0




where ν_0 is a parameter characteristic of the inverter. Eqs. <ref>a,b can be mapped onto the PSL Eqs. <ref>a,b by defining


    m_i = V_out,i/V_DD/2,    I_i = V_in,i/V_0


    C_b,i = b_i C_0   C_z,i = z_i C_0


    h_i = b_iV_bias,i/V_DD/2,   J_ij = C_ij/C_0


    I_0 = (V_DD/2ν_0)(V_DD/2V_0)/(C_g/C_0)+z_i+b_i + ∑_jJ_ij




C_g is the intrinsic gate capacitance of the neuMOS inverter. The significance of C_0 is that we assume the input is composed of many identical capacitors C_0, and that the weights J_ij have been designed to have integer values such that C_ij can be implemented by connecting J_ij elementary capacitors in parallel. The other coefficients z_i, b_i are also integers. We adjust the number b_i of bias capacitors to facilitate external biasing and the number z_i of grounded capacitors to make z_i+b_i + ∑_jJ_ij = K a constant, so that I_0 is independent of index i:

    I_0 = (V_DD/2ν_0)(V_DD/2V_0)/(C_g/C_0)+K


Note that K is usually a fairly large number equal to the sum of all the weights, and to implement an I_0∼ 1 it is important to keep the factor (V_DD/2ν_0)(V_DD/2V_0) to be much greater than 1. This is the reason for using an inverter between the capacitive voltage adder and the p-bit. Our model neglects any leakage resistances associated with the capacitive weights. Modern transistors with thin oxides can have gate leakage currents ∼1nA, with RC ∼μs-ms. This should not affect the weighting, since the examples presented here operate at sub-ns time scales. For slower neurons, it may be advisable to use thicker oxides for the capacitive weights to ensure lower leakage.

Fig. <ref>b shows the icon we use to represent our building block which we call a weighted p-bit. The input consists of three types of inputs designated S, D and Q having capacitances C_0, 2  C_0 and 4  C_0. Combinations of these are used to implement different weights 
J_ij and different bias h_i. Each block has two outputs V_OUT^+, V_OUT^-. The choice of output depends on the sign of the corresponding J_ij. Similarly different signs of h_i are implemented by choosing V_bias,i to be +V_DD/2 or -V_DD/2.



§ INVERTIBLE FULL ADDER

In PSL, any given truth table can be implemented using Eq. <ref> by choosing an appropriate [J] and [h] matrices <cit.>. Here we show how those [J] and [h] are mapped onto physical hardware using our proposed building block using only transistors, resistors and capacitances. 





A Full Adder can be implemented in PSL using the [J] matrix shown in Fig. <ref>. In this paper, we improve the 14 p-bit implementation of the invertible Full Adder (FA) in Ref.<cit.> and implement the same functionality using 5 p-bits. This is achieved by first noting that the first half  of the FA truth table is complementary to the second half for the FA (Fig. <ref>a inset). The first 4 lines in the truth table is turned into an orthonormal set by a Gram-Schmidt process and a [J] matrix is obtained using Eq.12 in Ref.<cit.> which is finally rounded to integer values, with diagonal entries replaced by zeros. This [J] defines the interconnection between the 5 ^Wp-bits of the Full Adder in hardware. Each row of the [J] matrix are realized in terms of capacitive coupling to the gate of the associated terminal.





To ensure a uniform I_0 is applied to each p-bit (Eq. <ref>), the same weighting factor K  needs to be used for all ^Wp-bits.  To apply a given I_0, we first find  max(b_i+∑ J_ij) for any given [J], and then ground z_i=M-b_i+ ∑ J_ij (z_i ≥ 0, z_i ∈ N) unit capacitances for all terminals where M is a number that can be used to control I_0, a larger M causing a smaller I_0. Fig. <ref>b shows explicit connections made to one of the inputs “A” and Fig. <ref>c shows the subcircuit  of the Full Adder with C_i, B, A as inputs, S, C_0 as the outputs, and h_Ci, h_B, h_A, h_S, h_Co as the clamping pins.


Fig. <ref> shows the operation of a Full Adder in the usual forward mode with C_i, B, A clamped to values (0,1,1) which forces the S and C_0 to (0,1) according to the truth table. In the invertible mode S and C_0 are clamped to (0,1) and the circuit stochastically searches consistent combinations of C_i, B, A to satisfy the truth table: {C_i, B, A } ={{0,1,1},{1,0,1},{1,1,0}}. Fig. <ref> shows steady state (t = 1 μ s) histogram plots of the Full Adder operation in direct and inverted mode side by side with results from the PSL behavioral model.

The good agreement between the ideal PSL behavioral model and the coupled SPICE simulation that solves PTM-based transistors models with stochastic LLG validates the hardware mapping of the ideal p-bit equations with the weighted p-bits. 




§ 3SUM PROBLEM



3SUM is a decision problem in complexity theory that asks whether three elements of a given set can sum up to zero.  A variant of the problem is when the set of three numbers have to add up to a given constant number. This problem has a polynomial time solution and is not in NP.  In this section, we show how the invertibility feature of the Full Adders can be utilized to design a hardware 3SUM solver, and in the next section, we show how the 3SUM hardware can be modified to design a general solver for the NP-complete Subset Sum Problem. 





The invertibility property of the Full Adders ensure that given the sum, it can provide the possible input combinations for that sum as shown in Fig.<ref>a. So an n-bit 3 number adder circuit implemented in PSL can essentially provide solution sets for the 3SUM problem when the sum is clamped to a given value.

Fig. <ref>a shows the circuit constructed out of Full Adders to solve a 4-bit 3SUM problem. Each of the Full Adders in the circuit are the 5 p-bit invertible adders that were shown in Fig. <ref>. The first row of adders adds the two 4-bit numbers A and B, and feeds its output X, to the next row of adders which adds X and C to give the sum S=C+X=C+B+A.  Because p-circuits are invertible, if we clamp the sum S, the circuit naturally explores through all possible sets and multisets of the set of all integers from 0 to 2^4-1 that add up to S. The given set for the problem could be implemented through clamping certain bits of A,B and C or externally circuitry could be used to detect only the results that belong to the given set. Fig. <ref>b shows the how A,B,C is fluctuating between values that satisfy the clamped sum 15.




§ SUBSET-SUM PROBLEM (SSP)
 

In this section, we show how the hardware circuit that was designed for 3SUM problem could be modified to solve a small instance of  subset-sum problem (SSP) <cit.> which is believed to be a fundamentally difficult  problem in computer science (NP-complete). The SSP asks, given a set G with a finite number of positive numbers, if there is a subset S' such that S' ⊆ G whose elements sum to a specified target. For example, Fig. <ref> shows a circuit that is programmed to choose a set, G={1,2,4} and a target that is defined by 4-bits. In the 3SUM circuit the input bits (A, B, C) were left “floating”,  here, the inputs are constrained to a given number (1,2,4) by clamping the remaining bits of an input. For example, the inputs A_1 and A_0 are clamped to zero to make A either 4 or 0. Under these conditions, clamping the output to a specified target makes the circuit search for a consistent input combination to find a subset that satisfies the clamped target. Fig. <ref>c shows three example targets where the inputs get correlated to satisfy the clamped sum. The invertibility feature that is utilized to solve the SSP in this hardware is similar to those discussed in the context of memcomputing <cit.>, however the physical mechanisms are completely different.

One striking difference in the design of the SSP we considered, compared to the 3SUM hardware is the direction of information. In 3SUM the connections  were from the first layer of  Full Adders to the second, as in normal addition (Fig. <ref>a). In the SSP, we observed that reversing these connections from the second layer of adder to the first layer drastically improves the accuracy of the solution (Fig. <ref>a). A similar observation regarding the directional flow of information for another inverse problem using p-circuits (integer factorization) was made in <cit.>.  Here we have limited the discussion to a small instance of the SSP which would in general require more layers of Full Adders in both vertical and horizontal directions to account for more numbers of elements in G and their size.  The purpose of this example is to illustrate how invertibility can be combined with standard digital VLSI design to construct any general “cost function” for hard problems of computer science in an asynchronously running hardware platform without any external clocking.





§ CONCLUSION

In this paper we have proposed a compact building-block for Probabilistic Spin Logic (PSL) combining a recently proposed Embedded MRAM-based p-bit, with an integrated capacitive network that can be implemented using Floating Gate MOS (FGMOS) transistors similar to the neuMOS concept. We have shown by extensive SPICE simulations that the results of the hardware model for the weighted p-bit agree well with the behavioral equations of PSL. Having dedicated MTJ based hardware stochastic neurons could help minimize the footprint and consume lower power for applications as also indicated by ref.<cit.>. Even though an FGMOS-based capacitive network for performing the voltage addition seems like a natural option, we note that the device equations for any capacitance [C_ij] or conductance network [G_ij] would have been essentially the same. Moreover, our discussion was only about static weights, but an FPGA-like reconfigurable weighting scheme can also be employed either by using transistor-based gates or by additional multiplexing circuitry to perform online learning or to redesign p-circuit connectivity. Finally, using the basic building block we have shown how a small instance of the NP-complete Subset Sum Problem hardware solver can be designed using the unique invertibility feature of p-circuits. 



§ ACKNOWLEDGMENT

This work was supported in part by the Center for Probabilistic Spin Logic for Low-Energy Boolean and Non-Boolean Computing  (CAPSL), one of the Nanoelectronic Computing Research (nCORE) Centers as task 2759.005, a Semiconductor Research Corporation (SRC) program sponsored by the NSF through ECCS 1739635.









12
fxundefined [1]
 ifx#1

fnum [1]
 #1firstoftwo
 secondoftwo
 
fx [1]
 #1firstoftwo
 secondoftwo
 





noop [0]secondoftwo

ref[1]@startlink#1@href
href[1]#1@endlink
anitize@url [0]`
12`$12`&12`#12`1̂2`_12`%12
startlink[1]
endlink[0]

rl [1]href #1












@bib@innerbibempty


[Sutton et al.(2017)Sutton,
  Camsari, Behin-Aein, and Datta]sutton2017intrinsic
    author author B. Sutton, author K. Y. Camsari,
  author B. Behin-Aein,  and  author S. Datta, https://doi.org/10.1038/srep44370 journal journal Scientific Reports volume 7 (year 2017)NoStop

[Behin-Aein et al.(2016)Behin-Aein, Diep, and Datta]behin2016building
  author author B. Behin-Aein, author V. Diep,   and author S. Datta, http://dx.doi.org/10.1038/srep29893 journal journal Scientific reports volume 6 (year 2016)NoStop

[Shim et al.(2017)Shim,
  Jaiswal, and Roy]shim2017
  author author Y. Shim, author A. Jaiswal,   and author K. Roy, 10.1063/1.4983636 journal journal
  Journal of Applied Physics volume 121, pages 193902 (year 2017), http://arxiv.org/abs/http://dx.doi.org/10.1063/1.4983636
  http://dx.doi.org/10.1063/1.4983636 NoStop

[Camsari et al.(2017a)Camsari, Faria,
  Sutton, and Datta]camsari2017stochastic
  author author K. Y. Camsari, author R. Faria,
  author B. M. Sutton,  and  author S. Datta, 10.1103/PhysRevX.7.031014 journal journal Phys. Rev. X volume 7, pages
  031014 (year 2017a)NoStop

[Zand et al.(2017)Zand,
  Camsari, Ahmed, Pyle,
  Kim, Datta, and DeMara]zand2017r
  author author R. Zand, author K. Y. Camsari,
  author I. Ahmed, author S. D. Pyle, author
  C. H. Kim, author S. Datta,  and author R. F.  DeMara, @noop  journal journal arXiv preprint arXiv:1710.00249  (year
  2017)NoStop

[Lin et al.(2009)Lin,
  Kang, Wang, Lee,
  Zhu, Chen, Li, Hsu, Kao, Liu et al.]lin200945nm
  author author C. Lin, author S. Kang, author Y. Wang, author
  K. Lee, author X. Zhu, author W. Chen, author X. Li, author W. Hsu, author
  Y. Kao, author M. Liu,  et al.,  https://doi.org/10.1109/IEDM.2009.5424368 booktitle
  Electron Devices Meeting (IEDM), 2009 IEEE International (organization IEEE, year 2009) pp. pages
  1–4NoStop

[Camsari et al.(2017b)Camsari, Salahuddin, and Datta]camsari2017implementing
  author author K. Y. Camsari, author S. Salahuddin,
   and author S. Datta,  @noop  journal journal IEEE Electron
  Device Letters volume 38, pages 1767
  (year 2017b)NoStop

[Shibata and Ohmi(1992)]ohmi1992neumos
  author author T. Shibata and author T. Ohmi,  @noop  journal journal IEEE Transactions
  on Electron devices volume 39, pages
  1444 (year 1992)NoStop

[Mizrahi(2018)]mizrahi2018neural
  author author A. Mizrahi, author T. Hirtzlin, author A. Fukushima, author K. Hitoshi, author Y. Shinji, author J. Grollier and author D. Querlioz, @noop  title Neural-like computing with populations of superparamagnetic basis functions publisher Nature communications,volume 9, pages1533  (year2018)NoStop

[Nakamura et al.(2015)Nakamura, Shimada, Matsuda, and  Kimura]nakamura2015neuron
  author author N. Nakamura, author K. Shimada,
  author T. Matsuda,  and  author M. Kimura,   @noop  booktitle Future of Electron Devices,
  Kansai (IMFEDK), 2015 IEEE International Meeting for (organization IEEE, year 2015) pp. pages
  90–91NoStop

[Cormen(2009)]cormen2009introduction
  author author T. H. Cormen, @noop  title Introduction to
  algorithms (publisher MIT press, year
  2009)NoStop 

[Traversa and Di Ventra(2017)]traversa2017polynomial
  author author F. L. Traversa and author M. Di Ventra, https://doi.org/10.1063/1.4975761 journal journal Chaos: An Interdisciplinary Journal of
  Nonlinear Science volume 27, pages
  023107 (year 2017)NoStop

  
  















 