GADGET-4
tree.h
Go to the documentation of this file.
1/*******************************************************************************
2 * \copyright This file is part of the GADGET4 N-body/SPH code developed
3 * \copyright by Volker Springel. Copyright (C) 2014-2020 by Volker Springel
4 * \copyright (vspringel@mpa-garching.mpg.de) and all contributing authors.
5 *******************************************************************************/
6
12#ifndef TREE_H
13#define TREE_H
14
15#ifndef TREE_NUM_BEFORE_NODESPLIT
16#define TREE_NUM_BEFORE_NODESPLIT 3 // daughter nodes are only created if there are more than this number of particles in a node
17#endif
18
19#define TREE_MODE_BRANCH 0
20#define TREE_MODE_TOPLEVEL 1
21
22#define MAX_TREE_ALLOC_FACTOR 30.0
23
24#define TREE_MAX_ITER 100
25
26#include <mpi.h>
27
28#include "../domain/domain.h"
29#include "../mpi_utils/shared_mem_handler.h"
30#include "../sort/peano.h"
31#include "../system/system.h"
32
33class sim;
34
48{
49 std::atomic<node_bit_field> flag_already_fetched;
50
59 int father;
60
61 int OriginTask; /* MPI rank (in full compute communicator) on which this node and its daughter nodes are natively stored */
62 int OriginNode; /* Index of the node on the MPI rank that stores it and its daughter nodes natively */
63
64 unsigned char level;
65 unsigned char sibling_shmrank;
66 unsigned char nextnode_shmrank;
67
68 std::atomic_flag access;
69
70 std::atomic<unsigned char> cannot_be_opened_locally;
71
72 // unsigned char cannot_be_opened_locally : 1;
73 unsigned char not_empty : 1;
74};
75
77{
78 int Node;
79};
80
82{
83 int Task;
84 int Index;
87};
88
89template <typename node, typename partset, typename point_data, typename foreign_point_data>
90class tree
91{
92 /* class for oct tree */
93
94 public:
96 {
97 int p;
99 };
100
102 partset *Tp;
103
104 int *Father;
108
109 node *TopNodes;
110 node *Nodes;
112 foreign_point_data *Foreign_Points;
113
119 ptrdiff_t *TreeP_offsets;
121 ptrdiff_t *TreePS_offsets;
122
124
125 unsigned char *NodeLevel;
126
127 point_data *Points;
130
135
141
142 int NumForeignNodes; // number of imported foreign tree nodes
144
145 int NumForeignPoints; // number of imported foreign particles to allow completion of local tree walks
147
148 // for some statistics about the number of imported nodes and points
151
153
156
160
164
166
167 double Buildtime;
168
171
173 {
177 };
179
180 static bool compare_ghostrank(const fetch_data &a, const fetch_data &b) { return a.GhostRank < b.GhostRank; }
181
187
189 {
191 int Node;
194 };
196
197 static bool compare_workstack(const workstack_data &a, const workstack_data &b)
198 {
200 return true;
202 return false;
203
204 return a.Target < b.Target;
205 }
206
207 void tree_add_to_fetch_stack(node *nop, int nodetoopen, unsigned char shmrank)
208 {
210 {
211 Terminate("we shouldn't get here");
212 MaxOnFetchStack *= 1.1;
213 StackToFetch = (fetch_data *)Mem.myrealloc_movable(StackToFetch, MaxOnFetchStack * sizeof(fetch_data));
214 }
215
217
218 node_bit_field oldval = nop->flag_already_fetched.fetch_or(mybit);
219
220 if((oldval & mybit) == 0) // it wasn't fetched by me yet
221 {
222 int ghostrank = Shmem.GetGhostRankForSimulCommRank[nop->OriginTask];
223
227
229 }
230 }
231
232 void tree_add_to_work_stack(int target, int no, unsigned char shmrank, int mintopleafnode)
233 {
235 {
236 Terminate("we shouldn't get here");
237 MaxOnWorkStack *= 1.1;
238 WorkStack = (workstack_data *)Mem.myrealloc_movable(WorkStack, MaxOnWorkStack * sizeof(workstack_data));
239 }
240
245
247 }
248
250 {
253 };
254
255 struct node_req
256 {
259 };
260
263
264 enum ftype
265 {
270 };
271
272 void tree_fetch_foreign_nodes(enum ftype fetch_type);
274
275 inline foreign_point_data *get_foreignpointsp(int n, unsigned char shmrank)
276 {
277 return (foreign_point_data *)((char *)TreeSharedMemBaseAddr[shmrank] + TreeForeign_Points_offsets[shmrank]) + n;
278 }
279
280 inline subfind_data *get_PSp(int n, unsigned char shmrank)
281 {
282 return (subfind_data *)((char *)TreeSharedMemBaseAddr[shmrank] + TreePS_offsets[shmrank]) + n;
283 }
284
285 typedef decltype(Tp->P) pdata;
286
287 inline pdata get_Pp(int n, unsigned char shmrank)
288 {
289 return (pdata)((char *)TreeSharedMemBaseAddr[shmrank] + TreeP_offsets[shmrank]) + n;
290 }
291
292 inline sph_particle_data *get_SphPp(int n, unsigned char shmrank)
293 {
294 return (sph_particle_data *)((char *)TreeSharedMemBaseAddr[shmrank] + TreeSphP_offsets[shmrank]) + n;
295 }
296
297 private:
306 public:
307 tree() /* constructor */
308 {
309 TopNodes = NULL;
310 Nodes = NULL;
311 NodeIndex = NULL;
312 NodeSibling = NULL;
313 NodeLevel = NULL;
314 Points = NULL;
315 Nextnode = NULL;
316 Father = NULL;
317 D = NULL;
318 }
319
321 int treebuild(int ninsert, int *indexlist);
322 void treefree(void);
323 void treeallocate(int max_partindex, partset *Pptr, domain<partset> *Dptr);
325
326 void tree_export_node_threads(int no, int i, thread_data *thread, offset_tuple off = 0);
327 void tree_export_node_threads_by_task_and_node(int task, int nodeindex, int i, thread_data *thread, offset_tuple off = 0);
328
329 virtual void update_node_recursive(int no, int sib, int mode) = 0;
330 virtual void exchange_topleafdata(void) = 0;
331 virtual void report_log_message(void) = 0;
332 virtual void fill_in_export_points(point_data *exp_point, int i, int no) = 0;
333
334 inline node *get_nodep(int no)
335 {
336 node *nop;
337
338 if(no < MaxPart + D->NTopnodes)
339 nop = &TopNodes[no];
340 else if(no < MaxPart + MaxNodes)
341 nop = &Nodes[no];
342 else
343 Terminate("illegale node index");
344
345 return nop;
346 }
347
348 inline node *get_nodep(int no, unsigned char shmrank)
349 {
350 node *nop;
351
352 if(no < MaxPart + D->NTopnodes)
353 nop = &TopNodes[no];
354 else if(no < MaxPart + MaxNodes) /* an internal node */
355 {
356 node *Nodes_shmrank = (node *)((char *)TreeSharedMemBaseAddr[shmrank] + TreeNodes_offsets[shmrank]);
357 nop = &Nodes_shmrank[no];
358 }
359 else if(no >= EndOfTreePoints && no < EndOfForeignNodes) /* an imported tree node */
360 {
361 node *Foreign_Nodes_shmrank = (node *)((char *)TreeSharedMemBaseAddr[shmrank] + TreeForeign_Nodes_offsets[shmrank]);
362
363 nop = &Foreign_Nodes_shmrank[no - EndOfTreePoints];
364 }
365 else
366 Terminate("illegale node index");
367
368 return nop;
369 }
370
371 inline int *get_nextnodep(unsigned char shmrank)
372 {
373 return (int *)((char *)TreeSharedMemBaseAddr[shmrank] + TreeNextnode_offsets[shmrank]);
374 }
375
376 inline point_data *get_pointsp(int no, unsigned char shmrank)
377 {
378 return (point_data *)((char *)TreeSharedMemBaseAddr[shmrank] + TreePoints_offsets[shmrank]) + no;
379 }
380
381 inline void tree_get_node_and_task(int i, int &no, int &task)
382 {
383 MyIntPosType xxb = Tp->P[i].IntPos[0];
384 MyIntPosType yyb = Tp->P[i].IntPos[1];
385 MyIntPosType zzb = Tp->P[i].IntPos[2];
386 MyIntPosType mask = (((MyIntPosType)1) << (BITS_FOR_POSITIONS - 1));
387 unsigned char shiftx = (BITS_FOR_POSITIONS - 3);
388 unsigned char shifty = (BITS_FOR_POSITIONS - 2);
389 unsigned char shiftz = (BITS_FOR_POSITIONS - 1);
390 unsigned char level = 0;
391 unsigned char rotation = 0;
392
393#if defined(PMGRID) && defined(PLACEHIGHRESREGION)
394 Tp->P[i].InsideOutsideFlag = Tp->check_high_res_point_location(Tp->P[i].IntPos);
395#endif
396
397 no = 0;
398 while(D->TopNodes[no].Daughter >= 0) // walk down top tree to find correct leaf
399 {
400 unsigned char pix = (((unsigned char)((xxb & mask) >> (shiftx--))) | ((unsigned char)((yyb & mask) >> (shifty--))) |
401 ((unsigned char)((zzb & mask) >> (shiftz--))));
402 unsigned char subnode = peano_incremental_key(pix, &rotation);
403
404 mask >>= 1;
405 level++;
406
407 no = D->TopNodes[no].Daughter + subnode;
408 }
409
410 no = D->TopNodes[no].Leaf;
411 task = D->TaskOfLeaf[no];
412 }
413
414 private:
415 /* private member functions */
416
417 int treebuild_construct(void);
418 int treebuild_insert_group_of_points(int num, index_data *index_list, int th, unsigned char level, int sibling);
419 int create_empty_nodes(int no, int level, int topnode, int bits, int sibling, MyIntPosType x, MyIntPosType y, MyIntPosType z);
420
421 private:
422 /* sort kernel */
423 static inline bool compare_index_data_subnode(const index_data &a, const index_data &b) { return a.subnode < b.subnode; }
424};
425
426#endif
Definition: domain.h:31
int Island_ThisTask
int * GetGhostRankForSimulCommRank
Definition: simulation.h:50
Definition: tree.h:91
int TreeSharedMem_ThisTask
Definition: tree.h:162
void tree_export_node_threads(int no, int i, thread_data *thread, offset_tuple off=0)
Definition: tree.cc:1301
int FirstNonTopLevelNode
Definition: tree.h:152
void treeallocate_share_topnode_addresses(void)
Definition: tree.cc:890
long long sum_NumForeignPoints
Definition: tree.h:150
double Buildtime
Definition: tree.h:167
workstack_data * WorkStack
Definition: tree.h:195
int MaxPart
Definition: tree.h:136
int NumForeignPoints
Definition: tree.h:145
point_data * get_pointsp(int no, unsigned char shmrank)
Definition: tree.h:376
int NumOnFetchStack
Definition: tree.h:169
sph_particle_data * get_SphPp(int n, unsigned char shmrank)
Definition: tree.h:292
int NumPartExported
Definition: tree.h:140
void cleanup_shared_memory_access(void)
Definition: tree.cc:970
foreign_point_data * get_foreignpointsp(int n, unsigned char shmrank)
Definition: tree.h:275
subfind_data * get_PSp(int n, unsigned char shmrank)
Definition: tree.h:280
int NextFreeNode
Definition: tree.h:159
node * Foreign_Nodes
Definition: tree.h:111
int * NodeIndex
Definition: tree.h:107
point_data * Points
Definition: tree.h:127
MPI_Comm TreeSharedMemComm
Definition: tree.h:161
int MaxOnFetchStack
Definition: tree.h:170
int * IndexList
Definition: tree.h:128
void treeallocate(int max_partindex, partset *Pptr, domain< partset > *Dptr)
Definition: tree.cc:776
int * NodeSibling
Definition: tree.h:106
unsigned char * NodeLevel
Definition: tree.h:125
domain< partset > * D
Definition: tree.h:101
ptrdiff_t * TreeNodes_offsets
Definition: tree.h:114
pdata get_Pp(int n, unsigned char shmrank)
Definition: tree.h:287
static bool compare_workstack(const workstack_data &a, const workstack_data &b)
Definition: tree.h:197
partset * Tp
Definition: tree.h:102
ptrdiff_t * TreePS_offsets
Definition: tree.h:121
int MaxForeignNodes
Definition: tree.h:143
int MaxOnWorkStack
Definition: tree.h:183
ptrdiff_t * TreeNextnode_offsets
Definition: tree.h:116
virtual void exchange_topleafdata(void)=0
int * get_nextnodep(unsigned char shmrank)
Definition: tree.h:371
long long sum_NumForeignNodes
Definition: tree.h:149
int NumPartImported
Definition: tree.h:139
tree()
Definition: tree.h:307
int TreeSharedMem_NTask
Definition: tree.h:163
virtual void report_log_message(void)=0
ptrdiff_t * TreeP_offsets
Definition: tree.h:119
ptrdiff_t * TreePoints_offsets
Definition: tree.h:115
node * TopNodes
Definition: tree.h:109
static bool compare_ghostrank(const fetch_data &a, const fetch_data &b)
Definition: tree.h:180
virtual void update_node_recursive(int no, int sib, int mode)=0
int EndOfForeignNodes
Definition: tree.h:155
int * Send_offset
Definition: tree.h:131
void tree_fetch_foreign_nodes(enum ftype fetch_type)
Definition: tree.cc:983
int NumNodes
Definition: tree.h:138
void prepare_shared_memory_access(void)
Definition: tree.cc:909
foreign_point_data * Foreign_Points
Definition: tree.h:112
fetch_data * StackToFetch
Definition: tree.h:178
virtual void fill_in_export_points(point_data *exp_point, int i, int no)=0
node * Nodes
Definition: tree.h:110
int NewOnWorkStack
Definition: tree.h:184
int * Recv_offset
Definition: tree.h:134
int AllocWorkStackBaseHigh
Definition: tree.h:186
int MaxForeignPoints
Definition: tree.h:146
void ** TreeSharedMemBaseAddr
Definition: tree.h:123
void treefree(void)
Definition: tree.cc:1232
int NumOnWorkStack
Definition: tree.h:182
node * get_nodep(int no, unsigned char shmrank)
Definition: tree.h:348
int TreeInfoHandle
Definition: tree.h:165
int MaxNodes
Definition: tree.h:137
decltype(Tp->P) pdata
Definition: tree.h:285
int * ResultIndexList
Definition: tree.h:129
int * Nextnode
Definition: tree.h:105
int ImportedNodeOffset
Definition: tree.h:157
int Ninsert
Definition: tree.h:158
node * get_nodep(int no)
Definition: tree.h:334
void tree_add_to_fetch_stack(node *nop, int nodetoopen, unsigned char shmrank)
Definition: tree.h:207
int * Send_count
Definition: tree.h:132
int treebuild(int ninsert, int *indexlist)
Definition: tree.cc:52
int * Father
Definition: tree.h:104
void tree_add_to_work_stack(int target, int no, unsigned char shmrank, int mintopleafnode)
Definition: tree.h:232
ftype
Definition: tree.h:265
@ FETCH_SPH_TREETIMESTEP
Definition: tree.h:269
@ FETCH_SPH_HYDRO
Definition: tree.h:268
@ FETCH_GRAVTREE
Definition: tree.h:266
@ FETCH_SPH_DENSITY
Definition: tree.h:267
void tree_initialize_leaf_node_access_info(void)
Definition: tree.cc:174
int * Recv_count
Definition: tree.h:133
int NumForeignNodes
Definition: tree.h:142
int AllocWorkStackBaseLow
Definition: tree.h:185
ptrdiff_t * TreeForeign_Nodes_offsets
Definition: tree.h:117
void tree_get_node_and_task(int i, int &no, int &task)
Definition: tree.h:381
int EndOfTreePoints
Definition: tree.h:154
ptrdiff_t * TreeForeign_Points_offsets
Definition: tree.h:118
ptrdiff_t * TreeSphP_offsets
Definition: tree.h:120
void tree_export_node_threads_by_task_and_node(int task, int nodeindex, int i, thread_data *thread, offset_tuple off=0)
Definition: tree.cc:1311
uint64_t node_bit_field
Definition: dtypes.h:136
uint32_t MyIntPosType
Definition: dtypes.h:35
#define BITS_FOR_POSITIONS
Definition: dtypes.h:37
#define Terminate(...)
Definition: macros.h:15
shmem Shmem
Definition: main.cc:45
memory Mem
Definition: main.cc:44
unsigned char peano_incremental_key(unsigned char pix, unsigned char *rotation)
Definition: peano.cc:107
Definition: tree.h:48
std::atomic_flag access
Definition: tree.h:68
unsigned char level
Definition: tree.h:64
unsigned char nextnode_shmrank
Definition: tree.h:66
std::atomic< unsigned char > cannot_be_opened_locally
Definition: tree.h:70
int OriginNode
Definition: tree.h:62
std::atomic< node_bit_field > flag_already_fetched
Definition: tree.h:49
int father
Definition: tree.h:59
unsigned char not_empty
Definition: tree.h:73
int nextnode
Definition: tree.h:57
vector< MyIntPosType > center
Definition: tree.h:51
int OriginTask
Definition: tree.h:61
unsigned char sibling_shmrank
Definition: tree.h:65
int sibling
Definition: tree.h:53
int Index
Definition: tree.h:84
node_info NodeInfo
Definition: tree.h:85
int Task
Definition: tree.h:83
Definition: tree.h:77
int Node
Definition: tree.h:78
int NodeToOpen
Definition: tree.h:174
int GhostRank
Definition: tree.h:176
int subnode
Definition: tree.h:98
int foreigntask
Definition: tree.h:257
int foreignnode
Definition: tree.h:258