JPH06101016B2 - Data processing system for dynamic programming calculation. - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a data processing system for dynamic programming calculation, and in particular, in computing N-stage multistage decision problems based on dynamic programming, the calculation of the p-th stage is divided. The present invention relates to a data processing system for dynamic programming calculation, which is provided with a plurality of data processing devices for performing shared execution and at least two high-speed storage devices, and is configured to perform calculation of each stage in parallel. .

It is known to solve a multi-stage decision problem based on dynamic programming, and the amount of calculation for finding the optimal policy by the dynamic programming is much smaller than when it is calculated by brute force. It has been known. However, even in this case, when it becomes a large-scale problem, a normal general-purpose data processing device cannot obtain a sufficient calculation speed. In particular, for example, when considering the execution of processing such as determining the injection angle of the engine for making the rocket reach a certain point with the minimum fuel consumption, analyze the content of the processing and obtain only the calculation result for each stage. It is desired to use it in the next stage and to increase the calculation speed by deciding the portion that requires high-speed processing.

The present invention, in order to be suitable for the operation based on the above-mentioned dynamic programming method, causes a plurality of data processing devices to perform the calculation of the Pth stage at the same time, and under the control of the control device, pipeline operation is performed. It is an object of the present invention to provide a high-speed data processing system having a data processing device capable of executing various processes in a stepwise manner. Therefore, the data processing system for dynamic programming calculation according to the present invention is a data processing system for dynamic programming calculation that calculates an N-stage multi-stage decision problem based on the dynamic programming. a plurality of data processing devices that divide and execute the p-th stage calculation; a control device that divides and distributes the p-th stage calculation to the plurality of data processing devices; 1) A first high-speed storage device for storing the calculation result of the first stage, a second high-speed storage device for receiving the calculation result of the p-th stage from each of the data processing devices, and storing the same. The plurality of data processing devices include a low-speed storage device that stores the calculation result in each stage up to the Nth stage and an output device that extracts the optimum output based on the contents of the low-speed storage device. (P-1) stage in executing the calculation of Is received from the first high-speed storage device, the p-th stage calculation result is stored in the second high-speed storage device, and information based on the p-th stage calculation result is stored in the low-speed storage device. At the same time, the contents of the second high speed storage device are transferred to the first high speed storage device according to an instruction from the control device when the calculation result of the p-th stage is completed in all of the plurality of data processing devices. , And the calculation of the (p + 1) th stage is executed on that. The concept of processing based on the dynamic programming will be described below and then described with reference to the drawings.

FIG. 1 is an explanatory view for explaining the structure of a table calculated for obtaining an optimum measure, FIG. 2 is an overall structure view of an embodiment of the present invention, and FIG. 3 is an implementation of the processing device shown in FIG. An example configuration is shown.

Generally, in a multi-stage decision problem, it is possible to find the optimal control using dynamic programming from the principle of optimality. Now, considering the N-stage decision problem, the K-stage and K + 1-stage of the decision problem of the target dynamic system But control State by adding From , The cost g _{K at} that time is above Shall be given by. I.e. Shall be given in.

The optimal control of such N-stage decision problem is Satisfy the control of Is. Hereinafter, the case of min will be described, but the case of max is substantially the same.

Satisfies formula (3) According to dynamic programming, Is determined by asking for. That is, (Where min is Means the minimum value for It turns out that it is enough to calculate in order.

In order to perform the calculation of equation (4) above with a digital computer And are quantized as follows.

Here, ▲ C ^X ₁ ▼ to ▲ C ^U _m ▼ and ▲ δ ^X ₁ ▼ to ▲ δ ^U _m ▼ are constants, respectively, and ▲ δ ^X ₁ ▼ to ▲ δ
^U _m ▼ is a positive value.

Substituting Eqs. (5) and (6) into Eq. (1), the state after one step is (i ₁ , i ₂ …, i _n ) and (j ₁ , j ₂ …, j _m ) Can be determined as a function of. That is, new Is Becomes here Is quantized in the same manner as in the equation (5), X ^l ″ ＝ ▲ C ^X _l ▼ ＋ ▲ δ ^X _l ▼ ・ ▲ i ′ _l ▼ (where l = 1,2,
…, N) − (8), where (However [P] is the maximum integer not exceeding P) When an error epsilon _l due to the approximated by X ^l "of the X ^l 'in the first _{(8), ε l = Δ l · δ} l X - (10) However, Δ _l = {X ^l ′ − (C _l ^X + δ _l ^X · i _l ′)} / δ _l ^X Note that (l = 1,2,3, ..., n), and Δ _l is From the definition of i _l ′, 0 ≦ Δ _l <1.

From the _{above, (i 1, i 2,} ..., i n) and _{(j 1, j 2, ...} , j m) when the _{given, (i 1 ', i 2} ', ..., i n ') And (Δ ₁ , Δ ₂ , Δ ₃ ,…, Δ _n ) are the expressions (9) and (10)
It can be calculated from the formula. Therefore, (i ₁ ′, i ₂ ′, ...,
i _n ′) and (Δ ₁ , Δ ₂ , ..., Δ _n ) will be expressed as follows.

The calculation for the above equation (4) is performed as follows.
That is, the computation of the first equation in the previous Dzu the (4) equation, the equation (5) _{(i 1, i 2, ...} , i n) defining the _{(j 1, j 2, ...} , j m ) For all combinations Is calculated, And find the minimum value of (i ₁ , i ₂ , ...,
i _n ) All finding a value that satisfies the _{(i 1, i 2, ...} , i n) performs the same calculation with respect to, at that time _{(j 1, j 2, ...} , j m)
And the value of f ₁ is stored. This is f ₁ (i ₁ , i ₂ ,
…, I _n ).

With this, the calculation of the second equation in the equation (4) is performed as follows. That is, first, (i ₁ , i ₂ ,
, I _n ) is determined, and for all combinations of (j ₁ , j ₂ , ..., j _m ) the same calculation as in equation (13) is performed to obtain the first term. Then, the (11) to calculate the equation and the equation _{(12), f 1 (i 1, i} 2, ..., i n) which has been already calculated and stored to the calculated values for the second term. This can be done as follows. That is, (i ′ ₁ , i ′ ₂ , ..., Calculated from the equation (11)
i ′ _n ) is a point in the n-dimensional space, and this point and (2 ⁿ −1) points adjacent to this point, The value of f ₁ at Then, since these are already calculated, using (Δ ₁ , Δ ₂ , ..., Δ _n ) of the equation (12), Find the approximate value of. For example, if you do linear interpolation, Is required as. In this way (i ₁ , i ₂ , ...,
i _n ), (j ₁ , j ₂ , ..., j _m ) Since but can be calculated, all _{(j 1, j 2, ...} , j m) is performed for the combination of obtains its minimum value, this (i _1,
for i ₂ , ..., i _n ) And

By performing the same calculation from the third equation of the equation (4) to the Nth equation, Can be calculated sequentially.

In summary, the table shown in FIG. 1 is obtained, and the optimum control can be obtained from this table. That is, the initial state _{(i 1, i 2, ...} , i n) given, corresponding to the column of the first N-stage of FIG. 1 _{(j 1, j 2, ...} , j m) this seek And then, then the equation (11) from _{(i '1, i' 2} , ..., i 'n) is determined and corresponds to the column of the (N-1) stage of FIG. 1 (j _1,
j ₂ , ..., j _m ) And so on Ask for.

In FIG. 2, reference numeral 1 is a control device, 2-0 to 2-n are processing devices (data processing devices according to the present invention), and 3A is a first high speed storage device at the (p-1) th stage. 3B is a second high-speed storage device for storing the calculation result of the p-th stage, 4 is a low-speed storage device,
Reference numeral 5 represents an output device for extracting and outputting the optimum policy as described above with reference to FIG. 1 based on the contents of the low speed storage device.

Controller 1 is for Nikki by Tsukasa controlling the entire system, shown in the equation (5) _{(i 1, i 2, ...} , i n) each processing unit generates a 2-0,2-1 , 2-n. Each processing device 2
-0,2-1, ..., 2-n has been transferred from the control unit _{1 (i 1, i 2,} ..., i n) as inputs, and respectively shared, the
All combinations of (j ₁ , j ₂ , ..., J _m ) shown in equation (6) are generated. Then, it corresponds to the calculation result of the (p-1) th stage stored in the first high-speed storage device 3A, that is, the above equation (15). The _{reads, (i 1, i 2,} ..., i n) a p-th calculation result corresponding to the words To the second high speed storage device 3B. Also shown in equation (4) The optimum control (j ₁ , j ₂ , ..., J _n ) that satisfies the above condition is written in the low-speed storage device 4.

The _{(i 1, i 2, ...} , i n) each processing unit all combinations of 2-0,2-1, ..., each processing unit after transferring the 2-n 2-0,2
When -1, ..., 2-n finishes the calculation of the p-th stage, the contents of the second high-speed storage device 3B, namely Is transferred to the first high-speed storage device 3A and is transferred to the next stage, that is, the (p +
1) The calculation of the first stage is started.

After repeating this operation from the first stage to the Nth stage, the control device 1 controls the output device 5 to use the contents of the low speed storage device 4, that is, the contents of the table as shown in FIG. Make sure that the optimum control sequence is output.

FIG. 3 shows the processing device 2-0,2-1, ..., 2-n shown in FIG.
1 shows the configuration of an embodiment. Reference numeral 6 in the drawing is a storage device portion, 7
Is a calculation unit, 8 is an address generation unit, 9 is an interpolation calculation unit, 10
Is 11 is a g calculation unit, 12 is an addition unit, and 13 is a MiN determination unit.

The calculation unit 7 performs calculations corresponding to the equations (11) and (12) to obtain (i ′ ₁ , i ′ ₂ , ..., i ′ _n ) and (Δ ₁ , Δ
₂ , ..., Δ _n ) is generated. The address generator 8 generates the (14) th based on the generated (i ′ ₁ , i ′ ₂ , ..., i ′ _n ).
Shown in the formula That is, an access address for the first high speed storage device 3A is generated, the first high speed storage device 3A is accessed, and the first (1
The (p-1) th stage corresponding to equation (5) Control so that the The interpolation calculation unit 9 calculates the first (1) based on the read data from the first high speed storage device 3A.
Value of the (p-1) th stage corresponding to equation (6) Calculate the value of.

10 sequentially generates (j ₁ , j ₂ , ..., j _m ) of the equation (6) and To occur. g calculation unit _{11, (i 1, i 2,} ..., i n) and _{(j 1, j 2, ...} , j m) corresponding from the first (13) To calculate. The addition unit 12 corresponds to the one shown in the expression (4).

And transfer it to the MiN determination unit 13. And MiN decision unit 13
Is sent from the adder 12. The values are compared to extract the smallest one, and the smallest one and its corresponding (j ₁ ,
j ₂ , ..., j _m ) is stored. And When 10 has finished generating all (j ₁ , j ₂ , ..., J _m ), the second minimum storage device 3B has the above minimum and , And sends the above-mentioned smallest one and the corresponding (j ₁ , j ₂ , ..., J _m ) to the low-speed storage device 4.

As described above, according to the present invention, a plurality of data processing devices share and execute the operation of the p-th stage, and the result of the (p-1) -th stage is obtained by using at least two high-speed storage devices. Is introduced into the operation of the p-th stage. For this reason, the processing is speeded up, and it becomes possible to obtain the optimum measure with sufficient speed even for a large-scale problem.

In FIG. 3, the contents of the second high-speed storage device 3B are transferred to the first high-speed storage device 3A, but it is optional to switch the roles of the two, if necessary. The present invention is not limited to the configuration shown in FIG.

[Brief description of drawings]

FIG. 1 is an explanatory view for explaining the structure of a table calculated for obtaining an optimum measure, FIG. 2 is an overall structure view of an embodiment of the present invention, and FIG. 3 is an implementation of the processing device shown in FIG. An example configuration is shown. In the figure, 1 is a control device, 2 is a data processing device, 3A and 3B are high-speed storage devices, 4 is a low-speed storage device, and 5 is an output device.

Claims (1)

[Claims] 1. A data processing system for calculating a dynamic programming method for calculating an N-stage multi-stage decision problem based on dynamic programming, wherein a plurality of p-stage calculations of dynamic programming are divided and executed. A plurality of data processing devices, a control device that divides and distributes the calculation of the p-th stage to the plurality of data processing devices, and a first result that stores the calculation result of the (p-1) -th stage. High speed storage device, a second high speed storage device for receiving the calculation result of the p-th stage from each of the data processing devices, and storing the calculation result in each stage from the first stage to the N-th stage. And the output device for extracting the optimum output based on the contents of the low-speed storage device, and the plurality of data processing devices execute the (p- 1) Receive the calculation result of the first stage from the first high speed storage device and The calculation result of the p-th stage is stored in the second high-speed storage device, the information based on the calculation result of the p-th stage is stored in the low-speed storage device, and When the processing is completed in all the data processing devices, the contents of the second high speed storage device are transferred to the first high speed storage device according to the instruction of the control device, and the calculation of the (p + 1) th stage is executed. A data processing system for dynamic programming calculation, characterized in that