Draft: New renumbering based on Hamiltonian path
Summary
Included a new renumbering method called 'hpathRenumber' which reorder the mesh cells using an Hamiltonian path approach.
Details of new models
Hamiltonian path is a path that traverses through the mesh faces and visits each cell exactly once. The Hamiltonian path approach tries to find such a path and renumber the mesh accordingly. This method ensures that after the mesh renumbering, consecutive cells in memory will likely share a common geometrical face. This in turn may allow for more efficient memory access and better vectorization performances when traversing the mesh.
Usage
Described below is the renumberMethodDict example used to apply Hamiltonian path renumbering:
method hpath;
hpathCoeffs
{
layered true;
}
The 'layered' argument (default true) controls whether the algorithm will separate the mesh cells into different 'layers' (otherwise, all cells are considered to be within the same layer). The layer separation approach is known to obtain better results and improved run-time for 3D cases, while 2D cases where a simpler Hamiltonian path may exist will benefit from avoiding the layer separation.
The algorithm will than try to find an Hamiltonian path traversing through all the cells sharing the same layer, and report the Hamiltonian path accuracy obtained. The path accuracy is defined as the percentage of consecutive cells in the renumbered order that share a common face.
Merge request reports
Activity
assigned to @andy
Hi @alonzameret
I took a quick look (nothing extensive), but a few minor remarks:
- generally need to avoid
int
and uselabel
instead. Otherwise can have problems with 64-bit compilations. - I have no real problems with using std containers. Not really sure how the performance compares, but if you wish to use OpenFOAM containers:
- bitSet : will behave somewhat similarly to the
std::vector<bool>
(more like boost dynamic_bitset) - CircularBuffer : can replace
std::dqueue
. May (or may not) have few allocations.
- generally need to avoid
added 1 commit
- 69df0ad4 - ENH: new renumbering method based on Hamiltonian path
Hi @alonzameret
Did some formatting (readability) and trying to see what the code is doing [force pushed the update just now]. In one of the parts, you have a point -> cell and cell -> point addressing. There is pretty much the same already within the OpenFOAM mesh.
could check
if (mesh.hasCellPoints()) { // Transcribe or use mesh.cellPoints(); } if (mesh.hasPointCells()) { // Transcribe or use mesh.pointCells(); }
ie, if the information is already there, can also just use it. I don't honestly know if your approach with marking the visited items is faster or slower though. Internally we have a double pass.
For some of the items (eg, number of cells connected to any given cell), using an
int
probably makes sense enough. For other quantities though, we usually uselabel
which is either int32_t or int64_t. Presumably this renumbering will only ever be called on a single domain, so can't really imagine exceeding int32 locally, but still a potential problem.Have you tried compiling with WM_LABEL_SIZE=64 ?
changed milestone to %v2312
added community contribution enhancement labels