Optimization system and control method thereof

Patent metadata

Field	Value
Publication number	US-2020050921-A1
Application number	US-201916518103-A
Country	US
Kind code	A1
Filing date	Jul 22, 2019
Priority date	Aug 10, 2018
Publication date	Feb 13, 2020
Grant date	—

Abstract

Storage devices each hold corresponding one of n weight coefficient groups obtained by dividing weight coefficients such that each group includes weight coefficients about at least two bits. Bit value calculation circuits each output a result (flag information) by determining whether to accept updating about each of the bits based on the weight coefficient group, a value of an updated bit, identification information, and thermal excitation energy and an updated value of an accepted bit whose uprate has been accepted. First selection circuits each select an accepted bit based on the flag information and output a state signal including the flag information, the updated value, and identification information associated with the accepted bit. A second selection circuit determines the updated bit based on the flag information in the state signal and supplies the value of the updated bit and the identification information to each of optimization apparatuses.

First claim

What is claimed is:

1 . An optimization system comprising:
n (n is an integer of 2 or more) optimization apparatuses; and a second selection circuit, wherein each of the n optimization apparatuses includes: a storage device that holds corresponding one of n weight coefficient groups obtained by dividing a plurality of weight coefficients, each of which indicates a magnitude of an interaction between a pair of bits among all bits corresponding to all spins included in an Ising model obtained by converting a calculation target problem, in such a manner that each of the n weight coefficient groups includes weight coefficients about at least two bits; a bit value calculation circuit that calculates, for each of the at least two bits, an energy change of the Ising model that occurs when one of the at least two bits changes, based on the corresponding one of the n weight coefficient groups, a value of an updated bit that has been updated among all the bits, and first identification information that identifies the updated bit, determines whether to accept updating about each of the at least two bits based on a magnitude relationship between a thermal excitation energy determined based on a random number and a temperature parameter and the energy change, and outputs flag information that indicates a determination result of whether to accept the updating and an updated value of an accepted bit whose update has been accepted among the at least two bits; and a first selection circuit that selects one accepted bit based on the flag information and outputs a state signal that includes the flag information about the one accepted bit selected, the updated value, and second identification information that identifies the one accepted bit selected, wherein each of the n optimization apparatuses outputs the state signal based on the corresponding one of the n weight coefficient groups that differs among the n optimization apparatuses, and wherein the second selection circuit determines the updated bit based on the flag information included in the state signal outputted by the first selection circuit of each of the n optimization apparatuses and supplies the value of the updated bit and the first identification information that identifies the updated bit to the each of the n optimization apparatuses.

2 . The optimization system according to claim 1 ,
wherein the n is equal to or more than a number obtained by dividing a square of a number of all the bits by an upper limit of a number of weight coefficients storable by the storage device of each of the n optimization apparatuses, and wherein the storage device of each of the n optimization apparatuses holds the corresponding one of the n weight coefficient groups each including the weight coefficients about a number of bits, the number being obtained by dividing the number of all the bits by the n.

3 . The optimization system according to claim 1 ,
wherein the second selection circuit supplies the value of the updated bit and the first identification information to the first selection circuit of the each of the n optimization apparatuses via a first path arranged in the second selection circuit, and wherein the first selection circuit of the each of the n optimization apparatuses supplies the value of the updated bit and the first identification information supplied by the second selection circuit to the bit value calculation circuit included in the each of the n optimization apparatuses via a second path arranged in the first selection circuit of the each of the n optimization apparatuses.

4 . An optimization system control method comprising:
dividing, by a control apparatus, a plurality of weight coefficients into n (n is an integer of 2 or more) weight coefficient groups in such a manner that each of the n weight coefficient groups includes weight coefficients about at least two bits and storing corresponding one of the n weight coefficient groups in a storage device of each of n optimization apparatuses different each other in an optimization system, the plurality of weight coefficients each indicating a magnitude of an interaction between a pair of bits among all bits corresponding to all spins included in an Ising model obtained by converting a calculation target problem; and controlling, by the control apparatus, size of a temperature parameter on the optimization system, wherein the optimization system includes the n optimization apparatuses and a second selection circuit, wherein each of the n optimization apparatuses includes: the storage device that holds the corresponding one of the n weight coefficient groups obtained by dividing the plurality of weight coefficients; a bit value calculation circuit that calculates, for each of the at least two bits, an energy change of the Ising model that occurs when one of the at least two bits changes, based on the corresponding one of the n weight coefficient groups, a value of an updated bit that has been updated among all the bits, and first identification information that identifies the updated bit, determines whether to accept updating about each of the at least two bits based on a magnitude relationship between a thermal excitation energy determined based on a random number and the temperature parameter and the energy change, and outputs flag information that indicates a determination result of whether to accept the updating and an updated value of an accepted bit whose update has been accepted among the at least two bits; and a first selection circuit that selects one accepted bit based on the flag information and outputs a state signal that includes the flag information about the one accepted bit selected, the updated value, and second identification information that identifies the one accepted bit selected, wherein each of the n optimization apparatuses outputs the state signal based on the corresponding one of the n weight coefficient groups that differs among the n optimization apparatuses, and wherein the second selection circuit determines the updated bit based on the flag information included in the state signal outputted by the first selection circuit of each of the n optimization apparatuses and supplies the value of the updated bit and the first identification information that identifies the updated bit to the each of the n optimization apparatuses.

5 . A non-transitory computer-readable recording medium storing therein an optimization system controlling program that causes a computer to execute a process comprising:
dividing a plurality of weight coefficients into n (n is an integer of 2 or more) weight coefficient groups in such a manner that each of the n weight coefficient groups includes weight coefficients about at least two bits and storing corresponding one of the n weight coefficient groups in a storage device of each of n optimization apparatuses different each other in an optimization system, the plurality of weight coefficients each indicating a magnitude of an interaction between a pair of bits among all bits corresponding to all spins included in an Ising model obtained by converting a calculation target problem; and controlling size of a temperature parameter on the optimization system, wherein the optimization system includes the n optimization apparatuses and a second selection circuit, wherein each of the n optimization apparatuses includes: the storage device that holds the corresponding one of the n weight coefficient groups obtained by dividing the plurality of weight coefficients; a bit value calculation circuit that calculates, for each of the at least two bits, an energy change of the Ising model that occurs when one of the at least two bits changes, based on the corresponding one of the n weight coefficient groups, a value of an updated bit that has been updated among all the bi

Assignees

• Fujitsu Ltd

Inventors

• Tamura Hirotaka

Classifications

• G06N3/063

  using electronic means · CPC title

• G06N3/044 Primary

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

• G06N3/047

  Probabilistic or stochastic networks · CPC title

• G06N3/0445 Primary

  Physics · mapped topic

• G06N3/088 Primary

  Non-supervised learning, e.g. competitive learning · CPC title