JP2012008946A - Distributed simulation method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a distributed simulation system which applies efficiently deletion of simulation using previous execution results even when simulation time progress by a barrier synchronization is being performed.SOLUTION: In the distributed simulation system which performs simulation processing by distributing in a plurality of arithmetic devices, if it is proved beforehand that an optional simulation processing result of the simulation time to be executed next to a Monte Carlo simulation which is in course of trial will be tried at the same time as the simulation time of previous trials and will be the same result as the simulation processing result of the previous trials, and if it is possible to omit optional simulation processing execution to be executed next by reusing the previous results, by performing assignment of the simulation processing except the omittable simulation processing to the arithmetic devices, the only simulation processing which needs to be executed is scheduled dynamically to the arithmetic devices and is executed.

Description

  The present invention relates to a distributed simulation method in a distributed simulation system in which different objects are simulated by a plurality of arithmetic devices and data of simulation results are communicated between the arithmetic devices.

  In general, in the simulation using the Monte Carlo method, when the occurrence probability of a certain event is unknown, the simulation is executed n times using a random number, the number m of occurrences of the event is obtained, and an approximate solution m of the occurrence probability is obtained. Used to determine / n. Since the accuracy of this approximate solution increases as the number of trials increases in probability theory, more simulation executions are required to obtain a better approximate solution. However, when there are time constraints, it is difficult to obtain a satisfactory number of simulation executions in the conventional simulation execution environment, and a method capable of executing the Monte Carlo simulation at a higher speed is required.

  Patent Document 1 and Non-Patent Document 1 can be cited as conventional techniques for executing Monte Carlo simulation at high speed. In Patent Document 1, as a speeding-up method of Monte Carlo simulation, in a moving body simulation executed based on a minute time step, a result that is executed for the first time is used and a simulation that becomes unnecessary as a result is deleted after the second time. This reduces the total execution time. The Monte Carlo simulation high-speed execution technology described in Non-Patent Document 1 is High Level Architecture (HLA), which is an architecture of a distributed simulation system standardized mainly by the US military. HLA defines an architecture for distributed processing of a simulation by a program called multiple federations, and divides a large problem (federation) to be simulated into multiple simulated processings by multiple federations. The purpose is to increase the processing speed of the entire system by allocating federates to arithmetic units, performing parallel distributed processing, and controlling the whole by a base program called Run-Time Infrastructure (RTI).

JP 2007-78288 "Simulation Execution Method"

IEEE 1516.1-2000-Standard for Modeling and Simulation High Level Architecture (HLA)-Federate Interface Specification

  The HLA listed in Non-Patent Document 1 is a standard architecture of a distributed simulation system, and a distributed simulation execution environment based on HLA or using distributed processing similar to HLA is generally widely used. FIG. 1 shows an example of a general distributed simulation system using HLA. In the HLA, the RTI 101 performs execution control and data communication control between the simulation processes 102 based on the progress of simulation time for the simulation processes 102 that are distributedly executed. FIG. 2 is an example of progress of simulation time of a general distributed simulation system constructed based on HLA. In such a system, a federation for simulating a simulation target such as a moving object or a sensor appearing in the simulation is assigned to the arithmetic device, and each federation executes the simulation processing of the simulation target in parallel according to the time interval of the simulation time. At this time, barrier synchronization is performed according to the progress of simulation time so that no contradiction occurs due to data communication between federated rates. Data communication and barrier synchronization between federated rates are controlled by RTI.

  FIG. 3 shows an event list used for controlling the execution of the simulation process based on the progress of the simulation time in the execution of the distributed simulation as shown in FIG. In the event list, the execution time and execution input value are set for the simulation process. When the execution time is updated during execution by simulation execution, information on which other simulation process is set to the same execution time The execution time and the execution input value are passed to the arithmetic unit to which other simulation processing is assigned, and the simulation processing is executed. When the execution of the simulation process in the arithmetic device at that time ends, the next execution time and execution input value of the simulation process are set in the event list.

The next execution time set in the event list is one of the following two types according to the type of simulation processing. One is a simulation process that is periodically executed, for example, an aerial radar simulation process. In such a simulation process, the simulation process itself sets the next execution time. The other is executed depending on the execution result event of another simulation process, such as an air traffic control simulation process (executed only when detection information that is the execution result of the aircraft radar simulation process is generated). In such simulation processing, the occurrence time of the dependent execution result event is set as the next execution time.
Execution input values set in the event list are input values required for the simulation process to simulate, and state information that is the simulation execution result of itself or execution results of other simulation processes are set. The

  In the distributed simulation execution environment that controls the execution of the simulation process based on the progress of the simulation time as described above, the execution results up to the previous time as described in Patent Document 1 are used to execute the Monte Carlo simulation at a higher speed. Then, when a method of deleting simulations that become unnecessary as a result after the second time is adopted, the example shown in FIG. 4 is obtained. FIG. 4 shows an example in which the simulation process of the aircraft federation being processed by the computing device 1 can be omitted at the time Tn and Tn + 1, but the simulation processing is omitted by the computing device 1 at each time. Even if possible, since the barrier synchronization is performed every time between federations, the arithmetic device that omits the simulation processing is kept waiting until the execution of the simulation processing of the other arithmetic devices is completed. . In other words, in the distributed simulation system, the execution results up to the previous time can be used in some simulation processing, and even if simulation can be omitted, the simulation is performed while other simulation processing is processing at the simulation time. There is a problem that it is difficult to execute a simulation at high speed as a whole because waiting for time progress is made.

  The present invention relates to a distributed simulation method that efficiently applies deletion of simulations using execution results up to the previous time even when the simulation time progress by barrier synchronization is performed in the distributed simulation system as described above. .

The distributed simulation method according to the present invention includes:
In a method of executing Monte Carlo simulation by a distributed simulation system that executes simulation processing distributed to a plurality of arithmetic devices,
It is known in advance that an arbitrary simulation processing result of the simulation time to be executed next to the Monte Carlo simulation currently being tried is the same as the simulation processing result tried at the same simulation time tried until the previous time, If you can skip the execution by reusing the result,
By assigning the simulation process to the arithmetic unit excluding the simulation process that can be omitted by reusing the result,
Only simulation processing that needs to be executed during simulation execution is dynamically scheduled and executed in the arithmetic unit.

According to the distributed simulation method of the present invention,
In the second and subsequent simulation executions in the Monte Carlo simulation, the number of barrier synchronizations can be reduced by determining the dynamic frame being executed by the scheduling process and assigning the simulation process to the arithmetic unit. Also, by starting the execution of the simulation process speculatively without waiting for the processing result in the other arithmetic device, the processing waiting time in the arithmetic device can be reduced and the arithmetic device can be used efficiently. These effects can speed up the simulation execution.

It is a figure which shows the structural example of the distributed simulation system by HLA. It is a figure which shows the example of simulation time progress of the distributed simulation system by HLA. It is a figure which shows the event list for simulation process control at the time of distributed simulation execution. It is a figure which shows the example of simulation time progress in case the simulation process of the aircraft federation in process can be omitted. It is a figure which shows the structural example of the distributed simulation system by this invention. It is a figure which shows the example of simulation time progress which performed the allocation to the arithmetic unit of the simulation process dynamically during simulation execution by this invention. It is a processing flowchart of the scheduling process by this invention. It is a figure which shows the example of a scheduling list of a scheduling process result.

Embodiment 1 FIG.
An embodiment will be described in which when a Monte Carlo simulation is executed using a distributed simulation system, a simulation process is assigned to an arithmetic unit excluding the simulation process that can be omitted by reusing the result.
FIG. 5 is a configuration example of a distributed simulation system according to the present invention. In FIG. 5, reference numeral 501 denotes a distributed simulation base that performs execution control and data communication control between the simulation processes 102 based on the progress of simulation time for the simulation processes 102 that are distributed and executed. The distributed simulation base 501 is a base program similar to the RTI 101 in the distributed simulation system compliant with the HLA shown in FIG. 1, but is a base program provided with a function for speeding up the Monte Carlo simulation according to the present invention. An event list 502 is used to control the execution of the simulation process based on the progress of the simulation time. Reference numeral 503 denotes a scheduling process in which the simulation process 102 is assigned to a computing device and executed based on the event list 502 and the scheduling list 504. Reference numeral 504 indicates that in the second and subsequent trials of the Monte Carlo simulation, the execution of the simulation process in which the same result has already been obtained in the previous trial is omitted, and at the same time, the simulation process that can schedule the execution to the arithmetic unit, the execution time, and the input information The scheduling process 503 sets a combination of simulation processes 102 that can be simultaneously allocated to the arithmetic apparatus based on the setting values of the event list 502, and the scheduling process 503 allocates the simulation process 102 to the arithmetic apparatus. It is something to refer to.
FIG. 6 shows an example in which simulation processing is dynamically assigned to an arithmetic unit during simulation execution according to the present invention. In the scheduling process executed by each arithmetic device after barrier synchronization shown in FIG. 4, a frame that is a step size of simulation time for performing barrier synchronization between arithmetic devices and a simulation process that assigns execution to the arithmetic device are determined.

FIG. 7 shows a process flow of the scheduling process. In the scheduling process, the simulation process to be executed in parallel by the arithmetic unit from that time is registered in the scheduling list, and until the next barrier synchronization is performed up to the maximum simulation process time set in the scheduling list. Set as the frame size.
FIG. 8 is an example of a scheduling list. The scheduling list is registered based on the processing flow of FIG. 7. Among the registered information, the execution input value and the execution output value are as follows from the event list and the result data in the simulation up to the previous Monte Carlo trial. Registered as follows.

○ For execution registration: Set execution input value, do not set execution output value
(A) If there is trial result information of the previous time in the same simulation that can be set as the execution input value: Set the trial result information of the previous time in the same simulation to the execution input value
(B) If there is no trial result information of the previous time in the same simulation that can be set as the execution input value: Set the trial result information of the previous time in the previous simulation to the execution input value (if there are multiple , Set any trial result information)
○ For omitted registration: Set the execution output value and do not set the execution input value. The execution output value is set to the result information searched in the process (1) in the process flow of FIG.

  In the process (2) of the process flow of FIG. 7, the simulation process assigned to the arithmetic device executes the simulation of the time in the frame, but before the same simulation process or other simulation processes assigned to the same frame. When the simulation is executed on the basis of the result information at the time, the simulation processes having a dependency relationship based on the simulation result are executed in parallel. Therefore, these simulation processes are speculatively executed using the result data in the previous simulation execution by the Monte Carlo trial. In other words, assuming that the dependent information is the result data in the previous simulation execution, the simulation execution is speculatively started, and the information assumed to be the information when the dependent information is generated later If they are different, the simulation is re-executed, and if they are not different, the result of speculative execution is adopted as it is. For example, in the frame m of FIG. 6, the aircraft control simulation process (Tn + 1) assigned to the computing device 2 and the aviation radar simulation process (Tn + 1) assigned to the computing device 3 are assigned to the computing device 1. Depending on the detection information that is the result of the simulated air radar simulation (Tn), speculative execution is performed using the detection information that is the result of the air radar simulation processing (Tn) in the previous simulation execution by the Monte Carlo trial. When the detection information that is the execution result of the aerial radar simulation process (Tn) of the arithmetic device 1 is received after that, it is determined whether or not it is necessary to re-execute the execution.

  As described above, in the second and subsequent simulation executions in the Monte Carlo simulation, the number of barrier synchronizations can be reduced by determining the dynamic frame being executed by the scheduling process and assigning the simulation process to the arithmetic unit. it can. Also, by starting the execution of the simulation process speculatively without waiting for the processing result in the other arithmetic device, the processing waiting time in the arithmetic device can be reduced and the arithmetic device can be used efficiently. These effects can speed up the simulation execution.

Embodiment 2. FIG.
Next, a method of dynamically simulating the excess processing of the number of computing devices to a computing device having a light load will be described.
In the condition determination of (3) in the processing flow of FIG. 7, a determination is made so that the number of simulation processes exceeding the number of arithmetic devices is not registered in the scheduling list. However, in the subsequent condition determination of (4), there is still a barrier in the event list. If it is determined that there is a simulation process that must be executed before synchronization, the simulation process in excess of the number of arithmetic devices may be registered for execution in the scheduling list. In such a case, the simulation process registered for execution by the following procedure is assigned to the arithmetic device.

(1) Allocation to computing devices in order from the simulation process with the earlier execution time.
(2) When the execution of the simulation process B is completed in a certain arithmetic unit A, the following is executed.
(A) When the result information C of the simulation process B becomes the execution input value of the unallocated simulation process remaining in the scheduling list, the execution input value of the corresponding simulation process in the scheduling list is rewritten to the result information C
(B) Select one simulation process with the earliest execution time from the unallocated simulation processes remaining in the scheduling list and assign it to the processing unit A
(3) Repeat the process of (2) until there is no unallocated simulation process remaining in the scheduling list.

  According to this procedure, scheduling is performed on the processing device that has dynamically finished processing, and the execution input value of the scheduling list is changed according to the result information of the simulation processing that has finished execution. Therefore, the risk of re-execution is avoided, so that even when a number of simulation processes exceeding the number of arithmetic devices are registered in the scheduling list, the simulation can be executed efficiently.

Note that when executing the simulation process assigned to the arithmetic device, depending on the result of the time before the same simulation process or other simulation process assigned to the same frame, The simulation execution is speculatively started assuming that the information is the result data from the previous simulation execution by the Monte Carlo trial, and when the dependent information is generated later, the information is compared with the assumed information. If it is different, repeat the simulation execution, and if it is not different, adopt the speculative execution result as it is,
Furthermore, when the simulation time for performing barrier synchronization between simulation processes executed in a distributed manner is obtained, if it is necessary to allocate more simulation processes than the number of arithmetic devices, simulation is performed during the simulation. By allocating simulation processing for the excess of the number of computing devices from the computing device that has finished executing the process, the simulation processing for the excess of the number of computing devices is dynamically scheduled to the computing device with a light load, and the entire trial is performed at high speed. You may make it perform the simulation inside. In this way, simulation execution can be further speeded up.

  The Monte Carlo simulation execution method by the distributed simulation system according to the present invention can be used for a distributed simulation system that performs, for example, aircraft simulation, air radar simulation, and air traffic control radar simulation.

  101; RTI, 102; simulation process, 501; distributed simulation infrastructure, 502; event list, 503; scheduling process, 504; scheduling list.

Claims (5)

In a method of executing a Monte Carlo simulation by a distributed simulation system that executes a simulation process for a plurality of objects distributed to a plurality of arithmetic devices,
It is known in advance that any simulation processing result of the simulation time to be executed next to the Monte Carlo simulation that is currently being tried will be the same as the simulation processing result that was tried at the same simulation time up to the previous time. If you can skip the execution of any simulation process to be executed next by reusing
By assigning the simulation process to the arithmetic unit excluding the simulation process that can be omitted by reusing the result,
A distributed simulation method characterized by dynamically scheduling and executing only a simulation process that needs to be executed during simulation execution in an arithmetic device.   The distributed simulation method is a method in which barrier synchronization is performed according to the progress of simulation time so that no contradiction occurs due to data communication performed between a plurality of arithmetic devices, and the simulation time for performing barrier synchronization between simulation processes executed in a distributed manner is set. 2. The distributed simulation method according to claim 1, wherein the simulation is dynamically performed during execution of simulation by assigning simulation processing to an arithmetic unit.   When the simulation time for performing barrier synchronization between distributed simulation processes is obtained, if it becomes necessary to allocate more simulation processes than the number of computing devices, the simulation process is executed during the simulation. By allocating simulation processing for the excess of the number of computing devices from the computing device that has finished execution, the simulation processing for the excess of the number of computing devices is dynamically scheduled to the computing device with a light load, and the simulation is executed. The dispersion simulation method according to claim 2.   3. The simulation process up to the simulation time is executed by speculative simulation time progress when a simulation time for performing barrier synchronization between the simulation processes distributed and executed is obtained. Distributed simulation method. When simulation time to perform barrier synchronization between distributed simulation processes is obtained, execution of simulation processes up to the simulation time is performed by speculative simulation time progress,
Furthermore, when the simulation time for performing barrier synchronization between simulation processes executed in a distributed manner is obtained, if it is necessary to allocate more simulation processes than the number of arithmetic devices, simulation is performed during the simulation. The simulation processing for the excess of the number of computing devices is assigned from the computing device that has finished executing the processing, and the simulation processing for the excess of the number of computing devices is dynamically scheduled to a computing device with a light load. The distributed simulation method described.

Images