System, method, and computer-readable medium for high throughput pseudo-random number generation

Patent metadata

Field	Value
Publication number	US-9977652-B2
Application number	US-201615091925-A
Country	US
Kind code	B2
Filing date	Apr 6, 2016
Priority date	Apr 14, 2015
Publication date	May 22, 2018
Grant date	May 22, 2018

Abstract

Disclosed embodiments include systems, methods, and computer-readable media for generating pseudo-random numbers. Disclosed embodiments may receive, by the at least one processor, range data indicating a range of numbers. Disclosed embodiments may generate, based on the range data and by the at least one processor, a digitized finite state machine configured to produce pseudo-random output within the range of numbers. Further, disclosed embodiments may provide, by the at least one processor to a specialized pattern-matching device, programmable instructions to implement the digitized finite state machine on the specialized pattern-matching device. Disclosed embodiments may transmit, by the at least one processor to the specialized pattern-matching device, a pseudo-random bit stream for processing by the digitized finite state machine. Disclosed embodiments may receive, by the at least one processor from the specialized pattern-matching device, pseudo-random output from the digitized finite state machine.

First claim

What is claimed is:

1. A method for generating pseudo-random numbers, comprising:
receiving, by at least one processor, range data indicating a range of numbers;
generating, based on the range data and by the at least one processor, a digitized finite state machine configured to produce pseudo-random output within the range of numbers;
providing, by the at least one processor to a specialized pattern-matching device, programmable instructions to implement the digitized finite state machine on the specialized pattern-matching device;
generating, by the at least one processor, a pseudo-random bit stream;
transmitting, by the at least one processor to the specialized pattern-matching device, the pseudo-random bit stream for processing by the digitized finite state machine; and
receiving, by the at least one processor from the specialized pattern-matching device, pseudo-random output from the digitized finite state machine based on the pseudo-random bit stream input to the digitized finite state machine.

2. The method of claim 1 , wherein the specialized pattern-matching device is an Automata Processor PCIe board.

3. The method of claim 1 , wherein the digitized finite state machine includes a number of states corresponding to the range of numbers.

4. The method of claim 1 , further comprising:
receiving, by the at least one processor, weight data indicating a distribution for the range of numbers;
wherein the digitized finite state machine includes probabilistic transitions corresponding to the distribution for the range of numbers.

5. The method of claim 4 , wherein
the weight data indicates that the distribution should be uniform; and
the probabilistic transitions each have an equal weight, based on the weight data indicating that the distribution should be uniform.

6. The method of claim 1 , wherein the digitized finite state machine is formed from multiple Markov chains.

7. A non-transitory computer-readable storage medium for generating pseudo-random numbers, the computer-readable storage medium including instructions that when executed by at least one processor, cause the at least one processor to:
receive, by the at least one processor, range data indicating a range of numbers;
generate, based on the range data and by the at least one processor, a digitized finite state machine configured to produce pseudo-random output within the range of numbers;
provide, by the at least one processor to a specialized pattern-matching device, programmable instructions to implement the digitized finite state machine on the specialized pattern-matching device;
generate, by the at least one processor, a pseudo-random bit stream;
transmit, by the at least one processor to the specialized pattern-matching device, the pseudo-random bit stream for processing by the digitized finite state machine; and
receive, by the at least one processor from the specialized pattern-matching device, pseudo-random output from the digitized finite state machine based on the pseudo-random bit stream input to the digitized finite state machine.

8. The computer-readable storage medium of claim 7 , wherein the specialized pattern-matching device is an Automata Processor PCIe board.

9. The computer-readable storage medium of claim 7 , wherein the digitized finite state machine includes a number of states corresponding to the range of numbers.

10. The computer-readable storage medium of claim 7 , wherein the instructions further configure the at least one processor to:
receive, by the at least one processor, weight data indicating a distribution for the range of numbers;
wherein the digitized finite state machine includes probabilistic transitions corresponding to the distribution for the range of numbers.

11. The computer-readable storage medium of claim 10 , wherein
the weight data indicates that the distribution should be uniform; and
the probabilistic transitions each have an equal weight, based on the weight data indicating that the distribution should be uniform.

12. The computer-readable storage medium of claim 7 , wherein the digitized finite state machine is formed from multiple Markov chains.

13. A computing apparatus for generating pseudo-random numbers, the computing apparatus comprising:
at least one processor; and
a memory storing instructions that, when executed by the at least one processor, cause the at least one processor to:
receive, by the at least one processor, range data indicating a range of numbers;
generate, based on the range data and by the at least one processor, a digitized finite state machine configured to produce pseudo-random output within the range of numbers;
provide, by the at least one processor to a specialized pattern-matching device, programmable instructions to implement the digitized finite state machine on the specialized pattern-matching device;
generate, by the at least one processor, a pseudo-random bit stream;
transmit, by the at least one processor to the specialized pattern-matching device, the pseudo-random bit stream for processing by the digitized finite state machine; and
receive, by the at least one processor from the specialized pattern-matching device, pseudo-random output from the digitized finite state machine based on the pseudo-random bit stream input to the digitized finite state machine.

14. The computing apparatus of claim 13 , wherein the specialized pattern-matching device is an Automata Processor PCIe board.

15. The computing apparatus of claim 13 , wherein the digitized finite state machine includes a number of states corresponding to the range of numbers.

16. The computing apparatus of claim 13 , wherein the instructions further configure the apparatus to:
receive, by the at least one processor, weight data indicating a distribution for the range of numbers;
wherein the digitized finite state machine includes probabilistic transitions corresponding to the distribution for the range of numbers.

17. The computing apparatus of claim 16 , wherein
the weight data indicates that the distribution should be uniform; and
the probabilistic transitions each have an equal weight, based on the weight data indicating that the distribution should be uniform.

18. The computing apparatus of claim 13 , wherein the digitized finite state machine is formed from multiple Markov chains.

Assignees

• Univ Virginia Patent Foundation

Inventors

• Wadden John Pierson
• BRUNELLE Nathan James

Classifications

• G06F2207/583

  Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs · CPC title

• G06F7/584 Primary

  using finite field arithmetic, e.g. using a linear feedback shift register · CPC title

• G06F7/582

  Pseudo-random number generators · CPC title