Distributed processing-type simulator

• US 8,280,706 B2
• Filed: 08/27/2010
• Issued: 10/02/2012
• Est. Priority Date: 08/28/2009
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Ikeda, Takuro, Kitagawa, Eiji, Yamada, Hiroshi
• Primary Examiner(s): Frejd, Russell
• Application Number:
  US12/869,934
• Publication Number:
  US 20110054874A1
• Time in Patent Office: 767 Days
• Field of Search: 703/2, 703/6, 703/13, 701117-119, 709/201, 709/202, 709/204, 709/205, 709/217, 709/219, 711/170, 711/E12.001, 711/E12.002
• US Class Current: 703/2
• CPC Class Codes: G06F 30/15 Vehicle, aircraft or watercraft design
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06N 3/006 based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]

Abstract

A simulator simulates the behavior of a plurality of agents existing in the virtual space. Each of a plurality of calculators, communicable with one another, includes a space allocation storage that stores space allocation information, a space allocation control part that updates the space allocation information, an allocation change candidate space extracting part that extracts a divided space to be a candidate for the allocation change, a communication amount estimating part that calculates an amount of communication or an amount of change in communication generated between calculators based on the number of agents, a space allocation change judging part that determines whether or not to allocate a divided space to another calculator based on the amount of communication or the amount of change in communication, and a space allocation change executing part that requests the space allocation control part and other calculators to change the space allocation.

Claims

1. A simulator that simulates behaviors of a plurality of agents existing in a virtual space by distributed processing that uses a plurality of calculators communicable with one another,

wherein at least two of the calculators are accessible to a space allocation storage that stores, as space allocation information, a division range of each of divided spaces in the virtual space, and a calculator to which processing related to an agent existing in each of the divided spaces is allocated,

at least two of the calculators comprising:

an allocation change candidate space extracting part that refers to the space allocation storage so as to extract, as an allocation change candidate space, a divided space to be a candidate for an allocation change from among divided spaces whose one or more adjacent spaces are allocated to another of the calculators;

a communication amount estimating part that calculates an amount of communication or an amount of change in communication to be generated between the calculator targeted for the allocation and another of the calculators when the allocation change candidate space is allocated to a calculator targeted for the allocation, based on the number of agents existing in the allocation change candidate space and an adjacent divided space thereof; and

a space allocation change judging part that determines whether or not to allocate the allocation change candidate space to the calculator targeted for the allocation, based on the amount of communication or the amount of change in communication calculated in the communication amount estimating part.

2. The simulator according to claim 1,

wherein at least two of the calculators further include:

a space allocation control part that updates the space allocation information stored in the space allocation storage; and

a space allocation change executing part that requests the space allocation control part and the space allocation control part of the calculator targeted for the allocation to update the space allocation information in accordance with the determination of the space allocation change judging part.

3. The simulator according to claim 1,

wherein the communication amount estimating part calculates, as an amount of communication before the allocation change, an amount of communication currently being generated between the allocation change candidate space and a divided space in another of the calculators, and also calculates, as an amount of communication after the allocation change, an amount of communication expected to be generated between the allocation change candidate space and a divided space in a calculator other than the calculator targeted for the allocation when the allocation change candidate space is allocated to the calculator targeted for the allocation, and

the space allocation change judging part determines to allocate the allocation change candidate space to the calculator targeted for the allocation when the amount of communication after the allocation change is smaller than the amount of communication before the allocation change.

4. The simulator according to claim 1,

wherein the communication amount estimating part calculates the amount of change in communication to be generated between the calculator targeted for the allocation and another of the calculators, considering an amount of communication currently being generated between an adjacent space that is adjacent to the allocation change candidate space and allocated to the calculator thereof, and a divided space in the calculator targeted for the allocation, and the space allocation change judging part determines whether or not to allocate the allocation change candidate space to the calculator targeted for the allocation, based on the amount of change in communication that reduces the amount of communication most.

5. The simulator according to claim 1,

wherein the space allocation change judging part determines whether or not to allocate the allocation change candidate space to the calculator targeted for the allocation, considering a penalty based on the number of agents to be generated when agent information related to an agent existing in the allocation change candidate space is moved to the calculator targeted for the allocation.

6. The simulator according to claim 2,

wherein at least two of the calculators further includes a processing load monitoring part that calculates and monitors processing load thereof, and

the space allocation change executing part accepts a request for the space allocation change from another of the calculators when the processing load obtained from the processing load monitoring part is equal to or less than a predetermined threshold.

7. The simulator according to claim 6,

wherein the processing load monitoring part calculates processing load of the calculator thereof based on the number of agents existing in at least a divided space allocated to the calculator thereof.

8. The simulator according to claim 3,

wherein the communication amount estimating part calculates the amount of communication after the allocation change, further considering an amount of communication to be generated when an agent existing in the allocation change candidate space moves to a divided space allocated to the calculator targeted for the allocation.

9. The simulator according to claim 8,

wherein the communication amount estimating part calculates an amount of communication to be generated when the agent existing in the allocation change candidate space moves to a divided space allocated to the calculator targeted for the allocation, based on the number of the agents having moved in a past fixed time.

10. A calculator used for a simulation in which behaviors of a plurality of agents existing in a virtual space are simulated by distributed processing that uses a plurality of calculators communicable with one another, comprising:

a space allocation storage that stores, as space allocation information, a division range of each of divided spaces in the virtual space, and a calculator to which processing related to an agent existing in each of the divided spaces is allocated;

an allocation change candidate space extracting part that refers to the space allocation storage so as to extract, as an allocation change candidate space, a divided space to be a candidate for an allocation change from among divided spaces whose one or more adjacent spaces are allocated to another of the calculators;

a communication amount estimating part that calculates an amount of communication or an amount of change in communication to be generated between the calculator targeted for the allocation and another of the calculators when the allocation change candidate space is allocated to a calculator targeted for the allocation, based on the number of agents existing in the allocation change candidate space and an adjacent divided space thereof; and

a space allocation change judging part that determines whether or not to allocate the allocation change candidate space to the calculator targeted for the allocation, based on the amount of communication or the amount of change in communication calculated in the communication amount estimating part.

11. A recording medium storing a simulation program using a computer for a simulator in which behaviors of a plurality of agents existing in a virtual space are simulated by distributed processing that uses a plurality of calculators communicable with one another, the simulation program causing the computer of at least two of the calculators to execute:

processing of accessing a space allocation storage that stores, as space allocation information, a division range of each of divided spaces in the virtual space, and a calculator to which processing related to an agent existing in each of the divided spaces is allocated;

allocation change candidate space extracting processing of extracting, as an allocation change candidate space, a divided space to be a candidate for an allocation change from among divided spaces whose one or more adjacent spaces are allocated to another of the calculators, by referring to the space allocation storage;

communication amount estimating processing of calculating an amount of communication or an amount of change in communication to be generated between the calculator targeted for the allocation and another of the calculators when the allocation change candidate space is allocated to a calculator targeted for the allocation, based on the number of agents existing in the allocation change candidate space and an adjacent divided space thereof; and

space allocation change judging processing of determining whether or not to allocate the allocation change candidate space to the calculator targeted for the allocation, based on the amount of communication or the amount of change in communication calculated in the communication amount estimating processing.