Stochastic Implementation and Analysis of Dynamical Systems Similar to the Logistic Map

Abstract:

Stochastic computing (SC) is a digital computation approach that operates on random bit streams to perform complex tasks with much smaller hardware footprints compared with conventional binary radix approaches. SC works based on the assumption that input bit streams are independent random sequences of 1s and 0s. Previous SC efforts have avoided implementing functions that have feedback, because doing so has the potential for creating highly correlated inputs. We propose a number of solutions to overcome the challenges of implementing feedback in stochastic logic. We use a family of dynamical system functions that are similar to the well-known logistic map x→µx(1−x)as case studies. We show that complex behaviors, such as period doubling and chaos, do indeed occur in digital logic with only a few gates operating on a few 0s and 1s. Our energy consumption is between 21% and 31% of the conventional binary approach. In order to verify our design methodology, we have measured the mean switching rate between the basins of attraction of two coexisting fixed points and the peak width of the steady-state distribution of the output using a logistic-map-like function as an example. Theoretical results match well with our numerical experiments. The proposed architecture of this paper analysis the logic size, area and power consumption using Xilinx 14.2.

Existing System:

SC provides several desired features compared with conventional binary: 1) it has a significantly smaller footprint area that can help with massive parallelism (e.g., compare the AND gate in Fig. 1 with an 8-bit conventional multiplier in terms of the number of gates); 2) it can handle noise much better than conventional logic; and 3) it provides designers with high flexibility in choosing the resolution at which computations are performed, with almost no change in the hardware. As we increase the bit stream length, we increase the resolution and decrease random variance in the output stream. Hence, we can use the same simple hardware to perform operations with different resolutions, trading OFF delay/power with accuracy. SC has three major disadvantages compared with conventional binary arithmetic, though the following holds.

Figure 1: Stochastic multiplication.

Disadvantages:

  • Accuracy is low

Proposed System:

Logistic Map:

The logistic map is a prototypical example in dynamical systems and shows how a simple iterated mapping can exhibit very complex behavior. In fact, experts still use it to study the statistical properties of dynamical systems, such as the densities of states and behavior under random perturbations. The reason for its popularity is that the logistic map is a representative for a larger class of maps that exhibit period doubling and chaotic behavior. For example, the function shown in Fig. 2(e), which unlike the logistic map is not symmetric, has a period-4 cycle similar to that of the logistic map with μ between 3.44949 and 3.54409 (approximately). Traditional methods of analyzing such dynamical systems require large number of experiments with random seeds to find the statistical distributions of points of convergence. As a result, parallel simulation of these systems in hardware would be beneficial. The examples of logistic-like functions are shown in Fig. 2(b) and (e).

Figure 2: Two functions with cyclic periods. (a) Function f(x)uses six instances ofxand has a period-2 cycle. (d) Functiong(x)uses eight instances ofxand has a period-4 cycle. (b) and (e) Functions and their intersections with y=xare plotted. (c) and (f) Second-iterate map f2(x)≡f(f(x))and fourth-iterate mapg 4(x)≡g2(g2(x))and their intersections withy=xare shown. (c) Two attractorsx1andx2for the second-iterate map of f, along with the derivatives of f2 at those points (denoted byλ1andλ2)

Core Logistic-Map-Like Stochastic Logic:

In this section, we ignore input correlations and feedback and focus only on the “core” stochastic logic that implements functions, assuming that the input bitstreams are ideal, uncorrelated inputs. Section III will look at the big picture, including interfacing to the core logic. In this section, we will show the examples of functions similar to the logistic map and discuss how they can be implemented using digital stochastic circuits. As mentioned in Section I, digital 1-bit values in a stochastic bitstream can be interpreted as real numbers when observed over a long period of time. As a result, we can go back and forth between the real values of x and its digital, single-bit slices in time when analyzing circuits.

Handling feedback in circuits:

A key assumption for a combinational stochastic logic circuit to work is that the inputs are independent stochastic streams with no correlations. As shown in Fig. 1, a two-input AND gate can implement multiplication. Using this circuit, x2 can be computed only if the two input streams are generated using independent random sources, each with a probability of x. If one feeds the exact same sequence of bits to both inputs (i.e., Xi =Yi =1orXi =Yi =0 in Fig. 1), the output will be the same as the input sequence, which represents x and not x2 . This will be especially challenging in dynamical systems where function outputs are fed back to their inputs, unless we devise a method to eliminate or drastically reduce the correlation between input streams.

Breaking Dependence in Feedback: The Basic Architecture:

Our strategy for minimizing correlations between bitstreams is to use multiple independent pseudorandom generators to generate fresh input bitstreams that show little correlations. Fig. 3 shows the basic architecture that we propose To computexn+1fromxn, we first represent xnin binary, then use binary to stochastic converters to generate independent input bitstreams. SC is performed on these bitstreams, and the result is again converted into binary for a new iteration. There are two clocks governing this system: one is a very fast clock controlling the stochastic logic, which we call a “microclock or stochastic bit clock,” and the other is a slower clock which we call the real-domain clock. Onexi value is generated per real-domain clock cycle.

Figure 3: Rerandomizer-based feedback.

Sharing Random Generators:

RNGs take a nontrivial percentage of the overall area of stochastic logic. Hence, if we can reduce the number of RNGs without significantly hurting the accuracy of the computations, i.e., without adding a significant correlation between the bitstreams, we can reduce the area-delay product of the design. Assuming that consecutive values generated by the RNG have little correlation, we can share random sources and use delayed versions of their outputs to feed to more than one input in the system. This is not a valid assumption when using simple RNGs such as LFSRs with their relatively high autocorrelation. Using higher quality RNGs would result in less correlation between different copies of X, and would make sharing the random source a viable option. We use an RNG referred to as LFSR4, in which a single-state change is equivalent to four state changes of an LFSR. Specifically, let Trepresent the state transition matrix of an LFSR.

Using a Lookup Table to Fast Forward Computations:

The architecture of Fig. 3 accumulates white noise over the course of 2w micro-clock cycles to add a Gaussian noise to the Xn+1value. If the system under simulation has a high signal-to-noise ratio, only a fraction of the 2w bits are needed to model Gaussian noise through accumulation of the white noise, and the bulk of the latency is used in calculating f(Xi).Note that one of the major drawbacks of SC is its exponential latency of 2W cycles.

As shown in Fig. 4, our solution is to divide the W bits into Slower bits and Lupper bits (they could overlap for better accuracy, e.g., S+L=W+1), where S and L are the design parameters (e.g.,L=6andS=4).

Figure 4: Architecture employing shared RNGs and LUT.

Advantages:

  • Accuracy is high

Software implementation:

  • Modelsim
  • Xilinx ISE