Parallel proximity detection for computer simulations

• US 5,781,762 A
• Filed: 03/07/1997
• Issued: 07/14/1998
• Est. Priority Date: 04/10/1995
• Status: Expired due to Fees

• Current Assignee: United States Incorporated, United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Wieland, Frederick P., Steinman, Jeffrey S.
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/813,531
• Time in Patent Office: 494 Days
• Field of Search: 395/500, 364/578, 364/423, 364/232.3, 364/916.5, 364/922.5, 364/933.8
• US Class Current: 703/21
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30

Abstract

The present invention discloses a system for performing proximity detection in computer simulations on parallel processing architectures utilizing a distribution list which includes movers and sensor coverages which check in and out of grids. Each mover maintains a list of sensors that detect the mover'"'"'s motion as the mover and sensor coverages check in and out of the grids. Fuzzy grids are included by fuzzy resolution parameters to allow movers and sensor coverages to check in and out of grids without computing exact grid crossings. The movers check in and out of grids while moving sensors periodically inform the grids of their coverage. In addition, a lookahead function is also included for providing a generalized capability without making any limiting assumptions about the particular application to which it is applied. The lookahead function is initiated so that risk-free synchronization strategies never roll back grid events. The lookahead function adds fixed delays as events are scheduled for objects on other nodes.

Claims

1. In a system of interconnected processor nodes operating on a parallel processing system, a method of performing proximity detection of sensors and movers in grids that model simulated space by processing events comprising discrete simulation objects defined by said sensors, said movers, and said grids distributed among said nodes as a sequence of discrete sensor, mover, and grid events, comprising the steps of:

generating current equations of motion for each mover and providing each of said equation of motion to each of said sensor within a coverage area;

processing said respective equations of motion; and

determining the exact positions of all movers by said sensors that are in said sensors coverage area from said equations of motion of said movers to create a logically correct solution without approximations.

2. The invention as set forth in claim 1 further comprising the step of changing motion of said movers.

3. The invention as set forth in claim 2, wherein said changing motion of said movers is performed by human interactions.

4. The invention as set forth in claim 2, wherein said changing motion of said movers is performed by internally computed changes.

5. The invention as set forth in claim 1, further comprising the step of providing fuzzy grids for crossings of said movers across irregular grids.

6. The invention as set forth in claim 5, further comprising the steps of:

modeling simulated space and managing spatial information for said movers and said sensor coverage areas;

computing approximate grid crossings of said movers and sensor coverage areas; and

expanding sensor coverage areas by fuzzy resolution parameters so that said crossing of said irregular grids are accommodated.

7. The invention as set forth in claim 6, further comprising the step of defining fuzzy resolution parameters to reflect various grid uncertainties.

8. The invention as set forth in claim 1, further comprising the steps of generating new events, and providing a lookahead function as a time difference between said processed events and said newly generated events for providing scalability and improving parallel performance.

9. The invention as set forth in claim 8, further comprising the step of adding fixed delays by said lookahead function as said events are scheduled for objects on other nodes.

10. The invention as set forth in claim 1, further comprising the step of providing zero time delays for events scheduled between objects on the same node.

11. The invention as set forth in claim 1, further comprising the step of providing correct spatial information for objects that are moving.

12. The invention as set forth in claim 8, wherein Breathing Time Buckets never roll back grid events.

13. The invention as set forth in claim 8, further providing a Lazy Cancellation step for allowing events to be processed out of order when each event does not affect another event.

14. The invention as set forth in claim 13, wherein said Lazy Cancellation step utilizes tolerances so that a user checks and decides whether said event is to be reprocessed or rolled forward.

15. The invention as set forth in claim 14, wherein said Lazy Cancellation step processes mover events and sensor events out of order so that mover events and sensor events are independent of each other.

16. The invention as set forth in claim 14, wherein said Lazy Cancellation in combination with a Time Warp reduces roll back of grid events.

17. A system of interconnected processor nodes operating in parallel, comprising:

a set of discrete simulation objects distributed among said nodes defined by movers, sensors, and grids;

a computer program operating on said system for simulating mutual interactions of said set of discrete simulation objects as a sequence of discrete events changing state variables of respective simulation objects;

wherein each of said grids represent discrete simulation objects that model simulated space and respectively manage movers and sensors that are operating in grid spaces of respective grids;

wherein said movers move according to a sequence of equations of motion and each of said sensor is provided with said equations of motion for each mover within a coverage area; and

wherein said computer program performs object-oriented simulation at each one of said nodes and performs proximity detection of said movers and said sensors in said sequence of events by processing said events, so as to generate new event-defining messages addressed to respective ones of said nodes for creating a logically correct solution without approximations.

18. The invention as set forth in claim 17, further comprising:

means for modeling simulated space and managing spatial information for said movers and said coverage areas of said sensors;

means for computing approximate grid crossings of said movers and said coverage areas of said sensors; and

means for expanding sensor coverages by fuzzy resolution parameters so that said crossing of said irregular grids are accommodated.

19. A computer-readable medium for causing a computer system of interconnected processor nodes operating in parallel to function as a parallel processing system, comprising:

a computer-readable storage medium;

a computer program stored on said medium;

a set of discrete simulation objects distributed among said nodes;

wherein said computer program operates on said system for simulating mutual interactions of said set of discrete simulation objects as a sequence of discrete events changing state variables of respective simulation objects and wherein said computer program performs object-oriented simulation at each one of said nodes and comprises,

grids representing discrete simulation objects that model simulated space and respectively manage movers and sensors that are operating in grid spaces of respective grids;

movers representing discrete simulation objects, wherein said movers move according to a sequence of equations of motion; and

sensors representing discrete simulation objects, wherein said sensors are provided with said equations of motion for each mover within a coverage area;

wherein proximity detection of said movers and said sensors is performed in said sequence of events by processing said events, so as to generate new event-defining messages addressed to respective ones of said nodes for creating a logically correct solution without approximations.

20. The invention as set forth in claim 19, further comprising a plurality of EOMAN objects located on said nodes having a list of mover scripts and a list of sensors for each of said mover scripts, wherein said EOMAN manages said mover equations of motion used by said sensors that are local to said nodes so that said equations of motion are locally distributed to appropriate sensors.

21. The invention as set forth in claim 19, further comprising newly generated events and a lookahead function defined as a time difference between said processed events and said newly generated events for reducing grid events from rolling back.

22. The invention as set forth in claim 21, wherein said grids further comprise grid spaces defining a tiled area, a list of movers that are located in said grid spaces, and a list of sensors for viewing said grid spaces and wherein said grids respectively manage said list of movers and said list of sensors that are operating in said grid spaces.