crate parallelization

[imrn99]

this issue is used to track and outline tasks related to the parallelization of this crate's code. this includes both kernels/algorithms parallelization as well as modifications to the data structure to make it parallel friendly (== ownership compliant).

Goals

Primary:

• Explore possibilities for grisubal parallelization
• Implement a parallel-friendly version of CMap2
• Make it good :)

Secondary:

• Introduce some parallelization in the building routines
• Test performance of a parallel cell triangulation routine (of existing cells, not triagnulation of a domain)

[imrn99]

ParallelCMap2 concept

name tbd, PMap2 ??

Main issues / challenges

• Attribute system relies on a bunch of traits so that the manager does not "see" attributes. All traits using &mut self would have to be duplicated to have non-mutable method signatures.
• Which sync mechanism to use over what data?
• How to handle darts addition / deletion (i.e. allocation to some extent)?
• Can the current builder be extended to output this new kind of map?

Task outline

• first impl
  • figure out vertex storage, ignore attributes for now
  • unused darts policy (should have similar sync to the beta storage)
  • beta values storage
  • basic ops
  • (un)links
  • (un)sews
  • orbits / id computations / i_cells (unchanged?)
  • vertex accesses
  • utils
  • improve & merge:
    • refactor!(core): change underlying implementation of CMap2 to add sync mechanisms #201
    • feat(core): implement parallel variants of attribute storage traits & structs #199
    • refactor!(core): create a common module in core crate #200

Issues

• enh: mitigate regression induced by the parallel implementation #215

[imrn99]

grisubal parallelization

Step 1 / Compute intersection data

this section needs significant changes for it to run in parallel. incidentally, this is the section that scales the worse.

Step 2 / Insert intersections

the main upgrade here would be precomputing and allocating darts beforehand so that all splitn_edge can be replaced with no-alloc variants (thus improving performance AND removing all contention).

the end result should probably be an additional step (~1.9) since having the dart information beforehand allows us to run step 3 in parallel of with step 2.

Step 3 / Compute edge data

last § + the code for this section can actually be parallelized as-is.

Step 4 / Insert edges

like in step 2, we can preallocate darts for the new edges & run iterations of this step fully in parallel.

Observations

not all sections scale the same: for the fixed input examples/shape.vtk, using 0.01 grid size instead of 1.0 multiplies the time of each section by:

section	_ times longer
step1	2000
step2	100
step 3	25
step 4	40

all of these being superseeded by the time taken by grid building (x6000, & the most significant by flat value).

[imrn99]

lots of challenges to get the implementation working just right. here's a road ahead:

• refactor(kernels::grisubal): clean-up module code #216
• finish cancelled due to perf issue refactor!: replace identifier type aliases with strong-typed structures #220
  • add in grisubal changes
  • benchmark
  • move collections to components module
  • document strong typing implementation & policy
• expose "retry" APIs: refactor!(core): rework sew methods to allow for more control #224 & refactor!(core): rework attribute semantics #226
  • retry a transactional method
  • retry if there was an issue with attributes merging/splitting
• write scaling kernels using the new API
  • triangulate all cells of a mesh
  • parallelize grisubal