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.

assigned to @andy

changed target branch from master to develop

Hi @alonzameret

I took a quick look (nothing extensive), but a few minor remarks:

• generally need to avoid int and use label 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.

added 1 commit

• 69df0ad4 - ENH: new renumbering method based on Hamiltonian path

Compare with previous version

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 use label 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 ?

added 3 commits

• fdfd2d15 - Added new renumbering method based on Hamiltonian path
• aaf02457 - Changed code data structures to correspond with openfoam objects
• 44c76c58 - Changed code data structures to correspond with openfoam objects

Compare with previous version

changed milestone to %v2312

added community contribution enhancement labels

marked this merge request as draft