forcetree.h File Reference

#include "types.h"
#include "domain.h"

Include dependency graph for forcetree.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	NodeChild
struct	NODE
struct	ForceTree

Macros
#define	NMAXCHILD   8
#define	PARTICLE_NODE_TYPE   0
#define	NODE_NODE_TYPE   1
#define	PSEUDO_NODE_TYPE   2
#define	ALLMASK   (1<<30)-1
#define	GASMASK   (1)
#define	DMMASK   (2)
#define	STARMASK   (1<<4)
#define	BHMASK   (1<<5)

Typedefs
typedef struct ForceTree	ForceTree

Functions
void	init_forcetree_params (const int FastParticleType)
int	force_tree_allocated (const ForceTree *tt)
void	force_update_hmax (int *activeset, int size, ForceTree *tt, DomainDecomp *ddecomp)
void	force_tree_rebuild (ForceTree *tree, DomainDecomp *ddecomp, const int HybridNuGrav, const int DoMoments, const char *EmergencyOutputDir)
void	force_tree_rebuild_mask (ForceTree *tree, DomainDecomp *ddecomp, int mask, const int HybridNuGrav, const char *EmergencyOutputDir)
void	force_tree_free (ForceTree *tt)
void	dump_particles (void)
static int	node_is_pseudo_particle (int no, const ForceTree *tree)
static int	node_is_particle (int no, const ForceTree *tree)
static int	node_is_node (int no, const ForceTree *tree)
int	force_get_father (int no, const ForceTree *tt)
int	force_tree_create_nodes (const ForceTree tb, const int npart, int mask, DomainDecomp *ddecomp, const int HybridNuGrav)
ForceTree	force_treeallocate (int64_t maxnodes, int64_t maxpart, DomainDecomp *ddecomp)
void	force_update_node_parallel (const ForceTree *tree, const DomainDecomp *ddecomp)

Macro Definition Documentation

ALLMASK

#define ALLMASK   (1<<30)-1

Definition at line 20 of file forcetree.h.

BHMASK

#define BHMASK   (1<<5)

Definition at line 24 of file forcetree.h.

DMMASK

#define DMMASK   (2)

Definition at line 22 of file forcetree.h.

GASMASK

#define GASMASK   (1)

Definition at line 21 of file forcetree.h.

NMAXCHILD

#define NMAXCHILD   8

Definition at line 12 of file forcetree.h.

NODE_NODE_TYPE

#define NODE_NODE_TYPE   1

Definition at line 16 of file forcetree.h.

PARTICLE_NODE_TYPE

#define PARTICLE_NODE_TYPE   0

Definition at line 15 of file forcetree.h.

PSEUDO_NODE_TYPE

#define PSEUDO_NODE_TYPE   2

Definition at line 17 of file forcetree.h.

STARMASK

#define STARMASK   (1<<4)

Definition at line 23 of file forcetree.h.

Typedef Documentation

ForceTree

typedef struct ForceTree ForceTree

Function Documentation

dump_particles()

void dump_particles

(

void

)

force_get_father()

int force_get_father	(	int	no,
		const ForceTree *	tt
	)

Definition at line 905 of file forcetree.c.

{
    if(no >= tree->firstnode)
        return tree->Nodes[no].father;
    else
        return tree->Father[no];
}

References NODE::father, ForceTree::Father, ForceTree::firstnode, and ForceTree::Nodes.

Referenced by _prepare(), check_moments(), check_tree(), effhsml(), force_tree_eh_slots_fork(), ngb_treefind_threads(), set_init_hsml(), and setup_smoothinglengths().

Here is the caller graph for this function:

force_tree_allocated()

int force_tree_allocated

(

const ForceTree *

tt

)

Definition at line 134 of file forcetree.c.

{
    return tree->tree_allocated_flag;
}

References ForceTree::tree_allocated_flag.

Referenced by _prepare(), force_tree_free(), force_tree_rebuild(), force_tree_rebuild_mask(), sfr_reserve_slots(), and treewalk_run().

Here is the caller graph for this function:

force_tree_create_nodes()

int force_tree_create_nodes	(	const ForceTree	tb,
		const int	npart,
		int	mask,
		DomainDecomp *	ddecomp,
		const int	HybridNuGrav
	)

Does initial creation of the nodes for the gravitational oct-tree. mask is a bitfield: Only types whose bit is set are added.

Definition at line 661 of file forcetree.c.

{
    int nnext = tb.firstnode;       /* index of first free node */
 
    /* create an empty root node  */
    {
        int i;
        struct NODE *nfreep = &tb.Nodes[nnext]; /* select first node */
 
        nfreep->len = PartManager->BoxSize*1.001;
        for(i = 0; i < 3; i++)
            nfreep->center[i] = PartManager->BoxSize/2.;
        for(i = 0; i < NMAXCHILD; i++)
            nfreep->s.suns[i] = -1;
        nfreep->s.Types = 0;
        nfreep->s.noccupied = 0;
        nfreep->father = -1;
        nfreep->sibling = -1;
        nfreep->f.TopLevel = 1;
        nfreep->f.InternalTopLevel = 0;
        nfreep->f.DependsOnLocalMass = 0;
        nfreep->f.ChildType = PARTICLE_NODE_TYPE;
        nfreep->f.unused = 0;
        memset(&(nfreep->mom.cofm),0,3*sizeof(MyFloat));
        nfreep->mom.mass = 0;
        nfreep->mom.hmax = 0;
        nnext++;
        /* create a set of empty nodes corresponding to the top-level ddecomp
         * grid. We need to generate these nodes first to make sure that we have a
         * complete top-level tree which allows the easy insertion of the
         * pseudo-particles in the right place */
        force_create_node_for_topnode(tb.firstnode, 0, tb.Nodes, ddecomp, 1, 0, 0, 0, &nnext, tb.lastnode);
    }
    /* Set up thread-local copies of the topnodes to anchor the subtrees. */
    int ThisTask, j, t;
    MPI_Comm_rank(MPI_COMM_WORLD, &ThisTask);
    const int StartLeaf = ddecomp->Tasks[ThisTask].StartLeaf;
    const int EndLeaf = ddecomp->Tasks[ThisTask].EndLeaf;
    const int nthr = omp_get_max_threads();
    int * topnodes = ta_malloc("topnodes", int, (EndLeaf - StartLeaf) * nthr);
    /* Topnodes for each thread. For tid 0, just use the real tree. Saves copying the tree back.*/
    for(j = 0; j < EndLeaf - StartLeaf; j++)
        topnodes[j] = ddecomp->TopLeaves[j + StartLeaf].treenode;
    /* Other threads need a copy*/
    for(t = 1; t < nthr; t++) {
        for(j = 0; j < EndLeaf - StartLeaf; j++) {
            /* Make a local copy*/
            topnodes[j + t * (EndLeaf - StartLeaf)] = nnext;
            memmove(&tb.Nodes[nnext], &tb.Nodes[topnodes[j]], sizeof(struct NODE));
            nnext++;
        }
    }
 
/*     double tstart = second(); */
    const int first_free = nnext;
    /* Increment nnext for the threads we are about to initialise.*/
    nnext += NODECACHE_SIZE * nthr;
    /* now we insert all particles */
    #pragma omp parallel
    {
        int i;
        /* Local topnodes*/
        int tid = omp_get_thread_num();
        const int * const local_topnodes = topnodes + tid * (EndLeaf - StartLeaf);
 
        /* This implements a small thread-local free Node cache.
         * The cache ensures that Nodes from the same (or close) particles
         * are created close to each other on the Node list and thus
         * helps cache locality. I tried each thread getting a separate
         * part of the tree, and it wasted too much memory. */
        struct NodeCache nc;
        nc.nnext_thread = first_free + tid * NODECACHE_SIZE;
        nc.nrem_thread = NODECACHE_SIZE;
 
        /* Stores the last-seen node on this thread.
         * Since most particles are close to each other, this should save a number of tree walks.*/
        int this_acc = local_topnodes[0];
        // message(1, "Topnodes %d real %d\n", local_topnodes[0], topnodes[0]);
 
        /* The default schedule is static with a chunk 1/4 the total.
         * However, particles are sorted by type and then by peano order.
         * Since we need to merge trees, it is advantageous to have all particles
         * spatially close be processed by the same thread. This means that the threads should
         * process particles at a constant offset from the start of the type.
         * We do this with a static schedule. */
        int chnksz = PartManager->NumPart/nthr;
        if(SlotsManager->info[0].enabled && SlotsManager->info[0].size > 0)
            chnksz = SlotsManager->info[0].size/nthr;
        if(chnksz < 1000)
            chnksz = 1000;
        #pragma omp for schedule(static, chnksz)
        for(i = 0; i < npart; i++)
        {
            /*Can't break from openmp for*/
            if(nc.nnext_thread >= tb.lastnode)
                continue;
 
            /* Do not add types that do not have their mask bit set.*/
            if(!((1<<P[i].Type) & mask)) {
                continue;
            }
            /* Do not add garbage/swallowed particles to the tree*/
            if(P[i].IsGarbage || (P[i].Swallowed && P[i].Type==5))
                continue;
 
            if(P[i].Mass == 0)
                endrun(12, "Zero mass particle %d type %d id %ld pos %g %g %g\n", i, P[i].Type, P[i].ID, P[i].Pos[0], P[i].Pos[1], P[i].Pos[2]);
            /*First find the Node for the TopLeaf */
            int cur;
            if(inside_node(&tb.Nodes[this_acc], i)) {
                cur = this_acc;
            } else {
                /* Get the topnode to which a particle belongs. Each local tree
                 * has a local set of treenodes copying the global topnodes, except tid 0
                 * which has the real topnodes.*/
                const int topleaf = domain_get_topleaf(P[i].Key, ddecomp);
                //int treenode = ddecomp->TopLeaves[topleaf].treenode;
                cur = local_topnodes[topleaf - StartLeaf];
            }
 
            this_acc = add_particle_to_tree(i, cur, tb, HybridNuGrav, &nc, &nnext);
        }
        /* The implicit omp-barrier is important here!*/
/*         double tend = second(); */
/*         message(0, "Initial insertion: %.3g ms. First node %d\n", (tend - tstart)*1000, local_topnodes[0]); */
 
        /* Merge each topnode separately, using a for loop.
         * This wastes threads if NTHREAD > NTOPNODES, but it
         * means only one merge is done per subtree and
         * it requires no locking.*/
        #pragma omp for schedule(static, 1)
        for(i = 0; i < EndLeaf - StartLeaf; i++) {
            int t;
            /* These are the addresses of the real topnodes*/
            const int target = topnodes[i];
            if(nc.nnext_thread >= tb.lastnode)
                continue;
            for(t = 1; t < nthr; t++) {
                const int righttop = topnodes[i + t * (EndLeaf - StartLeaf)];
//                  message(1, "tid = %d i = %d t = %d Merging %d to %d addresses are %lx - %lx end is %lx\n", omp_get_thread_num(), i, t, righttop, target, &tb.Nodes[righttop], &tb.Nodes[target], &tb.Nodes[nnext]);
                if(merge_partial_force_trees(target, righttop, &nc, &nnext, tb, HybridNuGrav))
                    break;
            }
        }
    }
 
    ta_free(topnodes);
    return nnext - tb.firstnode;
}

References add_particle_to_tree(), part_manager_type::BoxSize, NODE::center, NODE::ChildType, NODE::cofm, NODE::DependsOnLocalMass, domain_get_topleaf(), slot_info::enabled, task_data::EndLeaf, endrun(), NODE::f, NODE::father, ForceTree::firstnode, force_create_node_for_topnode(), NODE::hmax, slots_manager_type::info, inside_node(), NODE::InternalTopLevel, ForceTree::lastnode, NODE::len, NODE::mass, merge_partial_force_trees(), NODE::mom, NMAXCHILD, NodeCache::nnext_thread, NodeChild::noccupied, NODECACHE_SIZE, ForceTree::Nodes, NodeCache::nrem_thread, part_manager_type::NumPart, P, PARTICLE_NODE_TYPE, PartManager, NODE::s, NODE::sibling, slot_info::size, SlotsManager, task_data::StartLeaf, NodeChild::suns, ta_free, ta_malloc, DomainDecomp::Tasks, ThisTask, DomainDecomp::TopLeaves, NODE::TopLevel, topleaf_data::treenode, NodeChild::Types, and NODE::unused.

Referenced by do_tree_test(), and force_tree_build().

Here is the call graph for this function:

Here is the caller graph for this function:

force_tree_free()

void force_tree_free

(

ForceTree *

tree

)

This function frees the memory allocated for the tree, i.e. it frees the space allocated by the function force_treeallocate().

Definition at line 1409 of file forcetree.c.

{
    event_unlisten(&EventSlotsFork, force_tree_eh_slots_fork, tree);
 
    if(!force_tree_allocated(tree))
        return;
    myfree(tree->Nodes_base);
    myfree(tree->Father);
    tree->tree_allocated_flag = 0;
}

References event_unlisten(), EventSlotsFork, ForceTree::Father, force_tree_allocated(), force_tree_eh_slots_fork(), myfree, ForceTree::Nodes_base, and ForceTree::tree_allocated_flag.

Referenced by _prepare(), do_density_test(), do_force_test(), fof_fof(), force_tree_build(), force_tree_rebuild(), force_tree_rebuild_mask(), metal_return(), run(), run_gravity_test(), runfof(), runpower(), setup_smoothinglengths(), test_rebuild_close(), test_rebuild_flat(), test_rebuild_random(), and turn_on_quasars().

Here is the call graph for this function:

Here is the caller graph for this function:

force_tree_rebuild()

void force_tree_rebuild	(	ForceTree *	tree,
		DomainDecomp *	ddecomp,
		const int	HybridNuGrav,
		const int	DoMoments,
		const char *	EmergencyOutputDir
	)

Definition at line 140 of file forcetree.c.

{
    MPIU_Barrier(MPI_COMM_WORLD);
    message(0, "Tree construction.  (presently allocated=%g MB)\n", mymalloc_usedbytes() / (1024.0 * 1024.0));
 
    if(force_tree_allocated(tree)) {
        force_tree_free(tree);
    }
    walltime_measure("/Misc");
 
    *tree = force_tree_build(PartManager->NumPart, ALLMASK, ddecomp, HybridNuGrav, DoMoments, EmergencyOutputDir);
 
    event_listen(&EventSlotsFork, force_tree_eh_slots_fork, tree);
    walltime_measure("/Tree/Build/Moments");
 
    message(0, "Tree constructed (moments: %d). First node %d, number of nodes %d, first pseudo %d. NTopLeaves %d\n",
            tree->moments_computed_flag, tree->firstnode, tree->numnodes, tree->lastnode, tree->NTopLeaves);
    MPIU_Barrier(MPI_COMM_WORLD);
}

References ALLMASK, event_listen(), EventSlotsFork, ForceTree::firstnode, force_tree_allocated(), force_tree_build(), force_tree_eh_slots_fork(), force_tree_free(), ForceTree::lastnode, message(), ForceTree::moments_computed_flag, MPIU_Barrier, mymalloc_usedbytes, ForceTree::NTopLeaves, ForceTree::numnodes, part_manager_type::NumPart, PartManager, and walltime_measure.

Referenced by do_density_test(), do_force_test(), run(), run_gravity_test(), runfof(), runpower(), and setup_smoothinglengths().

Here is the call graph for this function:

Here is the caller graph for this function:

force_tree_rebuild_mask()

void force_tree_rebuild_mask	(	ForceTree *	tree,
		DomainDecomp *	ddecomp,
		int	mask,
		const int	HybridNuGrav,
		const char *	EmergencyOutputDir
	)

Definition at line 161 of file forcetree.c.

{
    MPIU_Barrier(MPI_COMM_WORLD);
    message(0, "Tree construction for types: %d.\n", mask);
 
    if(force_tree_allocated(tree)) {
        force_tree_free(tree);
    }
    walltime_measure("/Misc");
 
    /* No moments*/
    *tree = force_tree_build(PartManager->NumPart, mask, ddecomp, HybridNuGrav, 0, EmergencyOutputDir);
    walltime_measure("/SPH/Build");
 
    message(0, "Tree constructed (type mask: %d). First node %d, number of nodes %d, first pseudo %d. NTopLeaves %d\n",
            mask, tree->firstnode, tree->numnodes, tree->lastnode, tree->NTopLeaves);
    MPIU_Barrier(MPI_COMM_WORLD);
}

References ForceTree::firstnode, force_tree_allocated(), force_tree_build(), force_tree_free(), ForceTree::lastnode, message(), MPIU_Barrier, ForceTree::NTopLeaves, ForceTree::numnodes, part_manager_type::NumPart, PartManager, and walltime_measure.

Referenced by fof_fof(), metal_return(), and turn_on_quasars().

Here is the call graph for this function:

Here is the caller graph for this function:

force_treeallocate()

ForceTree force_treeallocate	(	int64_t	maxnodes,
		int64_t	maxpart,
		DomainDecomp *	ddecomp
	)

This function allocates the memory used for storage of the tree and of auxiliary arrays needed for tree-walk and link-lists. Usually, maxnodes approximately equal to 0.7*maxpart is sufficient to store the tree for up to maxpart particles.

Definition at line 1381 of file forcetree.c.

{
    ForceTree tb;
 
    tb.Father = (int *) mymalloc("Father", maxpart * sizeof(int));
    tb.nfather = maxpart;
#ifdef DEBUG
    memset(tb.Father, -1, maxpart * sizeof(int));
#endif
    tb.Nodes_base = (struct NODE *) mymalloc("Nodes_base", (maxnodes + 1) * sizeof(struct NODE));
#ifdef DEBUG
    memset(tb.Nodes_base, -1, (maxnodes + 1) * sizeof(struct NODE));
#endif
    tb.firstnode = maxpart;
    tb.lastnode = maxpart + maxnodes;
    if(maxpart + maxnodes >= 1L<<30)
        endrun(5, "Size of tree overflowed for maxpart = %ld, maxnodes = %ld!\n", maxpart, maxnodes);
    tb.numnodes = 0;
    tb.Nodes = tb.Nodes_base - maxpart;
    tb.tree_allocated_flag = 1;
    tb.NTopLeaves = ddecomp->NTopLeaves;
    tb.TopLeaves = ddecomp->TopLeaves;
    return tb;
}

References endrun(), ForceTree::Father, ForceTree::firstnode, ForceTree::lastnode, mymalloc, ForceTree::nfather, ForceTree::Nodes, ForceTree::Nodes_base, DomainDecomp::NTopLeaves, ForceTree::NTopLeaves, ForceTree::numnodes, DomainDecomp::TopLeaves, ForceTree::TopLeaves, and ForceTree::tree_allocated_flag.

Referenced by force_tree_build(), test_rebuild_close(), test_rebuild_flat(), and test_rebuild_random().

Here is the call graph for this function:

Here is the caller graph for this function:

force_update_hmax()

void force_update_hmax	(	int *	activeset,
		int	size,
		ForceTree *	tree,
		DomainDecomp *	ddecomp
	)

This function updates the hmax-values in tree nodes that hold SPH particles. Since the Hsml-values are potentially changed for active particles in the SPH-density computation, force_update_hmax() should be carried out just before the hydrodynamical SPH forces are computed, i.e. after density().

The purpose of the hmax node is for a symmetric treewalk (currently only the hydro). Particles where P[i].Pos + Hsml pokes beyond the exterior of the tree node may mean that a tree node should be included when it would normally be culled. Therefore we don't really want hmax, we want the maximum amount P[i].Pos + Hsml pokes beyond the tree node.

Definition at line 1271 of file forcetree.c.

{
    int NTask, ThisTask, recvTask;
    int i, ta;
    int *recvcounts, *recvoffset;
 
    walltime_measure("/Misc");
 
    /* If hmax has not yet been computed, do all particles*/
    if(!tree->hmax_computed_flag) {
        activeset = NULL;
        size = PartManager->NumPart;
    }
    MPI_Comm_size(MPI_COMM_WORLD, &NTask);
    MPI_Comm_rank(MPI_COMM_WORLD, &ThisTask);
 
    #pragma omp parallel for
    for(i = 0; i < size; i++)
    {
        const int p_i = activeset ? activeset[i] : i;
 
        if(P[p_i].Type != 0 || P[p_i].IsGarbage)
            continue;
 
        int no = tree->Father[p_i];
 
        while(no >= 0)
        {
            /* How much does this particle peek beyond this node?
             * Note len does not change so we can read it without a lock or atomic. */
            MyFloat readhmax, newhmax = 0;
            int j, done = 0;
            for(j = 0; j < 3; j++) {
                /* Compute each direction independently and take the maximum.
                 * This is the largest possible distance away from node center within a cube bounding hsml.
                 * Note that because Pos - Center < len, the maximum value this can have is Hsml.*/
                newhmax = DMAX(newhmax, fabs(P[p_i].Pos[j] - tree->Nodes[no].center[j]) + P[p_i].Hsml - tree->Nodes[no].len);
            }
            /* Most particles will lie fully inside a node. No need then for the atomic! */
            if(newhmax <= 0)
                break;
 
            #pragma omp atomic read
            readhmax = tree->Nodes[no].mom.hmax;
            do {
                if(newhmax <= readhmax) {
                    done = 1;
                    break;
                }
                /* Swap in the new hmax only if the old one hasn't changed. */
            } while(!__atomic_compare_exchange(&(tree->Nodes[no].mom.hmax), &readhmax, &newhmax, 0, __ATOMIC_RELAXED, __ATOMIC_RELAXED));
 
            if(done)
                break;
            no = tree->Nodes[no].father;
        }
    }
 
    double * TopLeafhmax = (double *) mymalloc("TopLeafMoments", ddecomp->NTopLeaves * sizeof(double));
    memset(&TopLeafhmax[0], 0, sizeof(double) * ddecomp->NTopLeaves);
 
    for(i = ddecomp->Tasks[ThisTask].StartLeaf; i < ddecomp->Tasks[ThisTask].EndLeaf; i ++) {
        int no = ddecomp->TopLeaves[i].treenode;
        TopLeafhmax[i] = tree->Nodes[no].mom.hmax;
    }
 
    /* share the hmax-data of the dirty nodes accross CPUs */
    recvcounts = (int *) mymalloc("recvcounts", sizeof(int) * NTask);
    recvoffset = (int *) mymalloc("recvoffset", sizeof(int) * NTask);
 
    for(recvTask = 0; recvTask < NTask; recvTask++)
    {
        recvoffset[recvTask] = ddecomp->Tasks[recvTask].StartLeaf;
        recvcounts[recvTask] = ddecomp->Tasks[recvTask].EndLeaf - ddecomp->Tasks[recvTask].StartLeaf;
    }
 
    MPI_Allgatherv(MPI_IN_PLACE, 0, MPI_DATATYPE_NULL,
            &TopLeafhmax[0], recvcounts, recvoffset,
            MPI_DOUBLE, MPI_COMM_WORLD);
 
    myfree(recvoffset);
    myfree(recvcounts);
 
    for(ta = 0; ta < NTask; ta++) {
        if(ta == ThisTask)
            continue; /* bypass ThisTask since it is already up to date */
        for(i = ddecomp->Tasks[ta].StartLeaf; i < ddecomp->Tasks[ta].EndLeaf; i ++) {
            int no = ddecomp->TopLeaves[i].treenode;
            tree->Nodes[no].mom.hmax = TopLeafhmax[i];
 
            while(no >= 0)
            {
                if(TopLeafhmax[i] <= tree->Nodes[no].mom.hmax)
                    break;
                tree->Nodes[no].mom.hmax = TopLeafhmax[i];
                no = tree->Nodes[no].father;
            }
         }
    }
    myfree(TopLeafhmax);
 
    tree->hmax_computed_flag = 1;
    walltime_measure("/Tree/HmaxUpdate");
}

References NODE::center, DMAX, task_data::EndLeaf, NODE::father, ForceTree::Father, NODE::hmax, ForceTree::hmax_computed_flag, NODE::len, NODE::mom, myfree, mymalloc, ForceTree::Nodes, NTask, DomainDecomp::NTopLeaves, part_manager_type::NumPart, P, PartManager, task_data::StartLeaf, DomainDecomp::Tasks, ThisTask, DomainDecomp::TopLeaves, topleaf_data::treenode, and walltime_measure.

Referenced by run().

Here is the caller graph for this function:

force_update_node_parallel()

void force_update_node_parallel	(	const ForceTree *	tree,
		const DomainDecomp *	ddecomp
	)

This routine determines the multipole moments for a given internal node and all its subnodes in parallel, assigning the recursive algorithm to different threads using openmp's task api. The result is stored in tb.Nodes in the sequence of this tree-walk.

• A new task is spawned from each down from each local topleaf. Local topleaves are used so that we do not waste time trying moment calculation with pseudoparticles.
• Each internal node found at that level is added to a list, together with its sibling.
• Each node in this list then has the recursive moment calculation called on it. Note: If the tree is very unbalanced and one branch much deeper than the others, this will not be efficient.
• Once each tree's recursive moment is generated in parallel, the tail value from each recursion is stored, and the node marked as done.
• A final recursive moment calculation is run in serial for the top 3 levels of the tree. When it encounters one of the pre-computed nodes, it searches the list of pre-computed tail values to set the next node as if it had recursed and continues.

Definition at line 1081 of file forcetree.c.

{
    int ThisTask;
    MPI_Comm_rank(MPI_COMM_WORLD, &ThisTask);
 
#pragma omp parallel
#pragma omp single nowait
    {
        int i;
        for(i = ddecomp->Tasks[ThisTask].StartLeaf; i < ddecomp->Tasks[ThisTask].EndLeaf; i ++) {
            const int no = ddecomp->TopLeaves[i].treenode;
            /* Nodes containing other nodes: the overwhelmingly likely case.*/
            if(tree->Nodes[no].f.ChildType == NODE_NODE_TYPE) {
                #pragma omp task default(none) shared(tree) firstprivate(no)
                force_update_node_recursive(no, tree->Nodes[no].sibling, 1, tree);
            }
            else if(tree->Nodes[no].f.ChildType == PARTICLE_NODE_TYPE)
                force_update_particle_node(no, tree);
            else if(tree->Nodes[no].f.ChildType == PSEUDO_NODE_TYPE)
                endrun(5, "Error, found pseudo node %d but domain entry %d says on task %d\n", no, i, ThisTask);
        }
    }
}

References NODE::ChildType, endrun(), NODE::f, force_update_node_recursive(), force_update_particle_node(), NODE_NODE_TYPE, ForceTree::Nodes, PARTICLE_NODE_TYPE, PSEUDO_NODE_TYPE, NODE::sibling, task_data::StartLeaf, DomainDecomp::Tasks, ThisTask, DomainDecomp::TopLeaves, and topleaf_data::treenode.

Referenced by do_tree_test(), and force_tree_build().

Here is the call graph for this function:

Here is the caller graph for this function:

init_forcetree_params()

void init_forcetree_params

(

const int

FastParticleType

)

Definition at line 43 of file forcetree.c.

{
    /* This was increased due to the extra nodes created by subtrees*/
    ForceTreeParams.TreeAllocFactor = 0.9;
    ForceTreeParams.FastParticleType = FastParticleType;
}

References forcetree_params::FastParticleType, ForceTreeParams, and forcetree_params::TreeAllocFactor.

Referenced by begrun(), setup_density(), setup_tree(), and test_fof().

Here is the caller graph for this function:

node_is_node()

static int node_is_node ( int  no, const ForceTree *  tree  )

inlinestatic

Definition at line 145 of file forcetree.h.

{
    return (no >= tree->firstnode) && (no < tree->firstnode + tree->numnodes);
}

References ForceTree::firstnode, and ForceTree::numnodes.

node_is_particle()

static int node_is_particle ( int  no, const ForceTree *  tree  )

inlinestatic

Definition at line 139 of file forcetree.h.

{
    return no >= 0 && no < tree->firstnode;
}

References ForceTree::firstnode.

Referenced by ngb_treefind_threads().

Here is the caller graph for this function:

node_is_pseudo_particle()

static int node_is_pseudo_particle ( int  no, const ForceTree *  tree  )

inlinestatic

Definition at line 133 of file forcetree.h.

{
    return no >= tree->lastnode;
}

References ForceTree::lastnode.

Referenced by ngb_treefind_threads().

Here is the caller graph for this function: