Parallel computing using stochastic circuits and deterministic shuffling networks

Patent metadata

Field	Value
Publication number	US-11018689-B2
Application number	US-201816165713-A
Country	US
Kind code	B2
Filing date	Oct 19, 2018
Priority date	Oct 19, 2017
Publication date	May 25, 2021
Grant date	May 25, 2021

Abstract

In some examples, a device includes shuffling circuitry configured to receive an input unary bit stream and generate a shuffled bit stream by selecting n-tuple combinations of bits of the input unary bit stream. The device also includes stochastic logic circuitry having a plurality of stochastic computational units configured to perform operations on the shuffled bit stream in parallel to produce an output unary bit stream, each of the stochastic computational units operating on a different one of the n-tuple combinations of the bits.

First claim

The invention claimed is:

1. A device comprising:
shuffling circuitry configured to receive an input unary bit stream and generate a shuffled bit stream by selecting n-tuple combinations of bits of the input unary bit stream, wherein the input unary bit stream comprises a deterministic bit stream that deterministically encodes a numerical value based on a proportion of data bits in the deterministic bit stream that are high relative to a total number of data bits in the deterministic bit stream; and
stochastic logic circuitry having a plurality of stochastic computational circuits configured to perform operations on the shuffled bit stream in parallel by operating on the deterministic bit stream to produce an output unary bit stream, each of the stochastic computational circuits operating on a different one of the n-tuple combinations of the bits.

2. The device of claim 1 , wherein the shuffling circuitry is configured to operate according to a sweeping pattern defined with respect to a matrix of bits to select the n-tuple combinations of bits, wherein each dimension of the matrix corresponds to bit positions of the input unary bit stream, and wherein the shuffling circuitry is configured to select the n-tuple combinations to draw exactly one combination per each layer of the matrix.

3. The device of claim 2 , wherein the shuffling circuitry is configured to select the n-tuple combinations of bits by selecting a subset of unique n-tuple combinations of bits of the input unary bit stream.

4. The device of claim 1 , further comprising:
encoder circuitry configured to convert a first portion of an input binary number to the input unary bit stream,
wherein the shuffling circuitry is configured to generate, from the input unary bit stream, at least two shuffled bit streams, and
wherein the stochastic logic circuitry is configured to perform operations on the at least two shuffled bit streams to produce at least two output unary bit streams;

decoder circuitry configured to convert the at least two output unary bit streams to at least two output binary numbers; and
a first multiplexer configured to select one output binary number of the at least two output binary numbers based on a second portion of the input binary number.

5. The device of claim 4 , further comprising:
a second multiplexer configured to select an offset value based on the second portion of the input binary number; and
an adder configured to add the selected output binary number to the selected offset value.

6. The device of claim 4 , wherein each of the at least two output unary bit streams represents a result of a different computational operation.

7. The device of claim 4 ,
wherein the first portion of the input binary number comprises M least significant bits of the input binary number, and
wherein the second portion of the input binary number comprises (N minus M) most significant bits of the input binary number.

8. The device of claim 1 , further comprising decoding circuitry configured to:
receive the output unary bit stream; and
convert the output unary bit stream to an output binary number or an analog output voltage.

9. The device of claim 1 , wherein the plurality of stochastic computational circuits comprises one or more of an AND logic gate, a MUX logic gate, an OR logic gate, an XOR logic gate, a NOR logic gate, a NAND logic gate, a XNOR logic gate, an INV logic gate, or a lookup table.

10. The device of claim 1 , wherein the device comprises one or more of a sensor, a field-programmable gate array, an application-specific integrated circuit, or an embedded system.

11. The device of claim 1 , wherein the n-tuple combinations of bits comprises a subset of unique pair-wise combinations of bits of the input unary bit stream.

12. The device of claim 1 , further comprising edge-coding circuitry configured to convert the input unary bit stream to an edge-coded bit stream, and wherein the shuffling circuitry is configured to generate the shuffled bit stream based on the edge-coded bit stream.

13. A method comprising:
receiving, with an electronic device, an input unary bit stream, wherein the input unary bit stream comprises a deterministic bit stream that deterministically encodes a numerical value based on a proportion of data bits in the deterministic bit stream that are high relative to a total number of data bits in the deterministic bit stream;
generating, from the input unary bit stream, a shuffled bit stream by selecting n-tuple combinations of bits of the input unary bit stream; and
processing the n-tuple combinations of bits in parallel with a plurality of stochastic computational circuits by operating on the deterministic bit stream to produce an output unary bit stream, each of the stochastic computational circuits operating on a different one of the n-tuple combinations of the bits.

14. The method of claim 13 , wherein generating the shuffled bit stream comprises operating according to a layered sweeping pattern defined with respect to a matrix of bits to select the n-tuple combinations of bits, wherein each dimension of the matrix corresponds to bit positions of the input unary bit stream, and wherein the n-tuple combinations is selected to draw exactly one combination per each dimension of the matrix.

15. The method of claim 13 , wherein selecting the n-tuple combinations of bits comprises selecting a subset of unique n-tuple combinations of bits of the input unary bit stream.

16. The method of claim 13 , further comprising:
converting a first portion of an input binary number to the input unary bit stream;
generating, from the input unary bit stream, at least two shuffled bit streams based on the input unary bit stream;
processing the at least two shuffled bit streams to produce at least two output unary bit streams;
converting the at least two output unary bit streams to at least two output binary numbers; and
selecting one output binary number of the at least two output binary numbers based on a second portion of the input binary number.

17. The method of claim 16 , further comprising:
selecting an offset value based on the second portion of the input binary number; and
adding the selected output binary number to the selected offset value.

18. A method comprising:
assembling stochastic logic circuitry having a plurality of stochastic computational circuits configured to perform operations on an input bit stream in parallel to produce an output bit stream,
wherein each of the stochastic computational circuits is configured to operate on a different one of n-tuple combinations of the bits selected from the input stream,
wherein the stochastic computational circuits are configured to perform operations on the input bit stream to produce the output bit stream by approximating a mathematical function, and
wherein assembling the stochastic logic circuitry is based on selection methodology by selecting a subset of a plurality of Bernstein basis functions and synthesizing the stochastic computational circuits using global optimization or genetic algorithms to fit the mathematical function.

19. A device comprising:
encoder circuitry configured to convert a first portion of an input binary number to an input unary bit stream;
shuffling circuitry configured to receive the input unary bit stream and generate at least two shuffled bit streams by selecting n-tuple combinations of bits of the input unary bit stream;
stochastic logic circuitry having a plurality of stochastic computational circuits configured to perform operations

Assignees

• Univ Minnesota

Inventors

• Mohajer Soheil
• Wang Zhiheng
• Bazargan Kiarash
• Riedel Marcus
• Lilja David J
• Faraji Sayed Abdolrasoul

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F7/58 Primary

  Random or pseudo-random number generators · CPC title

• G06F7/70

  using stochastic pulse trains, i.e. randomly occurring pulses the average pulse rates of which represent numbers {(conversion of analogue signals into stochastic pulse trains and vice versa H03M1/04)} · CPC title

• G06N3/126

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title

• H03M7/26 Primary

  Conversion to or from stochastic codes · CPC title