Parallel proximity detection for computer simulation

• US 5,652,871 A
• Filed: 04/10/1995
• Issued: 07/29/1997
• Est. Priority Date: 04/10/1995
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• 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): Teska, Kevin J.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/425,751
• Time in Patent Office: 841 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/6
• 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 with said movers continuously entering new grids and simultaneously exiting old grids and moving sensors periodically informing said grids of coverages of said sensors, comprising the steps of:

generating a distribution list of continually changing identifications of sensors and providing said list to said movers;

updating said distribution list of said changing identifications and providing said list to said movers as a script;

determining which nodes need said script of said movers and which nodes no longer need said script of said movers;

generating a mover'"'"'s current equation of motion and providing said equation of motion to said sensor;

sending first said mover'"'"'s script to said sensor'"'"'s node if said mover'"'"'s script is not on said sensor'"'"'s node and then providing a pointer to said mover'"'"'s current equation of motion to said sensor;

removing automatically said mover'"'"'s script if there are no more sensors on said node that need said mover'"'"'s current equation of motion;

passing pointers to new equations of motion to appropriate sensors when a mover'"'"'s equation of motion reaches its end time and a next equation of motion begins;

removing equation of motion pointers from corresponding sensors when said mover'"'"'s script ends so that there are no more equations of motion in a mover'"'"'s script; and

determining the exact positions of all movers by said sensors that are in said sensors coverage area from said mover'"'"'s equations of motion 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 coverages;

computing approximate grid crossings of said movers and sensor coverages; and

expanding sensor coverages 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 step of providing zero time delays for events scheduled between objects on the same node.

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

10. 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.

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

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

13. The invention as set forth in claim 8, further providing the step of Lazy Cancellation 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. In a system of interconnected processor nodes operating in parallel on a processing system to simulate mutual interactions of a set of discrete simulation objects defined by movers, sensors, and grids, wherein said simulation objects are distributed among said nodes as a sequence of discrete sensor, mover, and grid events changing state variables of respective simulation objects performing object-oriented simulation at each one of said nodes, a method of performing proximity detection of said movers and said sensors in said grids that model simulated space in said sequence of events by processing said discrete events, comprising the steps of:

entering a new grid and simultaneously exiting an old grid by said movers;

informing said grids of coverage areas of said sensors periodically;

generating a distribution list of sensors'"'"' identifications and providing said list to said movers;

updating said distribution list of said sensors'"'"' identifications and providing said list to said movers as a script;

determining which nodes need said script of said movers and which nodes no longer need said script of said movers;

managing said script of said movers by said movers;

generating a mover'"'"'s current equation of motion and providing said equation of motion to said sensor through an EOMAN object on said sensor'"'"'s node if said mover'"'"'s script is on said sensor'"'"'s node;

sending first said mover'"'"'s script to an EOMAN object on said sensor'"'"'s node if said mover'"'"'s script is not on said sensor'"'"'s node and then providing a pointer to said mover'"'"'s current equation of motion to said sensor;

removing a mover'"'"'s equation of motion pointer from said sensors through said EOMAN object;

removing automatically said mover'"'"'s script from said EOMAN object if there are no more sensors on said node that need said mover'"'"'s current equation of motion by said EOMAN object;

managing equation of motion in a mover'"'"'s script by the EOMAN for the sensors;

passing pointers to new equations of motion to appropriate sensors when a mover'"'"'s equation of motion reaches its end time and a next equation of motion begins;

removing equation of motion pointers from corresponding sensors when said mover'"'"'s script ends so that there are no more equations of motion in a mover'"'"'s script;

determining the exact positions of all movers by said sensors that are in said coverage areas of said sensors from said mover'"'"'s equation of motion provided by said EOMAN object;

changing motion of said movers;

updating said mover'"'"'s script in both said mover and in said EOMANs objects on different nodes.

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

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

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

21. The invention as set forth in claim 20, further comprising the steps of:

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

computing approximate grid crossings of said movers and sensor coverages; and

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

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

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

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

25. The invention as set forth in claim 17, 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.

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

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

28. The invention as set forth in claim 25, further providing the step of Lazy Cancellation for allowing events to be processed out of order when each event does not effect another event.

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

30. The invention as set forth in claim 29, 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.

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

32. A system of interconnected processor nodes operating in parallel on a processing system to simulate mutual interactions of a set of discrete simulation objects defined by movers and sensors, wherein said simulation objects are distributed among said nodes as a sequence of discrete sensor, mover, and grid events changing state variables of respective simulation objects performing object-oriented simulation at each one of said nodes and performing proximity detection of said movers and said sensors in said sequence of events by processing said events, comprising:

a plurality of grids each representing discrete simulation objects that model simulated space and have 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, wherein said plurality of grids respectively manage said list of movers and said list of sensors that are operating in said grid spaces;

wherein each of said movers has an equation of motion with node-distribution information and a script including a sequence of said equations of motion;

wherein each of said sensors has a list of pointers to said equations of motion of said movers;

wherein said movers further comprise a distribution list containing said sensors;

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 objects manage said equations of motion of said movers that are used by said sensors that are local to said nodes so that said equations of motion are locally distributed to appropriate sensors;

wherein said sensors move around a coverage area and periodically inform said grids of coverage areas of said sensors; and

wherein said movers move according to a sequence of at least one of said equations of motion.

33. The invention as set forth in claim 32, further comprising fuzzy grids modeling simulated space for approximating crossing calculations of said movers across irregular grids.

34. The invention as set forth in claim 32, 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.

35. The invention as set forth in claim 34, further comprising means for defining fuzzy resolution parameters to reflect various grid uncertainties.

36. A system of interconnected processor nodes operating on a parallel processing system having grids that model simulated space to simulate mutual interactions of a set of discrete simulation objects defined by movers, sensors, and said grids, wherein said simulation objects are distributed among said nodes as a sequence of discrete sensor, mover, and grid events for performing proximity detection of said movers and said sensors in said grids in said sequence of events by processing said events, said system comprising:

movers entering a new grid and simultaneously exiting an old grid and having an equation of motion with node-distribution information and a script including a sequence of said equations of motion;

sensors having a list of equations of motion of said movers, and wherein said sensors move around a coverage area;

wherein said movers further comprise a distribution list containing identifications of said sensors;

means for informing periodically said grids of said coverage areas of said sensors moving;

means for managing said distribution list that are operating in represented space of said grids;

means for creating a current list of said sensors;

means for returning said current list to said mover; and

means for updating said distribution list by said sensors of said movers based on said current list to define a new coverage area, wherein a logically correct solution is created without approximations.

37. The invention as set forth in claim 36, wherein said parallel processing system is a synchronous parallel environment emulation and discrete event simulation operating system.

38. The invention as set forth in claim 36, 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.

39. The invention as set forth in claim 36, further comprising fuzzy grids modeling simulated space for approximating crossing calculations of said movers across irregular grids.

40. The invention as set forth in claim 36, 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.

41. The invention as set forth in claim 36, 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.