PropagatorsParallelizer.java

  1. /* Copyright 2002-2024 CS GROUP
  2.  * Licensed to CS GROUP (CS) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * CS licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *   http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.orekit.propagation;

  18. import java.util.ArrayList;
  19. import java.util.Collections;
  20. import java.util.List;
  21. import java.util.concurrent.ExecutionException;
  22. import java.util.concurrent.ExecutorService;
  23. import java.util.concurrent.Executors;
  24. import java.util.concurrent.Future;
  25. import java.util.concurrent.SynchronousQueue;
  26. import java.util.concurrent.TimeUnit;

  27. import org.hipparchus.exception.LocalizedCoreFormats;
  28. import org.hipparchus.util.FastMath;
  29. import org.orekit.errors.OrekitException;
  30. import org.orekit.propagation.sampling.MultiSatFixedStepHandler;
  31. import org.orekit.propagation.sampling.MultiSatStepHandler;
  32. import org.orekit.propagation.sampling.MultisatStepNormalizer;
  33. import org.orekit.propagation.sampling.OrekitStepHandler;
  34. import org.orekit.propagation.sampling.OrekitStepInterpolator;
  35. import org.orekit.propagation.sampling.StepHandlerMultiplexer;
  36. import org.orekit.time.AbsoluteDate;

  37. /** This class provides a way to propagate simultaneously several orbits.
  38.  *
  39.  * <p>
  40.  * Multi-satellites propagation is based on multi-threading. Therefore,
  41.  * care must be taken so that all propagators can be run in a multi-thread
  42.  * context. This implies that all propagators are built independently and
  43.  * that they rely on force models that are also built independently. An
  44.  * obvious mistake would be to reuse a maneuver force model, as these models
  45.  * need to cache the firing/not-firing status. Objects used by force models
  46.  * like atmosphere models for drag force or others may also cache intermediate
  47.  * variables, so separate instances for each propagator must be set up.
  48.  * </p>
  49.  * <p>
  50.  * This class <em>will</em> create new threads for running the propagators.
  51.  * It adds a new {@link MultiSatStepHandler global step handler} to manage
  52.  * the steps all at once, in addition to the existing individual step
  53.  * handlers that are preserved.
  54.  * </p>
  55.  * <p>
  56.  * All propagators remain independent of each other (they don't even know
  57.  * they are managed by the parallelizer) and advance their simulation
  58.  * time following their own algorithm. The parallelizer will block them
  59.  * at the end of each step and allow them to continue in order to maintain
  60.  * synchronization. The {@link MultiSatStepHandler global handler} will
  61.  * experience perfectly synchronized steps, but some propagators may already
  62.  * be slightly ahead of time as depicted in the following rendering; were
  63.  * simulation times flows from left to right:
  64.  * </p>
  65.  * <pre>
  66.  *    propagator 1   : -------------[++++current step++++]&gt;
  67.  *                                  |
  68.  *    propagator 2   : ----[++++current step++++]---------&gt;
  69.  *                                  |           |
  70.  *    ...                           |           |
  71.  *    propagator n   : ---------[++++current step++++]----&gt;
  72.  *                                  |           |
  73.  *                                  V           V
  74.  *    global handler : -------------[global step]---------&gt;
  75.  * </pre>
  76.  * <p>
  77.  * The previous sketch shows that propagator 1 has already computed states
  78.  * up to the end of the propagation, but propagators 2 up to n are still late.
  79.  * The global step seen by the handler will be the common part between all
  80.  * propagators steps. Once this global step has been handled, the parallelizer
  81.  * will let the more late propagator (here propagator 2) to go one step further
  82.  * and a new global step will be computed and handled, until all propagators
  83.  * reach the end.
  84.  * </p>
  85.  * <p>
  86.  * This class does <em>not</em> provide multi-satellite events. As events
  87.  * may truncate steps and even reset state, all events (including multi-satellite
  88.  * events) are handled at a very low level within each propagators and cannot be
  89.  * managed from outside by the parallelizer. For accurate handling of multi-satellite
  90.  * events, the event detector should be registered <em>within</em> the propagator
  91.  * of one satellite and have access to an independent propagator (typically an
  92.  * analytical propagator or an ephemeris) of the other satellite. As the embedded
  93.  * propagator will be called by the detector which itself is called by the first
  94.  * propagator, it should really be a dedicated propagator and should not also
  95.  * appear as one of the parallelized propagators, otherwise conflicts will appear here.
  96.  * </p>
  97.  * @author Luc Maisonobe
  98.  * @since 9.0
  99.  */

  100. public class PropagatorsParallelizer {

  101.     /** Waiting time to avoid getting stuck waiting for interrupted threads (ms). */
  102.     private static long MAX_WAIT = 10;

  103.     /** Underlying propagators. */
  104.     private final List<Propagator> propagators;

  105.     /** Global step handler. */
  106.     private final MultiSatStepHandler globalHandler;

  107.     /** Simple constructor.
  108.      * @param propagators list of propagators to use
  109.      * @param globalHandler global handler for managing all spacecrafts
  110.      * simultaneously
  111.      */
  112.     public PropagatorsParallelizer(final List<Propagator> propagators,
  113.                                    final MultiSatStepHandler globalHandler) {
  114.         this.propagators = propagators;
  115.         this.globalHandler = globalHandler;
  116.     }

  117.     /** Simple constructor.
  118.      * @param propagators list of propagators to use
  119.      * @param h fixed time step (sign is not used)
  120.      * @param globalHandler global handler for managing all spacecrafts
  121.      * simultaneously
  122.      * @since 12.0
  123.      */
  124.     public PropagatorsParallelizer(final List<Propagator> propagators,
  125.                                    final double h,
  126.                                    final MultiSatFixedStepHandler globalHandler) {
  127.         this.propagators   = propagators;
  128.         this.globalHandler = new MultisatStepNormalizer(h, globalHandler);
  129.     }

  130.     /** Get an unmodifiable list of the underlying mono-satellite propagators.
  131.      * @return unmodifiable list of the underlying mono-satellite propagators
  132.      */
  133.     public List<Propagator> getPropagators() {
  134.         return Collections.unmodifiableList(propagators);
  135.     }

  136.     /** Propagate from a start date towards a target date.
  137.      * @param start start date from which orbit state should be propagated
  138.      * @param target target date to which orbit state should be propagated
  139.      * @return propagated states
  140.      */
  141.     public List<SpacecraftState> propagate(final AbsoluteDate start, final AbsoluteDate target) {

  142.         if (propagators.size() == 1) {
  143.             // special handling when only one propagator is used
  144.             propagators.get(0).getMultiplexer().add(new SinglePropagatorHandler(globalHandler));
  145.             return Collections.singletonList(propagators.get(0).propagate(start, target));
  146.         }

  147.         final double sign = FastMath.copySign(1.0, target.durationFrom(start));

  148.         // start all propagators in concurrent threads
  149.         final ExecutorService            executorService = Executors.newFixedThreadPool(propagators.size());
  150.         final List<PropagatorMonitoring> monitors        = new ArrayList<>(propagators.size());
  151.         for (final Propagator propagator : propagators) {
  152.             final PropagatorMonitoring monitor = new PropagatorMonitoring(propagator, start, target, executorService);
  153.             monitor.waitFirstStepCompletion();
  154.             monitors.add(monitor);
  155.         }

  156.         // main loop
  157.         AbsoluteDate previousDate = start;
  158.         final List<SpacecraftState> initialStates = new ArrayList<>(monitors.size());
  159.         for (final PropagatorMonitoring monitor : monitors) {
  160.             initialStates.add(monitor.parameters.initialState);
  161.         }
  162.         globalHandler.init(initialStates, target);
  163.         for (boolean isLast = false; !isLast;) {

  164.             // select the earliest ending propagator, according to propagation direction
  165.             PropagatorMonitoring selected = null;
  166.             AbsoluteDate selectedStepEnd  = null;
  167.             for (PropagatorMonitoring monitor : monitors) {
  168.                 final AbsoluteDate stepEnd = monitor.parameters.interpolator.getCurrentState().getDate();
  169.                 if (selected == null || sign * selectedStepEnd.durationFrom(stepEnd) > 0) {
  170.                     selected        = monitor;
  171.                     selectedStepEnd = stepEnd;
  172.                 }
  173.             }

  174.             // restrict steps to a common time range
  175.             for (PropagatorMonitoring monitor : monitors) {
  176.                 final OrekitStepInterpolator interpolator  = monitor.parameters.interpolator;
  177.                 final SpacecraftState        previousState = interpolator.getInterpolatedState(previousDate);
  178.                 final SpacecraftState        currentState  = interpolator.getInterpolatedState(selectedStepEnd);
  179.                 monitor.restricted                         = interpolator.restrictStep(previousState, currentState);
  180.             }

  181.             // handle all states at once
  182.             final List<OrekitStepInterpolator> interpolators = new ArrayList<>(monitors.size());
  183.             for (final PropagatorMonitoring monitor : monitors) {
  184.                 interpolators.add(monitor.restricted);
  185.             }
  186.             globalHandler.handleStep(interpolators);

  187.             if (selected.parameters.finalState == null) {
  188.                 // step handler can still provide new results
  189.                 // this will wait until either handleStep or finish are called
  190.                 selected.retrieveNextParameters();
  191.             } else {
  192.                 // this was the last step
  193.                 isLast = true;
  194.                 /* For NumericalPropagators :
  195.                  * After reaching the finalState with the selected monitor,
  196.                  * we need to do the step with all remaining monitors to reach the target time.
  197.                  * This also triggers the StoringStepHandler, producing ephemeris.
  198.                  */
  199.                 for (PropagatorMonitoring monitor : monitors) {
  200.                     if (monitor != selected) {
  201.                         monitor.retrieveNextParameters();
  202.                     }
  203.                 }
  204.             }

  205.             previousDate = selectedStepEnd;

  206.         }

  207.         // stop all remaining propagators
  208.         executorService.shutdownNow();

  209.         // extract the final states
  210.         final List<SpacecraftState> finalStates = new ArrayList<>(monitors.size());
  211.         for (PropagatorMonitoring monitor : monitors) {
  212.             try {
  213.                 finalStates.add(monitor.future.get());
  214.             } catch (InterruptedException | ExecutionException e) {

  215.                 // sort out if exception was intentional or not
  216.                 monitor.manageException(e);

  217.                 // this propagator was intentionally stopped,
  218.                 // we retrieve the final state from the last available interpolator
  219.                 finalStates.add(monitor.parameters.interpolator.getInterpolatedState(previousDate));

  220.             }
  221.         }

  222.         globalHandler.finish(finalStates);

  223.         return finalStates;

  224.     }

  225.     /** Local exception to stop propagators. */
  226.     private static class PropagatorStoppingException extends OrekitException {

  227.         /** Serializable UID.*/
  228.         private static final long serialVersionUID = 20170629L;

  229.         /** Simple constructor.
  230.          * @param ie interruption exception
  231.          */
  232.         PropagatorStoppingException(final InterruptedException ie) {
  233.             super(ie, LocalizedCoreFormats.SIMPLE_MESSAGE, ie.getLocalizedMessage());
  234.         }

  235.     }

  236.     /** Local class for handling single propagator steps. */
  237.     private static class SinglePropagatorHandler implements OrekitStepHandler {

  238.         /** Global handler. */
  239.         private final MultiSatStepHandler globalHandler;

  240.         /** Simple constructor.
  241.          * @param globalHandler global handler to call
  242.          */
  243.         SinglePropagatorHandler(final MultiSatStepHandler globalHandler) {
  244.             this.globalHandler = globalHandler;
  245.         }


  246.         /** {@inheritDoc} */
  247.         @Override
  248.         public void init(final SpacecraftState s0, final AbsoluteDate t) {
  249.             globalHandler.init(Collections.singletonList(s0), t);
  250.         }

  251.         /** {@inheritDoc} */
  252.         @Override
  253.         public void handleStep(final OrekitStepInterpolator interpolator) {
  254.             globalHandler.handleStep(Collections.singletonList(interpolator));
  255.         }

  256.         /** {@inheritDoc} */
  257.         @Override
  258.         public void finish(final SpacecraftState finalState) {
  259.             globalHandler.finish(Collections.singletonList(finalState));
  260.         }

  261.     }

  262.     /** Local class for handling multiple propagator steps. */
  263.     private static class MultiplePropagatorsHandler implements OrekitStepHandler {

  264.         /** Previous container handed off. */
  265.         private ParametersContainer previous;

  266.         /** Queue for passing step handling parameters. */
  267.         private final SynchronousQueue<ParametersContainer> queue;

  268.         /** Simple constructor.
  269.          * @param queue queue for passing step handling parameters
  270.          */
  271.         MultiplePropagatorsHandler(final SynchronousQueue<ParametersContainer> queue) {
  272.             this.previous = new ParametersContainer(null, null, null);
  273.             this.queue    = queue;
  274.         }

  275.         /** Hand off container to parallelizer.
  276.          * @param container parameters container to hand-off
  277.          */
  278.         private void handOff(final ParametersContainer container) {
  279.             try {
  280.                 previous = container;
  281.                 queue.put(previous);
  282.             } catch (InterruptedException ie) {
  283.                 // use a dedicated exception to stop thread almost gracefully
  284.                 throw new PropagatorStoppingException(ie);
  285.             }
  286.         }

  287.         /** {@inheritDoc} */
  288.         @Override
  289.         public void init(final SpacecraftState s0, final AbsoluteDate t) {
  290.             handOff(new ParametersContainer(s0, null, null));
  291.         }

  292.         /** {@inheritDoc} */
  293.         @Override
  294.         public void handleStep(final OrekitStepInterpolator interpolator) {
  295.             handOff(new ParametersContainer(previous.initialState, interpolator, null));
  296.         }

  297.         /** {@inheritDoc} */
  298.         @Override
  299.         public void finish(final SpacecraftState finalState) {
  300.             handOff(new ParametersContainer(previous.initialState, previous.interpolator, finalState));
  301.         }

  302.     }

  303.     /** Container for parameters passed by propagators to step handlers. */
  304.     private static class ParametersContainer {

  305.         /** Initial state. */
  306.         private final SpacecraftState initialState;

  307.         /** Interpolator set up for last seen step. */
  308.         private final OrekitStepInterpolator interpolator;

  309.         /** Final state. */
  310.         private final SpacecraftState finalState;

  311.         /** Simple constructor.
  312.          * @param initialState initial state
  313.          * @param interpolator interpolator set up for last seen step
  314.          * @param finalState final state
  315.          */
  316.         ParametersContainer(final SpacecraftState initialState,
  317.                             final OrekitStepInterpolator interpolator,
  318.                             final SpacecraftState finalState) {
  319.             this.initialState = initialState;
  320.             this.interpolator = interpolator;
  321.             this.finalState   = finalState;
  322.         }

  323.     }

  324.     /** Container for propagator monitoring. */
  325.     private static class PropagatorMonitoring {

  326.         /** Queue for handing off step handler parameters. */
  327.         private final SynchronousQueue<ParametersContainer> queue;

  328.         /** Future for retrieving propagation return value. */
  329.         private final Future<SpacecraftState> future;

  330.         /** Last step handler parameters received. */
  331.         private ParametersContainer parameters;

  332.         /** Interpolator restricted to time range shared with other propagators. */
  333.         private OrekitStepInterpolator restricted;

  334.         /** Simple constructor.
  335.          * @param propagator managed propagator
  336.          * @param start start date from which orbit state should be propagated
  337.          * @param target target date to which orbit state should be propagated
  338.          * @param executorService service for running propagator
  339.          */
  340.         PropagatorMonitoring(final Propagator propagator, final AbsoluteDate start, final AbsoluteDate target,
  341.                              final ExecutorService executorService) {

  342.             // set up queue for handing off step handler parameters synchronization
  343.             // the main thread will let underlying propagators go forward
  344.             // by consuming the step handling parameters they will put at each step
  345.             queue = new SynchronousQueue<>();

  346.             // Remove former instances of "MultiplePropagatorsHandler" from step handlers multiplexer
  347.             clearMultiplePropagatorsHandler(propagator);

  348.             // Add MultiplePropagatorsHandler step handler
  349.             propagator.getMultiplexer().add(new MultiplePropagatorsHandler(queue));

  350.             // start the propagator
  351.             future = executorService.submit(() -> propagator.propagate(start, target));

  352.         }

  353.         /** Wait completion of first step.
  354.          */
  355.         public void waitFirstStepCompletion() {

  356.             // wait until both the init method and the handleStep method
  357.             // of the current propagator step handler have been called,
  358.             // thus ensuring we have one step available to compare propagators
  359.             // progress with each other
  360.             while (parameters == null || parameters.initialState == null || parameters.interpolator == null) {
  361.                 retrieveNextParameters();
  362.             }

  363.         }

  364.         /** Retrieve next step handling parameters.
  365.          */
  366.         public void retrieveNextParameters() {
  367.             try {
  368.                 ParametersContainer params = null;
  369.                 while (params == null && !future.isDone()) {
  370.                     params = queue.poll(MAX_WAIT, TimeUnit.MILLISECONDS);
  371.                     // Check to avoid loop on future not done, in the case of reached finalState.
  372.                     if (parameters != null) {
  373.                         if (parameters.finalState != null) {
  374.                             break;
  375.                         }
  376.                     }
  377.                 }
  378.                 if (params == null) {
  379.                     // call Future.get just for the side effect of retrieving the exception
  380.                     // in case the propagator ended due to an exception
  381.                     future.get();
  382.                 }
  383.                 parameters = params;
  384.             } catch (InterruptedException | ExecutionException e) {
  385.                 manageException(e);
  386.                 parameters = null;
  387.             }
  388.         }

  389.         /** Convert exceptions.
  390.          * @param exception exception caught
  391.          */
  392.         private void manageException(final Exception exception) {
  393.             if (exception.getCause() instanceof PropagatorStoppingException) {
  394.                 // this was an expected exception, we deliberately shut down the propagators
  395.                 // we therefore explicitly ignore this exception
  396.                 return;
  397.             } else if (exception.getCause() instanceof OrekitException) {
  398.                 // unwrap the original exception
  399.                 throw (OrekitException) exception.getCause();
  400.             } else {
  401.                 throw new OrekitException(exception.getCause(),
  402.                                           LocalizedCoreFormats.SIMPLE_MESSAGE, exception.getLocalizedMessage());
  403.             }
  404.         }

  405.         /** Clear existing instances of MultiplePropagatorsHandler in a monitored propagator.
  406.          * <p>
  407.          * Removes former instances of "MultiplePropagatorsHandler" from step handlers multiplexer.
  408.          * <p>
  409.          * This is done to avoid propagation getting stuck after several calls to PropagatorsParallelizer.propagate(...)
  410.          * <p>
  411.          * See issue <a href="https://gitlab.orekit.org/orekit/orekit/-/issues/1105">1105</a>.
  412.          * @param propagator monitored propagator whose MultiplePropagatorsHandlers must be cleared
  413.          */
  414.         private void clearMultiplePropagatorsHandler(final Propagator propagator) {

  415.             // First, list instances of MultiplePropagatorsHandler in the propagator multiplexer
  416.             final StepHandlerMultiplexer multiplexer = propagator.getMultiplexer();
  417.             final List<OrekitStepHandler> existingMultiplePropagatorsHandler = new ArrayList<>();
  418.             for (final OrekitStepHandler handler : multiplexer.getHandlers()) {
  419.                 if (handler instanceof MultiplePropagatorsHandler) {
  420.                     existingMultiplePropagatorsHandler.add(handler);
  421.                 }
  422.             }
  423.             // Then, clear all MultiplePropagatorsHandler instances from multiplexer.
  424.             // This is done in two steps because method "StepHandlerMultiplexer.remove(...)" already loops on the OrekitStepHandlers,
  425.             // leading to a ConcurrentModificationException if attempting to do everything in a single loop
  426.             for (final OrekitStepHandler handler : existingMultiplePropagatorsHandler) {
  427.                 multiplexer.remove(handler);
  428.             }
  429.         }
  430.     }

  431. }