Optimization device and method of controlling optimization device

1. An optimization device, comprising:

M-stage (M is an integer of 2 or more) arithmetic processing circuits connected in a ring shape,

wherein each arithmetic processing circuit of the M-stage arithmetic processing circuits includes:

a determination circuit configured to

determine whether to permit updating for each of first bits based on information of an Ising model, a number of the first bits being obtained by dividing a number of second bits corresponding to all spins of the Ising model by M, the Ising model being obtained by converting an optimization problem;

a first selection circuit configured to:

select one update candidate bit from among update permission bits, for which updating is permitted, based on a determination result of the determination circuit; and

output identification information of the one update candidate bit;

a count circuit configured to

count a number of the update permission bits; and

a state update circuit configured to

update a value of any one of the second bits based on identification information supplied from a last stage arithmetic processing circuit of the M-stage arithmetic processing circuits to a top stage arithmetic processing circuit of the M-stage arithmetic processing circuits,

wherein each arithmetic processing circuit of the M-stage arithmetic processing circuits other than the top stage arithmetic processing circuit includes:

a second selection circuit configured to:

select first identification information output from the first selection circuit at a first probability obtained by dividing the number of the update permission bits by a sum of the number of the update permission bits and a number supplied from a previous stage arithmetic processing circuit; and

select second identification information supplied from the previous stage arithmetic processing circuit at a second probability obtained by subtracting the first probability from 1,

wherein the second selection circuit of the last stage arithmetic processing circuit is configured to

supply the selected identification information to the top stage arithmetic processing circuit,

wherein each of the second selection circuits other than the second selection circuit of the last stage arithmetic processing circuit is configured to

supply the selected identification information to a subsequent stage arithmetic processing circuit.

2. The optimization device according to claim 1 , wherein

the M-stage arithmetic processing circuits are connected to a control device configured to control the M-stage arithmetic processing circuits via a first bus, and are connected in a ring shape by a second bus whose communication speed is higher than a communication speed of the first bus, and

the M-stage arithmetic processing circuits use the second bus to transmit and receive the selected identification information.

3. The optimization device according to claim 1 , wherein

the first selection circuit includes:

a random number generation circuit configured to generate a random number value;

a selection signal generation circuit configured to generate a selection signal for selecting one of the update permission bits based on the random number value and the number of the update permission bits; and

a data selection circuit configured to output the identification information of the one update candidate bit based on the selection signal.

4. The optimization device according to claim 1 , wherein

the second selection circuit includes:

a selection signal generation circuit configured to generate a selection signal for selecting the first identification information at the first probability; and

a data selection circuit configured to output the selected identification information based on the selection signal.

5. A method of controlling an optimization device, the method comprising:

determining, by a determination circuit, whether to permit updating for each of first bits based on information of an Ising model, a number of the first bits being obtained by dividing a number of second bits corresponding to all spins of the Ising model by M, the Ising model being obtained by converting an optimization problem, the determination circuit being included in each arithmetic processing circuit of M-stage arithmetic processing circuits connected in a ring shape, the M-stage arithmetic processing circuits being included in the optimization device;

selecting, by a first selection circuit, one update candidate bit from among update permission bits, for which updating is permitted, based on a determination result of the determination circuit, the first selection circuit being included in each arithmetic processing circuit of the M-stage arithmetic processing circuits;

outputting, by the first selection circuit, identification information of the one update candidate bit;

counting, by a count circuit, a number of the update permission bits, the count circuit being included in each arithmetic processing circuit of the M-stage arithmetic processing circuits;

updating, by a state update circuit, a value of any one of the second bits based on identification information supplied from a last stage arithmetic processing circuit of the M-stage arithmetic processing circuits to a top stage arithmetic processing circuit of the M-stage arithmetic processing circuits, the state update circuit being included in each arithmetic processing circuit of the M-stage arithmetic processing circuits;

selecting, by a second selection circuit, first identification information output from the first selection circuit at a first probability obtained by dividing the number of the update permission bits by a sum of the number of the update permission bits and a number supplied from a previous stage arithmetic processing circuit, the second selection circuit being included in each arithmetic processing circuit of the M-stage arithmetic processing circuits other than the top stage arithmetic processing circuit;

selecting, by the second selection circuit, second identification information supplied from the previous stage arithmetic processing circuit at a second probability obtained by subtracting the first probability from 1;

supplying, by the second selection circuit of the last stage arithmetic processing circuit, the selected identification information to the top stage arithmetic processing circuit; and

supplying, by each of the second selection circuits other than the second selection circuit of the last stage arithmetic processing circuit, the selected identification information to a subsequent stage arithmetic processing circuit.