#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <mpi.h>
#include "allvars.h"
#include "proto.h"
Go to the source code of this file.
Data Structures  
struct  topnode_exchange 
Defines  
#define  TOPNODEFACTOR 20.0 
#define  REDUC_FAC 0.98 
Functions  
void  domain_Decomposition (void) 
void  domain_decompose (void) 
int  domain_findSplit (int cpustart, int ncpu, int first, int last) 
void  domain_shiftSplit (void) 
void  domain_findExchangeNumbers (int task, int partner, int sphflag, int *send, int *recv) 
void  domain_exchangeParticles (int partner, int sphflag, int send_count, int recv_count) 
void  domain_countToGo (void) 
void  domain_walktoptree (int no) 
void  domain_sumCost (void) 
void  domain_findExtent (void) 
void  domain_determineTopTree (void) 
void  domain_topsplit_local (int node, peanokey startkey) 
void  domain_topsplit (int node, peanokey startkey) 
int  domain_compare_toplist (const void *a, const void *b) 
int  domain_compare_key (const void *a, const void *b) 
This file contains the code for the domain decomposition of the simulation volume. The domains are constructed from disjoint subsets of the leaves of a fiducial toplevel tree that covers the full simulation volume. Domain boundaries hence run along treenode divisions of a fiducial global BH tree. As a result of this method, the tree force are in principle strictly independent of the way the domains are cut. The domain decomposition can be carried out for an arbitrary number of CPUs. Individual domains are not cubical, but spatially coherent since the leaves are traversed in a PeanoHilbert order and individual domains form segments along this order. This also ensures that each domain has a small surface to volume ratio, which minimizes communication.
Definition in file domain.c.





This is a comparison kernel used in a sort routine. 

This is a comparison kernel used in a sort routine. 

This function determines how many particles that are currently stored on the local CPU have to be moved off according to the domain decomposition. Definition at line 729 of file domain.c. References topnode_data::Daughter, DomainTask, Key, topnode_data::Leaf, NTask, P, topnode_data::Size, topnode_data::StartKey, TopNodes, and particle_data::Type. Referenced by domain_decompose(). 

This function carries out the actual domain decomposition for all particle types. It will try to balance the workload for each domain, as estimated based on the P[i]GravCost values. The decomposition will respect the maximum allowed memoryimbalance given by the value of PartAllocFactor. Definition at line 154 of file domain.c. References All, domain_countToGo(), domain_determineTopTree(), domain_exchangeParticles(), domain_findExchangeNumbers(), domain_findExtent(), domain_findSplit(), domain_shiftSplit(), domain_sumCost(), DomainEndList, DomainMyLast, DomainMyStart, DomainStartList, endrun(), NTask, NTopleaves, Ntype, NtypeLocal, P, global_data_all_processes::SofteningTable, ThisTask, global_data_all_processes::TotN_gas, and particle_data::Type. Referenced by domain_Decomposition(). 

This is the main routine for the domain decomposition. It acts as a driver routine that allocates various temporary buffers, maps the particles back onto the periodic box if needed, and then does the domain decomposition, and a final PeanoHilbert order of all particles as a tuning measure. Definition at line 62 of file domain.c. References All, global_data_all_processes::CPU_Domain, global_data_all_processes::CPU_Peano, do_box_wrapping(), domain_decompose(), Key, KeySorted, global_data_all_processes::MaxPart, global_data_all_processes::MaxPartSph, N_gas, NTask, global_data_all_processes::NumForcesSinceLastDomainDecomp, NumPart, peano_hilbert_order(), peanokey, global_data_all_processes::PM_Ti_endstep, second(), ThisTask, global_data_all_processes::Ti_Current, timediff(), global_data_all_processes::TotNumPart, global_data_all_processes::TreeDomainUpdateFrequency, and TreeReconstructFlag. 

This function constructs the global toplevel tree node that is used for the domain decomposition. This is done by considering the string of PeanoHilbert keys for all particles, which is recursively chopped off in pieces of eight segments until each segment holds at most a certain number of particles. < Bits per dimension available for PeanoHilbert order. Note: If peanokey is defined as type int, the allowed maximum is 10. If 64bit integers are used, the maximum is 21 < Bits per dimension available for PeanoHilbert order. Note: If peanokey is defined as type int, the allowed maximum is 10. If 64bit integers are used, the maximum is 21 < The number of different PeanoHilbert cells < Bits per dimension available for PeanoHilbert order. Note: If peanokey is defined as type int, the allowed maximum is 10. If 64bit integers are used, the maximum is 21 < The number of different PeanoHilbert cells Definition at line 898 of file domain.c. References BITS_PER_DIMENSION, DomainCorner, DomainFac, Key, KeySorted, P, and peano_hilbert_key(). Referenced by domain_decompose(). 

This function exchanges particles between two CPUs according to the domain split. In doing this, the memory boundaries which may restrict the exhange process are observed. Definition at line 595 of file domain.c. References topnode_data::Daughter, DomainKeyBuf, DomainPartBuf, DomainSphBuf, DomainTask, endrun(), Key, topnode_data::Leaf, N_gas, NumPart, P, peanokey, topnode_data::Size, SphP, topnode_data::StartKey, TAG_KEY, TAG_PDATA, TAG_SPHDATA, ThisTask, TopNodes, and particle_data::Type. Referenced by domain_decompose(). 

This function counts how many particles have to be exchanged between two CPUs according to the domain split. If the CPUs are already quite full and hold data from other CPUs as well, not all the particles may be exchanged at once. In this case the communication phase has to be repeated, until enough of the thirdparty particles have been moved away such that the decomposition can be completed. Definition at line 534 of file domain.c. References All, global_data_all_processes::BunchSizeDomain, imin(), global_data_all_processes::MaxPart, global_data_all_processes::MaxPartSph, and NTask. Referenced by domain_decompose(). 

This routine finds the extent of the global domain grid. < Bits per dimension available for PeanoHilbert order. Note: If peanokey is defined as type int, the allowed maximum is 10. If 64bit integers are used, the maximum is 21 Definition at line 845 of file domain.c. References DomainCenter, DomainCorner, DomainFac, DomainLen, P, and particle_data::Pos. Referenced by domain_decompose(). 

This function tries to find a split point in a range of cells in the domaingrid. The range of cells starts at 'first', and ends at 'last' (inclusively). The number of cpus that holds the range is 'ncpu', with the first cpu given by 'cpustart'. If more than 2 cpus are to be split, the function calls itself recursively. The division tries to achieve a best particleload balance under the constraint that 'maxload' and 'maxloadsph' may not be exceeded, and that each cpu holds at least one cell from the domaingrid. If such a decomposition cannot be achieved, a nonzero error code is returned. After successful completion, DomainMyStart[] and DomainMyLast[] contain the first and last cell of the domaingrid assigned to the local task for the given type. Also, DomainTask[] contains for each cell the task it was assigned to. Definition at line 327 of file domain.c. References dmax(), DomainCount, DomainCountSph, DomainEndList, DomainStartList, and DomainTask. Referenced by domain_decompose(). 

This function tries to improve the domain decomposition found by domain_findSplit() with respect to workload balance. To this end, the boundaries in the existing domainsplit solution (which was found by trying to balance the particle load) are shifted as long as this leads to better workload while still remaining within the allowed memoryimbalance constraints. Definition at line 447 of file domain.c. References dmax(), DomainCount, DomainCountSph, DomainEndList, DomainStartList, DomainTask, DomainWork, and NTask. Referenced by domain_decompose(). 

This routine bins the particles onto the domaingrid, i.e. it sums up the total number of particles and the total amount of work in each of the domaincells. This information forms the basis for the actual decision on the adopted domain decomposition. Definition at line 786 of file domain.c. References topnode_data::Daughter, domain_walktoptree(), DomainCount, DomainCountSph, DomainWork, particle_data::GravCost, Key, topnode_data::Leaf, NTopleaves, NTopnodes, P, topnode_data::Size, topnode_data::StartKey, ThisTask, particle_data::Ti_begstep, particle_data::Ti_endstep, TopNodes, and particle_data::Type. Referenced by domain_decompose(). 

This function is responsible for constructing the global toplevel tree segments. Starting from a joint list of all local toplevel segments, in which mulitple occurences of the same spatial segment have been combined, a segment is subdivided into 8 pieces recursively until the number of particles in each segment has fallen below All.TotNumPart / (TOPNODEFACTOR * NTask). < Maximum number of nodes in the toplevel tree used for domain decomposition Definition at line 1057 of file domain.c. References topnode_data::Blocks, topnode_data::Count, topnode_data::Daughter, endrun(), NTopnodes, topnode_data::Pstart, topnode_data::Size, topnode_data::StartKey, ThisTask, and TopNodes. 

This function is responsible for constructing the local toplevel PeanoHilbert segments. A segment is cut into 8 pieces recursively until the number of particles in the segment has fallen below All.TotNumPart / (TOPNODEFACTOR * NTask * NTask). < Maximum number of nodes in the toplevel tree used for domain decomposition Definition at line 990 of file domain.c. References topnode_data::Count, topnode_data::Daughter, endrun(), NTopnodes, topnode_data::Pstart, topnode_data::Size, topnode_data::StartKey, ThisTask, and TopNodes. 

This function walks the global top tree in order to establish the number of leaves it has. These leaves are distributed to different processors. Definition at line 765 of file domain.c. References topnode_data::Daughter, topnode_data::Leaf, NTopleaves, and TopNodes. Referenced by domain_sumCost(). 