Sparse Grids Roadmap

[sslattery]

Initial rectilinear partitioning path:

• Initial sparse grid functionality sparse grid #287
• Rename SparseIndexSpace -> SparseMap (Also the TileIndexSpace and similarly named classes). Note that a user will be inputting global ijk cell ids into this structure. Perhaps we should add a createSparseMap() function which takes a GlobalMesh<SparseMesh> to populate the number of global tiles including padding and returns a SparseMap. @YuxingQiu Sparsemap #326
• Partitioner needs to be generalized such that communicators with the given topology and block id information is returned by the partitioner. For example, the constructor implementation of GlobalGrid will largely be moved into the partitioners. @YuxingQiu Sparse Grid Partitioner #383; Update GlobalGrid and Partitioner #464
• Sparse Local Grid and Tile Index Space #534
• SparseArrayLayout and SparseArray @YuxingQiu Sparse Array #546
• Halo specialization for local grid which defines the relevant gather/scatter operations. May simply just need to return 0 at first when outside of sparse domain. @yuxing Sparse Halo #560

Hypre structured solvers mapped to SparseArray (future work)
Spline infrastructure for p2g and g2p mapped to sparse space (this will probably just work).

~ Unite load balancing interface (initially developed in #444) #541 ~ (separate issue)

Additional steps for non-rectilinear path:

• Develop new GlobalGrid<SparseMesh> specialization that will take and hold a SparseMap object. The blockRank will no longer be ijk but rather just the MPI rank. This information will be provided by the partitioner. Communicators will no longer have Cartesian topology - they will be general. We could consider trying out the general MPI topology feature. All indices are linearized so functions like dimNumBlock() are no longer needed. @sslattery
• Develop new SparseIndexSpace using SparseMap and information from the EntityType, Decomposition, and IndexType which would be used in a LocalGrid. @YuxingQiu
• LocalGrid specialization which defines partitioning strategy and returns SparseIndexSpace<3> based on EntityType, Decomposition, and IndexType. Our GlobalGrid specialization for sparse grids will have a partitioner which will help inform what things are owned and what are ghosted. This specialization should take a SparseMap in the constructor. @YuxingQiu
• LocalMesh specialization for sparse grids which describes the local geometry as a function of the dense local indices. @YuxingQiu
• Develop Kokkos::View allocation functions using a new CajitaLayoutSparse for 3d and 4d sparse index spaces. The new layout will map from ijk indices to the tile, cell, and, if 4D, field_dim indices. @sslattery
• Develop execution policy for sparse index spaces and the associated overloads of Cajita::grid_parallel_for in which user functors have the signature KOKKOS_LAMBDA(const int i, const int j, const int k) for 3D or KOKKOS_LAMBDA( const int i, const int j, const int k, const int d) for 4D. @YuxingQiu
• Refactor neighbors to not be ijk based but rather based on the 1d block id (e.g. MPI rank) as we will now communicate to arbitrary neighbors. Then add sharedIndexSpace() to local grid which will return SparseIndexSpace objects that describe overlap with neighbors for communication. The neighbor index in these functions is no longer a local ijk offset but rather the local 1D neighbor id. A numNeighbor() function should be added which returns the number of neighbors. Note that partitioning strategy means arbitrary number of neighbors now defined similar to unstructured grids and therefore more partitioning information will be needed in the LocalGrid specialization. @sslattery

Notes:

• The GlobalGrid<SparseMesh> will not support periodicity initially. We can try to add this later as needed. It will be difficult to deal with the halo overlap issues when we don't have a fixed grid domain to work with (e.g. in sparse grids usually the user is just putting a box around their particles).
• We will make a new partitioner for particle-balanced simulations (probably using RCB). For now just use the current partitioners which will partition the GlobalGrid based only on the mesh.
• p2g and g2p will probably just work for now (in a thread, not the global APIs) and we can look at different performance options later.

Other: performance testing

• Performance Test - Sparse Map and Partitioner #411