18157339. ACCELERATOR FOR COMPUTING COMBINATORIAL COST FUNCTION simplified abstract (MICROSOFT TECHNOLOGY LICENSING, LLC)

ACCELERATOR FOR COMPUTING COMBINATORIAL COST FUNCTION

Organization Name

MICROSOFT TECHNOLOGY LICENSING, LLC

Inventor(s)

Matthias Troyer of Clyde Hill WA (US)

Helmut Gottfried Katzgraber of Kirkland WA (US)

Christopher Anand Pattison of College Station TX (US)

ACCELERATOR FOR COMPUTING COMBINATORIAL COST FUNCTION - A simplified explanation of the abstract

This abstract first appeared for US patent application 18157339 titled 'ACCELERATOR FOR COMPUTING COMBINATORIAL COST FUNCTION

Simplified Explanation

The patent application describes a computing device that includes memory, an accelerator device, and a processor. The device is designed to update variables in a combinatorial cost function using a Monte Carlo algorithm. Here are the key points:

• The processor generates data packs that indicate updates to variables in a combinatorial cost function.
• These data packs are transmitted to the accelerator device.
• The accelerator device retrieves the variable values indicated by the data packs and generates updated variable values.
• Based on the updated variable values, the accelerator device generates an updated cost function value.
• The accelerator device uses a Monte Carlo algorithm to determine a transition probability.
• The updated variable value, updated cost function value, and transition probability are stored by the accelerator device.
• Finally, the accelerator device outputs the final updated cost function value to the processor.

Potential applications of this technology:

• Optimization problems: This technology can be used to solve optimization problems where a combinatorial cost function needs to be updated and optimized.
• Machine learning: The Monte Carlo algorithm and variable updates can be applied to machine learning algorithms to improve their performance and accuracy.
• Simulation: The technology can be used in simulations that require frequent updates to variables and cost functions.

Problems solved by this technology:

• Efficient variable updates: The technology provides a way to efficiently update variables in a combinatorial cost function, reducing the computational burden.
• Improved optimization: By using a Monte Carlo algorithm, the technology can potentially find better solutions to optimization problems.
• Real-time updates: The technology allows for real-time updates to variables and cost functions, making it suitable for dynamic environments.

Benefits of this technology:

• Faster computation: The use of an accelerator device and efficient variable updates can significantly speed up the computation of the cost function.
• Improved accuracy: By using a Monte Carlo algorithm, the technology can potentially find more accurate solutions to optimization problems.
• Real-time optimization: The ability to update variables and cost functions in real-time allows for continuous optimization in dynamic environments.

Original Abstract Submitted

A computing device, including memory, an accelerator device, and a processor. The processor may generate a plurality of data packs that each indicate an update to a variable of one or more variables of a combinatorial cost function. The processor may transmit the plurality of data packs to the accelerator device. The accelerator device may, for each data pack, retrieve a variable value of the variable indicated by the data pack and generate an updated variable value. The accelerator device may generate an updated cost function value based on the updated variable value. The accelerator device may be further configured to determine a transition probability using a Monte Carlo algorithm and may store the updated variable value and the updated cost function value with the transition probability. The accelerator device may output a final updated cost function value to the processor.