Optimization device and control method of optimization device

Patent metadata

Field	Value
Publication number	US-11521049-B2
Application number	US-201916584994-A
Country	US
Kind code	B2
Filing date	Sep 27, 2019
Priority date	Nov 27, 2018
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

Abstract

An optimization device includes: processing circuits each configured to: hold a first value of a neuron of an Ising model; and perform a process to determine whether to permit updating of the first value based on information of the Ising model and information about a target neuron; a control circuit configured to: set, while causing a portion of the processing circuits to perform the process for a partial neuron group, information to be used for the process for a first neuron other than the partial neuron group in a first processing circuit; cause a second processing circuit among the portion of the processing circuits to inactivate the process; and cause the first processing circuit to start the process for the first neuron; and an update neuron selection circuit configured to: select the target neuron from one or more update permissible neurons; and update the value of the target neuron.

First claim

What is claimed is:

1. An optimization device comprising:
arithmetic processing circuits each configured to:
hold a bit value of a neuron for which an arithmetic process is to be performed, the neuron being one of neurons of an Ising model obtained by converting an optimization problem of a calculation target; and
perform the arithmetic process to determine whether to permit updating of the bit value based on a first weighting factor of the Ising model and a first bit value of a target neuron, the first weighting factor of the Ising model indicating a magnitude of interaction between the target neuron and each of the neurons, a total number of the arithmetic processing circuits being smaller than a total number of the neurons;
a control circuit configured to:
set, while causing a portion of the arithmetic processing circuits other than a first arithmetic processing circuit among the arithmetic processing circuits to perform the arithmetic process for a partial neuron group that is a portion of the neurons and the arithmetic process of the first arithmetic processing circuit is inactivated, a second bit value of a first neuron among the neurons other than the partial neuron group in the first arithmetic processing circuit;
cause a second arithmetic processing circuit among the portion of the arithmetic processing circuits to inactivate the arithmetic process; and
cause the first arithmetic processing circuit to start the arithmetic process for the first neuron; and

an update neuron selection circuit configured to:
select the target neuron from one or more update permissible neurons among the partial neuron group, the one or more update permissible neurons being determined to be permitted to be updated; and
update the first bit value of the target neuron among bit values of neurons held by the portion of the arithmetic processing circuits.

2. The optimization device according to claim 1 , wherein the control circuit is configured to cause the second arithmetic processing circuit to inactivate the arithmetic process after storing, in a memory, a local field and last bit values of the neurons, the local field being calculated by the second arithmetic processing circuit last before the second arithmetic processing circuit inactivates the arithmetic process, the last bit values of the neurons being bit values of the neurons updated last before the second arithmetic processing circuit inactivates the arithmetic process.

3. The optimization device according to claim 1 , wherein the first arithmetic processing circuit is further configured to start the arithmetic process for the first neuron after updating a local field for the first neuron from an initial bit value based on update information and a second weighting factor, the update information being information of neurons whose bit values are updated from initial bit values, the second weighting factor indicating a magnitude of interaction between the first neuron and each of the neurons.

4. The optimization device according to claim 1 , wherein the first arithmetic processing circuit is further configured to resume the arithmetic process for the first neuron after updating, based on update information and a second weighting factor, a local field calculated last before a previous arithmetic process for the first neuron is inactivated, the update information being information of neurons whose bit values are updated from bit values updated last before the previous arithmetic process for the first neuron is inactivated, the second weighting factor indicating a magnitude of interaction between the first neuron and each of the neurons.

5. The optimization device according to claim 1 , wherein
each of the arithmetic processing circuits is further configured to:
calculate a local field based on the first weighting factor of the Ising model and the first bit value of the target neuron, and
determine whether to permit updating of the bit value of the neuron based on the local field and the bit value of the neuron.

6. The optimization device according to claim 5 , wherein
each of the arithmetic processing circuits is further configured to:
update the bit value of the neuron when the local field is less than 0 and the bit value of the neuron is 1, and
update the bit value of neuron when the local field is greater than 0 and the bit value of the neuron is 0.

7. The optimization device according to claim 1 , wherein the update neuron selection circuit is further configured to, when the one or more update permissible neurons is a plurality of update permissible neurons, select the target neuron from the plurality of update permissible neurons based on a random number.

8. A control method of an optimization device, the control method comprising:
holding, by each of arithmetic processing circuits included in the optimization device, a bit value of a neuron for which an arithmetic process is to be performed, the neuron being one of neurons of an Ising model obtained by converting an optimization problem of a calculation target;
performing, by each of the arithmetic processing circuits, the arithmetic process to determine whether to permit updating of the bit value based on a first weighting factor of the Ising model and a first bit value of a target neuron, the first weighting factor of the Ising model indicating a magnitude of interaction between the target neuron and each of the neurons, a total number of the arithmetic processing circuits being smaller than a total number of the neurons;
setting, by a control circuit included in the optimization device, while causing a portion of the arithmetic processing circuits other than a first arithmetic processing circuit among the arithmetic processing circuits to perform the arithmetic process for a partial neuron group that is a portion of the neurons and the arithmetic process of the first arithmetic processing circuit is inactivated, a second bit value of a first neuron among the neurons other than the partial neuron group in the first arithmetic processing circuit;
causing, by the control circuit, a second arithmetic processing circuit among the portion of the arithmetic processing circuits to inactivate the arithmetic process; and
causing, by the control circuit, the first arithmetic processing circuit to start the arithmetic process for the first neuron;
selecting, by an update neuron selection circuit included in the optimization device, the target neuron from one or more update permissible neurons among the partial neuron group, the one or more update permissible neurons being determined to be permitted to be updated; and
updating, by the update neuron selection circuit, the first bit value of the target neuron among bit values of neurons held by the portion of the arithmetic processing circuits.

Assignees

• Fujitsu Ltd

Inventors

• Tsukamoto Sanroku
• Matsubara Satoshi

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N3/047

  Probabilistic or stochastic networks · CPC title

• G06N3/044

  Recurrent networks, e.g. Hopfield networks · CPC title

• G06N3/063 Primary

  using electronic means · CPC title

• G05B13/042 Primary

  in which a parameter or coefficient is automatically adjusted to optimise the performance · CPC title