Stochastic computation using deterministic bit streams

Patent metadata

Field	Value
Publication number	US-10063255-B2
Application number	US-201715618530-A
Country	US
Kind code	B2
Filing date	Jun 9, 2017
Priority date	Jun 9, 2016
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

In some examples, a device includes an integrated circuit comprising a computational unit configured to process at least two input bit streams that each include a sequential set of data bits or two or more sets of data bits in parallel that is deterministically encoded to represent numerical values based on a probability that any data bit in the bit stream is high. In some examples, the computational unit includes a convolver configured to generate pair-wise bit combinations of the data bits of the input bit streams. In some examples, e computational unit further includes a stochastic computational unit configured to perform a computational operation on the pair-wise bit combinations and produce an output bit stream having a set of data bits indicating a result of the computational operation based on a probability that any data bit in the set of data bits of the output bit stream is high.

First claim

The invention claimed is:

1. A device comprising:
an integrated circuit comprising a computational unit configured to process at least a first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value,
wherein the computational unit comprises:
a convolver configured to generate pair-wise bit combinations of a first bit sequence and a second bit sequence that deterministically encode the first and second numerical values, respectively, based on a proportion of the data bits in the sequence that are high relative to the data bits in the sequence that are low, wherein a subset of the plurality of pair-wise bit combinations pairs a data bit of the first bit sequence with multiple different data bits of the second bit sequence, and
a stochastic computational unit configured to:
perform a computational operation on the pair-wise bit combinations; and
produce an output bit stream having a set of data bits indicating a result of the computational operation, wherein the data bits of the output bit stream represent the result based on a probability that any data bit in the set of data bits of the output bit stream is high.

2. The device of claim 1 , wherein the convolver is configured to perform convolution on the data bits of the first bit sequence and the data bits of the second bit sequence to generate the pair-wise bit combinations by at least implementing one of:
a relatively prime method in which a length of the first bit sequence is prime relative to a length of the second bit sequence,
a rotation method in which rotated versions of the first bit sequence are paired with the second bit sequence, or
a clock division method in which the first bit sequence is paired with clock divided versions of the second bit sequence.

3. The device of claim 1 , wherein the convolver comprises a set of converter modules configured to perform convolution on the data bits of the first bit sequence and the data bits of the second bit sequence to generate the pair-wise bit combinations.

4. The device of claim 3 , wherein each converter module of the set of converter modules corresponds to one of the first set of data bits and the second set of data bits, and wherein each converter module comprises:
a counter that iterates through a maximum range of the respective set of data bits; and
a comparator that, for each iteration of the counter, compares an output of the counter with the respective set of data bits to produce a data bit of the pair-wise bit combination.

5. The device of claim 4 , wherein each converter module of the set of converter modules independently operates on the proportions without interconnection to be capable of operating on proportions of relatively prime lengths.

6. The device of claim 4 , wherein the counter of a first converter module is configured to stall at least once for every cycle through the maximum range to generate a rotated proportion of the first bit sequence.

7. The device of claim 4 , wherein the set of converter modules is chained together to form a clock division unit capable of operating on proportions of arbitrary length, such that a counter of a second converter module is configured to iterate only once for every cycle through the maximum range by a counter of a first converter module.

8. The device of claim 1 , wherein the convolver generates pair-wise bit combinations for at least a programmable threshold number of data bits from the first bit sequence and the second bit sequence in accordance with a target accuracy.

9. The device of claim 1 , wherein the computational unit further comprises a downsampler configured to reduce a length of the output bit stream to a target precision.

10. The device of claim 1 , wherein a length of the output bit stream that is a product of a length of the first bit sequence and a length of the second bit sequence.

11. A method of operating an integrated circuit comprising a computational unit, the method comprising:
receiving, at the computational unit, a first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value;
convolving, by a convolver, a first bit sequence and a second bit sequence that deterministically encode the first and second numerical values, respectively, based on a proportion of the data bits in the sequence that are high relative to the data bits in the sequence that are low, to generate pair-wise bit combinations of the first bit sequence and the second bit sequence, wherein a subset of the plurality of pair-wise bit combinations pairs a data bit of the first bit sequence with multiple different data bits of the second bit sequence; and
processing the pair-wise bit combinations with a stochastic computational unit to produce an output bit stream having a set of data bits indicating a result of a computational operation, wherein the data bits of the output bit stream represent the result based on a probability that any data bit in the set of data bits of the output bit stream is high.

12. The method of claim 11 , wherein convolving the first bit sequence and the second bit sequence comprises performing convolution on at least a threshold number of the data bits of bit sequences by at least implementing a relatively prime method in which a length of the first bit sequence is prime relative to a length of the second bit sequence.

13. The method of claim 11 , wherein convolving the first bit sequence and the second bit sequence comprises performing convolution on at least a threshold number of the data bits of bit sequences by at least implementing a rotation method in which rotated versions of the first bit sequence are paired with the second bit sequence.

14. The method of claim 11 , wherein convolving the first bit sequence and the second bit sequence comprises performing convolution on at least a threshold number of the data bits of bit sequences by at least implementing a clock division method in which the first bit sequence is paired with clock divided versions of the second bit sequence.

15. The method of claim 11 , wherein convolving the first input bit stream and the second input bit stream comprises:
iterating, by a counter, through a maximum range of the respective set of data bits; and
comparing, for each iteration of the counter, an output of the counter with the respective set of data bits to produce a data bit of the pair-wise bit combination.

16. The method of claim 11 , further comprising:
generating pair-wise bit combinations for at least a programmable threshold number of data bits from the first bit sequence and the second bit sequence in accordance with a target accuracy.

17. The method of claim 11 , further comprising reducing a length of the output bit stream to a target precision.

18. A method comprising:
convolving, by a convolver, two deterministically encoded bit streams of operands to produce convolved bit streams, wherein each encoded bit stream of the encoded bit streams represents a respective number by a fraction of ones versus zeroes, and wherein a subset of data bits of a first convolved bit stream is paired with multiple different data bits of a second convolved bit stream; and
processing the convolved bit streams with circuit structures implementing stochastic logic operations to perform an arithmetic operation on the convolved bit streams.

19. The method of claim 18 ,
wherein convolving the two deterministically encoded bit streams of operands comprises generating pair-wise bit combinations for at least a

Assignees

• Univ Minnesota

Inventors

• Riedel Marcus
• Jenson Devon

Classifications

• H03M7/26 Primary

  Conversion to or from stochastic codes · CPC title

• H04B1/16

  Circuits · CPC title