US-20260126956-A1 - PSEUDORANDOM NUMBER GENERATOR CIRCUIT

US20260126956A1US 20260126956 A1US20260126956 A1US 20260126956A1US-20260126956-A1

Abstract

A computing system including hardware accelerator that includes a pseudorandom number generator (PRNG) circuit. The PRNG circuit is configured to compute an initial pseudorandom bit stream. The PRNG circuit is further configured to compute a plurality of output pseudorandom bit streams as sequences of bits selected from respective initial stream bit indices within the initial pseudorandom bit stream. For each of the output pseudorandom bit streams, for each output stream bit index within that output pseudorandom bit stream, the corresponding initial stream bit index is unique, across the plurality of output pseudorandom bit streams, among values of the initial stream bit index from which the PRNG circuit obtains the bit located at that output stream bit index. The PRNG circuit is further configured to output the plurality of output pseudorandom bit streams.

Inventors

Thomas Craig Savell

Assignees

MICROSOFT TECHNOLOGY LICENSING, LLC

Dates

Publication Date: 20260507
Application Date: 20241105

Claims (20)

1 . A computing system comprising: a hardware accelerator that includes a pseudorandom number generator (PRNG) circuit configured to: compute an initial pseudorandom bit stream; compute a plurality of output pseudorandom bit streams as sequences of bits selected from respective initial stream bit indices within the initial pseudorandom bit stream, wherein, for each of the output pseudorandom bit streams, for each output stream bit index within that output pseudorandom bit stream, the corresponding initial stream bit index is unique, across the plurality of output pseudorandom bit streams, among values of the initial stream bit index from which the PRNG circuit obtains the bit located at that output stream bit index; and output the plurality of output pseudorandom bit streams.
2 . The computing system of claim 1 , wherein the PRNG circuit is configured to compute the initial pseudorandom bit stream by executing a Trivium algorithm.
3 . The computing system of claim 1 , wherein the PRNG circuit is configured to compute the initial pseudorandom bit stream using one or more linear feedback shift registers (LFSRs).
4 . The computing system of claim 1 , wherein: the PRNG circuit is configured to output the plurality of output pseudorandom bit streams to a stochastic rounding circuit included in the hardware accelerator; and the stochastic rounding circuit is configured to: based at least in part on the plurality of output pseudorandom bit streams, perform stochastic rounding on a plurality of rounding inputs to compute a respective plurality of rounding outputs; and output the rounding outputs.
5 . The computing system of claim 4 , wherein: the rounding inputs are neural network parameters included in a neural network; and the rounding outputs are quantized neural network parameters.
6 . The computing system of claim 1 , wherein the PRNG circuit is further configured to: receive a state-advance signal; compute the initial pseudorandom bit stream and the plurality of output pseudorandom bit streams in response to receiving the state-advance signal; and remain idle during each clock cycle in which the state-advance signal is not received.
7 . The computing system of claim 1 , wherein the PRNG circuit is further configured to: store a PRNG internal state of the PRNG circuit in memory; retrieve the PRNG internal state from the memory subsequently to computing the output pseudorandom bit streams; using the PRNG internal state, deterministically replay the computation of the output pseudorandom bit streams; and output the output pseudorandom bit streams computed during the deterministic replaying.
8 . The computing system of claim 1 , wherein the PRNG circuit is configured to compute the plurality of output pseudorandom bit streams in parallel.
9 . The computing system of claim 1 , further comprising one or more additional processing devices configured to: receive the plurality of output pseudorandom bit streams from the hardware accelerator; execute a stochastic search algorithm based at least in part on the output pseudorandom bit streams to obtain a stochastic search result; and output the stochastic search result.
10 . The computing system of claim 1 , further comprising one or more additional processing devices configured to: receive the plurality of output pseudorandom bit streams from the hardware accelerator; apply dithering to an input signal based at least in part on the output pseudorandom bit streams to obtain a dithered signal; and output the dithered signal.
11 . A method for use with a computing system including a hardware accelerator, the method comprising: at a pseudorandom number generator (PRNG) circuit included in the hardware accelerator: computing an initial pseudorandom bit stream; computing a plurality of output pseudorandom bit streams as sequences of bits selected from respective initial stream bit indices within the initial pseudorandom bit stream, wherein, for each of the output pseudorandom bit streams, for each output stream bit index within that output pseudorandom bit stream, the corresponding initial stream bit index is unique, across the plurality of output pseudorandom bit streams, among values of the initial stream bit index from which the PRNG circuit obtains the bit located at that output stream bit index; and outputting the plurality of output pseudorandom bit streams.
12 . The method of claim 11 , wherein the initial pseudorandom bit stream is computed by executing a Trivium algorithm.
13 . The method of claim 11 , wherein the initial pseudorandom bit stream is computed using one or more linear feedback shift registers (LFSRs) included in the PRNG circuit.
14 . The method of claim 11 , wherein: the plurality of output pseudorandom bit streams are output to a stochastic rounding circuit included in the hardware accelerator; and the method further comprises, at the stochastic rounding circuit: based at least in part on the plurality of output pseudorandom bit streams, performing stochastic rounding on a plurality of rounding inputs to compute a respective plurality of rounding outputs; and outputting the rounding outputs.
15 . The method of claim 14 , wherein: the rounding inputs are neural network parameters included in a neural network; and the rounding outputs are quantized neural network parameters.
16 . The method of claim 11 , further comprising, at the PRNG circuit: receiving a state-advance signal; computing the initial pseudorandom bit stream and the plurality of output pseudorandom bit streams in response to receiving the state-advance signal; and remaining idle during each clock cycle in which the state-advance signal is not received.
17 . The method of claim 11 , further comprising, at the PRNG circuit: storing a PRNG internal state of the PRNG circuit in memory; retrieving the PRNG internal state from the memory subsequently to computing the output pseudorandom bit streams; using the PRNG internal state, deterministically replaying the computation of the output pseudorandom bit streams; and outputting the output pseudorandom bit streams computed during the deterministic replaying.
18 . The method of claim 11 , wherein the plurality of output pseudorandom bit streams are computed in parallel at the PRNG circuit.
19 . The method of claim 11 , further comprising, at one or more additional processing devices: receiving the plurality of output pseudorandom bit streams from the hardware accelerator; executing a stochastic search algorithm based at least in part on the output pseudorandom bit streams to obtain a stochastic search result; and outputting the stochastic search result.
20 . A computing system comprising: a hardware accelerator that includes a pseudorandom number generator (PRNG) circuit configured to: compute an initial pseudorandom bit stream; compute a plurality of output pseudorandom bit streams as sequences of bits selected from respective initial stream bit indices within the initial pseudorandom bit stream, wherein, for each of the output pseudorandom bit streams, for each output stream bit index within that output pseudorandom bit stream, across the plurality of output pseudorandom bit streams, the corresponding initial stream bit index is included 2 N−n or fewer times among values of the initial stream bit index from which the PRNG circuit obtains the bit located at that output stream bit index, where N is a total number of bits included in each of the output pseudorandom bit streams and n is the output stream bit index; and output the plurality of output pseudorandom bit streams.

Description

BACKGROUND Generating truly random inputs to a computing process typically requires an analog noise source. Hardware devices used as analog noise sources may be prohibitively expensive for computing applications that use large numbers of random inputs. In addition, many applications utilize deterministic and repeatable random number sequences, e.g., for debugging failures, and analog sources are non-deterministic and non-repeatable. Accordingly, pseudorandom number generators are frequently used instead of true random number generators. A pseudorandom number generator is a process or device that deterministically computes outputs mimicking random outputs. The outputs of a pseudorandom number generator may be indistinguishable, up to some guarantee, from random outputs sampled from a specified probability distribution. The guarantee may, for example, be a number of outputs needed to predict a subsequent value of an output sequence or distinguish the pseudorandom sequence from a random sequence. The pseudorandom number generator may accordingly produce outputs that are usable in place of truly random outputs in many computing processes. SUMMARY According to one aspect of the present disclosure, a computing system is provided, including hardware accelerator that includes a pseudorandom number generator (PRNG) circuit. The PRNG circuit is configured to compute an initial pseudorandom bit stream. The PRNG circuit is further configured to compute a plurality of output pseudorandom bit streams as sequences of bits selected from respective initial stream bit indices within the initial pseudorandom bit stream. For each of the output pseudorandom bit streams, for each output stream bit index within that output pseudorandom bit stream, the corresponding initial stream bit index is unique, across the plurality of output pseudorandom bit streams, among values of the initial stream bit index from which the PRNG circuit obtains the bit located at that output stream bit index. The PRNG circuit is further configured to output the plurality of output pseudorandom bit streams. This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. Furthermore, the claimed subject matter is not limited to implementations that solve any or all disadvantages noted in any part of this disclosure. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 schematically shows a computing system including a hardware accelerator that includes a pseudorandom number generator (PRNG) circuit, according to one example embodiment. FIG. 2A schematically shows the PRNG circuit in additional detail in an example in which an initial pseudorandom bit stream is computed using a synchronous stream cipher such as a Trivium algorithm and used to generate a plurality of output pseudorandom bit streams, according to the example of FIG. 1. FIG. 2B schematically shows the PRNG circuit in additional detail in an example in which the initial pseudorandom bit stream is computed using one or more linear feedback shift registers, according to the example of FIG. 1. FIG. 2C schematically shows the PRNG circuit in additional detail in an example in which, among a plurality of output pseudorandom bit streams, repeats of initial stream bit indices are allowed at some output stream bit indices, according to the example of FIG. 1. FIG. 3 schematically shows a stochastic rounding circuit configured to receive the output pseudorandom bit streams and perform stochastic rounding, according to the example of FIG. 1. FIG. 4 schematically shows the PRNG circuit and a controller included in the hardware accelerator as the hardware accelerator progresses through a plurality of clock cycles, according to the example of FIG. 1. FIG. 5 schematically shows the computing system 1 when the PRNG circuit replays the computation of the output pseudorandom bit streams, according to the example of FIG. 1. FIG. 6 schematically shows the computing system in an example in which one or more processing devices are configured to execute a stochastic search algorithm using the output pseudorandom bit streams, according to the example of FIG. 1. FIG. 7 schematically shows the computing system in an example in which one or more processing devices are configured to perform dithering using the output pseudorandom bit streams, according to the example of FIG. 1. FIG. 8A shows a flowchart of a method for use with a computing system including a hardware accelerator that includes a PRNG circuit, according to the example of FIG. 1. FIG. 8B shows additional steps of the method of FIG. 8A that may be performed in examples in which the output pseudorandom bit streams are used in stochastic rounding. FIG. 8C shows additional steps of the method of FIG. 8A that may