adaptive-cfd / WABBIT

Wavelet Adaptive Block-Based solver for Interactions with Turbulence
https://www.cfd.tu-berlin.de/
GNU General Public License v3.0
56 stars 27 forks source link

Numerical treecodes everywhere #56

Closed Arcadia197 closed 7 months ago

Arcadia197 commented 8 months ago

Treecodes are now fully encoded

And that also in an appropriate way to maximize the usage. All treecodes are now in binary representation, which is for $dim=2$ in base4 and for $dim=3$ in base 8. Each level consists of 2 or 3 bits which represent the direction for each dimension. The rightmost bits constitute the finest levels with larger numbers getting coarser and coarser. Here an example for a representation in 3D from a traditional Treecode Array:

 3.  4.  2.  7.  1.  5.  6.  0.  1. -1. -1
 |   |   |   |   |   |   |   |   |   |   |  
011.100.010.111.001.101.110.000.001.000.000

Sorting of blocks

As one can see, with this we do not encode the level anymore and representation between mother and 0-daughter become identical. In order to uniquely adress blocks, we have to take the level into account as well. This was adapted for the sorted_num_list. It is now sorted over tree_id, level and treecode together. However - as previously we do not mash those numbers together but keep them separate, ensuring the max-level of 21 (or 31 for 2D). This slightly slows down the sorting process. How much this affects runs still has to be evaluated.

Changing lgt_blocks

Since lgt_block is an int4 array and treecode is saved as int8, it is encoded onto the array taking up two integers. Functions to extract and set the treecode have been written and take into account how the MSB (sign-bit of integers) is handled for the second integer (as it can be encoded with a treecode value). That being said - the traditionally treecode is fully removed and the array now has a fixed size of 5, consisting of:

Neighbor search

Neighbor search with encoded treecodes is luckily a bit simplifiied. This was adapted and implemented but a possible speedup is not expected. Probably this is outweighted by the slower searching algorithm

Saving structures

The new treecode together with the level will be saved in the HDF5 file, while I was at it I cleaned up the module and made it a bit more consistent. This gives now a redundant information within the files. Currently both reading in from the old treecode array or new numerical treecode is supported and switched wether the numerical treecode is present.

Documenting

I made sure to document where necessary and make it doxygen-friendly

Things to consider

tommy-engels commented 7 months ago

Dear Julius, I checked your code on the IRENE/ROME machine and indeed the performance is unchanged with respect to the previous version (as expected, the difference in cpu time is below the fluctuations of the machine).

On my local machine, i have set export DEV=yes which results in many additional checks not done in production runs. You seem to have disabled this flag; in the file merge_blocks.f90, some compilation errors occur if DEV is set. Please ensure that it is used on your machine. I have corrected those.

I have also added

ifndef $(HDF_SOURCE)
HDF_SOURCE = $(HDF_ROOT)
endif

to the makefile.