Optimization device and control method of optimization device

Patent metadata

Field	Value
Publication number	US-2020167635-A1
Application number	US-201916584994-A
Country	US
Kind code	A1
Filing date	Sep 27, 2019
Priority date	Nov 27, 2018
Publication date	May 28, 2020
Grant date	—

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 first 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 first value based on information of the Ising model and information about a target neuron, the number of the arithmetic processing circuits being smaller than the number of the neurons; a control circuit configured to: set, while causing a portion of the arithmetic processing circuits to perform the arithmetic process for a partial neuron group that is a portion of the neurons, information to be used for the arithmetic process for a first neuron among neurons other than the partial neuron group in a first arithmetic processing circuit among the arithmetic processing circuits, the arithmetic process of the first arithmetic processing circuit being inactivated; 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 value of the target neuron among 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 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 values of the neurons being the 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 configured to start the arithmetic process for the first neuron after updating a local field for the first neuron from an initial value based on update information and a weighting factor, the update information being information of neurons whose values are updated from initial values, the 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 configured to resume the arithmetic process for the first neuron after updating, based on update information and a 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 values are updated from values updated last before the previous arithmetic process for the first neuron is inactivated, the weighting factor indicating a magnitude of interaction between the first neuron and each of the neurons.

5 . A control method of an optimization device, the control method comprising:
holding, by each of arithmetic processing circuits included in the optimization device, a first 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 first value based on information of the Ising model and information about a target neuron, the number of the arithmetic processing circuits being smaller than the number of the neurons; setting by a control circuit included in the optimization device, while causing a portion of the arithmetic processing circuits to perform the arithmetic process for a partial neuron group that is a portion of the neurons, information to be used for the arithmetic process for a first neuron among neurons other than the partial neuron group in a first arithmetic processing circuit among the arithmetic processing circuits, the arithmetic process of the first arithmetic processing circuit being inactivated; 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 value of the target neuron among values of neurons held by the portion of the arithmetic processing circuits.

Assignees

• Fujitsu Ltd

Inventors

• Tsukamoto Sanroku
• Matsubara Satoshi

Classifications

• G06N3/08

  Learning methods · CPC title

• G06F7/588

  Random number generators, i.e. based on natural stochastic processes · CPC title

• G06N3/063 Primary

  using electronic means · CPC title

• G06N3/047

  Probabilistic or stochastic networks · CPC title

• G06N5/01

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