Low-discrepancy deterministic bit-stream processing using Sobol sequences

Patent metadata

Field	Value
Publication number	US-11275563-B2
Application number	US-202016906122-A
Country	US
Kind code	B2
Filing date	Jun 19, 2020
Priority date	Jun 21, 2019
Publication date	Mar 15, 2022
Grant date	Mar 15, 2022

Abstract

Example devices are described that include a computational unit configured to process first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value. The computational unit includes a bit-stream generator configured to generate bit combinations representing first and second bit sequences that 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 total data bits. The first bit sequence is generated using a first Sobol sequence source, and the second bit sequence is generated using a second Sobol sequence source different from the first Sobol sequence source. The device also includes computation logic configured to perform a computational operation on the bit combinations and produce an output bit-stream having a set of data bits indicating a result of the computational operation.

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 bit-stream generator configured to generate bit combinations representing a first bit sequence and a second bit sequence that 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 total data bits in the sequence, wherein a subset of the bit combinations pairs a data bit of the first bit sequence with multiple different data bits of the second bit sequence, wherein the first bit sequence is generated using a first Sobol sequence source, wherein the second bit sequence is generated using a second Sobol sequence source different from the first Sobol sequence source, and
computation logic configured to:
perform a computational operation on the 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 first Sobol sequence source is generated by reversing an order of output bits of a counter.

3. The device of claim 1 ,
wherein the first bit sequence is generated by comparing the first set of data bits and the first Sobol sequence source, and
wherein the second bit sequence is generated by comparing the second set of data bits and the second Sobol sequence source.

4. The device of claim 1 ,
wherein the computation logic is configured to select a length of the output bit-stream,
wherein the length of the output bit-stream is less than 2{circumflex over ( )}(2N) data bits, and
wherein N is a length of the first bit sequence.

5. A device configured to process a first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value, the device comprising:
a counter configured to generate an output;
a first Sobol sequence source configured to generate a first Sobol sequence based on the output of the counter;
a second Sobol sequence source configured to generate a second Sobol sequence based on the output of the counter, wherein the second Sobol sequence source is different from the first Sobol sequence source, and wherein the first Sobol sequence source and the second Sobol sequence source are directly driven by the counter;
a first comparator configured to generate a first bit sequence based on the first Sobol sequence and a first constant number; a second comparator configured to generate a second bit sequence based on the second Sobol sequence and a second constant number; and
computation logic configured to:
perform a computational operation on the first bit sequence and the second bit sequence; 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.

6. The device of claim 5 ,
wherein the counter is configured to generate the output by generating two or more count values in parallel,
wherein the first Sobol sequence source is configured to generate the first Sobol sequence by generating a first set of Sobol numbers in parallel based on the two or more count values generated by the counter, and
wherein the second Sobol sequence source is configured to generate the second Sobol sequence by generating a second set of Sobol numbers in parallel based on the two or more count values generated by the counter.

7. The device of claim 6 , further comprising:
a first set of comparators comprising the first comparator, wherein each comparator of the first set of comparators is configured to generate a respective bit sequence based on a respective one of the first set of Sobol numbers, and
a second set of comparators comprising the second comparator, wherein each comparator of the second set of comparators is configured to generate a respective bit sequence based on a respective one of the second set of Sobol numbers.

8. The device of claim 6 ,
wherein the first set of Sobol numbers comprises two or more consecutive values of the first Sobol sequence, and
wherein the second set of Sobol numbers comprises two or more consecutive values of the second Sobol sequence.

9. The device of claim 5 ,
wherein the computation logic is a first set of computation logic,
wherein the output bit-stream is a first sub-result bit-stream,
wherein the first constant number is a first portion of a first input binary number,
wherein the second constant number is a first portion of a second input binary number, and
wherein the device further comprises:
a third bit-stream generator configured to generate a third bit-stream based on a numerical value represented by a second portion of the first input binary number;
a fourth bit-stream generator configured to generate a fourth bit-stream based on a numerical value represented by a second portion of the second input binary number;
a second set of computation logic configured to operate on the third bit-stream and the fourth bit-stream to generate a second sub-result bit-stream; and
an accumulator configured to generate a binary result based on the first sub-result bit-stream and the second sub-result bit-stream.

10. The device of claim 9 ,
wherein the third bit-stream generator comprises a third comparator configured to generate the third bit-stream based on the first Sobol sequence and the second portion of the first input binary number, and
wherein the fourth bit-stream generator comprises a fourth comparator configured to generate the fourth bit-stream based on the second Sobol sequence and the second portion of the second input binary number.

11. The device of claim 9 ,
wherein the second portion of the first input binary number is different than the first portion of the first input binary number, and
wherein the second portion of the second input binary number is different than the first portion of the second input binary number.

12. The device of claim 9 , further comprising an adder tree configured to:
add the first and second sub-result bit-streams to generate a summed bit-stream; and
deliver the summed bit-stream to the accumulator.

13. A device configured to process a first set of data bits encoding a first numerical value and a second set of data bits encoding a second numerical value, the device comprising:
a first counter;
a second counter configured to stall based on an output of the first counter;
a first Sobol sequence source configured to generate a first Sobol sequence based on an output of the first counter;
a second Sobol sequence source configured to generate a second Sobol sequence based on an output of the second counter, wherein the second Sobol sequence source is different from the first Sobol sequence source;
a first comparator configured to generate a first bit sequence based on the first Sobol sequence and a first constant number;
a second comparator configured to generate a second bit sequence based on the second Sobol sequence and a second constant number; and
computation logic configured to:
perform a computational operation on the first bit sequence and the second bit sequence; and
produce an output bit-stream having a set

Assignees

• Univ Minnesota

Inventors

• Najafi Mohammadhassan
• Lilja David J
• Riedel Marcus
• Bazargan Kiarash
• Faraji Sayed Abdolrasoul
• Li Bingzhe

Classifications

• H03K3/84

  Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators · CPC title

• G06F7/582 Primary

  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

• H03M7/26

  Conversion to or from stochastic codes · CPC title