Skip to content
Snippets Groups Projects

Draft: New renumbering based on Hamiltonian path

Open Alon Zameret requested to merge hpathRenumbering into develop

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.

2D_Cylinder_Hpath

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

Loading
Loading

Activity

Filter activity
  • Approvals
  • Assignees & reviewers
  • Comments (from bots)
  • Comments (from users)
  • Commits & branches
  • Edits
  • Labels
  • Lock status
  • Mentions
  • Merge request status
  • Tracking
  • assigned to @andy

  • Mark OLESEN changed target branch from master to develop

    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.
  • Mark OLESEN added 1 commit

    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 ?

  • Alon Zameret added 3 commits

    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

  • Mark OLESEN changed milestone to %v2312

    changed milestone to %v2312

  • Mark OLESEN marked this merge request as draft

    marked this merge request as draft

Please register or sign in to reply
Loading