|
DNDSR 0.2.1
Distributed Numeric Data Structure for CFV
|
Status: Proposal (partially implemented — see notes below) Date: 2026-04-21 (updated 2026-04-26) Depends on: Mesh Connectivity Architecture
Implementation status: Phases A-B of the migration path (Section 7) have been partially implemented. The
MeshConnectivityDSL class exists withInverse,Compose,ComposeFiltered,InterpolateGlobal, andevaluateGhostTree. Shared ownership viassp<>is in use. Phases C-D (full DAG abstraction, unified point numbering) remain future work. Some design choices described below (e.g., move semantics in Section 3.2, label system in Section 3.5, DAGState enum in Section 6) were superseded by the actual implementation — see MeshConnectivity.md for current architecture.
TL;DR: This is the original design proposal for replacing ~15 explicit adjacency arrays and 12 global/local conversion methods with a single DAG abstraction. The DAG stores cone (cell→face→edge→node) and support (face→cell, node→cell) relations as shared tAdjPair slots. Ghost generation becomes configurable traversal chains (e.g. cell→face→cell for face-neighbours instead of hard-coded cell→node→cell). Phases A–B (MeshConnectivity DSL + AdjPairTracked state) are implemented; Phases C–D (unified point numbering, full DAG abstraction) are future work.
The current UnstructuredMesh maintains ~15 explicit adjacency arrays, each as a separate tAdjPair with its own ghost mapping, state flag, and global-to-local conversion method. This leads to:
A DAG-based abstraction can eliminate these problems while providing the same query performance (or better) that the solver hot paths require.
An audit of all solver code (CFV, Euler, EulerP) reveals that runtime performance depends on exactly two adjacency queries:
| Query | Occurrences | Pattern |
|---|---|---|
face → (cellL, cellR) | ~60 | Constant-time, 2 entries per face |
cell → [faces] | ~62 | Variable-length row (3-8 entries) |
Everything else is derived:
CellFaceOther(iCell, iFace) reads face2cellCellIsFaceBack(iCell, iFace) reads face2cellface → zone_ID reads faceElemInfoKey finding: cell2cell (node-neighbor adjacency) is never accessed at runtime. It exists only to determine the ghost set during mesh setup, then is superseded by face-based traversal.
Setup-time queries (metric construction, initialization) also use:
cell → [nodes] (for coordinate gathering)face → [nodes] (for face metric computation)bnd → (face, cell, zone) (for boundary identification)node → [cells] (for inverse topology during ghost build)Every mesh entity gets a unique ID in a contiguous range. Entities are grouped by depth (topological dimension):
For 2D meshes, depth 1 = edges = faces (codim-1), and depth 2 = cells. For 3D meshes, all four strata exist.
Boundaries are not a separate entity type — they are labels on codim-1 faces (see Section 3.5).
Unlike DMPlex's single monolithic cone/support over all points, we store one adjacency pair per inter-layer edge. This maps naturally to DNDSR's existing tAdjPair infrastructure: each pair IS the legacy array, just organized by the DAG.
After face interpolation, a 2D mesh has these inter-layer adjacencies:
A 3D mesh with edges would have:
The non-interpolated source state (before face generation) has a single direct layer:
tAdjPair IS one of the existing arrays (cell2node, face2cell, etc.), moved in place. No data copy. Code holding a reference to face2cell continues to work after the pair is moved into the DAG.cell2node ghost exists from BuildGhostPrimary; face2cell ghost exists from InterpolateFace; edge ghost may be added later. A monolithic CSR would require all-or-nothing ghosting.InterLayerAdj.The existing arrays are moved (C++ move semantics) into the DAG at the point where the DAG takes ownership. The old member becomes a reference:
After the move, cell2face and face2cell point to the same memory, just organized under the DAG. Existing solver code that accesses mesh->cell2face or mesh->face2cell sees no change.
cpp // — Stratum accessors — auto cells() -> Range { return strata[meshDim]; } auto faces() -> Range { return strata[meshDim - 1]; } auto edges() -> Range { return strata[1]; } // only if interpolated auto nodes() -> Range { return strata[0]; }
// — Direct adjacency (single layer hop) — // These are O(1) CSR row lookups — identical cost to current arrays. auto cellFaces(index iCell) -> RowView { return findAdj(dim, dim-1)->cone[iCell]; } auto faceCells(index iFace) -> RowView { return findAdj(dim, dim-1)->support[iFace]; } auto faceNodes(index iFace) -> RowView { return findAdj(dim-1, 0)->cone[iFace]; // or findAdj(dim-1, 1)->cone → findAdj(1, 0)->cone for 3D with edges }
// — Multi-hop traversal (for setup-time queries) — auto cellNodes(index iCell) -> SmallVec { // Before face interpolation: direct cell→node layer exists if (auto *adj = findAdj(dim, 0)) return adj->cone[iCell]; // After interpolation: traverse cell → faces → nodes SmallVec result; for (auto iFace : cellFaces(iCell)) for (auto iNode : faceNodes(iFace)) result.insertUnique(iNode); return result; }
// — Convenience (performance-critical, inlined) — index cellFaceOther(index iCell, index iFace) { auto cells = faceCells(iFace); return cells[0] == iCell ? cells[1] : cells[0]; }
bool cellIsFaceBack(index iCell, index iFace) { return faceCells(iFace)[0] == iCell; }
cpp struct MeshLabels { // Element type per point (cells, faces, edges all share one array) tElemInfoArrayPair elemInfo; // indexed by point ID
// Zone/BC IDs per point // Replaces the separate zone queries per entity type // Boundaries = faces whose zone != BC_ID_INTERNAL
// Named label groups (like DMPlex's DMLabel) std::map<std::string, tAdj1Pair> labels; };
cpp struct MeshSection { // For each point: number of DOFs and offset into flat storage std::vector<int> ndof; // per point std::vector<index> offset; // per point, into data Vec
// The actual data lives in a separate flat array (Vec) };
cpp struct PointOwnership { // For each point in [chartStart, chartEnd): owning rank // Father points: owner == mpi.rank // Ghost (son) points: owner != mpi.rank std::vector<MPI_int> owner;
// PetscSF-like structure for communication // Maps (local ghost point) → (remote rank, remote local index) // Used for ghost pull/push GhostMapping ghostMap; };
cpp // A single hop: traverse from one stratum to another via an InterLayerAdj struct AdjHop { int fromDepth; int toDepth; enum Direction { Cone, Support } dir; // Cone = downward, Support = upward };
// A ghost requirement is a sequence of hops starting from a seed stratum struct GhostTraversalChain { int seedDepth; // starting entity depth (typically dim = cells) std::vector<AdjHop> hops; // sequence of traversals // The LAST hop's toDepth entities are the ones that become ghost. // All intermediate entities traversed are also ghosted if needed. };
struct GhostRequirement { std::vector<GhostTraversalChain> chains;
// Which depths to "complement" — for every ghost entity at this depth, // also pull all its cone sub-entities so their full connectivity is available. std::set<int> complementDepths; };
cpp // cell → node → cell (one ring of node-neighbors) GhostRequirement current; current.chains = {{ .seedDepth = dim, .hops = { {dim, 0, Cone}, // cell → node (downward) {0, dim, Support}, // node → cell (upward) } }}; current.complementDepths = {0}; // ghost cells get all their nodes
cpp // cell → face → cell (one ring of face-neighbors) GhostRequirement faceNeighbor; faceNeighbor.chains = {{ .seedDepth = dim, .hops = { {dim, dim-1, Cone}, // cell → face {dim-1, dim, Support}, // face → cell } }}; faceNeighbor.complementDepths = {0};
cpp // cell → face → cell → face → cell GhostRequirement wideStencil; wideStencil.chains = {{ .seedDepth = dim, .hops = { {dim, dim-1, Cone}, {dim-1, dim, Support}, {dim, dim-1, Cone}, {dim-1, dim, Support}, } }}; wideStencil.complementDepths = {0};
cpp // cell → node → cell → node → cell GhostRequirement nodeFV; nodeFV.chains = {{ .seedDepth = dim, .hops = { {dim, 0, Cone}, // cell → node {0, dim, Support}, // node → cell {dim, 0, Cone}, // cell → node (2nd ring) {0, dim, Support}, // node → cell } }}; nodeFV.complementDepths = {0, 1}; // nodes and edges
cpp // Ghost cells via faces, but complement nodes via node2cell GhostRequirement femLike; femLike.chains = { // Chain 1: ghost cells via face-neighbor {dim, {{dim, dim-1, Cone}, {dim-1, dim, Support}}}, // Chain 2: complement — for each local+ghost cell, pull all nodes // (this is implicit via complementDepths = {0}) }; femLike.complementDepths = {0};
cell → face → cell → node → cell
BuildGhost(dag, requirement): for each chain in requirement.chains: frontier = set of local entities at chain.seedDepth for each hop in chain.hops: nextFrontier = {} adj = dag.findAdj(hop.fromDepth, hop.toDepth) for entity in frontier: if hop.dir == Cone: for target in adj.cone[entity]: nextFrontier.add(target) else: // Support for target in adj.support[entity]: nextFrontier.add(target) frontier = nextFrontier
// frontier now contains all entities reached by this chain // Mark non-local entities as ghost for entity in frontier: if not local(entity): ghostSet[depthOf(entity)].add(entity)
// Complement: for each ghost at a complement depth, pull cone sub-entities for depth in requirement.complementDepths: for ghostEntity in ghostSet[depth+1..dim]: // higher-depth ghosts for sub in transitiveCone(ghostEntity, depth): if not local(sub): ghostSet[depth].add(sub)
cell → face → cell ⊆ cell → node → cell
cell → face → cell → face → cell ⊆ cell → node → cell → node → cell (in general, not true: depends on mesh topology)
cpp // Insert codim-1 entities (faces) between cells and nodes void InterpolateDepth(MeshConnectivity &dag, int depth);
// For 3D: InterpolateDepth(dag, 2); // faces: cell → face → node InterpolateDepth(dag, 1); // edges: face → edge → node
// For 2D: InterpolateDepth(dag, 1); // edges (= faces): cell → edge → node
cpp enum class DAGState : uint8_t { Empty, // No topology loaded SourceOnly, // cell2node (depth-max → depth-0) loaded, global indices Interpolated, // Intermediate entities (faces, edges) generated GhostBuilt, // Ghost points added LocalIndexed, // All indices converted to local (father+son) };
Empty → SourceOnly: ReadMesh / PartitionReorder SourceOnly → Interpolated: InterpolateDepth(all requested depths) Interpolated → GhostBuilt: BuildGhost(requirement) GhostBuilt → LocalIndexed: ConvertToLocal() LocalIndexed → GhostBuilt: ConvertToGlobal() (reversible)
cpp struct UnstructuredMesh : public DeviceTransferable<UnstructuredMesh> { MeshConnectivity dag; // NEW: the DAG organizer
// Legacy members remain as tAdjPair values (not references). // They share the same ssp<ParArray> pointers as the DAG's InterLayerAdj slots. tAdjPair cell2node; // cell2node.father == dag.findLayer(dim, 0)->cone.father tAdjPair cell2face; // cell2face.father == dag.findLayer(dim, dim-1)->cone.father tAdj2Pair face2cell; // face2cell.father == dag.findLayer(dim, dim-1)->support.father tAdjPair face2node; // face2node.father == dag.findLayer(dim-1, 0)->cone.father tAdjPair node2cell; // node2cell.father == dag.findLayer(dim, 0)->support.father // ... etc.
// Adoption: share ssp<> pointers between legacy members and DAG void AdoptIntoDAG() { auto &cellNodeLayer = dag.addLayer(dim, 0); // Share (not move!) the underlying ParArray shared_ptrs cellNodeLayer.cone.father = cell2node.father; cellNodeLayer.cone.son = cell2node.son; cellNodeLayer.support.father = node2cell.father; cellNodeLayer.support.son = node2cell.son; // ... etc. for all layers
// Both legacy members and DAG now point to the same data. // Mutations via either path are visible to both. } };
cpp // New API (preferred, more explicit) auto mesh->cellFaces(iCell) -> RowView; auto mesh->faceCells(iFace) -> RowView;
// Old API (still works, delegates to same storage) mesh->cell2face[iCell] mesh->face2cell(iFace, j)
cpp // Transfer the entire DAG topology to device dag.cone.to_device(backend); dag.support.to_device(backend); dag.coneOrientation.to_device(backend); dag.elemInfo.to_device(backend);
cpp template <DeviceBackend B> struct MeshConnectivityDeviceView { ArrayAdjacencyView cone; // cell → faces ArrayAdjacencyView support; // face → cells // Same query API as host }; ```
This is simpler than the current approach of transferring 15+ individual arrays.
The current cell2nodePbi / face2nodePbi arrays store per-connectivity-entry periodic transformation bits. In the DAG, this maps naturally to cone orientations:
periodicInfo.GetCoordByBits(coord, pbi) pattern becomes dag.getCoordWithOrientation(iNode, orientation)This unifies the periodic handling with the general orientation system.
| Aspect | Current | DAG-based |
|---|---|---|
| Storage | ~15 separate tAdjPair members | Same pairs, organized in InterLayerAdj slots |
| Legacy API | Direct member access | Same — references into DAG storage after move |
| State flags | 5 independent | 1 unified DAGState |
| Conversion methods | 12 (per-array-group) | 2 (iterate all layers) |
| Ghost specification | Hardcoded 1-ring node-neighbor | Traversal chains: arbitrary inter-layer hops |
| Ghost example | cell → node → cell only | cell → face → cell, cell → node → cell → node → cell, mixed |
| Edge support | Not possible | interpolateDepth(1) adds edge layer |
| Entity creation | InterpolateFace() only | Generic interpolateDepth(d) for any depth |
| Device transfer | 15+ individual transfers | Iterate layers, transfer cone+support per layer |
| Hot-path query cost | O(1) CSR row | O(1) CSR row (identical — same underlying data) |
| Data ownership | UnstructuredMesh owns all arrays | Shared ssp<> — DAG and legacy members point to same ParArrays |