Parallelisation - task scheduling potential enhancements

[Samuel-amap]

The generic nature of PlantSimEngine makes it harder to know what models or which independent subgraphs of the depency graph should be prioritised.

The exact order will heavily depend on the complexity of the models, and on their coupling, making it very case-specific. Sometimes a specific model might be quite computationally complex to run and a bottleneck to prioritise, sometimes there might be long dependency chains that outweigh the other bottlenecks.

One possible way of determining a usually good order when the user needs to run a simulation over many timesteps would be to have a short dry run that collects a little data, to then determine what seems like the potential ideal order in which the subgraphs and models should be run.

This might not be trivial with multi-scale, hard dependencies and soft dependencies. Perhaps having modelers declare some particularly complex models as being heavier to handle could help, as well.

[Samuel-amap]

Thinking back to this enhancement, considering the context, we might already be able to guess which portions are likely to be the most computationally expensive. These'd be :

• Light interception calculations on the 3D geometry (not part of PSE)
• Models which act on the most numerous organs of the plant (leaves, flowers, fruits, internodes, which will be many orders of magnitude more numerous than the number of plants in an agroforestry context, once the plant has grown a few years)
• Models that update the environment or interact with it in the case where its granularity is small enough (for instance, a voxelisation around the plant)

It actually seems likely that a dry run (especially on an immature tree with much fewer terminal organs) might not lead to a more interesting task scheduling, or would have the same predictable bottlenecks in many situations. It might be more valuable to organise scheduling and data around the three cases described in the list above.

[Samuel-amap]

Looking back at the comments in this issue : they are outdated.
Some models manipulate the MTG in a non-threadsafe way, with potential recursive calls, and organ creation currently affects the way the simulation is run, and the filtered outputs for every timestep. The approaches mentioned above are unlikely to be applicable in a straightforward manner. Best also to wait for varying timesteps and multi-plant simulations to better understand the problem's boundaries.

(That isn't to say that there aren't any nifty scheduling strategies or traits, or optimisations per-scale, etc.)

[Samuel-amap]

After a bit of discussion on the topic, some thoughts :

• Some individual models, or subbranches in the dependency DAG (Directed Acyclic Graph) can be run independently.
• Some models can be run at any timestep at any given point, as long as they get their inputs.
• Some models are run for every instance of a given scale/organ and don't depend on other same-scale knowledge, and can therefore be run in parallel for each instance of that scale.
• Some models will run at every timestep, others only some of the time.
• Independent subbranches of the DAG are unlikely to provide huge wins (in XPalm, anyway), given the heavily coupled nature of the models. This might not be so true if there are different timesteps, ie at the smallest timestep the models that run in practice most of the time might equate to a sparser subgraph that has several independent components.
• As indicated above, some models are more costly than others or will run many more times per timestep, or run on more timesteps. On a growing plant the number of leaf/phytomer/fruit/petiole/root/etc. organs might be initially quite small then increase polynomially or even exponentially for a while and number the tens or hundreds of thousands

And some models impact the MTG by changing its state -not just querying it- which causes some nasty potential concurrency issues if not properly taken into account. There might also be analogous issues with the plantsimengine_status attributes, I've not looked into it.

This makes potential effective parallelisation opportunities quite hard to infer without any extra knowledge provided by the specific simulation. It is extremely difficult to infer in advance which models should be prioritised, and which organs are likely to be most numerous without any user hints, or first pass.

Cache misses or write contention might also be problems in situations where multiple threads which to access or modify nearby data (MTG nodes, for instance). It is possible to duplicate some data and then agglomerate results at every timestep, or at specific synchronisation points, but that is also complex to achieve in a way that works both generically and efficiently. The same problem might apply to multi-timestep connector models, if they are accessed concurrently.

There are also other issues that might happen further down the line. Here are a couple that come to mind :

1. If some models that affect the MTG run in parallel, the order on which they run is dependent on thread-scheduling, and might differ from one run to another, or between a single and a multi-threaded simulation, since organs might be created in a different order and have different ids
2. This can also become a source of bugs if a model creates an organ and another model queries the MTG to, say, count the number of organs. There needs to be a guarantee that the MTG queried isn't affected by changes in the same timestep. I am not sure we provide that guarantee atm.
3. If PlantSimEngine is used to call another instance of itself (eg, by running XPalm on one end, but coupling that in another dependency graph with other tools), there might be some issues with subtler interdependencies (as well as world-age problems, potentially, come to think of it).
4. Any kind of inter-plant interaction model which affects two MTGs at once, or a model that requires propagating 3D data through the MTG might require some caution as well.

• For 1), it might be worth adding a single vs multi thread test, and make sure results are predictably consistent. This consistency can be achieved by either accepting specific differences in organ creation order within a single timestep, or by notifying changes to be made to a temporary structure, delaying MTG modification until the end of a timestep, and then forcing the order to mimick single-thread order.
• For 2), we could add the guarantee that the MTG organs use is consistent within a timestep, by disabling querying new organs until the next timestep, and updating the MTG at the end of a timestep. This isn't such a big change in terms of engine code, but does constrain model design (and requires some changes in the Toy Plant example in the documentation).
• For 3) and 4), I actually think there shouldn't be issues (outside of world-age, that might be a concern) in most common cases, but that does need testing.

Ensuring some of the data structures (especially the MTG) can be accessed concurrently (or duplicated thread-locally and then aggregated) to ensure performance doesn't degrade per thread compared to a single-threaded simulation will be necessary in any case.

One alternate approach for MTGs could be to have a read-only copy that is used for querying, and another that will be edited during the timestep, something along those lines. Or to store the current and 'next' state simultaneously. Caution would also need to be applied in terms of variable consistency (ie if a previous timestep variable is required, how to access it).

Overall, it feels like any fully generic approach isn't guaranteed to bring huge wins, even in the most common cases, as bottlenecks might be totally different with only minor model changes (or a different MTG structure), and would require a significant amount of work (and might be brittle).

It might be better to solve some of the prerequisites, then apply ad hoc parallelization to predictable bottlenecks at specific points (say, Leaf/Phytomer level in XPalm, or run PlantSimEngine in parallel per-plant in a multi-plant simulation), and profiling other configurations' bottlenecks before trying out more general approaches. Enabling the user -not just the modeler, unfortunately- to provide some hints on the approach might also be interesting.

[Samuel-amap]

Not sure about the following, it needs more investigation, but writing this down for future reference just in case :

Variables marked as PreviousTimestep may be changed by a model, and the updated value will become visible to models that make use of it further down the line, or even simulataneously. This approach was chosen as a mechanism to open a cycle.

This may cause some data dependency between models that affects parallelization implementations ; for instance, it may be undesirable for models that make use of that same variable (even if one is a bit further down the line) to run on different threads...