parallelize microsim

[namdre]

The current feature --threads is not recommended (#17057). The main problem (negligible speedup) is discussed in #9278
Help (i.e. on cache issues for multi-core code) is solicited.

• planMove

  • remove order-dependency from CRLL (caused by setApproaching / open)
  • remove order dependency from RNG calls (using lane-specific rngs)
  • removePassedDriveItems must be handled in setApproachingForAllLinks
    • handle non-actionStep removal of passedDrive items in setApproachingForAllLinks

• executeMove

  • remove order dependency from stopping place registration
  • synchronized access to MSMoveReminder - detectors (when it spans multiple lanes)
  • remove order dependency parkingArea occupancy check
  • remove order dependency from removeApproaching() - alternative resolution for linkstateEqual circular dependency
  • concurrent access to MSStopOut
  • remove order dependency on foe vehicle speed when computing zipper speed (foe speed must be stored in ApproachingVehicleInformation / DriveProcessItem)

• laneChange

  • compute change decision for all vehicles without executing them (can be done in parallel). Change decision can be encoded as a direction (default), distance (sublane model)
  • in a seperate phase, execute changes serially. Recheck if changing on an edge with more than 2 lanes. Reject decision if the target lane has been blocked by a change from the other direction

known issues

• nondeterministic routing result in parallel simulation #6319
• freeze in parallel simulation #16442
• non-deterministic behavior #16577
• When using multiple threads, the instant detector output file produces abnormal results. #17003

[namdre]

adding a RNG for every lane roughly doubles memory consumption (tested with /usr/bin/time --verbose on a 100x100 grid, memory consumption grows from 1,08GB to 2,24GB)

Alternatively: add option for setting the number of RNGs (>= number of threads) and use lane numerical id % numRNGs to assign RNG and thread. This allows for repeatable runs when the number of RNGs is kept constant.

[behrisch]

I would prefer the alternative mentioned. We can start with a default number of 32 (or 64?) RNGs and issue a warning about the possibility of different results if the user uses more threads. Another drawback of this approach is however that every small change to the network that modifies the number of lanes can change the results of the simulation. Should we rather assign the RNG depending on a hash of the edge id or is it not worth it?

[namdre]

Since we can assign a reference to the RNG once at simulation start, the additional effort of using a hash rather than modulo is negligible and well worth it.

[namdre]

@behrisch I've created branch 'Parallel' to continue work