JP7322308B2 - Circuit information, computing device, computing method and program - Google Patents

Description

The embodiments of the present invention relate to circuit information , computing devices, computing methods, and programs .

Various algorithms have been proposed to solve optimization problems using Ising models. Hardware that solves the optimization problem using the Ising model has also been proposed.

It is preferable that the hardware for solving such an optimization problem has a simple configuration and can solve the problem at high speed. Also, hardware that solves such optimization problems should preferably be able to handle a large number of variables. Moreover, hardware that solves such an optimization problem should preferably be able to cope with changes in the number of variables to be handled without any major design changes.

Japanese Patent No. 5865456 JP 2018-005541 A JP 2018-010474 A

T. Inagaki et al.,“A coherent Ising machine for 2000-node optimization problems”, Science 354, 603 (2016). H. Goto,“Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network”, Sci. Rep. 6, 21686 (2016). Y. Haribara et al., “Performance evaluation of coherent Ising machines against classical neural networks”, Quantum Sci. Technol. 2, 044002 (2017).

The problem to be solved by the invention is to solve the optimization problem with a simple configuration.

Circuit information according to the embodiment represents the configuration of a circuit described in a hardware description language. The circuit information causes the circuit to function as a computing device that solves an optimization problem using the Ising model. The computing device comprises a first variable memory, a second variable memory, a matrix multiplication unit, a time evolution unit, a management unit, and an output unit. The matrix multiplication unit performs matrix multiplication of N first intermediate variables (N is an integer equal to or greater than 2) at a first time and a coefficient matrix containing preset N rows×N columns of coefficients, Calculate N second intermediate variables at the first time. The time evolution unit generates N first variables at a second time after one sampling period from the first time and N variables at the second time based on the N second intermediate variables at the first time. N first variables at the second time are written into the first variable memory, and N second variables at the second time are written into the second variable memory. The management unit increases the time for each sampling period from the start time, and causes the matrix multiplication unit and the time evolution unit to execute processing for each time. The output unit outputs N first variables at a preset end time. The N first variables correspond to N spins in the Ising model . The N second variables correspond to the N spins. The N spins correspond to N points. Each of the N first variables represents the position of the point corresponding to the corresponding spin among the N points. Each of the N second variables represents the momentum of the point corresponding to the corresponding spin among the N points. The N first intermediate variables correspond to the N first variables, and each of the N first intermediate variables is a corresponding first variable of the N first variables or the It is a value obtained by multiplying the corresponding first variable by a preset coefficient. The N second intermediate variables correspond to the N second variables.

1 is a configuration diagram of a computing device according to a first embodiment; FIG. 4 is a flow chart showing the flow of processing in a computing unit; The block diagram of the calculating part which concerns on 2nd Embodiment. FIG. 10 is a relational diagram of variables and coefficient matrices in the second embodiment; FIG. 4 is a diagram showing a first example of the configuration of a function calculation section; The figure which shows the 2nd example of a structure of a function calculating part. The figure which shows the 3rd example of a structure of a function calculating part. The figure which shows the 4th example of a structure of a function calculating part. FIG. 10 is a relational diagram of variables and coefficient matrices in the third embodiment; The block diagram of the matrix multiplication part which concerns on 3rd Embodiment. The figure which shows the example of implementation which concerns on 3rd Embodiment. FIG. 11 is a relationship diagram of variables and coefficient matrices in the fourth embodiment; FIG. 11 is a configuration diagram of a partitioned matrix multiplication unit according to the fourth embodiment; FIG. 11 is a relationship diagram of variables and coefficient matrices in the fifth embodiment; The block diagram of the sub-matrix multiplication part which concerns on 6th Embodiment. FIG. 4 is a diagram showing a partitioning matrix stored in a partitioning matrix memory; FIG. 4 shows sub-matrices sent to the multiply-accumulate unit; FIG. 4 is a configuration diagram of a multiplication-accumulation unit; The figure which shows the parameter and timing in 5th Embodiment. The block diagram of the time evolution part which concerns on 6th Embodiment. Timing chart of the first intermediate variable and the second intermediate variable.

Hereinafter, the computing device 10 according to the embodiment will be described in detail with reference to the drawings. The computing device 10 according to the embodiment aims to solve an optimization problem using an Ising model.

(Premise)
First, the premise of the processing executed in the computing device 10 will be described.

The energy E _Ising of the Ising model is represented by the following equation (1).

In equation (1), N represents the number of spins. s _i represents the state of the i-th spin. For example, s _i =±1. s _j represents the state of the j-th spin. For example, s _j =±1. i and j are integers of 0 or more and (N-1) or less.

In Equation (1), J _i,j is the coefficient in the i-th row and the j-th column included in the coefficient matrix J of N rows×N columns. J _i,j represents the interaction between the i-th spin and the j-th spin. The coefficient matrix J is, for example, a real symmetric matrix. A real symmetric matrix is a matrix whose diagonal elements are all zeros. h _i is the i-th coefficient contained in the N coefficient array. h _i represents an action applied solely to the i-th spin. The problem of searching for the spin state (ground state) that minimizes the energy E _Ising of the Ising model is called the Ising problem. A machine that solves the Ising problem may be called an Ising machine. The Ising machine receives coefficient matrices J and h, and calculates and outputs a ground state or an approximate solution with lower energy.

A classical model of a quantum bifurcation machine (hereinafter referred to as a classical bifurcation machine) has been proposed. The classical bifurcation machine calculates the optimum solution of equation (1) using the equations of motion represented by the simultaneous ordinary differential equations shown in equations (2), (3) and (4).

In formulas (2), (3) and (4), N represents the number of mass points and is an integer of 2 or more. N corresponds to the number of spins. x _i is a real number representing the position of the i-th mass point. _yi is a real number representing the momentum of the i-th mass point. i and j are integers from 0 to (N-1).

In equations (2), (3), and (4), J _i,j is the coefficient in the i-th row and the j-th column included in the predetermined coefficient matrix J including the coefficients in N rows and N columns. . The coefficient matrix J is, for example, a real symmetric matrix. h _i is the i-th coefficient included in a predetermined N coefficient array. In the formulas (2), (3) and (4), the h _i term may be omitted.

In equations (2), (3) and (4), D is a constant corresponding to detuning, for example. c is a constant. K is a constant corresponding to, for example, the Kerr coefficient. For example, D, c and K are predetermined.

In equations (2), (3) and (4), t represents time. p(t) is, for example, a function with t as a variable and is a pump rate. a(t) is a function with t as a variable. a(t) is represented, for example, by the following formula (5).

The classical branching machine increments t from zero to a sufficiently large value by minute increments and updates x _i and y _i using equations (2) and (3) every t. The classical branching machine then outputs the sign (±1) of the final value of x _i for sufficiently large t as the optimal solution for s _i . Thus, the classical bifurcation machine considers the Ising model to be a Hamiltonian dynamical system with H in Equations (2), (3), and (4) as the Hamiltonian.

Also, simulated annealing is known as a method for calculating the optimum solution of the Ising model. This method employs an iterative update algorithm. The sequential update algorithm selects multiple spins one by one and updates them sequentially. Such a sequential update algorithm is not suitable for parallel computation and is difficult to speed up.

On the other hand, an algorithm that solves the equation of motion of the classical bifurcation machine by the discrete solution method using a digital computer is conceivable. This algorithm can update multiple variables simultaneously, unlike simulated annealing.

However, the classical bifurcation machine had to perform matrix multiplication with the most computationally intensive coefficient matrix J to compute both x _i and y _i . In addition, the classical bifurcation machine solves the equations of motion expressed by equations (2), (3) and (4) by a discrete solution method (fourth-order Runge-Kutta method, etc.) with high computational cost. , had to solve. For this reason, the classical branching machine has an enormous amount of computation.

On the other hand, the computing device 10 according to the embodiment uses the equations of motion represented by the new simultaneous ordinary differential equations shown in the following equations (6), (7), and (8) to calculate the equation ( Calculate the optimal solution for 1).

In equations (6), (7) and (8), N, x _{i ,} y _i , i, j, J _{i, j , hi} , D, c, K, t, p(t) and a (t) is the same as in formulas (2) to (4).

The computing device 10 according to the embodiment increments t from zero to a sufficiently large value in small time increments, and updates x _i and y _i using equations (6) and (7) every time t. Then, the computing device 10 according to the embodiment outputs the sign (±1) of the final value of x _i when t is sufficiently large as the optimum solution of s _i . As described above, the computing device 10 according to the embodiment solves the Ising problem by simulating the time evolution of the Hamiltonian dynamical system, where H in Equation (8) is the Hamiltonian.

In equations (6), (7), and (8), matrix multiplication for the coefficient matrix J, which requires the largest amount of calculation, is included in equation (7) but not included in equation (6). Therefore, the computing device 10 according to the embodiment only needs to perform matrix multiplication on the coefficient matrix J, which requires the largest amount of calculation, for updating _yi , and does not need to perform it for updating _xi . . Also, p(t) is eliminated from the equation (6) for calculating the time differential value (dx _i /dt) of x _i . Therefore, the computing device 10 according to the embodiment can compute the optimum solution of the Ising model with a small amount of computation.

Also, Equation (6) for calculating the time differential value (dx _i /dt) of x _i includes y _i but does not include x _i . Also, Equation (7) for calculating the time differential value (dy _i /dt) of y _i includes x _i but does not include y _i .

That is, when using equations (6) and (7), x _i and y _i are separated from each other in the Hamiltonian. Therefore, the computing device 10 according to the embodiment can update x _i and y _i by applying a stable discrete solution method with a small amount of computation. For example, the computing device 10 according to the embodiment applies the symplectic Euler method or the like to update x _i and y _i . Therefore, the computing device 10 according to the embodiment can calculate the optimum solution of the optimization problem using the Ising model with a simple calculation and a simple configuration.

Further, the calculation device 10 according to the embodiment calculates the optimum solution of Equation (1) using the equations of motion represented by the new simultaneous ordinary differential equations shown in Equations (9) and (10) below. may

In equations (9) and (10), N, x _{i ,} y _i , i, j, J _i,j , _hi , D, c, K, t, p(t) and a(t) are This is similar to formulas (2) to (4). In formulas (9) and (10), n is an even number of 2 or more.

In this case, the computing device 10 according to the embodiment increments t from zero to a sufficiently large value in small time increments, and calculates x _i and y _i using equations (9) and (10) for each t. Update. Then, the computing device 10 according to the embodiment outputs the sign (±1) of the final value of x _i when t is sufficiently large as the optimum solution of s _i .

Here, the matrix multiplication for the coefficient matrix J, which requires the largest amount of calculation, is included in Equation (9) and not included in Equation (10). Therefore, even when using equations (9) and (10), the calculation device 10 according to the embodiment only needs to perform matrix multiplication on the coefficient matrix J, which requires the largest amount of calculation, to update _yi . , _xi for updating. Also, p(t) is eliminated from the equation (9) for calculating the time differential value (dx _i /dt) of x _i . Therefore, even when Equations (9) and (10) are used, the computing device 10 according to the embodiment can calculate the optimum solution of the optimization problem using the Ising model with a small amount of calculation.

Also, Equation (9) for calculating the time differential value (dx _i /dt) of x _i includes y _i but does not include x _i . Also, Equation (10) for calculating the time differential value (dy _i /dt) of y _i includes x _i but does not include y _i .

That is, x _i and y _i are separated from each other in the Hamiltonian also when using equations (9) and (10). Therefore, when using formulas (9) and (10), as in the case of using formulas (6) and (7), the computing device 10 according to the embodiment can achieve Optimal solutions for optimization problems using Ising models can be calculated.

(First embodiment)
A computing device 10 according to the first embodiment will be described. In the description of each embodiment, devices, blocks, or circuits having substantially the same functions and configurations as the devices, blocks, or circuits described so far are denoted by the same reference numerals, and detailed descriptions other than the differences are given. Description is omitted.

FIG. 1 is a diagram showing the configuration of a computing device 10 according to the first embodiment. Calculation device 10 calculates the optimum It is a device that solves the transformation problem.

The computing device 10 includes an arithmetic unit 20 , an input unit 22 , an output unit 24 and a setting unit 26 .

The arithmetic unit 20 is an arithmetic processing device that includes a processor such as one or more CPUs (Central Processing Units) and a memory. Further, the calculation unit 20 may be the circuit of the second embodiment or later.

The calculation unit 20 increases t, which is a parameter representing the sampling time, by minute time (dt) from the start time (for example, 0). At each sampling time, the calculation unit 20 uses the simultaneous ordinary differential equations shown in equations (6) and (7), or the simultaneous ordinary differential equations shown in equations (9) and (10). , N first variables x _i and N second variables y _i are updated. Then, the calculation unit 20 outputs N first variables x _i at the end time T, which is a predetermined sampling time.

The input unit 22 acquires the N first variables x _i and the N second variables y _i at the start time prior to the arithmetic processing by the arithmetic unit 20 and gives them to the arithmetic unit 20 . The N first variables x _i and the N second variables y _i at the start time may be, for example, values generated by random numbers, or preset values (for example, all 0 or all predetermined value).

The output unit 24 acquires the N first variables x _i at the end time T after the arithmetic processing by the arithmetic unit 20 is completed. Then, the output unit 24 outputs a value (eg, +1, −1) representing the sign of the N first variables x _i at the end time T as the optimum solution for the combination of the states of the N spins in the Ising model. do.

Before the arithmetic processing by the arithmetic unit 20, the setting unit 26 sets the simultaneous ordinary differential equations shown in the equations (6) and (7) and the simultaneous ordinary differential equations shown in the equations (9) and (10). Each parameter to be used is set for the calculation unit 20 . More specifically, the setting unit 26 sets N, J, h, D, c, K, p(t) and a(t).

N is an integer of 2 or more representing the number of first variables and second variables.
J is a coefficient matrix of N rows×N columns. J _i,j is the coefficient in the i-th row and the j-th column included in the coefficient matrix J.
h is a coefficient array containing N coefficients. h _i is the ith coefficient in the coefficient array h.
D, c, K are constants.
p(t) is a function with the sampling time as a variable.
a(t) is a function with the sampling time as a variable.

Further, the setting unit 26 may set dt, T and M.
dt is a constant representing a sampling period (minute time).
T is a constant representing the sampling time corresponding to the end time.
M is an integer of 1 or more representing the number of repetitions of the calculations of formulas (6) and (7) or the number of repetitions of the calculations of formulas (9) and (10).

Note that the setting unit 26 may arbitrarily change some of these parameters according to user operations. Also, the setting unit 26 may set these parameters to fixed values without changing them for each calculation.

FIG. 2 is a flow chart showing the processing flow of the computing unit 20. As shown in FIG.

First, in S11, the calculation unit 20 initializes t, p and a. For example, the computing unit 20 sets t, p and a to all zero. t is a parameter representing sampling time. p is a parameter representing the value of p(t) at time t. a is a parameter representing the value of a(t) at time t.

Subsequently, the calculation unit 20 repeats the processing from S13 to S20 until t becomes equal to or greater than the preset end time T (loop processing between S12 and S21). Note that when a(t) is an increasing function, the calculation unit 20 may repeat the processing from S13 to S20 until a becomes equal to or greater than a predetermined value.

In S13, the calculation unit 20 multiplies each of the N first variables x _i by the sampling period (minute time) dt and a preset coefficient c to obtain N first intermediate variables x _i ' is calculated. That is, in S13, the calculation unit 20 executes the calculation of the following formula (21).
x _i ′=dt×c×x _i (21)

Subsequently, in S14, the calculation unit 20 multiplies the N first intermediate variables x _i ' by a coefficient matrix J including preset coefficients of N rows×N columns to obtain N A second intermediate variable b _i is calculated. That is, in S14, the calculation unit 20 executes the calculation of the following formula (22).

Note that the calculation unit 20 may execute the process of S13 after executing the process of S14. In this case, in S14, the calculation unit 20 performs matrix multiplication of the N first variables _xi and the coefficient matrix J to calculate N values. Subsequently, in S13, the calculation unit 20 calculates N second intermediate variables b _i by multiplying each of the N values calculated in S14 by (dt×c).

Subsequently, in S15, the calculation unit 20 updates the N second variables _yi by adding the corresponding second intermediate variables _bi to each of the N second variables _yi . That is, in S15, the calculation unit 20 executes the calculation of the following formula (23).
y _i +=b _i (23)

Subsequently, the calculation unit 20 repeats the processing from S17 to S18 M times (loop processing between S16 and S19). Note that M is an integer of 1 or more.

In S17, the computation unit 20 updates the second variable _yi by performing computation according to Equation (7) or Equation (10). For example, in S17, the calculation unit 20 executes the calculation of the following formula (24) when executing the calculation according to the formula (7).
y _i +=dt′×[(−D+p−Kx _i ² )x _i −c×h _i ×a] (24)

Further, for example, in S17, the calculation unit 20 executes the calculation of the following formula (25) when executing the calculation according to the formula (10). In addition, in Formula (25), n is an even number of 2 or more.
y _i +=dt′×{[(−D+p)(1+x _i ⁿ )−K _{x i} ⁿ⁺² ]x _i −c×h _i ×a} (25)

Subsequently, in S18, the calculation unit 20 updates the first variable _xi by executing the calculation according to Equation (6) or Equation (9). Note that equations (6) and (9) are the same equation. For example, in S18, the calculation unit 20 executes the calculation of the following formula (26) when executing the calculation according to the formula (6) or the formula (9).
x _i +=dt′×D×y _i (26)

The loop processing from S16 to S19 corresponds to repeated calculations in the symplectic Euler method. Note that the calculation unit 20 may perform the processing of S17 and the processing of S18 in reverse. That is, the calculation unit 20 may update the second variable _yi after updating the first variable _xi .

After executing the loop processing from S16 to S19, the calculation unit 20 advances the processing to S20. In S20, the calculation unit 20 updates t by adding dt to t. Furthermore, the calculation unit 20 updates p and a. For example, the calculation unit 20 updates p by adding a preset dp to p. Further, the calculation unit 20 updates a by calculating the square root of p after updating.

After executing the process of S20, the calculation unit 20 determines whether or not t has become T or more. If t is smaller than T, the calculation unit 20 returns the process to S13 and repeats the process from S13. When t becomes equal to or greater than T, the calculation unit 20 terminates this flow.

By executing the processing as described above, the computing device 10 according to the first embodiment converts the simultaneous ordinary differential equations represented by the equations (6) and (7), or the equations (9) and (10) into The optimization problem can be solved using the system of ordinary differential equations shown. According to the computing device 10 according to the first embodiment, the first variable x _i and the second variable y _i can be updated at high speed with a simple calculation or a simple configuration. Therefore, according to the computing device 10 according to the first embodiment, it is possible to calculate the optimum solution of the optimization problem at low cost and at high speed.

(Second embodiment)
A computing device 10 according to the second embodiment will be described.

FIG. 3 is a diagram showing the configuration of the calculation unit 20 according to the second embodiment. In the second embodiment, computing device 10 is a circuit realized by one or more semiconductor devices. Computing device 10 may be, for example, an FPGA (Field Programmable Gate Array), a gate array, an application specific integrated circuit (ASIC), or the like. Also, the computing device 10 may partially include a processor.

The calculation unit 20 according to the second embodiment includes a matrix multiplication unit 28, a time evolution unit 30, and a management unit 32.

The matrix multiplication unit 28 acquires from the time evolution unit 30 N first intermediate variables x _i '(t ₁ ) at a first time t ₁ representing an arbitrary sampling time. The matrix multiplication unit 28 performs matrix multiplication of the N first intermediate variables x _i '(t ₁ ) at the first time t ₁ and the coefficient matrix _J to obtain N second Compute the intermediate variables b _i (t ₁ ).

For example, the matrix multiplication section 28 has a coefficient matrix memory 36 and a matrix multiplication execution section 38 . A coefficient matrix memory 36 stores a coefficient matrix J. FIG. The matrix multiplication execution unit 38 performs matrix multiplication of the coefficient matrix J and the N first intermediate variables x _i '(t ₁ ) at the first time t ₁ .

The time evolution unit 30 acquires the N second intermediate variables b _i (t ₁ ) at the first time t ₁ from the matrix multiplication unit 28 . Based on _the N second intermediate variables b _i (t ₁ ) at the first time t ₁ , the time evolution unit ₃₀ calculates N first variables x _i (t ₂ ), N second variables y _i (t ₂ ) at the second time t ₂ and N first intermediate variables x _i ′(t ₂ ) at the second time t ₂ ) is calculated.

The management unit 32 increases the sampling time for each sampling period from the start time. Then, the management unit 32 causes the matrix multiplication unit 28 and the time evolution unit 30 to execute processing for each sampling time.

That is, the management unit 32 causes, for example, the matrix multiplication unit 28 to calculate N second intermediate variables b _i (t ₁ ) at the first time t ₁ . Subsequently, the management unit 32 provides the time evolution unit 30 with N first variables x _i (t ₂ ), N second variables y i (t ₂ ), and N second variables y _i (t ₂ ) at the second time t 2 . 1 Intermediate variables x _i '(t ₂ ) are calculated. Subsequently, the management unit 32 causes the matrix multiplication unit 28 to calculate N second intermediate variables b _i (t ₂ ) at the second time t ₂ . Subsequently, the management unit 32 provides the time evolution unit 30 with N first variables x _i (t ₃ ) at a third time t ₃ representing a sampling time after one sampling period from the second time t ₂ , N second variables y _i (t ₃ ) and N first intermediate variables x _i '(t ₃ ). In this way, the management unit 32 causes the matrix multiplication unit 28 and the time evolution unit 30 to alternately execute processing while increasing the sampling time.

Note that the N first variables x _i (t ₀ ) and the N second variables y _i (t ₀ ) at the start time (for example, t ₀ ) are previously calculated by the input unit 22, for example, prior to the arithmetic processing. Given.

For example, the time evolution unit 30 includes a first variable memory 40, a second variable memory 42, a first addition unit 44, a function operation unit 46, a first multiplication unit 48, and a first intermediate variable memory 50. have.

The first variable memory 40 stores N first variables x _i (t ₁ ) at the first time t ₁ . The second variable memory 42 stores N second variables y _i (t ₁ ) at the first time t ₁ .

The first adder 44 acquires the N second intermediate variables b _i (t ₁ ) at the first time t ₁ calculated by the matrix multiplier 28 . _The first _{adder 44} adds the N second intermediate _variables b Update the N second variables _{y i (} t ₁ ) at the first time t ₁ by adding i (t ₁ ). For example, the first adder 44 converts the second variable y ₀ (t ₁ ) of the top _index (i=0) to the second variable y N−1 (t 1 ) of the last index (i=N ₋ 1). ), update the N second variables y _i (t ₁ ) in index order.

In the embodiment, adding N first values and N second values means generating N third values by adding values of the same index.

The function calculation unit 46 calculates the N first variables x _i (t ₁ ) at the first time t ₁ stored in the first variable memory ₄₀ and N first variables x _i (t ₂ ) at the second time t ₂ and N second variables _y at the second time t ₂ based on the updated N second variables y i (t ₁ ) Calculate _i (t ₂ ). For example, the function operation unit 46 converts the first variable x ₀ (t ₂ ) and the second variable y ₀ (t ₂ ) of the top index (i=0) to the last index (i=N-1). N first variables x _i (t ₂ ) and N second variables y i (t ₂ ), in _index order, up to one variable x _N−1 (t ₂ ) and a second variable y N−1 (t 2 _{) 2} ) is calculated.

The function calculator 46 writes the N first variables x _i (t ₂ ) at the second time t ₂ to the first variable memory 40 . For example, the function operation unit 46 sequentially calculates each of the N first variables x _i (t ₂ ) at the second time t ₂ from the first variable x ₀ (t ₂ ) of the leading index (i=0). to the first variable memory 40. The first variable memory 40 is, for example, a dual port memory, and can write data to another address while reading data from a certain address. When the first variable memory 40 is a dual port memory, the function operation unit 46 converts the N first variables x i (t 2 ) at the second time t ₂ to the N first variables x _i (t ₂ ) at the first time t ₁ . The address at which the variable x _i (t ₁ ) was stored can be overwritten.

The function calculator 46 writes the N second variables y _i (t ₂ ) at the second time t ₂ to the second variable memory 42 . For example, the function operation unit 46 stores each of the N second variables y _i (t ₂ ) at the second time t ₂ in the second variable memory sequentially from the second variable y ₀ (t ₂ ) at the top index. Write to 42. The second variable memory 42 is, for example, a dual port memory. When the second variable memory 42 is a dual port memory, the function operation unit 46 converts the N second variables y i (t 2 ) at the second time t ₂ to the N second variables y _i (t ₂ ) at the first time t _{1 .} The address at which the variable y _i (t ₁ ) was stored can be overwritten.

The first multiplier 48 multiplies each of the N first variables x _i (t ₂ ) at the second time t ₂ by a preset value ((dt×c) in this embodiment). to calculate N first intermediate variables x _i ^' (t ₂ ) at the second time t ₂ . The first intermediate variable memory 50 stores N first intermediate variables x _i '(t ₂ ) at the second time t ₂ calculated by the first multiplier 48 . Note that the N first intermediate variables x _i '(t ₂ ) at the second time t ₂ are temporarily stored in the first intermediate variable memory 50 and then sent to the matrix multiplier 28 . The first intermediate variable memory 50 transmits each of the N first intermediate variables x _i '(t ₂ ) at the second time t ₂ to the matrix multiplier 28 after being generated by the first multiplier 48 . retained until The first intermediate variable memory 50 may include, for example, a FIFO (First In First Out) memory.

With such a configuration, the matrix multiplication unit 28 executes the processing of S14 described in the first embodiment. Also, the first addition unit 44 executes the process of S15. The function calculator 46 executes the processes from S16 to S19. Also, the first multiplier 48 executes the process of S13. The management unit 32 also manages S11, S20, and loop processing between S12 and S21. Therefore, according to the calculation unit 20 according to the second embodiment, the optimum solution of the optimization problem can be calculated at low cost and at high speed, as in the first embodiment.

Note that the first multiplication section 48 may be provided before the first addition section 44 instead of before the first intermediate variable memory 50 . This arrangement change corresponds to the process in which the processes of S13 and S14 in the first embodiment are reversed. However, when the value ((dt× _c ) in this embodiment) to be multiplied by each of the N first variables x _i (t ₂ ) at the second time t 2 is smaller than 1, the first multiplier 48 is preferably provided in the preceding stage of the first intermediate variable memory 50 . As a result, the first multiplier 48 reduces the number of digits of the N first intermediate variables x _i '(t ₂ ) at the second time t ₂ to reduce the probability of overflow in the matrix multiplier 28. be able to.

When the first multiplication unit 48 is provided before the first addition unit ₄₄ , the first intermediate variable memory 50 stores the N first variables x _i (t ₂ ) at the second time t 2 as Store as N first intermediate variables x _i '(t ₂ ) at t ₂ . Also, in this case _, the first multiplier 48 _assigns preset values ( _dt xc). In this case, the first addition unit 44 multiplies the N second variables y _i (t ₁ ) at the first time t ₁ by the value (dt×c) preset by the first multiplication unit 48 . N second variables y i ₍ t ₁ ) at the first time t ₁ are updated by adding the N second intermediate variables b _i (t ₁ ) at the first time t ₁ .

Also, the time evolution unit 30 converts the N first intermediate variables x _i '(t ₁ ) at the first time t ₁ to a first number (the first number is an integer equal to or greater than 1) in one clock cycle. It may be output to the matrix multiplier 28 as a first intermediate stream X' containing intermediate variables x _i '(t ₁ ). Also, the matrix multiplication unit 28 multiplies the N second intermediate variables b _i (t ₁ ) at the first time t ₁ by the second intermediate variables of a second number (the second number is an integer equal to or greater than 1) in one clock cycle. It may be output to the time evolution unit 30 as a second intermediate stream B including variables b _i (t ₁ ).

Here, a stream refers to time-series data. More specifically, a stream divides N pieces of data into, for example, P pieces of data sets each (P is an integer of 1 or more), and a data string containing P pieces of data sets is generated for each clock cycle. say.

When acquiring such a stream, the matrix multiplying unit 28 and the time evolution unit 30 sequentially process the data sets acquired earlier. This allows the matrix multiplication unit 28 and the time evolution unit 30 to start processing before all the data included in the stream have been acquired. Also, when the calculation of the leading data set of the N pieces of data is completed, the matrix multiplication unit 28 and the time evolution unit 30 sequentially start transmission from the data set for which the calculation has been completed. This allows the matrix multiplication section 28 and the time evolution section 30 to cause the next unit to start processing before the calculation of all data is completed.

FIG. 4 is a diagram showing the relationship among the N first intermediate variables x _i ', the coefficient matrix J, and the N second intermediate variables b _i in the second embodiment. The matrix multiplication unit 28 acquires N first intermediate variables (x ₀ ′, x _{1 ′} , x ₂ ′, . . . , x _i ', . . . , x _N-1 ') at each sampling time. The matrix multiplication unit 28 also generates a coefficient matrix (J _0,0 , J _0,1 , J _0,2 , . . . , J _i ,j _{, . -1} ).

Then, the matrix multiplication unit 28 generates the N first intermediate variables (x ₀ ', x ₁ ', x ₂ ', ..., x _i ', ..., x _N-1 ') and the coefficient matrix (J _{0, 0} , J _0,1 , J _0,2 , _{. . .} , J i _{,j ,} . ₁ , b ₂ , . _. . , b _i , .

In the second embodiment, the matrix multiplication unit 28 may perform matrix multiplication by any process. Further, in the second embodiment, the matrix multiplication unit 28 may include, for example, a processor inside, and execute matrix multiplication by a program.

FIG. 5 is a diagram showing a first example of the configuration of the function calculator 46. As shown in FIG. The function calculation unit 46 according to the first example includes a first FX calculation unit 51-1, a first FX addition unit 52-1, a first FY calculation unit 53-1, and a first FY addition unit. 54-1.

The first FX calculation unit 51-1 performs the first function calculation (FX(x _i )) on each of the N first variables at the first time to generate N second differential values Calculate The first FX addition unit 52-1 combines the N second differential values calculated by the first FX calculation unit 51-1 and the N updated second variables calculated by the first addition unit 44. N second update values are calculated by adding .

The first FY calculation unit 53-1 performs a second function calculation (FY(y _i )) on each of the N second update values calculated by the first FX addition unit 52-1. , N first differential values are calculated. The first FY addition unit 54-1 adds the N first differential values calculated by the first FY calculation unit 53-1 and the N first variables at the first time, thereby obtaining N Calculate the first updated value of .

Then, the function calculator 46 provides the first variable memory 40 with the N first update values calculated by the first FY adder 54-1. The first variable memory 40 stores the N first update values calculated by the first FY adding section 54-1 as the N first variables at the second time.

Also, the function calculation unit 46 provides the second variable memory 42 with the N second update values calculated by the first FX addition unit 52-1. The second variable memory 42 stores the N second update values calculated by the first FX adding section 52-1 as N second variables at the second time.

Here, the first function operation is the operation of Equation (31) below.
FX(x _i )=dt′×[(−D+p−Kx _i ² )x _i −c×h _i ×a] (31)

Also, the second function is the calculation of the following equation (32).
FY(y _i )=dt′×D×y _i (32)

Also, the first function operation may be the operation of the following equation (33).
FX(x _i )=dt′×{[(−D+p)(1+x _i ⁿ )−K _{x i} ⁿ⁺² ]x _i −c×h _i ×a} (33)

In equations (31), (32) and (33), x _i is the i-th first variable among the N first variables at the first time, or the i-th first variable among the N first update values It is the i-th first update value. _yi is the i-th second variable of the updated N second variables calculated by the first adder 44 or the i-th second update value of the N second update values; is.

dt' is a minute time set in advance. D, c, and K are preset constants. h _i is a coefficient set for each i. p and a are values that increase at each sampling time according to a predetermined arithmetic expression.

The function calculation unit 46 having such a configuration of the first example can execute the loop processing from S16 to S19 in the first embodiment once in the order of S17→S18. As a result, the function computing unit 46 uses a method called the symplectic Euler method to time-evolve the N first variables and N second variables at the first time to obtain N first variables and N second variables in can be calculated.

Furthermore, the function calculation unit 46 according to the first example may realize calculation by pipeline processing. When executing pipeline processing, for example, the function operation unit 46 receives one variable pair including the first variable X _IN and the second variable Y _IN in index order for each clock cycle. Then, the function calculation unit 46 calculates one variable pair including the first variable X _OUT and the second variable Y _OUT after the calculation processing by performing calculation on the received variable pair.

Specifically, when executing pipeline processing, the function operation unit 46 includes two stages of X transfer registers 55-1 to 55-2, two stages of Y transfer registers 56-1 to 56-2, 1 It further has one X output register 57 and one Y output register 58 .

The first-stage X transfer register 55-1 acquires one first variable X _IN out of N first variables at the first time from the first variable memory 40 for each clock cycle, and acquires One first variable X _IN is held for one clock cycle period. The Y transfer register 56-1 of the first stage acquires one second variable Y _IN out of the N updated second variables calculated by the first adder 44 for each clock cycle. One second variable Y _IN is held for one clock cycle period. The X transfer register 55-1 at the first stage and the Y transfer register 56-1 at the first stage acquire one first variable and one second variable of the same index i in the same clock cycle. .

The first FX calculation unit 51-1 executes the first function calculation on the first variable _XIN stored in the first-stage X transfer register 55-1 for each clock cycle, thereby obtaining the first Calculate the second differential value. For each clock cycle, the first FX addition unit 52-1 stores the second differential value calculated in the clock cycle by the first FX calculation unit 51-1 in the first-stage Y transfer register 56-1. The second update value _{Y_1} is calculated by adding the second variable _{Y_IN} .

The second-stage X transfer register 55-2 acquires the first variable X IN held by the first-stage X transfer register 55-1 in the immediately preceding clock cycle, and stores the acquired first variable X _IN at each clock cycle. The variable X _IN is held for one clock cycle period. The Y transfer register 56-2 in the second stage acquires the second update value _Y1 calculated in the immediately preceding clock cycle by the first FX addition unit 52-1 for each clock cycle, and stores the acquired second update value Hold Y ₁ for one clock cycle.

The first FY calculation unit 53-1 executes the second function calculation on the second update value _Y1 stored in the Y transfer register 56-2 of the second stage for each clock cycle. A first differential value is calculated. For each clock cycle, the first FY addition unit 54-1 stores the first differential value calculated in the clock cycle by the first FY calculation unit 53-1 in the second-stage X transfer register 55-2. The first update value _{X_1} is calculated by adding the first variable _{X_IN} obtained.

For each clock cycle, the X output register 57 acquires the first updated value _X1 calculated by the first FY adder 54-1 in the immediately preceding clock cycle, and stores the acquired first updated value _X1 at the second time. is stored in the first variable memory 40 as one first variable X _{OUT in} .

The Y output register 58 acquires the second update value Y ₁ stored in the second stage Y transfer register 56-2 at each clock cycle, and converts the acquired second update value Y ₁ to 1 at the second time. are stored in the second variable memory 42 as two second variables Y _OUT .

By executing such pipeline processing, the function calculation unit 46 according to the first example can execute the following calculation for each clock cycle.

_Y1 =FX( _XIN )+ _YIN
X1 =FY( _Y1 )+ _XIN
Y _OUT = Y ₁
X _OUT =X ₁

The function operation unit 46 according to such a first example performs first function operation → FX addition → for variable pairs including one first variable X _IN and one second variable Y _IN with the same index i. A series of operation sets of second function operation→FY addition can be executed once. Furthermore, since the function calculation unit 46 according to the first example executes pipeline processing, it is possible to execute calculations in parallel on a plurality of variable pairs. As a result, the function calculation unit 46 according to the first example can complete calculations for N variable pairs in a short period of time.

FIG. 6 is a diagram showing a second example of the configuration of the function calculator 46. As shown in FIG. The function calculator 46 may have the configuration of the second example as shown in FIG. The function calculator 46 according to the second example has the same components as those of the first example, but the arrangement of each component is different. In describing the second example, components that operate in the same manner as in the first example are denoted by the same reference numerals, and detailed description thereof will be omitted except for differences.

The first FY calculation unit 53-1 performs a second function calculation (FY(y _i )) on each of the N updated second variables calculated by the first addition unit 44, thereby obtaining N Calculate the first differential values. The first FY addition unit 54-1 adds the N first differential values calculated by the first FY calculation unit 53-1 and the N first variables at the first time, thereby obtaining N Calculate the first updated value of .

The first FX calculation unit 51-1 performs a first function calculation (FX(x _i )) on each of the N first update values calculated by the first FY addition unit 54-1. to calculate N second differential values. The first FX adder 52-1 combines the N second differential values calculated by the first FX calculator 51-1 and the updated N second variables calculated by the first adder 44. N second update values are calculated by adding .

The function calculation unit 46 having such a configuration of the second example can execute the loop processing from S16 to S19 in the first embodiment once in the order of S18→S17. As a result, the function computing unit 46 uses a method called the symplectic Euler method to time-evolve the N first variables and N second variables at the first time to obtain N first variables and N second variables in can be calculated.

Furthermore, the function calculation unit 46 according to the second example may realize calculation by pipeline processing. In this case as well, the function calculator 46 according to the second example has the same components as those of the first example, but the arrangement of the components is different.

The first FY calculation unit 53-1 executes a second function calculation on the updated second variable Y _IN stored in the Y transfer register 56-1 of the first stage at each clock cycle. Thus, the first differential value is calculated. For each clock cycle, the first FY addition unit 54-1 stores the first differential value calculated in the clock cycle by the first FY calculation unit 53-1 in the X transfer register 55-1 of the first stage. The first update value _{X_1} is calculated by adding the first variable _{X_IN} obtained.

The second-stage X transfer register 55-2 acquires the first update value _X1 calculated in the immediately preceding clock cycle by the first FY addition unit 54-1 for each clock cycle, and stores the acquired first update value Hold _X1 for one clock cycle. The second-stage Y transfer register 56-2 acquires the second _{variable Y_IN} held by the first-stage Y transfer register 56-1 in the immediately preceding clock cycle, and stores the acquired second variable Y_IN in each clock cycle. The variable _{Y_IN} is held for one clock cycle period.

The first FX calculation unit 51-1 executes the first function calculation on the first update value _X1 stored in the second-stage X transfer register 55-2 at each clock cycle. A second differential value is calculated. For each clock cycle, the first FX addition unit 52-1 stores the first differential value calculated in the clock cycle by the first FX calculation unit 51-1 in the second-stage Y transfer register 56-2. The second update value _{Y_1} is calculated by adding the second variable _{Y_IN} .

By executing such pipeline processing, the function calculation unit 46 according to the second example can execute the following calculation for each clock cycle.

_X1 =FY( _YIN )+ _XIN
Y1 =FX( _X1 )+ _YIN
X _OUT =X ₁
Y _OUT = Y ₁

The function operation unit 46 according to such a second example performs second function operation→FY addition→for variable pairs including one first variable X _IN and one second variable Y _IN of the same index i. A series of operation sets of first function operation→FX addition can be executed once. Furthermore, since the function calculation unit 46 according to the second example executes pipeline processing, it is possible to execute calculations in parallel on a plurality of variable pairs. As a result, the function calculation unit 46 according to the second example can complete calculations for N variable pairs in a short period of time.

FIG. 7 is a diagram showing a third example of the configuration of the function calculator 46. As shown in FIG. The function calculator 46 may have a configuration of a third example as shown in FIG. The function calculator 46 according to the third example has substantially the same configuration as that of the first example. In describing the third example, components that operate in the same manner as in the first example are denoted by the same reference numerals, and detailed description thereof will be omitted except for differences.

In addition to the configuration of the first example, the function calculation unit 46 according to the third example includes (M−1) FX calculation units 51-2 to 51 from second to Mth (M is an integer of 2 or more) -M, second to M-th (M-1) FX addition units 52-2 to 52-M, and second to M-th (M-1) FY operation units 53-2 53-M, and (M-1) second to M-th FY adders 54-2 to 54-M.

The m-th FX calculation unit 51-m (m is an arbitrary integer from 2 to M) calculates N first updates calculated by the (m-1)-th FY addition unit 54-(m-1) N second differential values are calculated by performing a first functional operation on each of the values. The m-th FX addition unit 52-m calculates the N second differential values calculated by the m-th FX calculation unit 51-m and the (m−1)th FX addition unit 52-(m−1) New N second update values are calculated by adding the N second update values.

The m-th FY calculation unit 53-m performs the second function calculation on each of the N second update values calculated by the m-th FX addition unit 52-m to obtain N first differential Calculate the value. The m-th FY addition unit 54-m calculates the N first differential values calculated by the m-th FY calculation unit 53-m and the (m−1)th FY addition unit 54-(m−1). New N first update values are calculated by adding the calculated N first update values.

Then, the function calculator 46 provides the first variable memory 40 with the N first update values calculated by the Mth FY adder 54-M. The first variable memory 40 stores the N first update values calculated by the M-th FY adding section 54-M as the N first variables at the second time.

Also, the function calculation unit 46 provides the second variable memory 42 with the N second update values calculated by the Mth FX addition unit 52-M. The second variable memory 42 stores the N second update values calculated by the M-th FX addition unit 52-M as N second variables at the second time.

The function calculation unit 46 having such a configuration of the third example can execute the loop processing from S16 to S19 in the first embodiment M times in the order of S17→S18. As a result, the function computing unit 46 uses a method called the symplectic Euler method to time-evolve the N first variables and N second variables at the first time to obtain N first variables and N second variables in can be calculated.

Furthermore, the function calculation unit 46 according to the third example may realize calculation by pipeline processing. In this case, the function operation unit 46 includes 2M stages of X transfer registers 55-1 to 55-2M, 2M stages of Y transfer registers 56-1 to 56-2M, one X output register 57, and one Y and an output register 58 . Of these configurations, the configuration shown in the first example operates in the same manner as the first example except for the X output register 57 and the Y output register 58. FIG.

The (2m−1)th stage X transfer register 55-(2m−1) is calculated in the immediately preceding clock cycle by the (m−1)th FY addition unit 54-(m−1) every clock cycle. A first update value X _m−1 is obtained, and the obtained first update value X _m−1 is held for one clock cycle. The (2m-1)th stage Y transfer register 56-(2m-1) is held by the (2m-2)th stage Y transfer register 56-(2m-2) in the immediately preceding clock cycle. The obtained second update value Y _{m−1 is} held for one clock cycle period.

For each clock cycle, the m-th FX calculation unit 51 _- m performs A second differential value is calculated by executing the first function operation. For each clock cycle, the m-th FX addition unit 52-m combines the second differential value calculated in the clock cycle by the m-th FX calculation unit 51-m with the (2m-1)th Y transfer register 56 A new second update value _Ym is calculated by adding the second update value _Ym-1 stored in -(2m-1).

The 2m-th stage X transfer register 55-2m updates the first update value X held by the (2m−1)th stage X transfer register 55-(2m−1) in the immediately preceding clock cycle. _m−1 , and holds one acquired first update value X _m−1 for one clock cycle period. The Y transfer register 56-2m of the 2mth stage acquires the second update value _Ym calculated in the immediately preceding clock cycle by the mth FX addition unit 52-m for each clock cycle, and stores the acquired second update value Hold _Ym for one clock cycle.

The m-th FY calculation unit 53-m executes the second function calculation on the second update value _Ym stored in the 2m-th stage Y transfer register 56-2m for each clock cycle, A first differential value is calculated. The m-th FY addition unit 54-m stores the first differential value calculated in the clock cycle by the m-th FY calculation unit 53-m in the 2m-th stage X transfer register 55-2m for each clock cycle. A new first update value X m is calculated by adding the calculated first update value X _{m −1} .

For each clock cycle, the X output register 57 acquires the first update value X _M calculated by the M-th FY addition unit 54-M in the immediately preceding clock cycle, and stores the acquired first update value X _M at the second time. is stored in the first variable memory 40 as one first variable X _{OUT in} .

The Y output register 58 acquires the second update value _YM stored in the Y transfer register 56-2M at the 2Mth stage every clock cycle, and converts the acquired second update value _YM to 1 at the second time. are stored in the second variable memory 42 as two second variables Y _OUT .

By executing such pipeline processing, the function calculation unit 46 according to the third example can execute the following calculations in each clock cycle.

_Y1 =FX( _XIN )+ _YIN
X1 =FY( _Y1 )+ _XIN
…
Y _m =FX(X _m−1 )+Y _m−1
Xm = FY( _Ym ) + Xm _-1
…
Y _M =FX(X _M−1 )+Y _M−1
XM = FY( _YM ) + XM _-1
YOUT = _YM
X _OUT =X _M

The function operation unit 46 according to such a third example performs first function operation→FX addition→for variable pairs including one first variable X _IN and one second variable Y _IN of the same index i. A series of operation sets of second function operation→FY addition can be executed M times. Furthermore, since the function calculation unit 46 according to the third example executes by pipeline processing, it is possible to execute calculations in parallel on a plurality of variable pairs. As a result, the function calculation unit 46 according to the third example can complete calculations for N variable pairs in a short period of time.

FIG. 8 is a diagram showing a fourth example of the configuration of the function calculator 46. As shown in FIG. The function calculator 46 may have the configuration of the fourth example as shown in FIG. The function calculator 46 according to the fourth example has substantially the same configuration as that of the second example. In describing the fourth example, components that operate in the same manner as in the second example are denoted by the same reference numerals, and detailed description thereof will be omitted except for differences.

The m-th FY calculation unit 53-m (m is an arbitrary integer from 2 to M) calculates N second updates calculated by the (m-1)-th FX addition unit 52-(m-1) N first differential values are calculated by performing a second function operation on each of the values. The m-th FY addition unit 54-m combines the N first differential values calculated by the m-th FY calculation unit 53-m with the N values calculated by the (m−1)th FY addition unit 54-m. N new first update values are calculated by adding the first update values.

The m-th FX calculation unit 51-m performs the first function calculation on each of the N first update values calculated by the m-th FY addition unit 54-m, thereby obtaining N second differential Calculate the value. The m-th FX addition unit 52-m calculates the N second differential values calculated by the m-th FX calculation unit 51-m and the (m−1)th FX addition unit 52-(m−1) New N second update values are calculated by adding the N second update values.

The function calculation unit 46 having such a configuration of the fourth example can execute the loop processing from S16 to S19 in the first embodiment M times in the order of S18→S17. As a result, the function computing unit 46 uses a method called the symplectic Euler method to time-evolve the N first variables and N second variables at the first time to obtain N first variables and N second variables in can be calculated.

Furthermore, the function computing unit 46 according to the fourth example may implement computation by pipeline processing. Also in this case, the function operation unit 46 includes 2M stages of X transfer registers 55-1 to 55-2M, 2M stages of Y transfer registers 56-1 to 56-2M, one X output register 57, and one and a Y output register 58 . Of these configurations, the configuration shown in the second example operates in the same manner as the second example except for the X output register 57 and the Y output register 58. FIG.

The (2m-1)th stage X transfer register 55-(2m-1) is held by the (2m-2)th stage X transfer register 55-(2m-2) in the immediately preceding clock cycle. The first update value X _m−1 that has been stored is acquired, and one acquired first update value X _m−1 is held for one clock cycle period. The (2m-1)th stage Y transfer register 56-(2m-1) calculates the A second update value Y _m−1 is acquired, and the acquired second update value Y _m−1 is held for one clock cycle.

For each clock cycle, the m-th FY calculation unit 53 _- m performs A first differential value is calculated by executing the second function operation. For each clock cycle, the m-th FY addition unit 54-m adds the first differential value calculated in the clock cycle by the m-th FY calculation unit 53-m to the X transfer register 55 of the (2m−1) stage A new first update value X _m is calculated by adding the first update value X _m−1 stored in −(2m−1).

The 2m-th stage X transfer register 55-2m acquires the first update value _Xm calculated in the immediately preceding clock cycle by the m-th FY addition unit 54-m, and stores the acquired first update value Xm in each clock cycle. Hold _Xm for one clock cycle. The 2m-th stage Y transfer register 56-2m updates the second update value Y held by the (2m−1)th stage Y transfer register 56-(2m−1) in the immediately preceding clock cycle. _m−1 , and holds one acquired second update value Y _m−1 for one clock cycle period.

The m-th FX calculation unit 51-m executes the first function calculation on the first update value _Xm stored in the 2m-th stage X transfer register 55-2m for each clock cycle, A second differential value is calculated. For each clock cycle, the m-th FX addition unit 52-m stores the second differential value calculated in the clock cycle by the m-th FX calculation unit 51-m in the Y transfer register 56-2m of the 2mth stage. A new second update value Y _m is calculated by adding the calculated second update value Y _m−1 .

The X output register 57 acquires the first update value _XM stored in the X transfer register 55-2M of the 2Mth stage every clock cycle, and converts the acquired first update value _XM to 1 at the second time. stored in the first variable memory 40 as two first variables X _OUT .

The Y output register 58 acquires the second update value _YM calculated in the immediately preceding clock cycle by the M-th FX addition unit 52-M for each clock cycle, and stores the acquired second update value _YM at the second time. is stored in the second variable memory 42 as one second variable Y _{OUT in} .

By executing such pipeline processing, the function calculation unit 46 according to the fourth example can execute the following calculations in each clock cycle.

_X1 =FY( _YIN )+ _XIN
Y1 =FX( _X1 )+ _YIN
…
X _m = FY(Y _m−1 )+X _m−1
Ym = FX( _Xm ) + _Ym-1
…
X _M = FY(Y _M−1 )+X _M−1
Y _M =FX(X _M )+Y _M−1
X _OUT =X _M
YOUT = _YM

The function calculation unit 46 according to such a fourth example performs second function calculation→FY addition→for variable pairs including one first variable X _IN and one second variable Y _IN of the same index i. A series of operation sets of first function operation→FX addition can be executed M times. Furthermore, since the function calculation unit 46 according to the fourth example executes by pipeline processing, it is possible to execute calculations on a plurality of variable pairs in parallel. As a result, the function calculation unit 46 according to the fourth example can complete calculations for N variable pairs in a short period of time.

(Third embodiment)
A computing device 10 according to the third embodiment will be described.

FIG. 9 is a diagram showing the relationship among the N first intermediate variables x _i ', the coefficient matrix J, and the N second intermediate variables b _i in the third embodiment.

The coefficient matrix J is divided into _Pr3 divided matrices (JG0, JG1, . . . JGk, . . . , JGPr3-1). Each of the P _r3 partition matrices contains (N/P _r3 ) rows by N columns of coefficients J _i,j . _Pr3 is a divisor of N. Also, k is an arbitrary integer from 0 to P _r3 −1.

Also, the N second intermediate variables b _i are divided into _Pr3 blocks (BG0, BG1, . . . BGk, . . . , BGPr3-1). Each of the P _r3 blocks contains (N/P _r3 ) second intermediate variables b _i . Furthermore, the _Pr3 blocks are mapped one-to-one to the _Pr3 partitioning matrices. For example, the kth block BGk corresponds to the kth partition matrix JGk.

In the third embodiment, the matrix multiplication unit 28 calculates P r ₃ blocks by matrix-multiplying the N first intermediate variables x _i ' and each of the Pr ₃ split matrices separately. .

FIG. 10 is a diagram showing the configuration of the matrix multiplication section 28 according to the third embodiment together with the time evolution section 30. As shown in FIG.

The matrix multiplication unit 28 has P _r 3 partitioned matrix multiplication units 60 that are associated one-to-one with the P _r 3 partitioned matrices. Each of the P _r3 partitioning matrix multiplication units 60 performs matrix multiplication of the N first intermediate variables x _i ′ and the corresponding partitioning matrix to obtain (N/P _r3 ) pieces included in the corresponding block. A second intermediate variable b _i of is calculated.

The Pr ₃ split matrix multipliers 60 have the same configuration. The Pr ₃ split matrix multiplication units 60 may be, for example, circuits implemented in different semiconductor devices.

Each of the _Pr3 split matrix multiplication units 60 generates a first intermediate stream X′ in which N first intermediate variables x _i ′ are streamed and a second intermediate stream X′ in which N second intermediate variables b _i are streamed. Receive stream B. Also, each of the _Pr3 split matrix multipliers 60 transmits the first intermediate stream X′ and the second intermediate stream B. FIG.

The Pr ₃ division matrix multipliers 60 are connected in series. The division matrix multiplier 60 at the top receives the first intermediate stream X′ from the time evolution unit 30 . Also, the division matrix multiplier 60 at the head receives dummy data as the second intermediate stream B. FIG. Dummy data may be transmitted from any block. The split matrix multipliers 60 other than the leading one receive the first intermediate stream X' and the second intermediate stream B transmitted from the split matrix multiplier 60 of the previous stage.

The split matrix multipliers 60 other than the last one transmit the first intermediate stream X' and the second intermediate stream B to the split matrix multiplier 60 in the immediately following stage. The division matrix multiplier 60 at the end transmits the second intermediate stream B to the time evolution unit 30 . The first intermediate stream X' transmitted from the last split matrix multiplier 60 is discarded. Note that the first intermediate stream X′ transmitted from the last division matrix multiplier 60 may be discarded in the time evolution section 30 after being received by the time evolution section 30 .

Each of the _Pr3 split matrix multiplication units 60 has a buffer unit 62 , a split matrix memory 64 , an execution unit 66 and a selector 68 .

The buffer unit 62 of the division matrix multiplication unit 60 at the head acquires the first intermediate stream X' output from the time evolution unit 30, stores the acquired first intermediate stream X' for a certain period of time, and outputs it. The buffer units 62 of the division matrix multiplication units 60 other than the head obtain the first intermediate stream X' output from the division matrix multiplication unit 60 of the immediately preceding stage, and store the obtained first intermediate stream X' for a certain period of time. Output.

The partitioning matrix memory 64 stores coefficients J _i,j of (N/P _r3 ) rows×N columns included in the corresponding partitioning matrix. Based on the first intermediate stream X′ stored in the buffer unit 62 and the partitioning matrix stored in the partitioning matrix memory 64, the execution unit 66 extracts (N/P _r3 ) second intermediate variables included in the corresponding block. Calculate b _i .

Here, the execution unit 66 converts the (N/P _r3 ) second intermediate variables b _i included in the corresponding block to a second intermediate stream containing P _r1 second intermediate variables b _i in one clock cycle. Output as B. _Pr1 is a divisor of N.

Furthermore, the execution unit 66 outputs the second intermediate stream B in a clock cycle different from that of the execution units 66 included in the other split matrix multiplication units 60 . Therefore, the second intermediate stream B is never output from a plurality of split matrix multipliers 60 in the same clock cycle.

The selector 68 of the top split matrix multiplication unit 60 outputs the second intermediate stream B from the execution unit 66 of the top split matrix multiplication unit 60 in the clock cycle in which the execution unit 66 of the top split matrix multiplication unit 60 outputs the second intermediate stream B. A second intermediate stream B is selected for output. Also, the selector 68 of the top split matrix multiplication unit 60 selects and outputs dummy data in the clock cycle when the execution unit 66 of the top split matrix multiplication unit 60 does not output the second intermediate stream B.

In addition, the selector 68 of the k-th divided matrix multiplication unit 60 excluding the head performs the k-th divided matrix multiplication in the clock cycle in which the execution unit 66 of the k-th divided matrix multiplication unit 60 outputs the second intermediate stream B. The second intermediate stream B output by the execution unit 66 of the unit 60 is selected and output. Further, in a clock cycle in which the execution unit 66 of the k-th divided matrix multiplication unit 60 does not output the second intermediate stream B, the second intermediate stream B output by the selector 68 of the preceding divided matrix multiplication unit 60 is selected. output.

FIG. 11 is a diagram showing an implementation example of the matrix multiplier 28 and the time evolution unit 30 according to the third embodiment.

The P _r 3 matrix multiplication units 28 and the time evolution unit 30 according to the third embodiment are, for example, (P _r3 +1) chips 70-1 to 70-(P _r3 +1), each of which is an independent semiconductor chip. ) can be implemented.

Each of the first to P _r3 -th chips 70 - 1 to 70 -P _r3 includes a split matrix multiplier 60 . The (P _r3 +1)th chip 70 −(P _r3 +1) includes the time evolution section 30 .

Each chip 70 also includes a receiver portion 74 and a transmitter portion 76 . The receiver 74 is a link port for data reception. The transmission unit 76 is a link port for data transmission. The receiving unit 74 and the transmitting unit 76 may be transmitting/receiving units that perform full-duplex communication. Each chip 70 may also include additional communication ports. For example, each chip 70 may include two independent receive link ports and two independent transmit link ports.

The transmission unit 76 synthesizes the first intermediate variable x _i ' and the second intermediate variable b _i for one clock cycle, and outputs a synthesized stream. If the bit width of the first intermediate stream X' is Wx' and the bit width of the second intermediate stream B is Wb, the composite stream has a bit width of Wx'+Wb or more.

Each of the receiver 74 and transmitter 76 includes, for example, a FIFO memory. The transmitter 76 combines the first intermediate stream X' and the second intermediate stream B and writes them into the FIFO. Then, the transmission unit 76 sequentially transmits the composite stream stored in the FIFO. Also, the receiving unit 74 writes the received composite stream into the FIFO. Then, the receiving unit 74 sequentially reads the combined stream from the FIFO and separates it into the first intermediate stream X' and the second intermediate stream B. FIG.

A connection is made between the two chips 70 via a communication link 72 . Output terminals of the first chip 70-1 are connected to input terminals of the second chip 70-2 via a first communication link 72-1. The output terminal of the kth chip 70-k is connected to the input terminal of the (k+1)th chip 70-(k+1) via the kth communication link 72-k. Then, the output terminal of the (P _r3 +1)th chip 70-(P _r3 +1) is connected to the input terminal of the first chip 70-1 to the (P _r3 +1)th communication link 72-(P _r3 +1) connected via Thus, the (P _r3 +1) chips 70-1 to 70-(P _r3 +1) are interconnected in a ring topology manner.

For example, the input and output terminals of chip 70 may be QSFP (Quad Small Form-factor Pluggable) ports. Also, the communication link 72 may be a QSFP compliant optical cable or a QSFP compliant metal cable. Also, the communication link 72 between the two chips 70 may be a high speed serial link, an Ethernet link or a peer-to-peer link.

In this embodiment, each chip 70 transmits/receives a composite stream, but the first intermediate stream X' and the second intermediate stream B may be transmitted/received separately. In this case, (P _r3 +1) chips 70-1 to 70-(P _r3 +1) are interconnected in a two-system ring topology.

Even if the number of the first variables x _i to be determined by the optimization problem is changed, the computing device 10 according to the third embodiment can cope with the change by changing the number of the partitioned matrix multipliers 60. can be done. Therefore, if the number of first variables x _i to be determined by the optimization problem increases significantly, the computing device 10 can cope with the problem by increasing the number of chips 70 having the same configuration, for example. Further, in the computing device 10, matrix operations are executed in parallel by a plurality of divided matrix multiplication units 60, so the optimization problem can be completed in a short period of time.

(Fourth embodiment)
A computing device 10 according to the fourth embodiment will be described.

FIG. 12 is a diagram showing the relationship among the N first intermediate variables x _i ', the coefficient matrix J, and the N second intermediate variables b _i in the fourth embodiment. In the fourth embodiment, the N first intermediate variables x _i ', the coefficient matrix J and the N second intermediate variables b _i have the same relationship as in the third embodiment, and furthermore, shown in FIG. There is a relationship like

The N first intermediate variables x _i ' are divided into N _s data sets. Each of the N _s data sets contains P _c first intermediate variables x _i ′. N _s and P _c are divisors of N. For example, N first intermediate variables x _i ' are divided into N _s data sets of x'b0, x'b1, ..., x'bNs.

Each of the P _r3 partitioned matrices is partitioned into P _r2 sub-matrices. Each of the P _r2 sub-matrices contains P _r1 rows by N columns of coefficients J _i,j . For example, the partitioning matrix of JG0 is partitioned into _Pr2 sub-matrices jb0, jb1, . . . , jbs, .

P _r1 and P _r2 are divisors of N, and P _r1 ×P _r2 ×P _r3 is N. s is any integer from 0 to P _r2 −1.

Each of the _Pr3 blocks contained in the N second intermediate variables b _i is divided into _Pr2 sub-blocks. Each of the P _r2 sub-blocks contains P _r1 second intermediate variables b _i . For example, a block of BG0 is divided into _Pr2 sub-blocks of bb0, bb1, . . . bbs, .

The _Pr2 sub-blocks included in the k-th block are in one-to-one correspondence with the _Pr2 sub-matrices included in the k-th partition matrix. For example, the s-th sub-block included in the k-th block BGk corresponds to the s-th sub-matrix jbs included in the k-th partition matrix JGk.

In the fourth embodiment, the split matrix multiplication unit 60 performs matrix multiplication with the N first intermediate variables x _i ' for each sub-matrix included in the corresponding split matrix. For example, the k-th division matrix multiplication unit 60 separately performs matrix multiplication between the N first intermediate variables x _i ' and each of the _Pr2 sub-matrices included in the k-th division matrix JGk. _Pr2 sub-blocks included in the k-th block BGk are calculated.

FIG. 13 is a diagram showing the configuration of the split matrix multiplier 60 according to the fourth embodiment. The execution unit 66 included in the split matrix multiplication unit 60 includes a _Pr2 sub-matrix multiplication unit 80 and a multiplexing unit 82 .

The P _r 2 sub-matrix multiplication units 80 are associated one-to-one with the P _{r 2} sub-matrices included in the corresponding divided matrix. For example, the _Pr2 sub-matrix multipliers 80 included in the partitioned matrix multiplier 60 associated with the k-th partitioned matrix correspond to the _Pr2 sub-matrices included in the k-th partitioned matrix on a one-to-one basis. Attached.

Each of the two P _r sub-matrix multiplication units 80 included in the k-th split matrix multiplication unit 60 performs matrix multiplication of the N first intermediate variables x _i ' and the corresponding sub-matrices to obtain the corresponding _Pr1 second intermediate variables b _i included in the sub-block to be calculated.

Also, each of the _Pr2 sub-matrix multiplication units 80 outputs the _Pr1 second intermediate variables b _i included in the corresponding sub-block in parallel in one clock cycle. For example, the s-th sub-matrix multiplication unit 80 included in the k-th split matrix multiplication unit 60 converts _Pr1 second intermediate variables b _i included in the s-th sub-block included in the k-th block to output on the same clock cycle.

Furthermore, each of the _Pr2 sub-matrix multipliers 80 outputs the _Pr1 second intermediate variables b _i in a different clock cycle than the other sub-matrix multipliers 80 . In other words, the second intermediate variable b _i is never output from a plurality of sub-matrix multipliers 80 in the same clock cycle.

The multiplexing unit 82 multiplexes the set of _Pr1 second intermediate variables b _i output from each of the _Pr2 sub-matrix multipliers 80, thereby generating _Pr1 second intermediate variables b i in one clock cycle. Generate a second intermediate stream B containing intermediate variables b _i . For example, the multiplexer 82 included in the k-th split matrix multiplier 60 outputs the second intermediate stream B including _Pr2 sub-blocks included in the k-th block in _Pr2 clock cycles.

The buffer unit 62 included in the partitioned matrix multiplying unit 60 includes a Pr _2- stage register 84 functioning as a shift register, an intra-buffer receiving unit 86 and an intra-buffer transmitting unit 88 .

The Pr _2- stage registers 84 are associated one-to-one with the Pr ₂ sub-matrix multipliers 80 . Each of the P _{r two-} stage registers 84 stores a data set containing P _c first intermediate variables x _i ′ for one clock cycle. Each of the P _{r two} -stage registers 84 transfers the stored data set containing the P _c first intermediate variables x _i ′ in parallel to the next-stage register 84 in the next clock cycle.

An in-buffer receiver 86 receives the first intermediate stream X' and converts the received first intermediate stream X' into a stream of _Pc words wide. Then, the intra-buffer receiving unit 86 writes a data set including P _c first intermediate variables x _i ′ to the head register 84 every clock cycle.

The intra-buffer transmission unit 88 reads out a data set including P _c first intermediate variables x _i ′ from the last-stage register 84 every clock cycle, and converts it into a first intermediate stream X′. Then, the intra-buffer transmission unit 88 transmits the first intermediate stream X'.

Each of the P _r 2 sub-matrix multipliers 80 reads out the data set containing the P _c first intermediate variables x _i ' stored in the corresponding register 84 every clock cycle. Each of the two P _r sub-matrix multiplication units 80 each of the read P _c first intermediate variables x _i ′ and the coefficient J _i,j of the corresponding column in the corresponding sub-matrix each clock cycle. Multiply with Each of the two P _r sub-matrix multiplication units 80 cumulatively adds the multiplication results of the first intermediate variable x _i ' and the coefficient J _i,j for each row included in the corresponding sub-matrix. As a result, each of the _Pr2 sub-matrix multipliers 80 can calculate the _Pr1 second intermediate variables b _i included in the corresponding sub-block.

Here, each of the _Pr2 sub-matrix multiplication units 80 stores the first intermediate variable x 0 ′ to the last intermediate variable x ₀ ′ among the N first intermediate variables x _i ′ in the corresponding register 84 . During the period before the variable x _N-1 ' is stored, multiplication and cumulative addition are performed. Then, each of the P _r2 sub-matrix multiplication units 80 performs the corresponding sub-block after a predetermined number of clock cycles have passed since the clock cycle when the last intermediate variable x _N−1 ′ was stored in the corresponding register 84. output _Pr1 second intermediate variables b _i contained in . Therefore, each of the _Pr2 sub-matrix multipliers 80 can output the _Pr1 second intermediate variables b _i included in the corresponding sub-block in different clock cycles.

The computing device 10 having such a configuration according to the fourth embodiment can perform matrix multiplication with a degree of parallelism of P _r3 ×P _r2 . As a result, the computing device 10 according to the fourth embodiment can execute matrix multiplication at high speed.

(Fifth embodiment)
A computing device 10 according to the fifth embodiment will be described.

FIG. 14 is a diagram showing the relationship among the N first intermediate variables x _i ', the coefficient matrix J, and the N second intermediate variables b _i in the fifth embodiment. In the fifth embodiment, the N first intermediate variables x _i ', the coefficient matrix J and the N second intermediate variables b _i have the same relationship as in the fourth embodiment, and furthermore, shown in FIG. There is a relationship like

Each of the P _r3 partitioned matrices is partitioned into P _r2 sub-matrices. Further, each of the P _r2 sub-matrices is divided into N _s coefficient sets by P _c columns. Each coefficient set contains _Pr1 rows by _Pc columns of coefficients J _i,j . For example, the sub-matrix of jb0 contained in the partitioning matrix of JG0 is partitioned into N _s coefficient sets jb0(0), jb0(1), . . . , jb0(N _s −1).

Also, the N _s coefficient sets correspond one-to-one to the N _s data sets obtained by dividing the N first intermediate variables x _i ′ into P _c pieces.

In the fifth embodiment, the sub-matrix multiplication unit 80 _calculates P c first intermediate variables x corresponding to P _c coefficients J _i,j for each of P _r1 rows included in one coefficient set. A multiplication accumulation value with _i ' is calculated. The sub-matrix multiplication unit 80 then adds all multiplication-accumulated values calculated for each of the N _s coefficient sets for each _Pr1 row. Thus, the sub-matrix multiplier 80 can multiply and accumulate the N coefficients J _i,j and the N first intermediate variables x _i ' for each of the _Pr1 rows.

FIG. 15 is a diagram showing the configuration of the sub-matrix multiplier 80 according to the sixth embodiment together with the corresponding register 84. As shown in FIG. Each sub-matrix multiplier 80 includes _Pr1 multiply-accumulate units 90 .

The _Pr1 multiply-accumulate units 90 are associated one-to-one with the _Pr1 rows contained in the corresponding sub-matrices. For example, the _Pr1 multiply-accumulate unit 90 associated with the s-th sub-matrix included in the partitioned matrix multiplier 60 associated with the k-th partitioned matrix is s _Pr1 rows included in the th sub-matrix are associated one-to-one.

All of the _Pr1 multiply-accumulate units 90 have the same configuration. Each of the _Pr1 multiply-accumulate units 90 multiply-accumulates the corresponding row in the coefficient matrix J with the N first intermediate variables x _i ' to obtain the corresponding Calculate a second intermediate variable b _i of the position. The _Pr1 multiply-accumulate units 90 compute the second intermediate variables _bi in parallel and output them in the same clock cycle.

More specifically, each of the _Pr1 multiply-accumulate units 90 stores the first intermediate variable at the beginning of the first intermediate stream X′ sequentially in the corresponding register 84 of the _Pr2- stage registers 84. From x ₀ ' to the last N first intermediate variables x _N-1 ' are obtained every clock cycle. In this case, each of the P _r1 multiply-accumulate units 90 acquires a data set containing P _c first intermediate variables x _i ′ in one clock cycle. Then, each of the P _r1 multiply-accumulate units 90 acquires N s data sets by executing the acquisition of data sets over N _s (N _s =N/P _{c )} clock cycles. . In addition, the p-th (p is an arbitrary integer from 0 to P _r1 −1) of the P _r1 multiply-accumulate units 90 converts the obtained data set into Obtain P _c coefficients ((jp, s0) to (jp, SPc-1)) contained in the p-th corresponding row contained in the corresponding coefficient set. Each of the P _r1 multiply-accumulate units 90 then acquires the corresponding P _c coefficients in the coefficient set over N _s clock cycles. Each of the _Pr1 multiply-accumulate units 90 generates _Pc first intermediate variables x _i ' and corresponding _Pc coefficients J _i,j contained in the corresponding row at each clock cycle. multiply and accumulate. Then, each of the _Pr1 multiply-accumulate units 90 calculates the second intermediate variable _bi by cumulatively adding the multiply-accumulate results over _Ns clock cycles.

FIG. 16 is a diagram showing the partitioning matrix stored in the partitioning matrix memory 64. As shown in FIG. The divided matrix memory 64 divides the divided matrix into _Pr2 sub-matrices and stores them. Each of the _Pr2 sub-matrices is output in parallel to the corresponding sub-matrix multiplier 80 .

Each of the P _r2 sub-matrices contains N _s coefficient sets. Each of the N _s coefficient sets contains P _c ×P _r1 coefficients. The split matrix memory 64 is capable of outputting in parallel P _c ×P _r1 coefficients included in one coefficient set for each of the P _r2 sub-matrices in one clock cycle.

FIG. 17 is a diagram showing _Pr1 multiply-accumulate units 90 included in one sub-matrix multiplying unit 80 and the sub-matrices transmitted to the sub-matrix multiplying units 80 .

Each of the P _r1 multiplication/accumulation units 90 included in one sub-matrix multiplication unit 80 receives P _c first intermediate variables x _i ' stored in the corresponding register 84 every clock cycle. The containing dataset is broadcast.

Partitioned matrix memory 64 contains N _s coefficient sets for each sub-matrix. In the divided matrix memory 64, one coefficient set included in each sub-matrix is specified by a pointer every clock cycle. More specifically, partitioned matrix memory 64 identifies the coefficient set corresponding to the data set stored in register 84 corresponding to that sub-matrix.

The split matrix memory 64 outputs in parallel P _c ×P _r1 coefficients included in the coefficient set specified by the pointer every clock cycle. Each of the P _c ×P _r1 coefficients included in the coefficient set has a predetermined multiplication-accumulation unit 90 as an output destination. The split matrix memory 64 outputs each of P _c ×P _r1 coefficients included in one coefficient set to a predetermined multiply-accumulate unit 90 . For example, P _c coefficients from the top to the P _c th coefficient in the coefficient set are output to the first multiply-accumulate unit 90 . Also, for example, P _c coefficients from (P _c +1) to (2×P _c ) are output to the second multiply-accumulate unit 90 . Also, the P _c coefficients from the (P _r1 −P _c )-th to the P _r1 -th are output to the P _r1 -th multiply-accumulate unit 90 .

FIG. 18 is a diagram showing the configuration of the multiply-accumulate unit 90. As shown in FIG. Multiply-accumulate unit 90 includes P _c multipliers 92 , an adder 94 , and an accumulator 96 . The multiply-accumulate unit 90 acquires a data set containing P _c first intermediate variables x _i ′ and a coefficient set containing P _c coefficients J _i,j for each clock cycle.

There is a one-to-one correspondence between the P _c first intermediate variables x _i ' included in the data set and the P _c coefficients J _i,j included in the coefficient set. Also, the P _c multipliers 92 correspond one-to-one to the P _c first intermediate variables x _i ' included in the data set and the P _c coefficients J _i,j included in the coefficient set. . Each of the P _c multipliers 92 multiplies a corresponding one first intermediate variable x _i ' contained in the data set with a corresponding one coefficient J _i,j contained in the coefficient set to Output the multiplied value. Each of the P _c multipliers 92 outputs a multiplied value every clock cycle.

The adder 94 calculates a multiplication-accumulated value by adding the P _c multiplied values output from the P _c multipliers 92 in each clock cycle. The accumulator 96 accumulatively adds the multiplication-accumulated values output from the adder 94 every clock cycle. Further, the accumulator 96 resets the cumulative addition value to 0 at the timing (S0=0) at which the leading first intermediate variable x ₀ ′ in the first intermediate stream X′ is stored in the corresponding register 84 . .

The multiply-accumulate unit 90 having such a configuration sequentially stores the first intermediate variable x 0 ′ to the last intermediate variable x ₀ ′ of the first intermediate stream X′, which are sequentially stored in the corresponding registers 84 of the Pr _2- stage registers 84 . N first intermediate variables x _i ' up to the first intermediate variable x _N-1 ' of are acquired every clock cycle. Further, the multiply-accumulate unit 90 calculates each of the obtained first intermediate variables x _i ' and the coefficients J i of the columns corresponding to the obtained first intermediate variables x _i ' included in the corresponding rows in the coefficient matrix _{J , j} . Then, the multiply-accumulate unit 90 multiplies the result of multiplication between the first intermediate variable x _i ' and the coefficient J _i,j from the first intermediate variable x ₀ ′ at the beginning of the first intermediate stream X′ to the first intermediate variable at the end. Cumulatively add up to the variable x _N-1 '. Through such processing, the multiply-accumulate unit 90 can calculate the second intermediate variable _bi at the corresponding position included in the corresponding sub-block.

FIG. 19 is a diagram showing an example of specific values of parameters and an example of processing timings in the fifth embodiment.

In the example of FIG. 19, N=16384. Also, in the example of FIG. 19, P _c =4 and N _S =4096. Also, in the example of FIG. 19, P _r1 =8, P _r2 =256, and P _r3 =8. 19, t0, t1, t2, . . . , t6143 represent the order of clock cycles.

The head data set in the N first intermediate variables x _i ' is stored in the head register 84 in the head matrix multiplier 28 at t0. Therefore, the leading coefficient set in the jb0 sub-matrix in the JG0 partition matrix is read at t0.

The data set at the end of the N first intermediate variables x _i ' is stored in the head register 84 in the head matrix multiplier 28 at t4095. Therefore, the last coefficient set in the jb0 sub-matrix in the JG0 partition matrix is read at t4095.

Then, the first block in the N second intermediate variables b _i can be output after the clock cycle (t4095) when the multiplication and accumulation of the last coefficient set in the jb0 submatrix in the JG0 division matrix is completed. . Therefore, the top block in the second intermediate variable b _i is output at t4095+α (α is a predetermined delay time).

The leading data set in the N first intermediate variables x _i ' is stored in the last register 84 in the last matrix multiplier 28 after being delayed (P _r1 ×P _r3 =2048) clock cycles from t0. . Therefore, the leading coefficient set in the sub-matrix of jbPr2-1 in the division matrix of JGPr3-1 is read at t2047.

Also, the last data set in the N first intermediate variables x _i ' is stored in the last register 84 in the last matrix multiplier 28 after being delayed (P _r1 ×P _r3 =2048) clock cycles from t4095. be done. Therefore, the last coefficient set in the jbPr2-1 sub-matrix in the JGPr3-1 partition matrix is read at t6143.

Then, after the clock cycle (t6143) when the multiplication and accumulation of the last coefficient set in the submatrix of jbPr2-1 in the division matrix of JGPr3-1 is completed, the last block in the N second intermediate variables b _{i is} Output is possible. Therefore, the last block in the second intermediate variable b _i is output at t6143+α.

The computing device 10 having such a configuration according to the fifth embodiment can perform matrix multiplication with a degree of parallelism of _Pr3 × _Pr2 × _Pr1 . As a result, the computing device 10 according to the fifth embodiment can perform matrix multiplication at high speed.

(Sixth embodiment)
A computing device 10 according to the sixth embodiment will be described.

FIG. 20 is a diagram showing the configuration of the time evolution section 30 according to the sixth embodiment together with a plurality of matrix multiplication sections 28. As shown in FIG. In the sixth embodiment, each matrix multiplier 28 outputs a second intermediate stream B containing _Pr1 second intermediate variables b _i in one clock cycle. Then, in the sixth embodiment, the time evolution unit 30 receives the second intermediate stream B containing _Pr1 second intermediate variables b _i in one clock cycle.

The time evolution unit 30 according to the sixth embodiment includes _Pr1 first variable memories 40, _Pr1 second variable memories 42, _Pr1 first addition units 44, and _Pr1 , _Pr1 first multipliers 48 and one first intermediate variable memory 50 .

Pr ₁ first variable memories 40, Pr ₁ second variable memories 42, Pr ₁ first addition units 44, Pr ₁ function operation units 46, and _Pr 1 first multiplication units 48 are There is a one-to-one correspondence with _Pr1 second intermediate variables b _i included in one clock cycle.

Then, each of the _Pr1 first addition units 44 and each of the _Pr1 function operation units 46 selects a corresponding one of the _Pr1 second intermediate variables b _i included in one clock cycle. Arithmetic processing is executed for the intermediate variable b _i . In addition, each of the _Pr1 first variable memories 40 and each of the _Pr1 second variable memories 42 correspond to one of the _Pr1 second intermediate variables b _i included in one clock cycle. A first variable x _i and a second variable _{y i} calculated using the two intermediate variables b i are stored. In addition, each of the _Pr1 first multipliers 48 is calculated using a corresponding one of the _Pr1 second intermediate variables _{b i} included in one clock cycle. Arithmetic processing is executed for one variable x _i .

In this way, the time evolution unit 30 according to the sixth embodiment provides N first variables x i and N second variables _{x i} for _Pr1 second intermediate variables b i included in one clock cycle. The calculation process of the variable _yi is executed with the degree of parallelism of _Pr1 . Thereby, the computing device 10 according to the sixth embodiment can execute the calculation process of the N first variables x _i and the N second variables y _i at high speed.

FIG. 21 is a diagram showing output timings of the first intermediate variable x _i ' and the second intermediate variable b _i . More specifically, (A) of FIG. 21 shows the timing at which the first intermediate variable x _i ' is output from the time evolution section 30 to the matrix multiplication section 28 at the top. (B) of FIG. 21 shows the timing at which the second intermediate variable _bi is output from the matrix multiplication unit 28 at the end to the time evolution unit 30 . (C) of FIG. 21 shows the calculation timing of the first intermediate variable x _i ' by the time evolution unit 30 .

The first intermediate variable x _i ' is transferred with P _c parallel degrees. Therefore, as shown in FIG. 21A, the transfer period of the first intermediate variables (x'b0 to x'b4095(t ₁ )) at the first time is N _S (=N/P _c ) clock cycles. becomes.

Also, the second intermediate variable b _i is transferred with _Pr1 parallelism. Therefore, as shown in FIG. 21B, the transfer period of the second intermediate variables (bb0 to bb2047(t ₁ )) at the first time is N/P _r1 clock cycles.

In addition, the time evolution unit 30 executes processing with a degree of parallelism of _Pr1 . Therefore, as shown in FIG. 21C, the calculation period of the second intermediate variables (bb0 to bb2047(t ₂ )) at the second time is N/P _r1 clock cycles.

Here _, L _a is the first second intermediate variable (bb0(t ₁ ) ) is the delay time until the output of L _b is calculated by the first intermediate variable (x′b0(t ₂ )) at the second time after the output of the first second intermediate variable (bb0(t ₁ )) at the first time starts. is the delay time until L _c is the output of the first intermediate variable (x′b0(t ₂ )) at the second time after the first intermediate variable (x′b0(t ₂ )) at the second time is calculated. is the delay time until

Here, the period from the start of one loop process to the start of the next loop process (one loop period) is N _S +L _a +L _b +L _c . The computing device 10 can make (L _b +L _c ) shorter than the transfer period (N/P _r1 ) of the second intermediate variables (bb0 to bb2047(t ₁ )) at the first time. Therefore, in the computing device 10, the first intermediate variables (x'b0 to _x'b4095 (t ₂ )) is started to be output. That is, the computing device 10 realizes overlapping loop processing. According to the computing device 10, by realizing such overlap, it is possible to execute processing at high speed.

Also, when N is large, _NS >>L _a +L _b +L _c . Therefore, when N is large, L _a +L _b +L becomes negligibly small relative to the overall execution time. In this case, the matrix multiplication time in computing device 10 can be considered as N _S (=N/P _c ) clock cycles.

For example, the matrix computation time of size N by a single-core processor is (N×N) clock cycles. The matrix multiplication time on computing device 10 relative to the matrix multiplication time on a single-core processor is (N/P _c )/N×N. Therefore, computing device 10 can perform matrix multiplication in 1/(P _c ×N) time for a single-core processor.

While several embodiments of the invention have been described, these embodiments have been presented by way of example and are not intended to limit the scope of the invention. These novel embodiments can be implemented in various other forms, and various omissions, replacements, and modifications can be made without departing from the scope of the invention. These embodiments and their modifications are included in the scope and gist of the invention, and are included in the scope of the invention described in the claims and equivalents thereof.

10 calculation device 20 calculation unit 22 input unit 24 output unit 26 setting unit 28 matrix multiplication unit 30 time evolution unit 32 management unit 36 coefficient matrix memory 38 matrix multiplication execution unit 40 first variable memory 42 second variable memory 44 first addition unit 46 function operation unit 48 first multiplication unit 50 first intermediate variable memory 60 division matrix multiplication unit 62 buffer unit 64 division matrix memory 66 execution unit 68 selector 80 sub-matrix multiplication unit 82 multiplexing unit 84 register 86 buffer internal reception unit 88 buffer Inner transmitter 90 Multiply accumulator 92 Multiplier 94 Adder 96 Accumulator

Claims (29)

Circuit information representing the configuration of a circuit described in a hardware description language,
causing the circuit to function as a computing device that solves an optimization problem using the Ising model;
The computing device
a first variable memory;
a second variable memory;
N (N is an integer of 2 or more) first intermediate variables at a first time and a coefficient matrix containing preset N rows×N columns of coefficients are multiplied by a matrix to obtain N at the first time a matrix multiplication unit that calculates second intermediate variables;
Calculate N first variables at a second time after one sampling period from the first time and N second variables at the second time based on the N second intermediate variables at the first time a time evolution unit that writes N first variables at the second time to the first variable memory and writes N second variables at the second time to the second variable memory;
a management unit that increments the time for each sampling period from the start time and causes the matrix multiplication unit and the time evolution unit to execute processing for each time;
an output unit that outputs N first variables at a preset end time;
with
The N first variables correspond to N spins in the Ising model ,
The N second variables correspond to the N spins ,
the N spins correspond to N points;
each of the N first variables represents the position of a point corresponding to a corresponding spin among the N points;
each of the N second variables represents the momentum of a point corresponding to the corresponding spin among the N points;
The N first intermediate variables correspond to the N first variables, and each of the N first intermediate variables is a corresponding first variable of the N first variables or the A value obtained by multiplying the corresponding first variable by a preset coefficient,
The N second intermediate variables correspond to the N second variables. Circuit information. Circuit information written to the reconfigurable semiconductor device to operate the reconfigurable semiconductor device,
causing the reconfigurable semiconductor device to function as a computing device that solves an optimization problem using an Ising model;
The computing device
a first variable memory;
a second variable memory;
N (N is an integer of 2 or more) first intermediate variables at a first time and a coefficient matrix containing preset N rows×N columns of coefficients are multiplied by a matrix to obtain N at the first time a matrix multiplication unit that calculates second intermediate variables;
Calculate N first variables at a second time after one sampling period from the first time and N second variables at the second time based on the N second intermediate variables at the first time a time evolution unit that writes N first variables at the second time to the first variable memory and writes N second variables at the second time to the second variable memory;
a management unit that increments the time for each sampling period from the start time and causes the matrix multiplication unit and the time evolution unit to execute processing for each time;
an output unit that outputs N first variables at a preset end time;
with
The N first variables correspond to N spins in the Ising model ,
The N second variables correspond to the N spins ,
the N spins correspond to N points;
each of the N first variables represents the position of a point corresponding to a corresponding spin among the N points;
each of the N second variables represents the momentum of a point corresponding to the corresponding spin among the N points;
The N first intermediate variables correspond to the N first variables, and each of the N first intermediate variables is a corresponding first variable of the N first variables or the A value obtained by multiplying the corresponding first variable by a preset coefficient,
The N second intermediate variables correspond to the N second variables. Circuit information. 3. The circuit information according to claim 1, wherein the time evolution unit further calculates the N second intermediate variables at the second time based on the N first variables at the second time. The time evolution unit calculates N second variables at the first time by adding the N second intermediate variables at the first time to the N second variables at the first time. 4. The circuit information according to claim 3, comprising an updating first addition unit. The time evolution unit
a first FX calculation unit;
a first FX adder;
a first FY calculation unit;
a first FY adder;
further having
The first FX calculation unit calculates N second differential values by performing a first function calculation on each of the N first variables at the first time,
The first FX addition unit adds the N second differential values calculated by the first FX operation unit and the updated N second variables calculated by the first addition unit. By calculating N second update values,
The first FY calculation unit calculates N first differential values by performing a second function calculation on each of the N second update values calculated by the first FX addition unit. death,
The first FY addition unit adds the N first differential values calculated by the first FY calculation unit and the N first variables at the first time to obtain N 5. The circuit information according to claim 4, wherein a first update value is calculated. The time evolution unit
a first FY calculation unit;
a first FY adder;
a first FX calculation unit;
a first FX adder;
further having
The first FY operation unit calculates N first differential values by performing a second function operation on each of the N updated second variables calculated by the first addition unit. death,
The first FY addition unit adds the N first differential values calculated by the first FY calculation unit and the N first variables at the first time to obtain N first 1 calculate the update value,
The first FX calculation unit calculates N second differential values by performing a first function calculation on each of the N first update values calculated by the first FY addition unit. death,
The first FX addition unit adds the N second differential values calculated by the first FX operation unit and the updated N second variables calculated by the first addition unit. 5. The circuit information according to claim 4, wherein N second update values are calculated. The time evolution unit
(M-1) FX operation units from the second to the Mth (M is an integer of 2 or more);
second to M-th (M-1) FX addition units;
(M−1) FY calculation units from the second to the Mth,
(M−1) FY addition units from the second to the Mth;
further having
The m-th (m is an integer from 2 to M) FX calculation unit performs the first function calculation on each of the N first update values calculated by the (m-1)th FY addition unit By calculating N second differential values,
The m-th FX addition unit adds the N second differential values calculated by the m-th FX calculation unit and the N second update values calculated by the (m−1)th FX addition unit. to calculate new N second update values,
The m-th FY calculation unit calculates N first differential values by performing the second function calculation on each of the N second update values calculated by the m-th FX addition unit. death,
The m-th FY addition unit adds the N first differential values calculated by the m-th FY calculation unit and the N first update values calculated by the (m−1)th FY addition unit. 6. The circuit information according to claim 5, wherein new N first update values are calculated by: The time evolution unit
(M−1) FY calculation units from the second to the Mth (M is an integer of 2 or more);
(M−1) FY addition units from the second to the Mth;
(M-1) FX operation units from the second to the Mth,
second to M-th (M-1) FX addition units;
further having
The m-th (m is an integer from 2 to M) FY operation unit performs the second function operation on each of the N second update values calculated by the (m-1)th FX addition unit. By calculating N first differential values,
The m-th FY addition unit adds the N first differential values calculated by the m-th FY calculation unit and the N first update values calculated by the (m−1)th FY addition unit. By calculating new N first update values,
The m-th FX calculation unit calculates N second differential values by performing the first function calculation on each of the N first update values calculated by the m-th FY addition unit. death,
The m-th FX addition unit adds the N second differential values calculated by the m-th FX calculation unit and the N second update values calculated by the (m−1)th FX addition unit. 7. The circuit information according to claim 6, wherein N new second update values are calculated by: The first functional operation is
dt′×[{−D+p−Kx _i ² }x _i −c×h _i ×a] (101)
and
The second function operation is
dt′×D× _yi (102)
and
x _i is the i-th first variable among the N first variables at the first time, or the i-th first update value among the N first update values;
y _i is the i-th updated second variable among the N updated second variables calculated by the first adder or the i-th updated value among the N second updated values; is the second updated value of
dt' is a minute time set in advance,
D, c, K are preset constants,
h _i is a coefficient set for each i,
The circuit information according to any one of claims 5 to 8 , wherein p and a are values that increase with time according to a predetermined arithmetic expression. The first functional operation is
dt′×{[(−D+p)(1+x _i ⁿ )−K _{x i} ⁿ⁺² ]x _i −c×h _i ×a} (103)
and
The second function operation is
dt′×D× _yi (104)
and
x _i is the i-th first variable among the N first variables at the first time, or the i-th first update value among the N first update values;
y _i is the i-th updated second variable among the N updated second variables calculated by the first adder or the i-th updated value among the N second updated values; is the second updated value of
dt' is a minute time set in advance,
D, c, K are preset coefficients,
h _i is a coefficient set for each i,
The circuit information according to any one of claims 5 to 8 , wherein p and a are values that increase with time according to a predetermined arithmetic expression. The time evolution unit
a first multiplier that calculates the N first intermediate variables at the second time by multiplying each of the N first variables at the second time by a preset value;
a first intermediate variable memory for storing the N first intermediate variables at the second time calculated by the first multiplier;
11. The circuit information according to any one of claims 4 to 10 , further comprising: The time evolution unit
a first intermediate variable memory that stores the N first variables at the second time as the N first intermediate variables at the second time;
a first multiplier that multiplies each of the N second intermediate variables at the first time output from the matrix multiplier by a preset value;
further having
The first adder adds the N second intermediate variables at the first time obtained by multiplying the N second variables at the first time by a value preset by the first multiplier. 11. The circuit information according to any one of claims 4 to 10 , further comprising: updating said N second variables at said first time by: The circuit information according to any one of claims 1 to 12 , further comprising an input unit that acquires N first variables at the start time. The time evolution unit outputs the N first intermediate variables at the first time to the matrix multiplication unit as a first intermediate stream containing a first number of first intermediate variables in one clock cycle;
The matrix multiplication unit outputs the N second intermediate variables at the first time to the time evolution unit as a second intermediate stream containing a second number of second intermediate variables in one clock cycle. 14. The circuit information according to any one of 1 to 13 . The coefficient matrix is divided into P r3 partition matrices each including (N _/ P _r3 ) rows (P _r3 is a divisor of N)×N columns of coefficients;
the N second intermediate variables are divided into P _r3 blocks each containing (N/P _r3 ) second intermediate variables;
The P _r3 blocks are associated one-to-one with the P _r3 partitioning matrices;
The matrix multiplication unit has Pr ₃ partitioned matrix multiplication units that are associated one-to-one with the Pr ₃ partitioned matrices,
Each of the P _r3 split matrix multiplication units performs matrix multiplication of the first intermediate variable and the corresponding split matrix to obtain (N/P _r3 ) second intermediate variables included in the corresponding block 15. The circuit information according to claim 14 , wherein: The Pr ₃ split matrix multiplication units are connected in series,
each of the _Pr3 split matrix multiplication units includes a buffer unit;
the buffer unit of the head division matrix multiplication unit acquires the first intermediate stream output from the time evolution unit, stores the acquired first intermediate stream for a certain period of time, and outputs the acquired first intermediate stream;
The buffer units of the dividing matrix multiplication units other than the first one acquire the first intermediate stream output from the immediately preceding stage dividing matrix multiplication unit, store the acquired first intermediate stream for a certain period of time, and output the acquired first intermediate stream. 15 circuit information. 17. The circuit information according to claim 15 or 16 , wherein the P _r3 partitioned matrix multiplication units and the time evolution unit are each included in independent ( _Pr3 + 1) chips. further comprising ( _Pr3 + 1) communication links for transmitting the first intermediate stream and the second intermediate stream;
The output terminal of the k _- th chip (k is an integer of 1 or more and Pr3 or less) among the (P _r3 +1) chips is connected to the input terminal of the ( _k +1)-th chip. ) communication links via the k-th communication link,
18. Circuit information according to claim 17 , wherein the output terminal of the (P _r3 +1) th chip is connected to the input terminal of the first chip via the (P _r3 +1) th communication link. Each of the P _r3 partitioned matrices is partitioned into P _r2 sub-matrices each containing P _r1 rows by N columns of coefficients, where P _r1 and P _r2 are divisors of N and P _r1 × P _r2 ×P _r3 =N, and
each of said P _r3 blocks is divided into P _r2 sub-blocks each containing P _r1 second intermediate variables;
The Pr2 sub-blocks included in the k-th block (k _is an integer equal to or greater than 1 and _Pr3 or less) are _associated one-to-one with the Pr2 sub-matrices included in the k-th partition matrix. ,
Each of _{the Pr3} partitioned matrix multipliers further includes Pr2 submatrix multipliers that are associated one-to-one with the _Pr2 submatrices included in the corresponding partitioned matrix,
Each of the _Pr2 sub-matrix multiplication units included in the k-th split matrix multiplication unit performs matrix multiplication of the N first intermediate variables and the corresponding sub-matrix to obtain the corresponding sub-block 17. The circuit information according to claim 16 , wherein P _r1 second intermediate variables included in are calculated. The buffer unit includes a Pr _two- stage register functioning as a shift register,
The Pr _2- stage registers are associated one-to-one with the Pr ₂ sub-matrix multiplication units,
Each of the P _{r two-} stage registers stores P _c (P _c is a divisor of N) first intermediate variables in parallel for one clock cycle, and in the next clock cycle, the stored P _c 20. The circuit information according to claim 19 , wherein the first intermediate variables are transferred in parallel to the next-stage register. each of the _Pr2 sub-matrix multiplication units includes Pr1 multiply-accumulate units that _are associated one-to-one with the _Pr1 rows included in the corresponding sub-matrix;
Each of the _Pr1 multiply-accumulate units:
acquiring N first intermediate variables from the beginning to the end of the first intermediate stream sequentially stored in corresponding registers of the Pr _two-stage registers for each clock cycle;
multiplying each obtained first variable by the coefficient of the column corresponding to the obtained first intermediate variable contained in the corresponding row in the coefficient matrix;
By cumulatively adding the multiplication result of the first intermediate variable and the coefficient from the first intermediate variable at the beginning of the first intermediate stream to the first intermediate variable at the end,
21. The circuit information according to claim 20 , wherein a second intermediate variable for a corresponding position included in a corresponding sub-block is calculated. Each of the _Pr2 sub-matrix multiplication units outputs the _Pr1 second intermediate variables included in the corresponding sub-block in parallel in one clock cycle, and is different from the other sub-matrix multiplication units. 22. Circuit information according to any one of claims 19 to 21 , wherein said P _r1 second intermediate variables are output in a clock cycle. Each of the _Pr3 split matrix multipliers multiplexes the _Pr1 second intermediate variables output from each of the _Pr2 sub-matrix multipliers, thereby performing _Pr1 in one clock cycle. 23. The circuit information according to claim 22 , further comprising a multiplexing unit for generating said second intermediate stream containing second intermediate variables. Each of the P _r3 split matrix multiplication units calculates (N/P _r3 ) second intermediate variables included in the corresponding block based on the first intermediate stream stored in the buffer unit. further comprising
The execution unit
(N/P _r3 ) second intermediate variables included in the corresponding block as the second intermediate stream including P _r1 (P _r1 is a divisor of N) second intermediate variables in one clock cycle 24. Circuit information according to any one of claims 19 to 23 , outputting and outputting the second intermediate stream in a different clock cycle than other split matrix multipliers. each of the _Pr3 split matrix multipliers includes a selector;
The selector of the leading split matrix multiplication unit,
selecting and outputting the second intermediate stream output by the execution unit of the top split matrix multiplication unit in the clock cycle in which the execution unit of the top split matrix multiplication unit outputs the second intermediate stream;
The selector of the k-th split matrix multiplication unit excluding the head,
selecting and outputting the second intermediate stream output by the execution unit of the k-th partitioned matrix multiplication unit in a clock cycle in which the execution unit of the k-th partitioned matrix multiplication unit outputs the second intermediate stream; death,
selecting and outputting the second intermediate stream output by the selector of the preceding divided matrix multiplication unit in a clock cycle in which the execution unit of the k-th divided matrix multiplication unit does not output the second intermediate stream. Circuit information according to claim 24 . 26. The time evolution unit according to claim 24 or 25 , for _Pr1 second intermediate variables included in one clock cycle, performs the calculation process of the N first variables with a degree of parallelism of _Pr1 . Circuit information listed. A computing device that solves an optimization problem using an Ising model,
a first variable memory;
a second variable memory;
N (N is an integer of 2 or more) first intermediate variables at a first time and a coefficient matrix containing preset N rows×N columns of coefficients are multiplied by a matrix to obtain N at the first time a matrix multiplication unit that calculates second intermediate variables;
Calculate N first variables at a second time after one sampling period from the first time and N second variables at the second time based on the N second intermediate variables at the first time a time evolution unit that writes N first variables at the second time to the first variable memory and writes N second variables at the second time to the second variable memory;
a management unit that increments the time for each sampling period from the start time and causes the matrix multiplication unit and the time evolution unit to execute processing for each time;
an output unit that outputs N first variables at a preset end time;
with
The N first variables correspond to N spins in the Ising model,
The N second variables correspond to the N spins,
the N spins correspond to N points;
each of the N first variables represents the position of a point corresponding to a corresponding spin among the N points;
each of the N second variables represents the momentum of a point corresponding to the corresponding spin among the N points;
The N first intermediate variables correspond to the N first variables, and each of the N first intermediate variables is a corresponding first variable of the N first variables or the A value obtained by multiplying the corresponding first variable by a preset coefficient,
The N second intermediate variables correspond to the N second variables
computing device. A calculation method for solving an optimization problem using an Ising model by an information processing device,
The information processing device is
a first variable memory;
a second variable memory;
with
A matrix multiplication unit of the information processing device performs matrix multiplication of N first intermediate variables (N is an integer equal to or greater than 2) at a first time and a coefficient matrix containing preset N rows×N columns of coefficients. to calculate N second intermediate variables at the first time,
The time evolution unit of the information processing device generates the N first variables and the second calculating N second variables at the time, writing the N first variables at the second time to the first variable memory, and writing the N second variables at the second time to the second variable memory write in,
The management unit of the information processing device increases the time for each sampling period from the start time, and causes the matrix multiplication unit and the time evolution unit to perform processing for each time,
The output unit of the information processing device outputs N first variables at a preset end time,
The N first variables correspond to N spins in the Ising model,
The N second variables correspond to the N spins,
the N spins correspond to N points;
each of the N first variables represents the position of a point corresponding to a corresponding spin among the N points;
each of the N second variables represents the momentum of a point corresponding to the corresponding spin among the N points;
The N first intermediate variables correspond to the N first variables, and each of the N first intermediate variables is a corresponding first variable of the N first variables or the A value obtained by multiplying the corresponding first variable by a preset coefficient,
The N second intermediate variables correspond to the N second variables
Method of calculation. A program for causing an information processing device to function as a computing device that solves an optimization problem using an Ising model,
The information processing device is
a first variable memory;
a second variable memory;
with
the information processing device,
N (N is an integer of 2 or more) first intermediate variables at a first time and a coefficient matrix containing preset N rows×N columns of coefficients are multiplied by a matrix to obtain N at the first time a matrix multiplication unit that calculates second intermediate variables;
Calculate N first variables at a second time after one sampling period from the first time and N second variables at the second time based on the N second intermediate variables at the first time a time evolution unit that writes N first variables at the second time to the first variable memory and writes N second variables at the second time to the second variable memory;
a management unit that increments the time for each sampling period from the start time and causes the matrix multiplication unit and the time evolution unit to execute processing for each time;
an output unit that outputs N first variables at a preset end time;
to make it work,
The N first variables correspond to N spins in the Ising model,
The N second variables correspond to the N spins,
the N spins correspond to N points;
each of the N first variables represents the position of a point corresponding to a corresponding spin among the N points;
each of the N second variables represents the momentum of a point corresponding to the corresponding spin among the N points;
The N first intermediate variables correspond to the N first variables, and each of the N first intermediate variables is a corresponding first variable of the N first variables or the A value obtained by multiplying the corresponding first variable by a preset coefficient,
The N second intermediate variables correspond to the N second variables
program.

Images