Patent ID: 12248532

DETAILED DESCRIPTION

The invention can be implemented in numerous ways, including as a process; an apparatus; a system; a composition of matter; a computer program product embodied on a computer readable storage medium; and/or a processor, such as a processor configured to execute instructions stored on and/or provided by a memory coupled to the processor. In this specification, these implementations, or any other form that the invention may take, may be referred to as techniques. In general, the order of the steps of disclosed processes may be altered within the scope of the invention. Unless stated otherwise, a component such as a processor or a memory described as being configured to perform a task may be implemented as a general component that is temporarily configured to perform the task at a given time or a specific component that is manufactured to perform the task. As used herein, the term ‘processor’ refers to one or more devices, circuits, and/or processing cores configured to process data, such as computer program instructions.

A detailed description of one or more embodiments of the invention is provided below along with accompanying figures that illustrate the principles of the invention. The invention is described in connection with such embodiments, but the invention is not limited to any embodiment. The scope of the invention is limited only by the claims and the invention encompasses numerous alternatives, modifications and equivalents. Numerous specific details are set forth in the following description in order to provide a thorough understanding of the invention. These details are provided for the purpose of example and the invention may be practiced according to the claims without some or all of these specific details. For the purpose of clarity, technical material that is known in the technical fields related to the invention has not been described in detail so that the invention is not unnecessarily obscured.

Certain fields present significant challenges to obtaining solutions using standard computing architectures. Although technologies such as quantum computing architectures may be used in solving such problems, there are significant drawbacks. Standard computing methods may be limited in speed. Solutions obtained using other more recently developed computing methods may not have the desired precision. Consequently, an improved mechanism that is usable in addressing complex and/or difficult to solve problems is desired.

Techniques usable in optimization processing and/or solving complex problems are described. A system including digital oscillators and at least one programmable interconnect is described. The programmable interconnect(s) provide weights for and selectably couples at least a portion of the digital oscillators. The digital oscillators and the programmable interconnect(s) form an optimization processing unit (OPU). In some embodiments, processor(s), such as a central processing unit (CPU) and/or a graphics processing unit (GPU), are coupled to the OPU.

In some embodiments, the digital oscillators include injection locked digital oscillators. In some embodiments, an injection locked digital oscillator is configured to have two stable states. In some embodiment, the differential equation solver is configured to model real and imaginary portions of a state. The state corresponds to a phase of the injection locked digital oscillator. The digital oscillator may be configured as a differential equation solver. In some embodiments, the differential equation solver solves at least one governing differential equation for a resistance-inductance-capacitance circuit. In some embodiments, the differential equation solver may be configured to solve coupled differential equations corresponding to a satisfiability problem. The differential equation solvers may be configured for Euler's method and/or to utilize the Kuramoto model. The programmable interconnect(s) may include digital matrix multiplier(s). In some embodiments, the digital matrix multiplier sparsely connects the plurality of digital oscillators. In some embodiments, the digital matrix multiplier fully connects the plurality of digital oscillators. The connections (e.g. sparse or fully connected) may vary throughout use of the system in some embodiments. The programmable interconnect(s) may also perform other functions.

In some embodiments, a method and/or a computer a computer program product embodied in a non-transitory computer readable storage medium are described. The method includes receiving, at an OPU, data for at least a portion of an optimization problem. In some embodiments, the data may be received at the OPU from a CPU and/or GPU. The OPU includes digital oscillators and programmable interconnect(s). Thus, the OPU may be analogous to that described herein. In some embodiments, the information provided by the user may be in the form of a quadratic unconstrained binary optimization (QUBO) problem. In some embodiments, the information provided by the user may be in the form of a quadratic programming form (QP) problem. In some embodiments, the information provided by the user may be in the form of an Ising Model. In some embodiments, the information provided by the user may be in the form of a linear program (LP) problem or a satisfiability (sat) problem. In some embodiments, the information provided may be in another form.

Responses for the optimization problem are calculated in the digital oscillators. For example, data may be input to and responses sampled from each digital oscillator. In some embodiments, the digital oscillators are injection locked digital oscillators. Thus, calculating the responses may include receiving the injection lock signal at the digital oscillators. Weights are applied to the responses from the digital oscillators to provide weighted responses. This may be accomplished via the programmable interconnect(s). The weighted responses are provided as input(s) some or all of the remaining digital oscillators. The digital oscillators receiving the weighted responses may be selected via the programmable interconnect(s). This process of receiving responses from digital oscillators, weighting the responses and providing the weighted responses as input(s) to some or all of the digital oscillators may be repeated one or more times. The OPU may then provide optimized responses to the portion of the problem received.

Boolean logic (“logic”) gates, such as OR, NOR, AND and XOR gates, are usable for a variety of computations. For such gates, the output of the gate given a set of inputs to the gate is well known. For example, for an OR gate, the output of the gate is a logical “1” if at least one of the inputs to the gate is also a logical “1”. Reversible logic gates are those from which the inputs can be determined for a particular output. For example, if the output of the particular oscillator(s) are forced to specific value(s) (e.g. a logical “1” or a logical “0”), the inputs to the logic gate are forced to take on valid values for the specific value(s). In principle, reversible logic may be used in applications such as factoring in computer security applications and/or other fields.

A system for performing reversible logic is also described. The system includes digital oscillators coupled to perform a logic operation and an error correction unit coupled to the digital oscillators. Thus, the digital oscillators may be considered to form a logic gate corresponding to the logic operation. Such a system of coupled oscillators may be described by the Ising (or another) model. Solving the Ising (or the other) model for the system results in the output of particular oscillator(s) in the system mimicking the behavior of a logic gate for inputs to oscillator(s) in the system. Logic gates constructed using oscillators may be useful because such logic gates are reversible, but are also subject to errors.

Thus, the system includes the error correction unit. The error correction unit is configured to sample states of the digital oscillators, detect error(s) in the states, and tune connection coefficient(s) between the oscillators in response to detecting the error(s). In some embodiments, the error correction unit tuning the connection coefficient(s) includes the error correction unit pinning the connection coefficient(s) at a first value corresponding to a logical “1” or a second value corresponding to a logical “0”. In some embodiments, the digital oscillators are injection locked digital oscillators. Thus, in such embodiments, the digital oscillators receive injection lock signals. The injection locked digital oscillator may be configured to model a real portion of a state and an imaginary portion of the state, the state corresponding to a phase of the injection locked digital oscillator. In some embodiments, each digital oscillator is a differential equation solver selected from a Kuramoto model differential equation solver and an Euler's method differential equation solver.

FIGS.1A and1Care block diagrams depicting an embodiment of system100.FIG.1Adepicts system100including OPU110.FIG.1Bdepicts an embodiment of digital oscillator120B usable in OPU110.FIG.1Cdepicts an embodiment of digital oscillator120C usable in OPU110. System100is usable in combinatorial optimization (CO) and/or in other fields. For example, system100may be used in fields in having complex problems and/or problems which are challenging to solve using conventional architectures. For example, system100may be used in scheduling compute tasks and/or other allocation of resources. For clarity, only certain components of system100are depicted. System100includes CPU102and GPU104in addition to OPU110. Although system100is described in the context of a single OPU110, a single CPU102and a single GPU104, system100may include multiple OPUs, multiple CPUs and/or multiple GPUs. In some embodiments, CPU102and/or GPU104may be omitted. Further, in the case of multiple OPUs, all OPUs can, but need not, be configured in a manner analogous to OPU110.

CPU102may be used to carry out various functions associated with optimization processing. CPU102may read and decode instructions and offload at least some of its work to OPU110, GPU104and/or FPGAs (not shown), depending on the instructions. In some embodiments, CPU102can itself perform some of the optimization. More specifically, CPU102can be used for solving CO problems defined in a classical manner e.g. as a linear programming solution. The CO problem itself can be partitioned into a classical part and an OPU part. In one embodiment, the classical part can be solved using CPU102and the OPU part can be solved using an OPU110, GPU104and/or FPGA(s) (not shown inFIGS.1A-1C). The part of the problem that is to be partitioned between various units (e.g. CPU102, GPU104and/or OPU110) can be defined by a user through a programmable interface (not shown inFIG.1A). The user can choose to partition the workload related to solving the CO problem between CPU102, GPU104, FPGA(s), and/or OPU110. Partitioning the problem into classical versus stochastic computing parts is also programmable. Thus, the systems and techniques described herein are programmable, e.g. by the user.

OPU110includes programmable interconnect130and digital oscillators120-1,120-2through120-N (collectively digital oscillators120/generically digital oscillator120). For simplicity, OPU110is described in the context of a single programmable interconnect130. However, in some embodiments, multiple programmable interconnects are present. N digital oscillators120capable of functioning in parallel are shown. InFIG.1A, digital oscillators120are shown as the same. However, in other embodiments, digital oscillators120may differ.

Programmable interconnect130is configured to provide weights for and to selectably couple some or all of digital oscillators120. For example, results sampled from a particular digital oscillator120are weighted and provided to some or all of the remaining digital oscillators120via programmable interconnect130. In some embodiments, programmable interconnect130fully connects digital oscillators120. In such a case, each digital oscillator120is coupled with all other digital oscillators120in OPU110. In some embodiments, programmable interconnect130sparsely connects digital oscillators120. In this case, each digital oscillator120is connected with a subset of the remaining digital oscillators120. In some embodiments, the connections between digital oscillator(s)120are reconfigurable and, therefore, not fixed in hardware. In other embodiments, the digital oscillator(s)120that are coupled via programmable interconnect130are fixed. Programmable interconnect130may be or include a digital matrix multiplier. Such a digital matrix multiplier may be implemented via an FPGA, GPU, and/or an application specific integrated circuit (ASIC). Thus, programmable interconnect130may be viewed as weighting and mixing signals from digital oscillators120and providing weighted, mixed signals as inputs to one or more other digital oscillators120. In some embodiments, programmable interconnect130may perform additional functions. For example, some calculations for digital oscillators120may be offloaded to programmable interconnect130.

In some embodiments, digital oscillators120digitally model periodic (or wave) functions and/or the corresponding systems. More generally, digital oscillators120model a system governed by one or more differential equations. Stated differently, a digital oscillator120may be a differential equation solver for a periodic differential equation and/or a differential equation solver for the differential equation(s) governing particular systems. For example, a digital oscillator120may model an analog oscillator, such as an inductive-capacitive (LC) or resistive-inductive-capacitive (RLC) circuit. Such a digital oscillator120may be viewed as solving the differential equation for an LC or RLC circuit. A digital oscillator120may model Schrodinger's equation (i.e. the differential equation related to the Hamiltonian) of an electron. Thus, digital oscillator120may solve Schrodinger's (differential) equation to find the ground states of the electron. Digital oscillator120may model the portion of the Ising Hamiltonian for a spin in a system of coupled spins. Stated differently, digital oscillator120may be used to model the differential equation (i.e. the Ising Hamiltonian) for a system of coupled spins in which each spin may have a +1 state or −1 state. Thus, digital oscillator120may be used to model a particular system governed by differential equations.

Similarly, digital oscillator120may be viewed as solving differential equations that can be used to solve particular problems. As discussed above, some CO problems may be solved via digital oscillators configured to solve differential equations. Similarly, satisfiability problems, such as Boolean satisfiability problems (k-SAT problems), may be described by differential equations. A k-SAT problem has a set of Boolean variables and conditions related to the variables. The conditions relate to the values taken by subsets of the Boolean variables. Using the method proposed by Maria Ercsey-Ravasz, et al., the k-SAT problem can be described by an energy function. It has been determined that the energy function can be generalized and mapped to an Ising model. It has also been determined that this model is governed by a particular set of differential equations. Moreover, such a k-SAT problem, and the differential equations governing the problem, correspond to an optimized solution to a scheduling problem. Thus, digital oscillators120may also be used in solving differential equations to which scheduling problems have been mapped.

Digital oscillator120may employ various mechanisms including but not limited to Euler's method and the Kuramoto model to solve such differential equations. In some embodiments, digital oscillator120includes or consists of digital circuit components that are utilized at temperatures at or above zero degrees Celsius (e.g. room temperature or above). In some embodiments, digital oscillators120may include or consist of circuit components formed on silicon wafers as part of an integrated circuit. Thus, digital oscillators120include digital circuit components which are connected and configured to solve the corresponding differential equations using a mechanism such as Euler's method and/or the Kuramoto model.

The combination of digital oscillators120coupled via programmable interconnect130digitally models coupled differential equations, coupled periodic functions and/or the corresponding coupled systems. Coupled together via programmable interconnect130, digital oscillators120may be viewed as functioning substantially in parallel to digitally solve a set of coupled differential equations. For example, coupled digital oscillators120may be used to model the Ising Hamiltonian used to solve CO problems. Thus, digital oscillators120coupled via programmable interconnect130may model systems having nodes coupled in accordance with the Ising model. In some embodiments, OPU110(i.e. digital oscillators120in combination with programmable interconnect130) models a system of coupled analog oscillators, such as coupled LC circuits and/or coupled RLC circuits. Thus, OPU110may solve the differential equations governing a set of coupled LC and/or RLC circuits. In some embodiments, OPU110may solve the differential equations governing the phases of a set of coupled LC and/or RLC circuits. OPU110may be used to model Schrodinger's equations for electrons in a molecule. Electrons in such a molecule interact. Thus, digital oscillators120coupled via programmable interconnect130solve the differential equations governing the wave functions for interacting (i.e. coupled) electrons in the molecule. OPU110may, therefore, determine the ground states of the electrons in the molecule. In some embodiments, OPU110may solve the differential equations governing a k-SAT problem, or the Ising Hamiltonian to which a k-SAT problem has been mapped. Thus, digital oscillators120in conjunction with programmable interconnect130may be used to model a particular system governed by coupled differential equations. Such digital oscillators120may employ various mechanisms including but not limited to Euler's method and the Kuramoto model. Digital oscillators120are thus configured to provide, based on data input to digital oscillators120and weights provided via programmable interconnect130, responses that are probabilistic and periodic in nature. For example, the responses may be based upon the phases corresponding to digital oscillator120at the particular time the oscillator(s) are sampled.

In some embodiments, digital oscillators120are injection locked digital oscillators. Injection locked digital oscillators120may be more likely to synchronize to reach a stable state for the combination of digital oscillators120. In some embodiments, each injection locked digital oscillator120may settle in one of two states. For example, the phases of the oscillators may be considered to be 0° or 180° and may differ based upon initial conditions for the oscillator and/or the time at which the oscillator is sampled. The phases of these oscillators may be used to model equations, such as the Hamiltonian (e.g. the Ising Hamiltonian) used for some CO problems. The phases of these oscillators120may also be used to model the corresponding differential equations for the phases of oscillators used in providing a solution to the Ising Hamiltonian. In some embodiments, injection locked digital oscillators are configured by providing injection lock signals to digital oscillators120. The frequency of such injection lock signals is greater than the frequency of the corresponding digital oscillator120. In some embodiments, the injection lock signal is at 1.5 multiplied by the frequency and not more than 2.5 multiplied by the frequency of the corresponding digital oscillator120. For example, in some embodiments, the injection lock signal is at nominally twice the frequency of the corresponding digital oscillator120. Thus, injection locked digital oscillators120may synchronize to provide a stable set of states for digital oscillators120coupled via programmable interconnect130.

FIG.1Bdepicts a particular digital oscillator120B that can be utilized as one or more of digital oscillators120. In the embodiment shown, digital oscillator120B is an injection locked digital oscillator. Thus, digital oscillator120B receives an injection lock signal. In some embodiments, the injection lock signal has a frequency that is nominally twice the modeled oscillator frequency. The injection lock signal assists in syncing digital oscillators120to provide the solution to the coupled differential equations (or coupled system) being modeled. Digital oscillator120B also receives inputs ViL and ViR and provides outputs VoL and VoR. Inputs ViL and ViR correspond to weighted inputs provided by programmable interconnect130using outputs of other digital oscillators120. Outputs VoL and VoR are outputs provided by digital oscillator120B. In some embodiments, digital oscillator120B is configured to solve a differential equation governing a corresponding analog LC oscillator. Thus, in some embodiments digital oscillator120B is configured to solve the following equation or its analog:

1R⁢A⁢⁢exp⁢⁢(j⁢⁢θ)+C⁢dd⁢⁢t⁢(A⁢⁢exp⁢⁢(j⁢⁢θ))+1L⁢∫t⁢A⁢⁢exp⁢⁢(j⁢⁢θ)⁢d⁢⁢τ=(4⁢⁢I⁢/⁢π)⁢exp⁢⁢(j⁢⁢θ)+Iinj⁢exp⁡(j⁢⁢θinj).

In the above equation, A is a scale factor, C is the capacitance, R is the resistance, L is the inductance, Iinjis the amplitude of the injection locking signal, I is the current. Digital oscillator120B may thus be viewed as modeling a particular oscillating LC circuit that is coupled with other oscillators. In some embodiments, for example, digital oscillator120B may utilize Euler's method (described herein), the Kuramoto model (described herein) to solve the above differential equation and model the oscillators. In some embodiments, other differential equations may be modeled.

FIG.1Cdepicts a particular digital oscillator120C that can be used as one or more of digital oscillators120. In the embodiment shown, digital oscillator120C is an injection locked digital oscillator. Thus, digital oscillator120C receives an injection lock signal that is analogous to the injection lock signal provided for digital oscillator120B. The injection lock signal assists in syncing digital oscillators120to provide the solution to the coupled differential equations (or coupled system) being modeled. Digital oscillator120C also receives inputs ViL and ViR and provides outputs VoL and VoR. Inputs ViL and ViR correspond to weighted inputs provided by programmable interconnect130using outputs of other digital oscillators120. Outputs VoL and VoR are outputs provided by digital oscillator120C. In some embodiments, digital oscillator120C is configured to solve a differential equation governing a corresponding Ising model to which a k-SAT problem has been mapped. Thus, in some embodiments digital oscillator120C is configured to solve the following coupled differential equations or their analogs:

d⁢sid⁢t=-(∇s⁢V⁡(s,a))=-(2⁢J⁢s^+h+14⁢(s^°3-s^))d⁢amd⁢t=am⁢Km⁡(s)2=G⁡(A⁢12⁢(s^+1^)-b)2

In the above equations, the right side is in matrix/vector form, siis the ithIsing spin, amis a term multiplied by the mthconstraint, Kmis the mthconstraint, V is the energy matrix that depends upon the spins (s) and the constraint terms (a), G is a diagonal matrix including amon its diagonal (where m is the row and column of the matrix) and 0 elsewhere, Ax−b (in matrix form) corresponds to the problem matrix, si=2xi−1, ŝ°3is the s matrix with each element cubed, J and h weights that may be changed. In some embodiments, for example, digital oscillator120C may utilize Euler's method (described herein), the Kuramoto model (described herein) to solve the above differential equations and, therefore, provide an optimized solution to the k-SAT problem. In some embodiments, other differential equations may be modeled.

System100including OPU110may be utilized in solving complex problems, such as CO problems and k-SAT problems including but not limited to scheduling problems. Digital oscillators120operate in parallel. Thus, OPU110may more rapidly and efficiently provide responses to input data. Digital oscillators120may be built on silicon and/or run at temperatures well above liquid helium (e.g. above four Kelvin). In some embodiments, digital oscillators120are used at temperatures of at least zero degrees Celsius. For example, digital oscillators120may operate at or above room temperature (approximately twenty-three degrees Celsius). Consequently, OPU110may be more readily fabricated and utilized than, for example, quantum processors. Because programmable interconnect130is reconfigurable, not only can the weight(s) applied be changed, but the digital oscillators120to which the weighted responses are applied can be altered. Programmable interconnect130creates a much more versatile platform and help address a wider array of problems, as different applications tend to have different connectivity requirements. This is in stark contrast to both quantum systems which have limited connectivity and alternative digital annealers which aim for full all-all connectivity and as a result have limited size. In addition, the communication between OPU110and remaining components of system100, such as CPU102and/or GPU104may be facilitated and subject to reduced latency than other mechanisms such as quantum computing. Further, use of digital oscillators120allows for increased precision in the responses provided by OPU110over analog systems. Moreover, system100and OPU110may provide improved solutions to problems, such as the k-SAT problem in a shorter amount of time. Thus, jobs such as scheduling of compute tasks may be performed rapidly (e.g. in real-time or close to real-time) while providing an improved allocation of resources. Thus performance of system100may be improved and solutions to complex problems facilitated.

FIGS.2A-2Bdepict an embodiment of a portion of system200usable in solving problems such as those in CO and/or other fields. System200is analogous to system100and includes OPU210. OPU210is analogous to OPU110and includes programmable interconnect230and digital oscillators220-1through220-N (collectively digital oscillators220/generically digital oscillator220). Programmable interconnect230is analogous to programmable interconnect130. Digital oscillators220are analogous to digital oscillators120,120B and/or120C. Digital oscillators220thus model a set of coupled differential equations.

FIG.2Adepicts the coupling between digital oscillator220-1and remaining digital oscillators220provided via programmable interconnect230. Thus,FIG.2Aillustrates a portion of programmable interconnect230. Each digital oscillator220-2,220-3through220-N has a corresponding multiplier234-1,236-1through238-1. The multipliers234-1,236-1through238-1multiply the response of the corresponding digital oscillator220-2,220-3through220-N by the corresponding weight J12, J13through J1N. Multipliers234-1,236-1through238-1output the weighted responses from digital oscillators220-2,220-3through220-N. In some embodiments, one or more of the weights J1jmay be zero if digital oscillator220-1is desired to be decoupled from the jthdigital oscillator. Adder232-1sums the weighted responses and provides the weighted responses to digital oscillator220-1.

Similarly,FIG.2Bdepicts the coupling between digital oscillator220-2and remaining digital oscillators220provided via programmable interconnect230. Thus,FIG.2Billustrates another portion of programmable interconnect230. Each digital oscillator220-1,220-3through220-N has a corresponding multiplier232-2,236-2through238-2. The multipliers232-2and236-2through238-2multiply the response of the corresponding digital oscillator220-1and220-3through220-N by the corresponding weight J21and J23through J2N. Multipliers232-2and236-2through238-2output the weighted responses from digital oscillators220-1and220-3through220-N. In some embodiments, one or more of the weights J2jmay be zero if digital oscillator220-2is desired to be decoupled from the jthdigital oscillator. Adder234-2sums the weighted responses and provides the weighted responses to digital oscillator220-2.

The remaining portion of programmable interconnect230may be configured in an analogous manner. Thus, programmable interconnect230provides weights for and selectably couples digital oscillators220. The combination of digital oscillators120coupled via programmable interconnect230digitally models coupled differential equations, coupled periodic functions and/or the corresponding coupled systems. Digital oscillators120may function substantially in parallel to digitally solve a set of coupled differential equations. System200may provide benefits analogous to those of system100including but not limited to more rapidly providing improved precision solutions to complex problems. Thus performance of system200may be improved.

FIG.3is a flow chart depicting an embodiment of method300for performing optimization processing utilizing an OPU such as OPU310. For example, method300may be used in CO and/or other disciplines. Method300commences after the user has defined the problem for which the OPU is utilized. For example, if a traveling salesman problem is desired to be solved, the cities visited, the distance between cities, cost of case, miles per gallon, cost of hotels, problem constraints, and other information is provided by the user. In some embodiments, the information provided by the user may be in the form of a quadratic unconstrained binary optimization (QUBO) problem: xTQx+cTx, where x is a binary vector such that xi∈{0,1}, Q is a 2D matrix of real numbers, and c is a vector of real numbers. The problem is encoded in the elements of Q and c. In some embodiments, the information provided by the user may be in the form of a quadratic programing form (QP) problem: xTQx+cTx, where x is a continuous vector such that xi∈R, Q is a 2D matrix of real numbers, and c is a vector of real numbers. The problem is encoded in the elements of Q and c. In some embodiments, the information provided by the user may be in the form of an Ising Model: sTJs+hTs, where s is a vector such that the elements are either +1 or −1 si∈{−1, +1}, J is a 2D matrix of real numbers, h is a vector of real numbers. The problem is encoded in the elements of J and h. In some embodiments, the information provided by the user may be in the form of a linear program (LP) problem: Ax−b, where x is a vector of real numbers xi∈R, A is a matrix of real numbers, and b is a vector of real numbers. The problem is encoded in the elements of A and b. In some embodiments, the information provided may be in another form. In some embodiments, the CPU or GPU may break the problem up into smaller chunks for presentation to the OPU. In some embodiments, the CPU or GPU may use the OPU to address the problem in its entirety. The CPU and/or GPU may also be used to map the problem to the behavior of a system of nodes used in the OPU.

The OPU receives data for at least a portion of the optimization problem, at302. In some embodiments, the OPU receives the input from the CPU or GPU. In addition to the inputs for the digital oscillators, the OPU may also receive weights for the programmable interconnect(s), an indication of the number of iterations performed by the digital oscillators, timing of changes to weights and/or other information used to address the optimization problem. Thus, the processing by the OPU may be managed by the CPU.

Using the data, the OPU calculates responses in the digital oscillators, at304. In some embodiments, the digital oscillators may operate in parallel to provide their responses at304. Thus, the appropriate data is provided to the digital oscillators. In some embodiments, the same data is provided to each of the digital oscillators. For example, the initial conditions such as initial phase for each digital oscillator may be the same. In some embodiments, different data are provided to different digital oscillators. For example, initial conditions such as the initial phase for each digital oscillator may be different. Further, in some embodiments, an injection lock signal is provided to each of the digital oscillators as part of304. As a result, the digital oscillators more readily synchronize to their final states.

Weights are applied to the responses from the digital oscillators to provide weighted responses, at306. In some embodiments,306may precede304. In such cases, weights are applied to initial inputs to the digital oscillators. In other embodiments,304precedes306. In some embodiments, the weights are applied by the programmable interconnect(s) and may be controlled by the CPU and/or GPU. In some embodiments, the weights are applied by an FPGA or other digital matrix multiplier. In some embodiments, the weight(s) applied to responses from a particular digital oscillator do not depend upon the digital oscillator(s) which receive the weighted response. In other embodiments, the weight(s) applied to responses from a particular digital oscillator do depend upon the digital oscillator(s) which receive the weighted response. In some embodiments, the weights may only be applied to a portion of the digital oscillators. The portion of the digital oscillators may be selected programmably by the user, which serves as a reconfigurable interconnect system. In some embodiments, the weight applied may be zero if the digital oscillator providing the response is desired to be decoupled from the digital oscillator receiving the response. In some embodiments, the weights applied to the responses may be scaled by a time step. The time step may be programmed by a user.

The weighted response(s) for the digital oscillator(s) are provided as inputs to some or all of the other digital oscillators, at308. In some embodiments,308is performed by the programmable interconnect(s). Further, the selection of the digital oscillators to which the weighted response for a given digital oscillator is applied may be controlled by the CPU and/or GPU. In some embodiments,304,306and308may be repeated as desired to update the responses from the digital oscillators, at310. One or more responses are selected to be provided from the OPU, at312. These responses may be provided to the CPU and/or GPU for use in solving the desired problem. In some embodiments, method300may be iterated multiple times. For example, the response provided from OPU at312may be utilized by the CPU or GPU to adjust weights for the optimization problem and method300repeated for the same portion(s) of the optimization problem. In some embodiments, the response provided at312may simply be utilized to provide a solution to the optimization problem. Method300may also be performed for other portion(s) of the optimization problem.

For example, if system100utilizes method300, OPU110receives data for at least a part of the problem being addressed, at302. The data is received at OPU110from CPU102and/or GPU104. OPU110utilizes the data to calculate responses in digital oscillators120, at304. Thus, responses are determined in parallel by digital oscillators120, at304. The outputs (i.e. responses) from digital oscillators120are provided to programmable interconnect130also at304. Programmable interconnect130applies weights to the outputs, at306. These weighted outputs are (re) input to some or all of digital oscillators120, at308. This process of sampling each digital oscillator120, weighting the outputs, and providing the weighted outputs as inputs to other digital oscillator(s)120may be iteratively performed multiple times in OPU110, at310. A response is provided from OPU110to CPU102and/or GPU104, at312. System100may repeat some or all of method300. In some embodiments, the response provided at312for the first iteration may simply be utilized to provide a solution to the optimization problem. Method300may also be performed for other portion(s) of the optimization problem.

In another example, scheduling of multiple tasks on a number or processors is desired to be optimized. Thus, the user-defined problem is a scheduling problem. The tasks are subject to a number of constraints that are to be fulfilled. An exemplary constraint is that if a particular task is running on a given processor, no other tasks may run simultaneously on that processor. Thus, tasks running on a single processor do not conflict. Another constraint may be that particular tasks may not be started/provided to a processor until specified other task(s) have been completed. A simple schedule that satisfies the constraints could be to assign the tasks in series to a single processor. However, such an allocation of resources could consume a large amount of time. Optimization includes ensuring that all constraints are satisfied and that the tasks are allocated to processors in a manner that is more efficient (e.g. the set of tasks are assigned to processors such that processing is completed in a shorter amount of time). The scheduling problem may be mapped to a Boolean satisfiability problem. As discussed above, such a problem may be mapped to an Ising problem and the corresponding coupled differential equations described herein. Some or all of such a problem may be desired to be solved using method300and an OPU such as OPU110and/or210.

At302, the OPU receives data, such as an initial set of weights, the iterations to be performed or other mechanism for determining when a solution has been found, and/or other data such as the conditions to be satisfied and the maximum number of processors that may be used in scheduling. Using the data, the OPU calculates responses in the digital oscillators, at304. In some embodiments, digital oscillators120C are used to calculate solutions to the corresponding differential equations. In some embodiments, the digital oscillators may operate in parallel to provide their responses at304. Weights are applied to the responses from the digital oscillators to provide weighted responses, at306. The weighted response(s) for the digital oscillator(s) are provided as inputs to some or all of the other digital oscillators, at308. In some embodiments,308is performed by the programmable interconnect(s). At310,304,306and308may be repeated as desired to update the responses from the digital oscillators, at310. One or more responses are selected to be provided from the OPU, at312. These responses correspond to the solution to the differential equations for the Boolean satisfiability problem. Thus, an optimized schedule may be provided.

Thus, using method300, system100and OPU110may be used in solving challenging problems, for example in CO, scheduling, fluid dynamics, data analytics, and other fields. Because digital oscillators120operate in parallel, OPU110may more rapidly and efficiently provide responses using method300. In addition, the communication between OPU110and remaining components of system100, such as CPU102and/or GPU104may be facilitated and subject to reduced latency in implementing method300. Further, because digital oscillators120are used, the precision of method300has improved.

FIGS.4-8depict various embodiments of systems400,500,600,700and800, respectively, including digital oscillators used in an OPU.FIG.4depicts a particular digital oscillator420that is analogous to digital oscillators120,120B,120C, and/or220and can be used in systems100and/or200. Digital oscillator420receives inputs including weighted response from other digital oscillators (not shown inFIG.4) and outputs a response. In some embodiments, the inputs are provided by a programmable interconnect (not shown inFIG.4). Digital oscillator420is configured to solve a differential equation. In some embodiments, digital oscillator420is configured to model a differential equation governing a corresponding LC oscillator. In some embodiments, other differential equations may be solved. Digital oscillator420utilizes Euler's method to model the differential equation. Thus, digital oscillator420includes derivative block430that calculates the derivative of the relevant function with respect to a particular variable. For example, derivative block430may calculate the derivative of a function for the phase of the corresponding LC oscillator with respect to time. Derivative block430may calculate other derivative(s) in other embodiments. Thus, derivative block430includes digital components that operate on an input signal to provide an output signal that corresponds to the derivative of the differential equation for that input signal. In either case, derivative block430includes digital components connected such that the derivative of the relevant differential equations for the inputs is provided as an output. Digital oscillator also includes increment block432, which stores the amount by which the particular variable (e.g. time) is incremented. Digital oscillator420also includes multiplier440, adder450and memory450. Memory450stores the current value of the relevant function. For example, the current value of the phase may be stored in memory460. In some embodiments, memory460is implemented as a register.

In operation, derivative block430utilizes inputs and the current value of the relevant function to calculate the derivative of the relevant function for the current iteration. Using increment432, multiplier440multiplies the value of the derivative for the current iteration by the increment. This amount is added to the value of the relevant function for the previous iteration by adder450. The result is stored by memory460as the current value of the relevant function. This current value of the relevant function is also output by memory460. For example, if the relevant function is the phase of the oscillator over time, the derivative of the phase for the current iteration is calculated by derivative block430. Multiplier440multiplies the value of the derivative of the phase with respect to time for the current iteration by a time increment received from increment block432. The result is the amount the phase has changed in the time increment. This amount is added to the value of the phase from the previous iteration by added450to provide the current value of the phase. The current value of the phase is stored by memory460and output by digital oscillator420. Although digital oscillator420is described in the context of phase being the value output, other functions may be used. For example, a function of the oscillator phase, such as the sine and/or cosine of the phase, may be used in some embodiments.

Digital oscillator420may be used in an OPU, such as OPU110and/or210to model a periodic function. Digital oscillator420may be a straightforward mechanism for solving the relevant differential equations. A system operating digital oscillators analogous to digital oscillator420in parallel and in combination with programmable interconnect(s) may more rapidly provide higher precision solutions to complex problems governed by the differential equations. Further, such a system may be built on silicon and/or run at temperatures of at least zero degrees Celsius. Consequently, such a system may be more readily fabricated and utilized than, for example, quantum processors. In addition, communication between digital oscillators420and remaining components of the system, such as a CPU and/or GPU may be facilitated. Reduced latency may thus be achieved. Thus performance of a system employing digital oscillator420may be improved.

FIG.5depicts a particular digital oscillator520that is analogous to digital oscillators120,120B and/or220and can be used in systems100and/or200. Digital oscillator520receives inputs including weighted response from other digital oscillators (not shown inFIG.5) and outputs a response. The inputs are provided by a programmable interconnect (not shown inFIG.5) in some embodiments. Digital oscillator520is configured to solve a differential equation. In some embodiments, digital oscillator520is configured to model a differential equation governing a corresponding LC oscillator in a group of coupled oscillators. Digital oscillator520directly models the Kuramoto model of the coupled oscillators. Thus, in some embodiments, digital oscillator520is used to model a system governed by/solve the differential equation:

dd⁢t⁢ϕi⁡(t)=Ac⁢∑j⁢Jij·sin⁢⁢(ϕi⁡(t)-ϕj⁡(t))-As·sin⁢⁢(2⁢⁢ϕi⁡(t)).

In this embodiments, ϕiis the phase of the ithoscillator in a set of coupled oscillators, Jijis the coupling between the jthoscillator and the ithoscillator, ϕjis the phase of the jthcoupled oscillator, Asis the magnitude of the injection lock signal, Acis a multiplier, t is the relevant variable (i.e. time in this case), and the sum over j is over the remaining oscillators. Thus, digital oscillator520includes calculator block530that calculates the current value of the time derivative of the phase using the Kuramoto model. Calculator block530thus includes digital components coupled such that the output provided is the time derivative of the phase for the corresponding input. Digital oscillator520also includes increment block532, which stores the amount by which the particular variable (i.e. time) is incremented. Digital oscillator520also includes multiplier540, adder550and memory550. Memory550stores the current value of the phase. In some embodiments, memory560is implemented as a register.

In operation, calculator block530receives inputs related to the coupling. In some embodiments, the inputs correspond to a coupling matrix including the values of Jij. Calculator block530utilizes these inputs and the value of the Kuramoto model (i.e. phase of the oscillator) for the previous iteration to calculate the derivative of the value for the current iteration. Using increment532, multiplier540multiplies the derivative of the Kuramoto model for the current iteration by the increment. This amount is added to the value for the previous iteration by adder550. The resulting value of the Kuramoto model for the current iteration is stored by memory560. This current value of the phase function is also provided as a response by memory560.

In other embodiments, digital oscillator520utilizes the Kuramoto model in calculator block530to determine the current value of the time derivatives corresponding to equations:

d⁢sid⁢t=-(∇s⁢V⁡(s,a))=-(2⁢J⁢s^+h+14⁢(s^°3-s^))d⁢amd⁢t=am⁢Km⁡(s)2=G⁡(A⁢12⁢(s^+1^)-b)2

Thus, digital oscillator520includes calculator block530that includes digital components configured, based on the Kuramoto model, to output the current value of the time derivative for the inputs. In this embodiment, digital oscillator520also utilizes increment block532to increment time, multiplier540to multiply the current value determined via the Kuramoto model with the increment, adder550to add this to the previously stored value, and memory550to store the current value. Thus, regardless of whether digital oscillator520explicitly models phase of coupled oscillators, coupled electrons, a k-SAT problem or other problem, digital oscillator520include components connected such that a response corresponding to a solution of the differential equation is output.

Digital oscillator520may be used in an OPU, such as OPU110and/or210to model a periodic or other function. Digital oscillator520directly solves the Kuramoto model for a system of coupled oscillators. A system operating digital oscillators analogous to digital oscillator520in parallel and in combination with programmable interconnect(s) may more rapidly provide higher precision solutions to complex problems governed by the differential equations. Further, such a system may be built on silicon and/or run at temperatures of at least zero degrees Celsius. Consequently, such a system may be more readily fabricated and utilized than, for example, quantum processors. In addition, communication between digital oscillators520and remaining components of the system, such as a CPU and/or GPU may be facilitated. Reduced latency may thus be achieved. Thus performance of a system employing digital oscillator520may be improved.

FIG.6depicts a particular digital oscillator620that is analogous to digital oscillators120,120B and/or220and can be used in systems100and/or200. Digital oscillator620may be an injection locked oscillator using a sub-harmonic injection locking (SHIL) mechanism. Digital oscillator620models evolution of a periodic, complex-valued state by modeling the differential equations governing the state. The state value can be represented as two numerical values: x and y. One value (x) represents the real part of the state, while the other value (y) represents the imaginary part of the state. The complex-valued state, z(t), may be viewed as approximating a point on the unit circle, eiθ, that rotates continuously and is, therefore, periodic. The complex-valued state rotates at a time-varying instantaneous angular frequency ω(t). Thus, the time derivative of state variable z(t) is given by iω(t)t. For a set of coupled oscillators, the instantaneous angular frequency of kthdigital oscillator620is given by ωk(t). The time-derivative of the state variable zk(t)for the kthdigital oscillator620corresponds to the equation żk=iωk(t)t. Thus, operation of digital oscillator620is described in the context of the kthdigital oscillator620in a set of multiple coupled digital oscillators.

To compute zk(t) at a particular time given an initial value at time t0, the equation for żkis integrated from t0to t. To approximate this integration, digital oscillator620computes the complex-valued state corresponding to successive discrete time steps at times t=nΔt for integer values of n. In some embodiments, the computation for each digital oscillator620in a set of coupled oscillators is based on a common time-increment, Δt, which is a parameter of the system. For each digital oscillator620, the instantaneous angular frequency for that oscillator, ωk,n+1, is computed to update the state from iteration n to step n+1. Using this instantaneous angular frequency, digital oscillator620computes the n+1 state zk,n+1from the previous state zk,n.

To begin the overall process, the state of each digital oscillator620is initialized to a value corresponding to a point uniformly distributed on the unit circle (that is, eiθ, where θ is uniformly distributed in the range −π<θ≤π). In addition to the digital oscillators620used to represent the state of each Ising-model variable, a distinct reference oscillator is used for the SHIL computation. In some embodiments, this reference oscillator is initialized to a known value of 1. This value is arbitrary and may be either a known value or a random value somewhere approximately on the complex unit circle.

Given the values of ωk,nand ωk,n+1for digital oscillator620, in some embodiments, the complex state value is updated using a method similar to the “leapfrog” method, which results in a stable rotation around the unit circle under a broad range of conditions. Specifically, the update of the state of each digital oscillator620may be performed as follows. The complex state of digital oscillator620at step n is as zn=xn+iyn, with x and y being the real and imaginary parts, respectively, as indicated above. Although the index k indicating which oscillator is being referred to is omitted, the following equations are utilized for each digital oscillator620:

yh=yn+ωn⁢xn⁢Δ⁢t2⁢⁢xn+1=xn-(ωn+ωn+1)⁢yh⁢Δ⁢t2⁢⁢yn+1=yh+ωn+1⁢xn+1⁢Δ⁢t2

Thus, the real and imaginary values of the state for the current iteration (Xn+1and yn+1) are determined in digital oscillator620. These values of x and y are stored in registers630and640, respectively, as well as output as responses. Each register630,640and650may be connected to a common clock, which synchronously updates the register values from the corresponding input on each clock tick. The angular frequency, ωn+1, for the current iteration is provided as an input to digital oscillator620. The value Δt is a constant that is common across all oscillators620in some embodiments. Memory674stores the time increment. In some embodiments, the numerical value Δt is chosen to be a power of two, allowing multiplication by

Δ⁢t2
to be performed simply, such as a bit-shift in the case of a fixed-point representation.

In some embodiments, to perform the iteration, half of the time increment from memory674is multiplied by the angular frequency for the current iteration by multiplier676to provide an angle. This angle (wn+1Δt/2) is stored in register650and summed with the corresponding angle for the previous iteration (wnΔt/2) by adder672. The x value for the previous iteration (xn) from register630is multiplied by the angle for the previous iteration (wnΔt/2) at multiplier660and summed with the y value for the previous iteration (yn) by adder662. The resultant is yh. Here, yhcan be thought of as representing the imaginary value of the state at an intermediate point approximately halfway between iteration n and iteration n+1. The value yhis multiplied by the output of adder672(wn+1Δt/2+wnΔt/2=(wn+1+wn)Δt/2) by multiplier664. The value of the real part of the state from the previous iteration (xn) is removed by subtracter666and the output is stored in register630as the value of the real part of the state at the current iteration (xn+1). The output subtracter666is also multiplied by the angle wn+1Δt/2 at multiplier668. The output of multiplier668is added to yhat670. This yields the current value of the imaginary part of the state, yn+1, which is stored in register640and output. Thus, digital oscillator620provides outputs based on the equations indicated above.

For digital oscillators620, a reference oscillator is also used. For the reference oscillator, the instantaneous angular frequency is constant, with a value ωref. In other embodiments, other forms of integration that are stable for an oscillator, such as those with higher order terms, may be used in lieu of the method described herein.

For each digital oscillator620(other than the reference oscillator), the instantaneous angular frequency is updated on each time step (i.e. each iteration). The instantaneous angular frequency corresponds to a constant nominal frequency ω0, modified by time-varying components due to the coupling between each oscillator and some or all other oscillators, and due to the coupling with the reference oscillator for the SHIL operation. In some embodiments, a random component is also included in computing the instantaneous angular frequency.

At an iteration, n, the angular frequency for oscillator k may be governed by:

ωk,n=ω0+∑j⁢ωj,k,n+ωS,k,n+ωN,k,n

Here, ωj,k,nis the relative instantaneous angular frequency due to the oscillator-to-oscillator coupling from oscillator j, ωS,k,n, is that due to the SHIL operation. The frequency ωN,k,nis that due to the noise component and may be omitted. In some embodiments, the coupling between digital oscillators620is derived from the coupling computed in the Kuramoto model of couple oscillators. Specifically, in that model, the coupling from oscillator j to oscillator k is proportional to sin (θk−θj), where θkand θjare the instantaneous phases of oscillators k and j, respectively, with a proportionality constant of −Jkj. Here, Jkjcorresponds to the corresponding entry of the coupling matrix J that defines the Ising model associated with the computation. Other coupling may be used in some embodiments. At iteration n, the resulting component of the instantaneous frequency associated with oscillator-to-oscillator coupling is ωj,k,n=−AJ(t)Jkjsin (θk,n−θj,n). Here, AJ(t) is a scale factor that in some embodiments is time varying. In some embodiments, rather than explicitly computing the instantaneous phases and the sine function, the complex states are used directly to determine the equivalent value (assuming the state values, z, are approximately on the complex unit circle):
ωj,k,n=−AJ(t)JkjIm(zk,nzj,n*)

Here, Im( ) corresponds to the imaginary component of the value and * represents the complex conjugate.

The second component for instantaneous angular frequency is due to the SHIL operation. Stated differently, the second component is used for injection locking. Here, digital oscillators620are coupled to a single fixed-frequency oscillator generating a frequency twice the nominal frequency of the other oscillators (that is, 2ω0). In some embodiments, another frequency may be used. This frequency is coupled to the other oscillators via a function referred to as a perturbation projection vector (PPV). The PPV represents a model of small-valued disturbances of a physical or electrical oscillator, which corresponds to the linearized effect of the disturbing signal on the phase of the oscillator. The effect of this signal is modeled as a function of the phase of the oscillator being disturbed. For the purpose of locking each oscillator of the system to one of two phases, this function includes at least a significant second harmonic as a function of phase. Thus, the PPV includes at least a component proportional to sin (2θ). The resulting effect is a component of the instantaneous frequency that is proportional to the product of the PPV as a function of that oscillator's phase, and the SHIL oscillator, producing a signal at frequency 2ω0. That is,
ωS,k,n=AS(t)PPVk,nSHILn=AS(t) sin (2θk,n) sin (2ω0t+φ).

Here, As(t) is the coupling amplitude that may vary with time; θk,nis the instantaneous phase of oscillator k at time-step n; sin (2ω0t+φ) is the SHIL signal applied to all digital oscillators620, which is at a fixed frequency, and may have an arbitrary initial phase, φ, and t=nΔt. In some embodiment, the PPV function is determined directly from the complex oscillator state without explicitly using the instantaneous phase angle or the sine function. Specifically,
PPVk,n=2Re(zk,n)Im(zk,n)

Here, Re( ) is the real part of the complex argument and Im( ) is the imaginary part. For z values approximately on the complex unit circle, this is equivalent to sin (2θk,n). However, in some embodiments, the PPV value is either PPVk,n=2Re(zk,n)2−1 or PPVk,n=2 Im(zk,n)2−1. These alternatives are equivalent to utilizing cos (2θk,n) or −cos (2θk,n), respectively, which are similar to sin (2θk,n), but phase shifted by

π2.
The result of using these alternatives is a phase shift of the resulting bistable states by the corresponding amounts.

In some embodiments, the SHIL signal is determined using a single complex-valued reference oscillator operating at the fixed angular frequency ωref=ω0. The SHIL signal is determined from the state of this oscillator as the square of the state. That is,
SHILn=Im(zref,n2)

The resulting component of the instantaneous angular frequency is:
ωS,k,n=AS′(t)Re(zk,n)Im(zk,n)Im(zref,n2)

Here, AS′(t)=2AS(t), incorporating the factor of two. In some embodiments, the SHIL signal is generated by a reference oscillator operating at the fixed angular frequency ωref=2ω0. In this case, the imaginary part of the complex state is used directly as the SHIL signal.

In some embodiments, a noise component is included in the instantaneous frequency of each oscillator. In such cases, the noise signal for each time step for each oscillator is an independent random sample distributed approximately as a normal distribution. That is, the resulting noise component of the instantaneous angular frequency is computed as:
ωN,k,n˜(0,σN2)

Here, σN2is the noise variance, which may vary as a function of time.

Digital oscillator620performs by a particular number of iterations that may be fixed or may vary. For example, the number of iterations may be varied depending on the specific parameters of the computation or on the progress of the computation. After the final iteration, the binary result associated with the final result computation may be determined. This value may also be computed at any or all intermediate steps. In some embodiments, the binary is determined from the state of each oscillator, zk, with respect to the state of the reference oscillator zref,nas follows:
bk,n=(Im(zref,n*zk,n)≥0)

Here, zref,n* is the complex conjugate of the reference oscillator state, which is operating at frequency ω0, at the current time step; and( ) is an indicator function, taking the value 1 if the enclosed statement is true, or −1 if the enclosed statement is false.

In some embodiments, the digital oscillator620in a system of coupled oscillators may be implemented as a synchronous fully parallel implementation. In this embodiment, each digital oscillator620may be a separate finite state machine, coupled in a synchronous manner through the specified coupling terms. The state values for each digital oscillator620are stored in distinct registers, and directly coupled to the computing elements. In a synchronous manner based on a common clock, all parallel state machines update their state on each discrete time step. The state of each digital oscillator620includes the real and imaginary components of the oscillator state, x and y; and the most recent instantaneous angular frequency, co.

In some embodiments, digital oscillator620is fully connected to other digital oscillators. The connectivity between digital oscillators620may be implemented in the form of a crossbar configuration. In other embodiments, the oscillator-to-oscillator coupling is limited to a restricted connection configuration. Stated differently, digital oscillator620is desired to be sparsely connected to other digital oscillators. Thus, the connectivity is arranged accordingly. In some embodiment, digital oscillators620(other than the reference oscillator) are grouped into clusters of more than one digital oscillator620. In some such embodiments, each cluster shares a single implementation of the computation elements and stores the state in an addressable register file or memory. In some such embodiments, the computation for each cluster is performed in parallel with that of the other clusters. However, within a single cluster, the computation for each oscillator is performed sequentially. In this case, the addressing sequence of the memories may limit the structure of the connectivity between oscillators to ensure that the state values from adjacent oscillators are available to each computation unit at the time they are needed. In some embodiments, the state variables are stored in digital oscillator620as floating-point values and the computation performed on these values uses floating-point arithmetic. In other embodiments, the state variables are stored in a fixed-point representation and the computation on these values uses fixed-point arithmetic. In this case, additional scaling operations may be required to ensure values are within a specified numerical range.

In some embodiments of digital oscillator620, the iteration is performed such that the nominal frequency of each oscillator is zero (i.e., ω0=0). Such embodiments correspond closely to a particular implementation of the Kuramoto model. In this embodiment, the digital oscillators620are as previously described and depicted. However, the computation of the instantaneous angular frequency differs. The instantaneous angular frequency is computed without the ω0term, as:

ωk,n=∑j⁢ωj,k,n+ωS,k,n+ωN,k,n

In this embodiment, the ωj,k,nand ωN,k,nterms are as described above. The ωS,k,nterm differs in that there is no reference oscillator. Instead, this term is directly proportional to the PPV value, sin (2θk,n). In this embodiment, this term may be:
ωS,k,n=AS(t)Re(zk,n)Im(zk,n)

As there is no reference oscillator, the resulting binary value is computed by comparing with the known bistable phase states, which in this case, corresponds to:
bk,n=(Im(zk,n)≥0)

Digital oscillator620may be used in an OPU, such as OPU110and/or210to model a periodic function. Because it models the real and imaginary portions of the state variable, digital oscillator620may be more readily configured than, for example, a digital oscillator which directly models a sine function. A system operating digital oscillators analogous to digital oscillator620in parallel and in combination with programmable interconnect(s) may more rapidly provide higher precision solutions to complex problems governed by the differential equations. Further, such a system may be built on silicon and/or run at temperatures of at least zero degrees Celsius. Consequently, such a system may be more readily fabricated and utilized than, for example, quantum processors. In addition, communication between digital oscillators620and remaining components of the system, such as a CPU and/or GPU may be facilitated. Reduced latency may thus be achieved. Thus performance of a system employing digital oscillator620may be improved.

FIG.7depicts an embodiment of system700usable in conjunction with a digital oscillator such as digital oscillator620and that may be used in solving problems such as those described herein and/or other fields. System700is analogous to system100and includes OPU710. OPU710is analogous to OPU110. OPU710includes programmable interconnect730and digital oscillators720-1through720-N (collectively digital oscillators720/generically digital oscillator720). Programmable interconnect730is analogous to programmable interconnect130. Digital oscillators720are analogous to digital oscillators120,120B and/or120C. Digital oscillators720may also be analogous to digital oscillator620and thus receive as an input the current value of the angular frequency.FIG.7indicates that in addition to weighting the responses (Xi, Yi) from digital oscillators720and selectably coupling digital oscillators720, programmable interconnect730also provides the angular frequency for the current iteration. Thus, programmable interconnect730performs multiple functions.

Programmable interconnect730provides weights for and selectably couples digital oscillators720. The combination of digital oscillators720coupled via programmable interconnect730digitally models coupled differential equations, coupled periodic functions and/or the corresponding coupled systems. Digital oscillators720may function substantially in parallel to digitally solve a set of coupled differential equations. System700may provide benefits analogous to those of system100including but not limited to more rapidly providing improved precision solutions to complex problems. Thus performance of system700may be improved.

FIG.8depicts an embodiment of a system800usable in conjunction with a digital oscillator such as digital oscillator620and that may be used in solving problems such as those described herein and/or other fields. System800is analogous to system100and includes OPU810. OPU810is analogous to OPU110and/or700. OPU810includes programmable interconnect830and digital oscillators820-1through820-N (collectively digital oscillators820/generically digital oscillator820). Digital oscillators820are analogous to digital oscillators120,120B, and/or120C. Digital oscillators820are also analogous to digital oscillator620and thus receive as an input the current value of the angular frequency.

Programmable interconnect830is analogous to programmable interconnect130and to programmable interconnect730. Thus, in addition to weighting the responses (Xi, Yi) from digital oscillators820and selectably coupling digital oscillators820, programmable interconnect830provides the angular frequency for the current iteration. Thus, programmable interconnect830performs multiple functions. Programmable interconnect830breaks the calculation of the angular frequency into two sections performed by multiplication units832-1through832-N and matrix-vector multiplier834. The combination of digital oscillators820coupled via programmable interconnect830digitally models coupled differential equations, coupled periodic functions and/or the corresponding coupled systems. Digital oscillators820may function substantially in parallel to digitally solve a set of coupled differential equations. System800may provide benefits analogous to those of system100including but not limited to more rapidly providing improved precision solutions to complex problems. Thus performance of system800may be improved.

FIG.9is a diagram depicting an embodiment of system900usable in providing solutions to problems described herein and/or other fields. For clarity, only certain components of system900are depicted. System900is analogous to system100. Thus, system900includes CPU902and GPU904in addition to optimization unit940. Optimization unit940includes interconnects930and multiple OPUs910. Although system900is described in the context of a CPU902and a single GPU904, in some embodiments, system900may include multiple CPUs and/or multiple GPUs. In some embodiments, CPU902and/or GPU904may be omitted.

Optimization unit940of system900includes multiple OPUs910interconnected via interconnects930. Each OPU910is analogous to OPU110,210,710and/or810. Thus, each OPU910includes digital oscillators and programmable interconnects (not shown) such as those described herein. Interconnects930may sparsely or fully connect OPUs910. Further, the connections between OPUs910may be programmable. In some embodiments, interconnects930operate in an analogous manner to programmable interconnects130, but couple and weight outputs of OPUs910instead of individual digital oscillators.

System900may provide benefits analogous to those of system100including but not limited to more rapidly providing improved precision solutions to complex problems. Further, system900allows for the use of multiple OPUs910in solving problems. Thus performance of system900may be improved.

In addition to providing solutions to complex problems, digital oscillators such as those described herein may be used in logic applications.FIGS.10A-12depict embodiments of techniques for providing reversible logic utilizing digital oscillators.

FIGS.10A-10Bdepict an embodiment of system1000for performing logic operations and utilizing oscillators and error correction. For clarity, only portions of system1000are shown.FIG.10Adepicts system1000including logic gate(s)1010and error correction unit1040.FIG.10Bdepicts an embodiment of digital oscillator1020B usable in logic gate(s)1010. Logic gate(s)1010include interconnect1030and digital oscillators1020-1,1020-2through1020-N (collectively digital oscillators1020/generically digital oscillator1020). Thus, digital oscillators1020are configured to perform one or more logic operations. For example, digital oscillators1020may be configured to perform a logical OR operation. Thus, digital logic gate(s)1010form an OR gate in such a case. In other embodiments, digital oscillators1020may be configured to carry out one or more other and/or additional logical operations. Although shown as digital oscillators in other embodiments, oscillators1020may be analog oscillators. Other mechanisms for determining the connection coefficients may be used in other embodiments.

In configuring digital oscillators1020to carry out the logical operation(s), digital oscillators1020are coupled through interconnect(s)1030. In some embodiments, interconnects1030are merely electrical connections between and to digital oscillators1020. For example, the output of oscillator1020-1may be connected to the input of another digital oscillator1020-2. In some embodiments, interconnects1030may be programmable or otherwise configured to provide additional functionality. Interconnects1030receive the output from (e.g. the states of) digital oscillators1020and provide the output from the appropriate digital oscillator(s)1020as the resultant of the logical operation(s). Interconnects also provide the connection coefficient(s), hi, (for the ithdigital oscillator1020) and/or Jij(between the ithand jthoscillators1020). These connection coefficients are received from error correction unit1040and provided to one or more of digital oscillators1020by interconnect(s)1030. In some embodiments, the value(s) of the connection coefficients are determined by error correction unit1040. In some embodiments, the value(s) of the connection coefficients are determined by interconnects1040. Thus, digital oscillators1020in combination with interconnect(s)1030may be viewed as governed by the Ising Hamiltonian:

H⁡(σ)=-∑(ij)⁢⁢Jij⁢σi⁢σj-μ⁢∑j⁢hj⁢σj

Here, the connection coefficient(s), hiand/or Jijare tuned provided based on error correction unit1040.

Although described in the context of reversible logic operations, digital oscillators1020can more generally viewed as modeling digitally model periodic (or wave) functions and/or the corresponding systems. Digital oscillators1020may thus model a system governed by one or more differential equations. Stated differently, a digital oscillator1020may be a differential equation solver for a periodic differential equation and/or a differential equation solver for the differential equation(s) governing particular systems. For example, a digital oscillator1020may model an analog oscillator, such as an inductive-capacitive (LC) or resistive-inductive-capacitive (RLC) circuit. Such a digital oscillator1020may be viewed as solving the differential equation for an LC or RLC circuit. A digital oscillator1020may model Schrodinger's equation (i.e. the differential equation related to the Hamiltonian). Thus, digital oscillator1020may solve Schrodinger's (differential) equation to find the ground states of the electron. Digital oscillator1020may model the portion of the Ising Hamiltonian for a spin in a system of coupled spins. Thus, digital oscillator1020may be used to model a particular system governed by a differential equation. Digital oscillator1020may employ various mechanisms including but not limited to Euler's method and the Kuramoto model to solve such differential equations. In some embodiments, digital oscillator1020includes or consists of digital circuit components that are utilized at temperatures at or above zero degrees Celsius (e.g. room temperature or above). In some embodiments, digital oscillators1020may include or consist of circuit components formed on silicon wafers as part of an integrated circuit.

The combination of digital oscillators1020coupled via interconnect(s)1030digitally models coupled differential equations, coupled periodic functions and/or the corresponding coupled systems. For example, coupled digital oscillators1020may be used to model the Ising Hamiltonian configured to perform the desired logic operation(s). In some embodiments, digital oscillators1020in combination with interconnect(S)1030model a system of coupled analog oscillators, such as coupled LC circuits and/or coupled RLC circuits. Thus, digital oscillators1020in conjunction with interconnect(s)1030may be used to model a particular system governed by coupled differential equations. Digital oscillators1020may employ various mechanisms including but not limited to Euler's method and the Kuramoto model. Digital oscillators1020are thus configured to provide, based on data input to digital oscillators1020and connection coefficients provided by interconnect(s)1030, responses that are probabilistic and periodic in nature. For example, the responses may be based upon the phases corresponding to digital oscillator1020at the particular time the oscillator(s) are sampled.

In some embodiments, digital oscillators1020are injection locked digital oscillators. Injection locked digital oscillators1020may be more likely to synchronize to reach a stable state for the combination of digital oscillators1020. In some embodiments, each injection locked digital oscillator1020may settle in one of two states. For example, the phases of the oscillators may be considered to be 0° or 180° and may differ based upon initial conditions for the oscillator and/or the time at which the oscillator is sampled. The phases of these oscillators may be used to model equations, such as the Hamiltonian (e.g. the Ising Hamiltonian) used for logical operations. The phases of these oscillators1020may also be used to model the corresponding differential equations for the phases of oscillators used in providing a solution to the Ising Hamiltonian. In some embodiments, injection locked digital oscillators are configured by providing injection lock signals to digital oscillators1020. The frequency of such injection lock signals is greater than the frequency of the corresponding digital oscillator1020. In some embodiments, the injection lock signal is at 1.5 multiplied by the frequency and not more than 2.5 multiplied by the frequency of the corresponding digital oscillator1020. For example, in some embodiments, the injection lock signal is at nominally twice the frequency of the corresponding digital oscillator1020. Thus, injection locked digital oscillators1020may synchronize to provide a stable set of states for digital oscillators1020coupled via programmable interconnect1030.

FIG.10Bdepicts a particular digital oscillator1020B of digital oscillators1020. In the embodiment shown, digital oscillator1020B is an injection locked digital oscillator. Thus, digital oscillator1020B receives an injection lock signal. In some embodiments, the injection lock signal has a frequency that is nominally twice the modeled oscillator frequency. The injection lock signal assists in syncing digital oscillators1020to provide the solution to the coupled differential equations (or coupled system) being modeled. Digital oscillator1020B also receives inputs ViL and ViR and provides outputs VoL and VoR. Inputs ViL and ViR correspond to connection coefficients provided by interconnect(s)1030and outputs of other digital oscillators1020. Outputs VoL and VoR are outputs provided by digital oscillator1020B. In some embodiments, digital oscillator1020B is configured to solve a differential equation governing a corresponding analog LC oscillator. Thus, in some embodiments digital oscillator1020B is configured to solve the following equation or its analog:

1R⁢A⁢⁢exp⁢⁢(j⁢⁢θ)+C⁢dd⁢⁢t⁢(A⁢⁢exp⁢⁢(j⁢⁢θ))+1L⁢∫t⁢A⁢⁢exp⁢⁢(j⁢⁢θ)⁢d⁢⁢τ=(4⁢⁢I⁢/⁢π)⁢exp⁢⁢(j⁢⁢θ)+Iinj⁢exp⁡(j⁢⁢θinj).

In the above equation, A is a scale factor, C is the capacitance, R is the resistance, L is the inductance, Iinjis the amplitude of the injection locking signal, I is the current and θ is the phase of the oscillator. Digital oscillator1020B may thus be viewed as modeling a particular oscillating LC circuit that is coupled with other oscillators. In some embodiments, for example, digital oscillator1020B may utilize Euler's method (described herein), the Kuramoto model (described herein) to solve the above differential equation and model the oscillators. In some embodiments, other differential equations may be modeled.

Logic gate(s)1010perform logical operations, but may result in errors. Consequently error correction unit1040is utilized. Error correction unit1040samples the outputs of digital oscillators1020(i.e. the states of digital oscillators1020) as well as the inputs to digital oscillators1020. Using the inputs to and states of digital oscillators1020, error correction unit1040determines whether errors exist in the logical operation(s) performed by logic gate(s)1010. For example, error correction unit1040may compare the input(s) to and output(s) of each logic gate in logic gate(s)1010to a truth table for the corresponding logic gate. If the input(s) and output(s) match the truth table, then error correction unit1040takes no action. If, however, there is a mismatch, an error is detected. In response, error correction unit1040adjusts the values of the connection coefficient(s) for at least one of digital oscillators1020. Thus, error correction nit tunes the connection coefficient(s) for one or more digital oscillators1020for reduced error operation. For example, the connection coefficient(s) may be pinned to values corresponding to a logical “1” or logical “0”. Tuning the connection coefficient(s) forces digital oscillators1020to provide a different output. Thus, errors may be corrected.

Using system1000, reversible logic gates1010may be provided. Consequently, system1010may be used in complex operations such as factoring. Further, errors that would otherwise be present may be corrected. As a result, system1000has the desired accuracy. Performance may thus be improved.

FIG.11depicts system1200for carrying out a particular logic operation utilizing oscillators and error correction. System1200is analogous to system1000. System1200includes logical OR gate1210analogous to logic gate(s)1010and error correction unit1240analogous to error correction unit1040. Logical OR gate1210includes digital oscillators1220-1,1220-2,1220-3and1220-4(collectively digital oscillators1220/generically digital oscillator1220). Thus, digital oscillators1220are configured to carry out a logical OR operation. Logical OR gate1210also includes interconnects1230between individual digital oscillators1220and between digital oscillators1220and error correction unit1240. In the embodiment shown, interconnects1230between individual digital oscillators1220are shown as lines. The interconnects between error correction unit1240and digital oscillators1220are shown as arrows to and from error correction unit1240. Logic gate1210can be described by the Ising Hamiltonian above, where Jijand hiare the connection coefficients.

Digital oscillators1220coupled by interconnects1230perform a logical OR operation. However, as indicated above, without more, logical OR gate1210may be subject to errors. Consequently, error correction unit1240is used. Error correction unit1240samples the states of digital oscillators1220(output 1, output 2, output 3 and output 4) as well as the inputs to digital oscillators1220. By comparing the output of logical OR gate1210to the expected output(s) for the given inputs, error correction unit1240detects whether an error has occurred. If no error is detected, then error correction unit1240takes no action. Thus, logical OR gate1210operates normally. If, however, an error is detected, then error correction unit1240takes action. Error correction unit1240tunes the connection coefficient(s) for one or more digital oscillators1220. Thus, hiand/or Jijmay be adjusted. For example, the connection coefficient(s) may be pinned to values corresponding to a logical “1” or logical “0”. Tuning the connection coefficient(s) forces digital oscillators1220to provide a different output. Thus, errors may be corrected.

Using system1200, reversible logic gates1210may be provided. Further, errors that would otherwise be present may be corrected. As a result, system1200may be subject to fewer errors. Performance may thus be improved.

FIG.12is a flow chart depicting an embodiment of method1300for performing error correction for logical operations. For clarity, only some steps are indicated. Although depicted in a particular order, in some embodiments, method1300may include other and/or additional processes that may be performed in another order.

The states of the oscillators used in performing the logic operation are received, at1302. In some embodiments, digital oscillators receive the inputs for the logic operation and calculate their responses. In some embodiments, an injection lock signal is provided to each of the digital oscillators as part of the inputs. As a result, the digital oscillators more readily synchronize to their final states. Any error(s) in the states are detected, at1304. In some embodiments, the errors are detected based on the inputs to the oscillators, the states of the oscillators and the known function of the logic operation(s). Thus, the output of the logic gate(s) formed using the digital oscillators and/or logic operations may be compared to the expected output in order to detect errors.

Connection coefficient(s) between the digital oscillators are tuned in response to detecting the error(s), at1306. Thus, the coupling between the oscillators and/or for particular oscillator(s) may be adjusted to correct the error. In some embodiments, tuning the connection coefficient(s) includes pinning the connection coefficient(s) at a value corresponding to a logical “1” or a logical “0”.

For example, if system1000utilizes method1300, inputs are provided to digital oscillators1020. Digital oscillators1020calculate their responses. Error correction unit1040receives the states of digital oscillators1020in logic gate(s)1010, at1302. Error correction unit1040also receives the inputs to digital oscillators1020at1302. At1304, error correction unit1040determines whether an error is present, for example by comparing the output of the logic gate(s) to an expected output. In response to an error being detected, error correction unit1040tunes the connection coefficients to one or more of digital oscillators1020.

Thus, using method1300, system1000may be used performing reversible logic operations. Because error correction unit1040corrects errors, the desired accuracy for system1000may be achieved.

Although the foregoing embodiments have been described in some detail for purposes of clarity of understanding, the invention is not limited to the details provided. There are many alternative ways of implementing the invention. The disclosed embodiments are illustrative and not restrictive.