Patent Description:
According to one aspect of the present disclosure, a computing device is provided, including memory storing instructions to compute a combinatorial cost function of a plurality of variables. The computing device may further include an accelerator device and a processor. The processor may be configured to generate a plurality of data packs. Each data pack may indicate an update to a variable of the one or more variables. The processor may be further configured to transmit the plurality of data packs to the accelerator device. The accelerator device may be configured to, for each data pack, retrieve a variable value of the variable indicated by the data pack. The accelerator device may be further configured to generate an updated variable value of the variable as indicated by the data pack. The accelerator device may be further configured to generate an updated cost function value of the combinatorial cost function based on the updated variable value. The accelerator device may be further configured to determine a transition probability using a Monte Carlo algorithm. The accelerator device may be further configured to store the updated variable value and the updated cost function value with the transition probability. The accelerator device may be further configured to output a final updated cost function value of the combinatorial cost function to the processor.

In order to address the inefficiency of existing systems and methods for computing combinatorial cost functions, as discussed above, the inventors have conceived of the following devices and methods. <FIG> shows a computing device <NUM> according to one example embodiment. The computing device <NUM> may include a processor <NUM> and may further include memory <NUM>. The memory <NUM> may store instructions to compute a combinatorial cost function <NUM> of a plurality of variables <NUM>. For example, the instructions to compute the combinatorial cost function <NUM> may be included in an application program and may be executed by the processor <NUM>.

The computing device <NUM> may further include an accelerator device <NUM>, which is configured as a hardware device operatively coupled to the processor <NUM>. The processor <NUM> and the accelerator device <NUM> may be coupled by an interconnect such as PCI Express, AMBA, or some other type of interconnect. The accelerator device <NUM> may be specialized for computing combinatorial cost functions <NUM>. In some embodiments, the accelerator device <NUM> may be selected from the group consisting of a field programmable gate array (FPGA), an application-specific integrated circuit (ASIC), a graphical processing unit (GPU), and a tensor processing unit (TPU). However, the accelerator device <NUM> may be another type of device in other embodiments. In embodiments in which the accelerator device <NUM> is an FPGA, the accelerator device <NUM> may include dynamic random-access memory (DRAM) <NUM> in which data may be stored when evaluating a combinatorial cost function <NUM>, as discussed in further detail below. In some embodiments, the computing device <NUM> may further include on-board block RAM <NUM>. It will be appreciated that block RAM is often used in FPGA type accelerator devices. In other implementations, other forms of static RAM maybe used instead of block RAM.

While the computing device <NUM> is shown in <FIG> as a single hardware device, the components of the computing device <NUM> may be distributed over a plurality of communicatively coupled computing devices in some embodiments. In such embodiments, the computing device <NUM> may include one or more communication devices <NUM>. In one example, the plurality of communicatively coupled computing devices may include a server computing device and a client computing device that communicate over a network.

The combinatorial cost function <NUM> evaluated at the computing device <NUM> may have the form H = f(x<NUM>,. The variables xi may be either discrete or continuous variables. In some examples, the combinatorial cost function <NUM> may be expressed as a sum of a plurality of terms <NUM>. In one example, the combinatorial cost function <NUM> may have the following form: <MAT> In this example, · is an arbitrary binary operation between discrete or continuous variables xi. Ti are real-valued scalar weights applied to the terms <NUM>. In other embodiments, the combinatorial cost function <NUM> may include one or more terms <NUM> that include operations applied over some other number of inputs. Each term <NUM> has an order n equal to the number of variables appearing in it.

The processor <NUM> may be configured to generate a plurality of data packs <NUM>. Each data pack <NUM> may indicate an update to a variable <NUM> of the one or more variables <NUM> included in the combinatorial cost function <NUM>. The update <NUM> may set the variable <NUM> to a new variable value <NUM>. When the combinatorial cost function <NUM> includes a plurality of terms <NUM>, the data pack <NUM> may further include one or more term indicators <NUM> that indicate one or more terms <NUM> of the combinatorial cost function <NUM> in which the variable <NUM> indicated in the data pack <NUM> occurs. In some embodiments, the data pack <NUM> may further include a flag <NUM> that affects the processing order of the plurality of data packs <NUM>, as discussed in further detail below.

The processor <NUM> may be further configured to transmit the plurality of data packs <NUM> to the accelerator device <NUM>. In some embodiments, the processor <NUM> may determine an update order <NUM> for the plurality of data packs <NUM> and may transmit the plurality of data packs <NUM> to the accelerator device <NUM> in the update order <NUM>. The determination of the update order <NUM> is discussed in further detail below with reference to <FIG>.

In embodiments in which the accelerator device <NUM> is an FPGA that includes DRAM <NUM>, the plurality of data packs <NUM> may be written to the DRAM <NUM>. The data packs <NUM> may be written to the DRAM <NUM> in the update order <NUM> specified by the processor <NUM>. For each data pack <NUM>, the accelerator device <NUM> may be further configured to retrieve a variable value <NUM> of the variable <NUM> indicated by the data pack <NUM>. The variable value <NUM> may be retrieved from the DRAM <NUM>. In addition, the accelerator device <NUM> may be further configured to retrieve one or more other variable values <NUM> of one or more other variables <NUM>. The one or more other variables <NUM> may be other variables <NUM> that occur in one or more terms <NUM> in which the variable <NUM> indicated in the data pack <NUM> occurs.

Alternatively to retrieving the variable value <NUM> from the DRAM <NUM>, the accelerator device <NUM> may instead be configured to retrieve one or more memory addresses of the variable value <NUM> from the DRAM <NUM>. In such embodiments, the accelerator device <NUM> may then retrieve the variable value <NUM> and/or the value of the combinatorial cost function <NUM> from the on-board block RAM <NUM> by accessing their respective memory addresses as indicated in the DRAM <NUM>.

For each data pack <NUM>, the accelerator device <NUM> may be further configured to generate an updated variable value <NUM> of the variable <NUM> as indicated by the data pack <NUM>. For example, in some embodiments, the update <NUM> included in each data pack <NUM> may indicate a perturbation to add to the variable value <NUM>. The accelerator device <NUM> may then input the updated variable value <NUM> into the one or more terms <NUM> of the combinatorial cost function <NUM> in which the variable <NUM> occurs. Thus, the accelerator device <NUM> may generate an updated cost function value <NUM> of the combinatorial cost function <NUM> based on the updated variable value <NUM>.

For each data pack <NUM>, the accelerator device <NUM> may be further configured to determine a transition probability <NUM> using a transition probability algorithm such as a Monte Carlo algorithm <NUM>, as discussed in further detail below. The transition probability <NUM> is a probability that the updated variable value <NUM> is saved to be used in further iterations of determining the updated cost function value <NUM>, or, if the data pack <NUM> is the last data pack <NUM> in the update order <NUM>, included in the combinatorial cost function <NUM> when the accelerator device <NUM> outputs a final updated cost function value. For each data pack <NUM>, when the updated variable value <NUM>, the transition probability <NUM>, and the updated cost function value <NUM> have been determined, the accelerator device <NUM> may be further configured to store the updated variable value <NUM> and the updated cost function value <NUM> with the transition probability <NUM>. When the updated variable value <NUM> and the updated cost function value <NUM> are stored, the updated variable value <NUM> and the updated cost function value <NUM> may be stored in the DRAM <NUM> of the accelerator device <NUM>. Alternatively, the updated variable value <NUM> and the updated cost function value <NUM> may be stored in the on-board block RAM <NUM>. When the updated variable value <NUM> and the updated cost function value <NUM> are not stored, the variable <NUM> and the combinatorial cost function <NUM> may keep their previous values.

After the accelerator device <NUM> processes the last data pack <NUM> of the plurality of data packs <NUM>, the accelerator device <NUM> may be further configured to output a final updated cost function value of the combinatorial cost function <NUM> to the processor <NUM>. The final updated cost function value may be the updated cost function value <NUM> obtained when the last data pack <NUM> is processed. The accelerator device <NUM> may also output to the processor <NUM> a respective final variable value for one or more of the variables <NUM> included in the combinatorial cost function <NUM>.

The Monte Carlo algorithm <NUM> is now described in further detail with reference to the example embodiments provided below. The Monte Carlo algorithm <NUM> may be a Markov chain Monte Carlo algorithm in which the transition probability <NUM> is determined based on the updated cost function value <NUM> and is independent of previous values of the combinatorial cost function <NUM>. For example, the Monte Carlo algorithm <NUM> may be selected from the group consisting of simulated annealing, parallel tempering, and simulated quantum annealing.

The processor <NUM> may be configured to generate the plurality of data packs <NUM> for an update step <NUM> in which a respective data pack <NUM> is generated for each variable <NUM> of the plurality of variables <NUM> included in the combinatorial cost function <NUM>, as shown in the example of <FIG>. The processor <NUM> may generate sets of data packs <NUM> for a plurality of update steps <NUM> over which the value of the combinatorial cost function <NUM> may converge toward a global maximum or minimum. The update step <NUM> may be a Monte Carlo sweep, for example.

When the accelerator device <NUM> performs the Monte Carlo algorithm <NUM>, the accelerator device <NUM> may, for each data pack <NUM> of the plurality of data packs <NUM>, generate a pseudorandom number z. In one example embodiment, the pseudorandom number z may be generated from a uniform probability distribution with a range from <NUM> to <NUM>. The accelerator device <NUM> may be further configured to determine the transition probability <NUM> based at least in part on the updated cost function value <NUM>. For example, the transition probability <NUM> may be based at least in part on a change in the cost function value ΔH from the previous value of the combinatorial cost function <NUM> to the updated cost function value <NUM>.

The accelerator device <NUM> may be further configured to store the updated cost function value <NUM> and the updated variable value <NUM> for the variable <NUM> indicated in the data pack <NUM> in response to determining that the transition probability <NUM> exceeds the pseudorandom number z. In some embodiments, rather than comparing the transition probability <NUM> and the pseudorandom number z directly, the accelerator device <NUM> may compare a logarithm of the transition probability <NUM> to a logarithm of the pseudorandom number z. This may save steps of computation in embodiments in which the transition probability is given at least in part by an exponential function, as in some examples discussed below.

In some example embodiments, the accelerator device <NUM> may be configured to determine the transition probability <NUM> based at least in part on a Boltzmann distribution <NUM> with an inverse temperature β. The Boltzmann distribution <NUM> is used in such embodiments to simulate thermal fluctuations in a system that allow the system to escape local optima that are not global optima. Thus, over a large number of update steps <NUM>, the combinatorial cost function <NUM> may tend toward thermodynamic equilibrium at its global maximum or minimum.

In one example, the Monte Carlo algorithm <NUM> may be simulated annealing. When simulated annealing is used, the processor <NUM> may initialized each of the plurality of data packs <NUM> with an initial value for the inverse temperature β. The initial value of the inverse temperature β may be a minimum value that is incremented after each update step <NUM>. Thus, as the Monte Carlo algorithm <NUM> progresses, the search for optima of the combinatorial cost function <NUM> may move away from the β = <NUM> limit, corresponding to random assignment, and toward the β = ∞ limit, corresponding to greedy search. This allows the accelerator <NUM> to iterate a process of first identifying a candidate region of parameter space in which a global maximum or minimum may occur and then searching for the global maximum or minimum within the candidate region in further detail.

In another example, the Monte Carlo algorithm <NUM> may be parallel tempering. When parallel tempering is used, the processor <NUM> may initialize a plurality of sets of variable values <NUM>, each set of values having a corresponding initial value of the inverse temperature β. The initial values of the variables <NUM> and the inverse temperature β may be pseudorandom. After each update step <NUM>, each data pack <NUM> may swap values of β with a previous or subsequent data pack <NUM> with the following probability: <MAT> where Δβ denotes the difference in values of β between the adjacent data packs <NUM>. This allows for sets of variable values <NUM> at high temperatures (low values of β) to be set to low temperatures (high values of β) when the change in cost function value ΔH is large compared to the change in the inverse temperature Δβ. Thus, the parameter space of the combinatorial cost function <NUM> may be traversed more quickly due to faster "cooling" of sets of variable values <NUM> around which the rate of change in the updated cost function value <NUM> is higher.

In another example, the Monte Carlo algorithm <NUM> may be simulated quantum annealing. When simulated quantum annealing is used, the processor <NUM> may initialize a plurality of configurations of variable values <NUM> with a fixed value of the inverse temperature β. The accelerator device <NUM> may update the value of the combinatorial cost function <NUM> during each update step <NUM> according to the following rule: <MAT> where A and β are tuning parameters that are varied according to a predefined schedule over the execution of the Monte Carlo algorithm <NUM>, and the sum over n is a sum over a plurality of copies of the combinatorial cost function <NUM>. The simulated quantum annealing algorithm is analogous to a discrete time Path Integral Monte Carlo simulation of a transverse field Ising model.

Additionally or alternatively to the example Monte Carlo algorithms <NUM> described above, one or more other algorithms could be used. Other example algorithms include Population Annealing Monte Carlo, combination with cluster updates, and steepest descent algorithms. In some embodiments, a combination of two or more of the above example algorithms could be used. Additionally or alternatively to Monte Carlo algorithms, other Markov-chain-based heuristics may be used to update the variable value <NUM>.

In embodiments in which the processor <NUM> determines an update order <NUM> for the plurality of data packs <NUM>, the processor <NUM> may pipeline the data packs <NUM> to account for dependencies in the terms <NUM> of the combinatorial cost function <NUM>. <FIG> show two example flags <NUM> that may be included in a data pack <NUM> and how those flags <NUM> affect the evaluation of the combinatorial cost function <NUM> across a plurality of update cycles <NUM> of the accelerator device <NUM>. In the example of <FIG>, a data pack <NUM> includes an Accumulate flag 46A. The Accumulate flag 46A specifies that one or more subsequent data packs <NUM> are included in the same update <NUM> as the current data pack <NUM>. The Accumulate flag 46A indicates that the term <NUM> of the combinatorial cost function <NUM> updated by the data pack <NUM> also depends upon one or more other variables <NUM> included in one or more other terms <NUM> in addition to the variable <NUM> updated by the data pack <NUM>. The one or more other variables <NUM> may instead be included in one or more subsequent data packs <NUM>. Thus, evaluation of a term <NUM> that includes a plurality of variables <NUM> may occur across a plurality of update cycles <NUM> of the accelerator device <NUM>. In some embodiments, the Accumulate flag 46A may indicate a number of subsequent data packs <NUM> after which to wait to evaluate the combinatorial cost function <NUM>.

In the example of <FIG>, the data pack <NUM> includes an Order_Extend flag 46B in addition to the Accumulate flag 46B. The Order_Extend flag 46B may be used when updating a term <NUM> that depends upon a plurality of variables <NUM>. The Order_Extend flag 46B denotes that the subsequent data pack <NUM> includes an update to a variable <NUM> that is included in the same term <NUM> of the combinatorial cost function <NUM>. Thus, the subsequent data pack <NUM> includes an update continuation <NUM> and allows a term <NUM> that includes multiple variables to be evaluated across a plurality of update cycles <NUM>.

<FIG> shows an example in which the update order <NUM> is set to avoid dependencies between terms <NUM> that may bottleneck evaluation of the updated cost function value <NUM>. In the example of <FIG>, the processor <NUM> may be configured to identify at least a first set 74A of one or more terms <NUM> and a second set 74B of one or more terms <NUM> included in the combinatorial cost function <NUM>. In this example the first set 74A includes a first term 72A and a second term 72B, and the second set 74B includes a third term 72C. The processor <NUM> divides the terms <NUM> into the first set 74A and the second set 74B such that the first set 74A of one or more terms <NUM> and the second set 74B of one or more terms <NUM> respectively include non-overlapping sets of variables <NUM>. In the example of <FIG>, the first set 74A of one or more terms <NUM> includes the variables x<NUM>, x<NUM>, and x<NUM>, and the second set 74B of one or more terms <NUM> includes the variables x<NUM> and x<NUM>. Although two such sets of terms <NUM> are shown in <FIG>, the combinatorial cost function <NUM> may include three or more such sets in other examples.

The combinatorial cost function <NUM> may be represented by a cost function graph <NUM> in which nodes represent variables <NUM> and edges represent the inclusion of two variables <NUM> in a term <NUM>. The cost function graph <NUM> may indicate, for each variable <NUM>, any variables <NUM> upon which the update <NUM> to that variable <NUM> depends. The cost function graph <NUM> may further indicate one or more terms <NUM> including such variables <NUM>. Alternatively, the combinatorial cost function <NUM> may be represented as a hypergraph in which nodes represent variables <NUM> and each edge represents a term <NUM>. As shown in <FIG>, since the combinatorial cost function <NUM> includes a first set 74A of one or more terms <NUM> and a second set 74B of one or more terms <NUM> that respectively include non-overlapping sets of variables <NUM>, the cost function graph <NUM> is disconnected. In some embodiments, the processor <NUM> may use depth-first or breadth-first search to determine that the cost function graph <NUM> is disconnected.

The processor <NUM> may then set the update order <NUM> to include a first data pack stream 76A in which the one or more terms <NUM> of the first set 74A are configured to be updated and a second data pack stream 76B in which the one or more terms <NUM> of the second set 74B are configured to be updated. The first data pack stream 76A, as shown in <FIG>, includes a first plurality of data packs 40A, and the second data pack stream 76B includes a second plurality of data packs 40B. The first plurality of data packs 40A includes updates to the variables x<NUM>, x<NUM>, and x<NUM>, and the second plurality of data packs 40B includes updates to the variables x<NUM> and x<NUM>. Thus, independent terms of the combinatorial cost function <NUM> may be evaluated in parallel; for each data pack <NUM>, evaluation of the updated cost function value <NUM> is not delayed by redundant evaluation of terms left unchanged by the update <NUM> included in that data pack <NUM>. This may result in improved performance.

<FIG> shows another example in which the processor <NUM> determines an update order <NUM> for a combinatorial cost function <NUM>. In the example of <FIG>, the combinatorial cost function <NUM> includes a first term 172A, a second term 172B, and a third term 172C. However, as seen from the connected cost function graph <NUM> representing the combinatorial cost function <NUM>, the combinatorial cost function <NUM> does not include two or more independent sets of terms <NUM>. In the example of <FIG>, two variables <NUM> are independent if those variables <NUM> are not connected by an edge in the cost function graph <NUM>. Since each of the variables x<NUM>, x<NUM>, and x<NUM> shown in <FIG> is connected to each of the others, none of the variables x<NUM>, x<NUM>, and x<NUM> are independent. Thus, in the example of <FIG>, the processor <NUM> may be configured to determine that each term <NUM> of the combinatorial cost function <NUM> includes one or more variables <NUM> that are included in at least one other term <NUM>. For example, the processor <NUM> may use depth-first or breadth-first search to determine whether the cost function graph <NUM> is connected.

The processor <NUM> may be further configured to set the update order <NUM> to include a first plurality of data packs 140A configured to update a first copy 130A of the combinatorial cost function <NUM> and a second plurality of data packs 140B configured to update a second copy 130B of the combinatorial cost function <NUM>. By generating a first copy 130A and a second copy 130B of the combinatorial cost function <NUM> and updating them separately, the processor <NUM> may treat the combinatorial cost function as though it were divided into two independent sets of terms <NUM> as in the example of <FIG>. In order to avoid bottlenecks in the processing pipeline of the accelerator device <NUM>, the first plurality of data packs 140A and the second plurality of data packs 140B may be interspersed in the update order <NUM>. For example, as shown in <FIG>, the update order <NUM> may alternate between data packs 140A and 140B from the first plurality of data packs 140A and the second plurality of data packs 140B respectively.

In some embodiments, the processor <NUM> may generate three or more copies of the combinatorial cost function <NUM>. In such embodiments, the processor <NUM> may generate a respective plurality of data packs for each copy and may intersperse data packs from each plurality of data packs in the update order <NUM>.

<FIG> shows a flowchart of a method <NUM> that may be used with a computing device to approximate a maximum and/or minimum of a combinatorial cost function. The computing device may be the computing device <NUM> of <FIG> or may alternatively be some other computing device. At step <NUM>, the method <NUM> may include generating a plurality of data packs. Each data pack may indicate an update to a variable of one or more variables of the combinatorial cost function. In some embodiments, each data pack may indicate one or more terms of the combinatorial cost function in which the variable indicated in the data pack occurs. Additionally or alternatively, the plurality of data packs may be generated for an update step in which a respective data pack is generated for each variable of the plurality of variables. At step <NUM>, the method <NUM> may further include transmitting the plurality of data packs to an accelerator device. Steps <NUM> and <NUM> may occur at a processor of the computing device. Additionally or alternatively, the accelerator device may be included in the computing device. In some embodiments, when the accelerator device is an FPGA, the accelerator device may include DRAM. In such embodiments, the plurality of data packs may be written to the DRAM.

The following steps of the method <NUM> may be performed at the accelerator device. At step <NUM>, the method <NUM> may further include, for each data pack, retrieving a variable value of the variable indicated by the data pack. In embodiments in which the accelerator device includes DRAM, the variable value may be retrieved from the DRAM for each data pack. Alternatively, in some embodiments, respective memory addresses of the combinatorial cost function and plurality of variables may be retrieved from the DRAM and the variable values may be retrieved from the on-board block RAM. At step <NUM>, the method <NUM> may further include, for each data pack, generating an updated variable value of the variable as indicated by the data pack. For each data pack, the method <NUM> may further include, at step <NUM>, generating an updated cost function value of the combinatorial cost function based on the updated variable value. Thus, the updated variable value may be plugged into the combinatorial cost function and the combinatorial cost function may be evaluated.

At step <NUM>, the method <NUM> may further include, for each data pack, determining a transition probability using a Monte Carlo algorithm. For example, the Monte Carlo algorithm may be selected from the group consisting of simulated annealing, parallel tempering, and simulated quantum annealing. In some embodiments, the transition probability is based at least in part on a change in cost function value, relative to a previous value of the cost function, that occurs when the updated cost function value is determined based on the updated variable value. Additionally or alternatively, the transition probability may be determined based at least in part on a Boltzmann distribution.

At step <NUM>, the method <NUM> may further include storing the updated variable value and the updated cost function value with the transition probability. In embodiments in which the accelerator device includes DRAM, the updated variable value and the updated cost function value may be stored in the DRAM with the transition probability. Alternatively, the updated variable value may be stored in on-chip block RAM for enhanced computational speed. In embodiments in which the variable value and the cost function value are stored in on-board block RAM, the updated variable values and updated cost function values may be written to the on-board block RAM. When the updated variable value and the updated cost function value are stored, they may respectively replace previous values of the variable and the combinatorial cost function and may be used when processing one or more subsequent data packs. After the last data pack of the plurality of data packs is processed at the accelerator device, the method <NUM> may further include, at step <NUM>, outputting a final updated cost function value of the combinatorial cost function to the processor. A respective final variable value for one or more of the variables included in the combinatorial cost function may also be output to the processor.

<FIG> shows additional steps of the method <NUM> that may be performed in some embodiments. At step <NUM>, the method <NUM> may include determining an update order for the plurality of data packs. In some instances, determining the update order for the plurality of data packs may include, at step <NUM>, identifying at least a first set of one or more terms and a second set of one or more terms included in the combinatorial cost function, wherein the first set of one or more terms and the second set of one or more terms respectively include non-overlapping sets of variables. For example, step <NUM> may include performing an algorithm for determining graph connectivity on a representation of the combinatorial cost function as a cost function graph. In the cost function graph, each node may represent a variable. The cost function graph may have edges between each pair of nodes representing variables that occur together in at least one term. In embodiments in which step <NUM> is performed, step <NUM> may further include, at step <NUM>, setting the update order to include a first data pack stream in which the one or more terms of the first set are configured to be updated and a second data pack stream in which the one or more terms of the second set are configured to be updated. Thus, independent terms of the combinatorial cost function may be evaluated in parallel, which may improve evaluation speed.

In some instances, step <NUM> may include, at step <NUM>, determining that each term of the combinatorial cost function includes one or more variables that are included in at least one other term. In such instances, the combinatorial cost function is not separable into two or more sets of independent terms as in steps <NUM> and <NUM>. When step <NUM> is performed, step <NUM> may further include setting the update order to include a first plurality of data packs configured to update a first copy of the combinatorial cost function and a second plurality of data packs configured to update a second copy of the combinatorial cost function, the first plurality of data packs and the second plurality of data packs may be interspersed in the update order, for example, by alternating between data packs from the first plurality of data packs and the second plurality of data packs.

In embodiments in which step <NUM> is performed, the method <NUM> may further include, at step <NUM>, transmitting the plurality of data packs to the accelerator device in the update order.

<FIG> shows additional steps of the method <NUM> that may be performed in some embodiments. The steps of <FIG> may be performed for each data pack of the plurality of data packs. At step <NUM>, the method <NUM> may include generating a pseudorandom number. The pseudorandom number may be generated, in some embodiments, from a uniform probability distribution over an interval from <NUM> to <NUM>. The method may further include, at step <NUM>, determining the transition probability based at least in part on the updated cost function value. For example, when parallel tempering is used as the Monte Carlo algorithm, the transition probability is determined using a change in cost function value between iterations. At step <NUM>, the method <NUM> may further include storing the updated cost function value and the updated variable value for the variable indicated in the data pack in response to determining that the transition probability exceeds the pseudorandom number. In some embodiments, determining that the transition probability exceeds the pseudorandom number may include comparing a logarithm of the transition probability to a logarithm of the pseudorandom number rather than comparing the transition probability and the pseudorandom number directly.

Using the example computing devices and methods described herein, the efficiency of combinatorial cost function maximization and minimization may be improved. In tests performed by the inventors, speedups of <NUM> to <NUM> times have been achieved using the devices and methods described above, in comparison to existing systems and methods for combinatorial cost function optimization. Since combinatorial cost function optimization problems occur in a wide variety of applications, the devices and methods described herein may allow problems in many fields to be solved with greater computational efficiency.

Computing system <NUM> may embody the computing device <NUM> described above and illustrated in <FIG>. Computing system <NUM> may take the form of one or more personal computers, server computers, tablet computers, home-entertainment computers, network computing devices, gaming devices, mobile computing devices, mobile communication devices (e.g., smart phone), and/or other computing devices, and wearable computing devices such as smart wristwatches and head mounted augmented reality devices.

According to one aspect of the present disclosure, a computing device is provided, including memory storing instructions to compute a combinatorial cost function of a plurality of variables. The computing device may further comprise an accelerator device and a processor. The processor may be configured to generate a plurality of data packs, wherein each data pack indicates an update to a variable of the one or more variables, and transmit the plurality of data packs to the accelerator device. The accelerator device may be configured to, for each data pack, retrieve a variable value of the variable indicated by the data pack. The accelerator device may be further configured to generate an updated variable value of the variable as indicated by the data pack and generate an updated cost function value of the combinatorial cost function based on the updated variable value. The accelerator device may be further configured to determine a transition probability using a Monte Carlo algorithm and store the updated variable value and the updated cost function value with the transition probability. The accelerator device may be further configured to output a final updated cost function value of the combinatorial cost function to the processor.

According to this aspect, the processor may be further configured to determine an update order for the plurality of data packs. The processor may be further configured to transmit the plurality of data packs to the accelerator device in the update order.

According to this aspect, each data pack may indicate one or more terms of the combinatorial cost function in which the variable indicated in the data pack occurs.

According to this aspect, the processor may be further configured to identify at least a first set of one or more terms and a second set of one or more terms included in the combinatorial cost function, wherein the first set of one or more terms and the second set of one or more terms respectively include non-overlapping sets of variables. The processor may be further configured to set the update order to include a first data pack stream in which the one or more terms of the first set are configured to be updated and a second data pack stream in which the one or more terms of the second set are configured to be updated.

According to this aspect, the processor may be further configured to determine that each term of the combinatorial cost function includes one or more variables that are included in at least one other term. The processor may be further configured to set the update order to include a first plurality of data packs configured to update a first copy of the combinatorial cost function and a second plurality of data packs configured to update a second copy of the combinatorial cost function, wherein the first plurality of data packs and the second plurality of data packs are interspersed in the update order.

According to this aspect, the processor may be further configured to generate the plurality of data packs for an update step in which a respective data pack is generated for each variable of the plurality of variables.

According to this aspect, the computing device may further include on-board block random access memory (RAM). The accelerator device may include dynamic random-access memory (DRAM). The plurality of data packs may be written to the DRAM. For each data pack, the variable value may be retrieved from the on-board block RAM. The updated variable value and the updated cost function value may be stored in the on-board block RAM with the transition probability.

According to this aspect, the accelerator device is further configured to, for each data pack, generate a pseudorandom number. The accelerator device may be further configured to determine the transition probability based at least in part on the updated cost function value. The accelerator device may be further configured to store the updated cost function value and the updated variable value for the variable indicated in the data pack in response to determining that the transition probability exceeds the pseudorandom number.

According to this aspect, the Monte Carlo algorithm may be selected from the group consisting of simulated annealing, parallel tempering, simulated quantum annealing, and population annealing Monte Carlo.

According to this aspect, the accelerator device may be configured to determine the transition probability based at least in part on a Boltzmann distribution.

According to this aspect, the accelerator device may be selected from the group consisting of a field programmable gate array (FPGA), an application-specific integrated circuit (ASIC), a graphical processing unit (GPU), and a tensor processing unit (TPU).

According to another aspect of the present disclosure, a method for use with a computing device is provided. The method may include, at a processor, generating a plurality of data packs, wherein each data pack indicates an update to a variable of one or more variables of a combinatorial cost function. The method may further include transmitting the plurality of data packs to an accelerator device. The method may further include, at the accelerator device, for each data pack, retrieving a variable value of the variable indicated by the data pack. The method may further include generating an updated variable value of the variable as indicated by the data pack. The method may further include generating an updated cost function value of the combinatorial cost function based on the updated variable value. The method may further include determining a transition probability using a Monte Carlo algorithm. The method may further include storing the updated variable value and the updated cost function value with the transition probability. The method may further include outputting a final updated cost function value of the combinatorial cost function to the processor.

According to this aspect, the method may further include, at the processor, determining an update order for the plurality of data packs. The method may further include transmitting the plurality of data packs to the accelerator device in the update order.

According to this aspect, the method may further include, at the processor, identifying at least a first set of one or more terms and a second set of one or more terms included in the combinatorial cost function, wherein the first set of one or more terms and the second set of one or more terms respectively include non-overlapping sets of variables. The method may further include setting the update order to include a first data pack stream in which the one or more terms of the first set are configured to be updated and a second data pack stream in which the one or more terms of the second set are configured to be updated.

According to this aspect, the method may further include, at the processor, determining that each term of the combinatorial cost function includes one or more variables that are included in at least one other term. The method may further include setting the update order to include a first plurality of data packs configured to update a first copy of the combinatorial cost function and a second plurality of data packs configured to update a second copy of the combinatorial cost function, wherein the first plurality of data packs and the second plurality of data packs are interspersed in the update order.

According to this aspect, the plurality of data packs may be generated for an update step in which a respective data pack is generated for each variable of the plurality of variables.

According to this aspect, the method may further include, for each data pack, generating a pseudorandom number. The method may further include determining the transition probability based at least in part on the updated cost function value. The method may further include storing the updated cost function value and the updated variable value for the variable indicated in the data pack in response to determining that the transition probability exceeds the pseudorandom number.

According to this aspect, the Monte Carlo algorithm may be selected from the group consisting of simulated annealing, parallel tempering, and simulated quantum annealing.

According to another aspect of the present disclosure, a computing device is provided, including memory storing instructions to compute a combinatorial cost function of a plurality of variables. The computing device may further include an accelerator device and a processor. The processor may be configured to, for each variable of the plurality of variables, generate a respective plurality of data packs, wherein each data pack indicates an update to a variable of the one or more variables. For each plurality of data packs, the processor may be further configured to determine a respective update order. The processor may be further configured to transmit each plurality of data packs to the accelerator device in the update order determined for that plurality of data packs. The accelerator device may be configured to, for each data pack, retrieve a variable value of the variable indicated by the data pack. The accelerator device may be further configured to generate an updated variable value of the variable as indicated by the data pack. The accelerator device may be further configured to generate an updated cost function value of the combinatorial cost function based on the updated variable value. The accelerator device may be further configured to determine a transition probability using a transition probability algorithm. The accelerator device may be further configured to store the updated variable value and the updated cost function value with the transition probability. The accelerator device may be further configured to output a final updated cost function value of the combinatorial cost function to the processor.

Claim 1:
A computing device (<NUM>) comprising:
memory (<NUM>) storing instructions to compute a combinatorial cost function (<NUM>) of a plurality of variables (<NUM>);
an accelerator device (<NUM>); and
a processor (<NUM>) configured to:
generate a plurality of data packs (<NUM>), wherein each data pack indicates an update (<NUM>) to a variable of the one or more variables, wherein each data pack indicates one or more terms of the combinatorial cost function in which the variable indicated in the data pack occurs;
identify at least a first set of one or more terms and a second set of one or more terms included in the combinatorial cost function, wherein the first set of one or more terms and the second set of one or more terms respectively include non-overlapping sets of variables; and
set an update order to include a first data pack stream in which the one or more terms of the first set are configured to be updated and a second data pack stream in which the one or more terms of the second set are configured to be updated; and
transmit the plurality of data packs to the accelerator device (<NUM>) in the update order;
wherein the accelerator device (<NUM>) is configured to:
for each data pack:
retrieve a variable value (<NUM>) of the variable indicated by the data pack; and
generate an updated variable value (<NUM>) of the variable as indicated by the data pack;
generate an updated cost function value (<NUM>) of the combinatorial cost function based on the updated variable value;
determine a transition probability (<NUM>) using a Monte Carlo algorithm (<NUM>); and
store the updated variable value and the updated cost function value with the transition probability; and
output a final updated cost function value of the combinatorial cost function to the processor (<NUM>).