Incremental Simulation

[bradNASA]

I was hoping we could collaboratively edit a design here. I wrote up some notes on this based on conversations with the team.

Incremental simulation is updating a simulation for changes to a plan by re-simulating

• a subset of activities,
• a subset of resources, and
• a subset of time.

The goal is to minimize the time it takes to simulate by reusing past simulation results.

[bradNASA]

Use cases

• Use case 1: edit plan
  • A plan is simulated
  • Activities in the plan are modified.
  • When the plan is simulated again, it takes advantage of incremental sim
• Use case 2: update mission model jar file (not expected to implement)
  • A plan is simulated
  • A new mission model is loaded
  • A copy of the plan is made for the new mission model
  • When the plan is simulated again, it takes advantage of incremental sim
    • Changes are detected by
      • comparing changes in classes in the jar and
      • comparing what resources are registered
• Use case 3: scheduling
  • User invokes scheduler on a scheduling goal
  • Plan is updated with new activities and fully simulated taking advantage of incremental simulation

[bradNASA]

Where does incremental sim get the changes?

Options:

1. The cleanest way to identify changes is to diff the plan with the simulation results to be reused
   • Computed parameters must not be compared since they are not computed for the plan. For example, computed durations should be expected to differ without be recognized as a change.
2. The changes are tracked in memory
   • Only after the first simulation
   • A full simulation is necessary on startup
3. The changes are tracked in the database
   • Do we already get diffs for free? Maybe with the hidden branches in the next option
4. The changes come from diffs between branches/versions
   • This requires the user to branch before making edits, or
   • A hidden branch is created after every simulation and the merged in as part of the next simulation.
5. Invoker must specify whether incremental sim is applied and for what changes

[bradNASA]

Scheduler interaction with simulation

• Currently, the scheduler invokes simulation in its own process independent of the merlin server and without updating the database with simulation results.
• Why?
  • The simulation is done in the scheduler instead of over http for efficiency.
  • The scheduler has a database separate from Merlin's.
  • The scheduler is meant to only have access like any user to the Merlin server.
• In order to take advantage of incremental sim on merlin,
  • the scheduler needs to be able to simulate up to a point in time or to an activity.
  • Then, based on simulation details, the scheduler will schedule other activities.
• Since getting simulation results over http is expensive, can the scheduler make GraphQL queries for specific information instead?
  • We would then need the capability to write to the DB after a partial simulation.
  • Or, we could answer GraphQL queries on simulation results from memory.
• If the scheduler was part of Merlin, would there be a more natural integration and execution of scheduling and simulation?
• If the scheduler continued to use its own simulation, then could it write the result to the DB?
  • The simulation database is a separate component from Merlin, and the server and workers have access to it. Is it a big deal if other apps can access, too?
  • If not, under what conditions or changes to the interface would this be acceptable?
  • Assuming results are not written back, at least the activities will, and incremental simulation will hopefully be able to resimulate quickly.

[bradNASA]

Implementation task breakdown

• Incremental simulation with given changes to activities.
  • Update SimulationDriver to
    • Reuse simulation result data from memory and/or database
    • Update simulation results
      • Are new sim results created for each simulation, or are they overwritten? new
      • Are they saved as diffs from other sims?
        • If not, should they?
    • Reuse event-graph from memory and/or database
    • Optionally store event graph with simulation results
    • Optionally store and retrieve cell states If serialization is provided by the user
• Implement one of the above approaches from "Where does incremental sim get the changes?"
• Updating the scheduler as necessary to leverage incremental simulation or the Merlin interface

[bradNASA]

Approach -- How it might work

• Initialize the simulation in the SimulationDriver as usual except
  • Only add tasks for changed activities
  • Suppress/pause (exclude from simulation) resources not known to be affected by the changed activities
  • Load past simulation results, event graph, and any cell states from the DB if not already in memory
    • Could load parts of these dynamically when needed if it is more efficient
• Update the event graph and simulation results for activity changes as part of the simulation
  • This may be implemented by another effort to stream simulation results to the database during the simulation
  • This includes removed affects for removed (or moved) activities
• When a resource is affected during the simulation,
  • Initialize the resource with the the latest saved cell state before the current sim time if necessary
    • or if no cell state exists, initialize the cell from beginning of the plan horizon
  • Use the event graph to simulate the cell up to the current simulation time.
    • Should not need to record simulation results since it was suppressed before because no change was expected
• After updating the cell state for the effects of changed activities, if the state value matches the pre-existing simulation results, suppress simulation for the resource
• Other activities may change during the simulation
  • Update the affected resources, event graph, and simulation results
  • Update the plan!
• An activity that reads a changed state needs to be resimulated, and it may have started at beginning of the plan horizon, so it needs to be simulated from its start time, and its past effects can be ignored. Daemon tasks can be resimulated similarly.

[JoelCourtney]

Suppress/pause (exclude from simulation) resources not known to be affected by the changed activities

Unfortunately we have no information about this. As long as we want to guarantee correctness, there is a chance that a changed activity could theoretically affect any resource.

Only add tasks for changed activities

If any resource changes, any tasks after that point could do something different, not just the changed activities. This is because we don't know what activities query what resources, or what they use those values for.

[JoelCourtney]

Some ideas have been floating around for runtime dependency tracking - recording which tasks get or set which resources so we know the above information - but the main problem is that if a task has any control flow then the records can easily be incomplete.

[bradNASA]

We don't need to know all of the resources that will be affected. We can play catch-up when we simulate activities and discover which resources they do affect. But, yes, that assumes that we know which activities need to be re-simulated. It's not clear to me where the info about activities reading resources lives or was meant to live. Anyone know?

Even if an activity can change what it affects or gets based on a condition, that condition would (should) only change based on a change to a resource that is read by that activity or a parent activity. And, assuming we noticed it read that resource before, we know when to resimulate it and see what other resources it affects or gets. And, we can then recompute those resources if they are not already up to date. Make sense?

[bradNASA]

@mattdailis pushed the prototype/dependency-graph branch with some changes that attempt to capture the reads in the event graph, too. There may be a performance disadvantage with mixing the reads with the effects, but there are different ways that can be avoided, and changing later wouldn't be hard.

[dandelany]

We are renewing our work towards an Incremental Simulation feature this year 🚀 - @bradNASA is leading this effort and we are bringing @jswope2112 onto the Aerie team to help with the implementation.

The comments above from last year are still a good reflection of the planed design, so they're a useful reference for anyone just joining the conversation. Additionally @bradNASA recently gave a presentation to the AI Group summarizing things with some great visualizations - the slides can be found here: https://jpl.slack.com/archives/C04NJK8E52T/p1712010300532409

Today we had a meeting with @Mythicaeda @bradNASA @adrienmaillard & myself to talk about some concerns and edge cases that @Mythicaeda wanted to make sure are being considered. My notes are below - this was a very useful discussion and almost all of the points below will need some further thought and work before Aerie is ready to support incremental sim.

• Config files staleness
  • The sim config can define external files to be uploaded and used by the sim.
  • what happens if they change? How does incremental sim know that it's stale & needs to re-run?
  • If the file path changes, no problem. Current plan is to have any changes to sim config mark the entire simulation as stale (ie. "invalidate" it)
  • However - if the file is replaced (contents changed, but same name), we need to detect it somehow
  • Proposal: hash/checksum the files on every simulation run & compare to last run, invalidate & re-run sim if changed.
• Files loaded by activities
  • Clipper has some activities that load external files at simulation time, when they are run
  • Incremental sim has no way to know if these files are changed, which would invalidate that activity
  • Proposal: should have a way to mark certain activities as "always stale" or "external dependency". Force sim to always re-run these.
    • These would ruin much of the performance benefit of incremental sim but at least could guarantee correctness.
  • Proposal 2: For these activities, fetch the file on every sim run and do a hash/checksum comparison, then you can decide whether or not that particular activity is stale.
    • However, this would require Aerie to register/know about all of these files. We would need to implement an API in Aerie for making external file requests and force users to use that in activities, rather than allowing them to fetch files however they want.
• Storing "reads" in the EventGraph
  • Incremental sim needs to know about which activities read from which cells/resources and when, to figure out what needs to be resimulated.
  • Current plan is to make "reads" a new type of Event and keep them in the EventGraph
  • These would not be serialized and therefore not stored in the DB(?)
  • Some concern about memory implications of this - they are small but there could be a lot of them.
  • Also some questions from @Twisol and @mattdailis about whether this is the correct philosophical approach, or whether any alternatives exist if we change architecture more significantly.
  • TODO: meet with @mattdailis and @Twisol since this is important decision to make early.
• Memory concerns
  • Sim engines can grow very large im memory, based on clipper experiments. At the end of the planning horizon - roughly 3GB.
    • If incremental sim is storing multiple engines, this could be even worse.
    • Brad: not too concerned yet, because subsequent sims/engines will only need to store the delta from last sim instead of entire copy
  • How to deal with a venue with lots of plans & lots of engines loaded in memory?
    • Proposal: some kind of LRU cache, evict oldest engines when nearing memory limit?
  • TODO: Most of our incremental sim prototyping thus far has been with Banananation & similarly small models. Going forward we should use copies of the Clipper TT-6 model/plans
• Workers
  • Aerie sims use a worker pool. Which worker will run your simulation? Today it's random and doesn't matter.
  • In future it will become important for incremental simulation requests to run on the same worker that ran their previous sim
  • We don't have any mechanism for doing this, we don't distinguish between workers and have no way to identify them
  • (rough) proposal: some way to distribute work to particular workers, OR for workers to be able to filter out work that they're not allowed to do
    • This may cause issues with worker distribution - need to make sure some don't get overloaded while others are free. Can redistribute to another worker if we pay the price of a full resimulation.
• Closing connections opened by the Model
  • Mission models may open connections & don't currently have a way to specify how to close them
    • because today the worker/engine are "thrown away" and all connections are automatically closed then.
  • With incremental sim, if we keep old engines around, these open connections could cause problems
  • Proposal: provide an interface for users to implement a close() function in their model where they would do any cleanup necessary
    • This would be called by incremental sim to cleanup old sim engines.
• Multiple mission models in the worker
  • currently, a worker can't load multiple models, and we get a new worker if the model changes at all
  • incremental sim needs to solve the problem of having multiple mission models for different plans loaded
  • TODO: figure out a proposal for this...

[bradNASA]

I asked @mattdailis about the last bullet, and he said that the worker creates a class loader for each sim request, so there shouldn't be a problem with multiple mission model instantiations, but we need to test and see.

[bradNASA]

For the "Files loaded by activities" bullet, I expect we can get the best of both of the two proposals and avoid modifying aerie code. For example, the user could have a resource, C, for the checksum of the file and an activity, A, that is marked "always stale," computes the checksum of the file, and writes it to R. Activity A would precede activity B that actually reads the file. B would not need to be marked "always stale" and would only be re-executed if R changed. That can all be done by the user.

[ewferg]

While it's nice that there seems to be a solution to the files loaded by activities problem that wouldn't require core changes, I'd caution us not to put too much onus on our users to implement workaround solutions. If we do ask them to do something like @bradNASA described, we will want to document it thoroughly!!

[bradNASA]

A New Set of Work Items

This list is a few weeks old--needs updating based on recent discussions

1. database interface for storing and merging partial (incremental) simulation results
   a. How does this overlap with streaming results?
2. testing
   a. ensure that the inc sim git branch results for a first/single simulation are the same as for the develop branch
   b. ensure that incremental simulations have the same results as if fully simulated. [This should be extensive and consider many interactions (of tasks and conditions), especially within a single time point.]
   c. test with existing complex models (e.g., from clipper)
   d. scheduling tests
   e. performance tests (simulation and scheduling)
   f. test with contrib streamline resources
3. scheduling integration -- Adrien suggested that most or all of a java class could be removed since it replicates what inc sim already does.
4. container-level management -- routing sim requests to the merlin-worker with the right SimulationEngine
5. inc sim user controls
   a. override to do full simulation (and throw out past sims)
   b. override to allow inc sim to apply across sim config changes (?)
6. inc sim core implementation (if re-doing the work in prototype/incremental-sim branch)
7. combine checkpoint restart and inc sim so that past sim can be loaded from DB and used with inc sim
8. provide user/modeler the ability to mark a task, activity, directive, cell, or resource as "always stale" so that inc sim knows to rerun/recompute it.
9. have a collapse mechanism to merge a chain of simulation engines in memory into one to avoid overhead of chaining
10. have a collapse mechanism to merge partial sim results in the database (related to bullet 1 above)