Data structures and processing methods for highly scalable simulation platforms

Inventors

Basin, Ilya

Abstract

Disclosed herein are systems and methods for simulating an environment over a plurality of intervals of in-simulation time by using a two-part data structure to represent agents or entities in the simulation. A system may create and store a data structure representing an agent in the simulation, wherein a first portion of the data structure represents characteristics of the agent at a present interval and a second portion of data structure represents characteristics of the agent at a future interval of the simulation. Also disclosed herein are systems and methods for executing a multi-agent simulation using multiple processing threads. A system may group a plurality of agents in the simulated environment into subsets associated respectively with nodes of the simulated environment, assign the subsets to respective separate processors of the system, and execute the simulation using separate processing threads associated respectively with the separate processors.

Core Innovation

The disclosed invention provides a simulation system for executing a simulation comprising a plurality of agents in a simulated environment using multiple processing threads. The system groups the plurality of agents into a first subset and a second subset, where the first subset is associated with a first node of the simulated environment and the second subset is associated with a second node of the simulated environment. Each subset is assigned to a different processor, and the simulation is executed with a first processing thread associated with the first processor to perform calculations for agents in the first subset and a second processing thread associated with the second processor to perform calculations for agents in the second subset.

The invention improves the scalability of multi-agent and cyber-physical systems simulation by using a two-part time-interval data structure per agent with a first interval representation and a second interval representation. A read-only state and a write-only state are represented using an indicator/flag, with a flip configuration or an optional copy of data to avoid per-interval allocation and deallocation and reduce memory deallocation and garbage collection overhead.

In addition, the invention supports near-linear scalability by using a flat query-time in-memory database and/or in-process database to keep query time at a flat query processing time, described as about 1 millisecond. It further uses node-based processing resource allocation by grouping agents into subsets mapped to simulation nodes, including inflection points, and assigning each subset to a dedicated processing thread to reduce thread contention. Shared variables are updated across threads using atomic increment and decrement operations rather than locking, including atomic interlock behavior.

The disclosure further aligns method and system implementations with multi-threaded simulation partitioning and the time-interval agent representation, including program execution on processors and thread-based calculations for subsets associated with nodes. It describes refining behavior tied to inflection points, such as conditional reassignment when agents do not reach inflection points during a current interval and shared-variable update control across processors.

Claims Coverage

The independent claim set described in the provided relevant claims includes three independent claim families: clm-00001, clm-00009, and clm-00010. Across these, the core coverage consists of grouping agents into first and second subsets associated with first and second nodes, assigning those subsets to first and second processors, and executing each subset’s calculations in separate processing threads; additional families refine node and inflection-point association and thread-safe concurrency behavior.

Overall, the claim coverage centers on executing a simulation by partitioning agents into node-associated first and second subsets, assigning subsets to respective processors, and calculating in parallel using corresponding processing threads. Dependent refinements further specify node and inflection-point-based grouping, query-based identification of agents per node, inflection-point-based conditional behavior during intervals, and concurrent updates to shared variables using atomic increment and decrement operations without locking.

Stated Advantages

Documented Applications