tree-of-tree architecture

[Kurt Sansom]

Hi all,

   I am working on a plasma project, and working on implementing a tree-of-tree simulation environment for Vladimir Kolobov and Robert Arslanbekov. During my inspection of the code, it looks like the data structures for the grid/tree, boundaries are managed internally (which makes alot of sense for the current use and design). For example the boundaries are statically defined , `static Boundary ** boundaries = NULL; `

One path forward to implement the desired tree-of-trees is to duplicate the tree/grid functionality into new code, but instead of using static data structures, pass the references around. The end goal would eventually hide all of this from the user, but needs to be exposed in order to associate a new tree grid with each cell in the physical space grid. I would appreciate any feedback you have to offer. 

Example here extending the boundaries.h passing pointers rather than using the static instance.

#include "boundaries.h"

// extended boundaries

void ext_add_boundary (Boundary ** boundaries, Boundary * b) {

int len = 0;

if (boundaries) {

Boundary ** i = boundaries;

while (*i++) len++;

}

qrealloc (boundaries, len + 2, Boundary *);

boundaries[len] = b;

boundaries[len+1] = NULL;

}

void ext_free_boundaries(Boundary ** boundaries) {

if (!boundaries)

return;

Boundary ** i = boundaries, * b;

while ((b = *i++))

if (b->destroy)

b->destroy (b);

else

free (b);

free (boundaries);

boundaries = NULL;

}

#define ext_boundary_iterate(boundaries, type,...) { \

Boundary ** _i = boundaries, * _b; \

while (_i && (_b = *_i++)) \

if (_b->type) \

_b->type (_b, __VA_ARGS__); \

}

regards,

 ~Kurt

[Stephane Popinet]

Hi Kurt,

Just to say that this "tree-of-tree" architecture is planned for
Basilisk. I have some draft code but unfortunately I do not have the
time to release and/or share it right now.

Note that you do not necessarily need to duplicate any code. The
"tree-of-tree" can just be defined as an embedding of the current
trees/grids into a new "meta-grid". This is transparent for users.

cheers,

Stephane

[Kurt Sansom]

Thank you Stephane, 

   This is very helpful information. I have been tasked with implementing "tree-of-tree" in basilisk ( as soon as possible). I would much rather be able to do it in a way that works for the needs of the current project and the larger basilisk community.  You and the community know much more than me, and I would like opportunity to contribute and work together.

Given your limited time availability, is there a path forward that would provide mutual benefit? I would be happy to write up something with words and pictures for your review, or if you have some design outline put together? 

Do you know of other people who would be interested in the topic and would be interested in supporting? 

More details:

Currently I am targeting, for every grid cell in the physical space grid be able to instantiate a new tree grid. This would include functionality to manage calls to creation, modification and deletion and use a physical space scalar to hold a pointer to the tree grids  

For example on each tree linked to a physical space grid cell provide:

• grid + (scalar) variables init
• grid refine
• grid wavelet adapt on selected variables
• grid vtk output
• selected variable advection (advection.h)
• grid clean up 

From what I have read in the source code, it appears the physical space grid is created statically, meaning there is only one grid (which is 100% good).

The part that I am working on right now is  being able to manage a new tree grid separate from the static one for physical space. 

Currently the functions I am working through are:

 ext_init_grid: which returns a pointer to a newly allocated grid/tree

ext_refine_level: takes and tree and depth

ext_update_cache_f: updates cache on tree pointer input

ext_free_grid: frees the memory on a provided grid

These are essentially using what is in the tree but passes around pointers instead of of using the static grid instance.

Regards,

 ~Kurt

[j.a.v...@gmail.com]

Hallo Kurt,

For a user unfriendly option:

One way to combine various grids is by creating a pipe from a parent grid to child grid processes.

https://www.geeksforgeeks.org/pipe-system-call/

An example where a 3D parent spawns a quadtree child/helper grid is here:

http://basilisk.fr/sandbox/Antoonvh/sketch.h#store-adaptive

Antoon

Op donderdag 6 mei 2021 om 16:49:38 UTC+2 schreef kay...@gmail.com:

[Stephane Popinet]

Hi Antoon,

I have seen your interesting use of pipes to couple Basilisk with
itself. A much better option, however, is to simply link basilisk with
itself:

1) write the function you need, using any grid/dimension/function of
Basilisk required.

2) compile the corresponding code as an object i.e.:

qcc -c myhelper.c

3) call the function from your Basilisk code using another
grid/dimension (you will need to declare the external function prototype).

4) link the resulting code with the object above i.e.

qcc mycode.c myhelper.o -o mycode -lm

This should also be much more efficient than pipes.

However I don't think that Kurt even needs this to implement a
"tree-of-tree": this can all be done with pre-processor "tricks".

cheers,

Stephane

[Stephane Popinet]

Hi Kurt,

I have attached an example of what I mean by "preprocessor tricks" (this
needs to go in grid/ obviously). This is a simpler example of how I see
the tree-of-tree being implemented. So you see that this is quite
different from what you propose.

cheers,

Stephane

[j.a.v...@gmail.com]

Hallo Stephane,

Did you ever manage to do this via your linked-library suggestion?

I did try this in an (unrecorded) earlier attempt but failed before

switching to the cumbersome pipes.

Antoon

Op vrijdag 7 mei 2021 om 10:54:30 UTC+2 schreef Stephane Popinet:

[j.a.v...@gmail.com]

I tried some more (including trying various linkers), I got it working by creating a shared object file at your step 2:

# Assuming CC99='gcc'

qcc -shared -o helper.so helper.c -fPIC

export LD_LIBRARY_PATH=$PWD

I ll give it a try.

Sorry for side tracking this topic, I am looking forward for the meta grid functionalities.

Antoon

Op vrijdag 7 mei 2021 om 12:27:04 UTC+2 schreef j.a.v...@gmail.com:

[Kurt Sansom]

Thank you both immensely.

 Stephane,

   Maybe I was coming at this from a bottom up approach, rather than the top down approach your example provides.

But either way I think this example gives me the fodder I need to proceed. Thank you for helping me.

Originally I was thinking in terms of the specific tree grid, now I see how to avoid that obstacle more clearly.

The next thing this made me think of would be how to manage the dimension, i.e. the base physical grid dimension should not restrict the dimension of the grid dimension for each grid in the meta grid. e.g. 2d physical space, and 1d in the meta dimension space, I think this would be easy enough but because dimension is a preprocessor directive I imagine it will cause conflicts?

Regards,

 ~Kurt

[Stephane Popinet]

Hi Kurt,

It seems to me (based on your question about 'dimension') that you are
thinking of reusing the existing grids as "meta-grids".

I don't think this is the right approach because existing grids are
highly-tuned for storing (relatively small in term of memory) Cartesian
cells, not for storing large structures like an entire mesh.

For example, an octree structure designed to store entire grids on each
leaf would be designed quite differently. It should actually be easier
to design since the computational and memory cost of such a structure
would be much less critical than its lower-level equivalent (because
what you store in the leaves and the associated computations are much
heavier than the data structure itself).

So I think you should think about writing completely new data structures
for the meta-grids (such as the "graph-like" data structure used in the
example I sent).

cheers,

Stephane

[Kurt Sansom]

This is helpful information Stephane, 

   I must be misinterpreting what is meant by grid, or by tree? 

What are the mesh/grid data structures in basilisk and what do they map to in a mental model?

Simple definition:

- mesh: Composition of cells, faces, and points related via connectivity information. I usually think of grid as a synonym for mesh in the structured case. Is this definition true for basilisk? i.e. a `Grid struct` holds the mesh information?

Based on my ability to grok the tree.h code it is not clear to me how Grid, Tree, Cell, Layer, Cache, CacheLevel are related.

Would you help me build a better mental model of what a 'grid' is in basilisk and how it relates to the other data structures?

 

What does the quadtree/octree structure hold in basilisk? It sounds like it holds information about the grid connectivity, tree structure, scalars, vectors, and tensors on the grid?

This is why I thought it would make sense to create a separate quadtree/octree implementation that has similar functionality of the physical grid and use a scalar field on the physical grid to hold pointers to the additional grids.

would a picture be helpful?

[Kurt Sansom]

Here is a simple diagram. each linked grid is not expected to have the same resolution or domain size  (it was a quick and dirty copy and paste)

~Kurt

[vik...@uah.edu]

Hi Stephane et al,

we briefly discussed ToT in basilisk with you in Pasis in 2019.

We previously implemented ToT in gerris, pls see https://arxiv.org/abs/1304.3330

Now we want to do it in basilisk, hopefully better.

Your help doing it most elegantly would be greatly appreciated.

All the best,

Vladimir

[Kurt Sansom]

I think I made some progress at least in terms of creating/deleting multiple tree grids.

The solution requires a wrapper around anything that calls the iterators and other functions that reference the `grid` 

e.g. 

int count_leaves(Grid * in_grid) 

{

  grid = in_grid;

  int n_leaves = 0;

  foreach() {

    n_leaves += 1;

  }

grid = NULL;

return n_leaves;

}

this also means that code with automatic deletes have to be scoped 

e.g. 

void write_grid(Grid * in_grid, int test, char* file_name) {

  grid = in_grid;

  {

    scalar a[];

    scalar b[];

    vector vel[];

    foreach() {

      a[] = test;

      vel.x[] = 1.;

      vel.y[] = 1.;

      vel.z[] = 1.;

    }

    FILE * fp = fopen(file_name, "w");

    scalar * outscalars = list_concat ({a}, {b});

    output_vtu_bin_foreach ((scalar *) {outscalars}, (vector *) {vel}, N, fp, false);

    free (outscalars);

    outscalars = NULL;

    fclose(fp);

  }

  grid = NULL;

}

Regards,

 ~Kurt

[Kurt Sansom]

Thank you Stephane for your input.

I saw the overloads for the realloc_scalar in the example file, but how does that translate to creating scalars on the meta grid?

Currently I don't see how to use the `scalar a[];` syntax. I can see how to use pointers to the scalars on each grid using the underlying 

`scalar sc = new_scalar("sc");` syntax and keeping track of the pointer, but that seems kludgy and hackish, and so far doesn't appear to work very well.

~Kurt

[Stephane Popinet]

Hi Kurt,

I am afraid I don't understand your question. More generally, you need
to give some context on what you are trying to do, otherwise it is very
difficult to interpret what you are asking.

cheers,

Stephane

[Kurt Sansom]

My apologies, I will keep trying to improve my question.

Short description:

The context is that I created a list of grids and I want to create/delete scalars on each grid without causing memory leaks and segfaults.

Context from your previous provided example:

Previously you provided an example of the meta grid approach you suggested in cartesian-meta.h.

    The example doesn't appear to show how creating scalars on the meta grid would be handled.

 How would that be handled in the meta-grid example you provided?

( Maybe it is handled with the overloading as mentioned in the example, but that is not clear to me.)

I am aware that creating a scalar like  `scalar a[];` will allocate and delete within the same scope, so I need at least to use `scalar a = new scalar;` to manage creating and deleting the scalars on each grid, however It appears that I keep creating memory leaks and segfaults. any guidance would be greatly appreciated.

Longer description and approach:

 Currently approach I am using calls `init_grid(N)` once at the beginning to create the base "physical" grid and stores a pointer to the `grid`, `boundaries`, `all`, and `datasize`. These appear to be the variables that need to be managed for each grid.

( My best guess is that grid: is the grid structure, boundaries: is the boundary cells, all: is the list of all scalars, and datasize: is amount of bytes past the cell size to store the scalar information)

the new separate grids populate

typedef struct {

  Grid *grid;

  Boundary **boundaries; // boundary list

  size_t datasize;

  scalar * all;

} extGrid;

I am essentially using the same functionality that is already there except that I store the pointer information in the extGrid structure.

here is an example of creating a scalar on a grid

scalar * create_scalar(extGrid *ext_in_grid, int test, char *scalar_name)

{

  scalar * ptr_sc;

  grid = ext_in_grid->grid;

  datasize = ext_in_grid->datasize;

  all = ext_in_grid->all;

  {

    scalar sc = new_scalar(scalar_name);

    printf("sc %d\n", sc.i);

    ptr_sc = ≻

    foreach ()

    {

      sc[] = (double)test;

    }

  }

  ext_in_grid->datasize = datasize;

  datasize = 0;

  grid = NULL;

  all = NULL;

  return ptr_sc;

}

~Kurt

[Kurt Sansom]

I determined one thing I was missing was adding the grid `_attribute` information.

now the meta grid struct is: 

typedef struct {

  Grid *grid; // single grid

  Boundary **boundaries; // boundary list 

  size_t datasize; // keep track of scalars?

  scalar * all; // list of scalars ?

  _Attributes * _attribute; // grid attributes ?

} extGrid; 

[Kurt Sansom]

I figured out how to create scalars on each grid in a manner that is consistent without segfaults, the name issue was with the _attribute structure.

The problem I have now is that I have two memory leaks both occur at qrealloc calls.

[Kurt Sansom]

Antoon,

  Do you have an example of the shared object file using basilisk?

Regards,

 ~Kurt

On Friday, May 7, 2021 at 6:39:26 AM UTC-5 j.a.v...@gmail.com wrote:

[j.a.v...@gmail.com]

Hallo Kurt,

Here is a minimal example:

helper.c

int helper_dimension(void) {

  return dimension;

}

main.c

#include "grid/octree.h"

int helper_dimension(void); //prototype

int main() {

  printf ("%s is %dD, but the helper has %d dimensions\n",

            gridname, dimension, helper_dimension());

}

minimal howto:

$ qcc -shared -o helper.so helper.c -fPIC

$ qcc main.c helper.so -lm

$ export LD_LIBRARY_PATH=.

$ ./a.out

An Octree is 3D, but the helper has 2 dimensions

I hope it helps.

Antoon

Op woensdag 9 juni 2021 om 18:06:48 UTC+2 schreef kay...@gmail.com:

[Kurt Sansom]

Thank you Antoon,

 This doesn't appear to be working for me, I get a ton of errors like " multiple definition of 'grid'" for each variable that is duplicated.

[j.a.v...@gmail.com]

Unfortunately, this is where my linker knowledge ends.

A hack could be to rename all these symbols. Using something like

$ qcc -c -o helper.o helper.c

# Check if the following pattern matches your compiler. This should create a list with the offending definitions in `out`

$ qcc main.c helper.o -lm 2>&1 | grep -o -P '(?<=multiple definition of `).*(?=;)' > out

# remove each ' at the end

$ sed 's/.$//' out > out2

# create list of old and new name pairs

$ paste out2 out > out3

# old becomes new in helper.o

$ objcopy --redefine-syms out3 helper.o

# try again

$ qcc main.c helper.o -lm

# succes?

Antoon

Op woensdag 9 juni 2021 om 20:52:41 UTC+2 schreef kay...@gmail.com:

[Kurt Sansom]

I realized I was using the "-c" flag and was causing the issue, need to dig a little more to understand why.

~Kurt

[Kurt Sansom]

What I am trying to accomplish:

 Create N dynamically independent executions of basilisk with the ability to create variables on the grid of each instance, modify the scalars and vectors and boundary conditions, mesh adaptation, and communicate the scalar information between instances or to a root instance. Each instance could have a different dimension.

Things I have tried:

1. Created structs and functions that manage the storage and manipulation of global variables like Grid * grid, _Attributes * _attributes, scalar * all. this currently creates memory leaks due to stale pointers and appears to require a new data structure in the low level (level 3) to do correctly without breaking the layers of basilisk. (also preprocessor tricks?)

2. Compile a basilisk source file as shared library, exposing functionality for access. This allows for having multiple grids/execution with different dimensions. I think this could work for 2-3 shared libraries, but each shared library would need unique function signatures. I don't see how this would scale to N of them?

3. Other things I could try?