Peano

Searching...

No Matches

Associate particles to spacetree vertices. More...

Inheritance diagram for peano4.toolbox.particles.api.UpdateParticleGridAssociation_BucketSort.UpdateParticleGridAssociation_BucketSort:

[legend]

Collaboration diagram for peano4.toolbox.particles.api.UpdateParticleGridAssociation_BucketSort.UpdateParticleGridAssociation_BucketSort:

[legend]

Public Member Functions
	__init__ (self, particle_set, guard="true")
	get_body_of_operation (self, operation_name)
	Core actions triggered when we run through the mesh.
	get_action_set_name (self)
	Return unique action set name.
	get_constructor_body (self)
	Define a tailored constructor body.
	get_destructor_body (self)
	get_attributes (self)
	Return attributes as copied and pasted into the generated class.
Public Member Functions inherited from peano4.toolbox.particles.api.AbstractUpdateParticleGridAssociation.AbstractUpdateParticleGridAssociation
	__init__ (self, particle_set, guard="true")
	get_body_of_getGridControlEvents (self)
	user_should_modify_template (self)
	Is the user allowed to modify the output.
	get_includes (self)
	Inject all the default includes.
	get_body_of_unprepareTraversal (self)
Public Member Functions inherited from peano4.solversteps.ActionSet.ActionSet
	__init__ (self, descend_invocation_order=0, parallel=False)
	get_static_initialisations (self, full_qualified_classname)
	get_body_of_prepareTraversal (self)

Static Protected Attributes
	_Template_Sieve
Static Protected Attributes inherited from peano4.toolbox.particles.api.AbstractUpdateParticleGridAssociation.AbstractUpdateParticleGridAssociation
	_Template_BeginTraversal
	_Template_EndTraversal
	_Template_ValidateParticleLevelAssociation
	_Template_Drop
	_Template_LiftAllParticles

Static Private Attributes
	__Template_LiftParticles

Additional Inherited Members
Data Fields inherited from peano4.toolbox.particles.api.AbstractUpdateParticleGridAssociation.AbstractUpdateParticleGridAssociation
dict	d = {}
Data Fields inherited from peano4.solversteps.ActionSet.ActionSet
	descend_invocation_order = descend_invocation_order
	parallel = parallel
Static Public Attributes inherited from peano4.toolbox.particles.api.AbstractUpdateParticleGridAssociation.AbstractUpdateParticleGridAssociation
int	DefaultDescendInvocationOrder = -65536
Static Public Attributes inherited from peano4.solversteps.ActionSet.ActionSet
str	OPERATION_BEGIN_TRAVERSAL = "beginTraversal"
str	OPERATION_END_TRAVERSAL = "endTraversal"
str	OPERATION_CREATE_PERSISTENT_VERTEX = "createPersistentVertex"
str	OPERATION_DESTROY_PERSISTENT_VERTEX = "destroyPersistentVertex"
str	OPERATION_CREATE_HANGING_VERTEX = "createHangingVertex"
str	OPERATION_DESTROY_HANGING_VERTEX = "destroyHangingVertex"
str	OPERATION_CREATE_PERSISTENT_FACE = "createPersistentFace"
str	OPERATION_DESTROY_PERSISTENT_FACE = "destroyPersistentFace"
str	OPERATION_CREATE_HANGING_FACE = "createHangingFace"
str	OPERATION_DESTROY_HANGING_FACE = "destroyHangingFace"
str	OPERATION_CREATE_CELL = "createCell"
str	OPERATION_DESTROY_CELL = "destroyCell"
str	OPERATION_TOUCH_VERTEX_FIRST_TIME = "touchVertexFirstTime"
str	OPERATION_TOUCH_VERTEX_LAST_TIME = "touchVertexLastTime"
str	OPERATION_TOUCH_FACE_FIRST_TIME = "touchFaceFirstTime"
str	OPERATION_TOUCH_FACE_LAST_TIME = "touchFaceLastTime"
str	OPERATION_TOUCH_CELL_FIRST_TIME = "touchCellFirstTime"
str	OPERATION_TOUCH_CELL_LAST_TIME = "touchCellLastTime"
Protected Attributes inherited from peano4.toolbox.particles.api.AbstractUpdateParticleGridAssociation.AbstractUpdateParticleGridAssociation
	_particle_set = particle_set

Detailed Description

Associate particles to spacetree vertices.

Sort particles into the respective levels and cells. This mapping should be used every time you move particles around.

Algorithm

The present algorithm is a bucket sort. It consists of very few, simple steps:

If a particle has not moved or has moved but not approached another vertex, leave it where it is. We sort incrementally.
If a particle has moved and is not associated to its closest vertex anymore, add it to a global list.
If a particle has increased its cut-off radius and this cut-off radius does not fit into the present mesh resolution anymore, add it to a global list.
Exchange the global list between all ranks after each sweep.
If a particle from the global list fits into a cell, add it to the closest vertex.

Dynamic adaptive mesh refinement

If the grid is refined around a certain vertex, we usually have to drop particles associated to the coarser vertex - which is now a refined one - to the next finer level. However, such a drop would violate our bucketing principle. The other sorting algorithms are fine with drops, but we are not using them here.

What we do instead is that we identify such particles and lift them into the sieve set. Which is counterintuitive as we lift particles which should be dropped. However, we know that the subsequent mesh sweep then will insert them into the right level. That is, we map a drop operation onto a lift-globally-sieve sequence.

Contextualisation

The algorithm describes an incremental bucket sort and naturally supports tunneling or massive changes of the cut-off. From an conceptional point of view, it is a stripped down version of the lift and drop variant without the lifts and the drops. After all, each lift becomes directly an additional to the global sieve list, and then we are done.

So, in theory, we could basically take UpdateParticleGridAssociation_LiftDrop and remove the lifts and drops. However, this is slow.

Impact on particle storage

Whenever we remove a particle from the mesh and add it to the global sieve list or whenever we actually sieve a particle, i.e. add it to a vertex, we alter the respective vertex. However, we never ever alter the vertex lists from a coarser vertex. If this action set becomes a preamble to a gather, we hence always maintain continuous memory segments in line with Peano's memory pool discussion.

Sieve set administration

For bucket sort, each action set clones its own sieve set and then inserts all particles, i.e. both inside and virtual ones. This is important, as we want to have everything in the right place in one mesh sweep. We cannot just insert local particles (as in other action sets) and then rely on the boundary exchange to get the halos right. As each action set clones its own particle set, we can in return remove any particle successfully inserted.

This means we have some high overhead initially to replicate all sieved particles. From thereon, we however run embarassingly parallel and bring the memory footprint successively down.

Definition at line 12 of file UpdateParticleGridAssociation_BucketSort.py.

Constructor & Destructor Documentation

◆ init()

peano4.toolbox.particles.api.UpdateParticleGridAssociation_BucketSort.UpdateParticleGridAssociation_BucketSort.__init__	(	self,
		particle_set,
		guard = "true" )

Definition at line 92 of file UpdateParticleGridAssociation_BucketSort.py.

References __init__().

Referenced by __init__().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

◆ get_action_set_name()

peano4.toolbox.particles.api.UpdateParticleGridAssociation_BucketSort.UpdateParticleGridAssociation_BucketSort.get_action_set_name ( self )

Return unique action set name.

Returns a description (word) for the mapping which is also used as class name for the generated type. As a consequence, the result should be one word (if possible) and uppercase. Also, every subclass should overwrite this routine.

The generator will take the result and construct eventually classes similar to MyStep2Dummy.h and MyStep2Dummy.cpp or similar for the example below, where we return Dummy.

Reimplemented from peano4.solversteps.ActionSet.ActionSet.

Definition at line 261 of file UpdateParticleGridAssociation_BucketSort.py.

◆ get_attributes()

peano4.toolbox.particles.api.UpdateParticleGridAssociation_BucketSort.UpdateParticleGridAssociation_BucketSort.get_attributes ( self )

Return attributes as copied and pasted into the generated class.

Please note that action sets are not persistent, i.e. there is one object creation per grid sweep per tree.

Reimplemented from peano4.toolbox.particles.api.AbstractUpdateParticleGridAssociation.AbstractUpdateParticleGridAssociation.

Definition at line 284 of file UpdateParticleGridAssociation_BucketSort.py.

Referenced by get_attributes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_body_of_operation()

peano4.toolbox.particles.api.UpdateParticleGridAssociation_BucketSort.UpdateParticleGridAssociation_BucketSort.get_body_of_operation	(		self,
			operation_name )

Core actions triggered when we run through the mesh.

See class description. If you compare this function to UpdateParticleGridAssociation_LiftDrop.get_body_of_operation(), we see that we use our modified lift routine when particles have moved and in return can omit the dropping. That is, the cousin's realisation is

if operation_name == ActionSet.OPERATION_TOUCH_VERTEX_FIRST_TIME:
    result =  self._Template_Drop.render(**self.d)
    result += self._Template_Sieve.render(**self.d)

while we only do the sieve here.

Reimplemented from peano4.solversteps.ActionSet.ActionSet.

Definition at line 229 of file UpdateParticleGridAssociation_BucketSort.py.

◆ get_constructor_body()

peano4.toolbox.particles.api.UpdateParticleGridAssociation_BucketSort.UpdateParticleGridAssociation_BucketSort.get_constructor_body ( self )

Define a tailored constructor body.

By default, the constructor of an action set is empty. If you you assign attributes to your action set, you however might want to initialise them here. We do not support initialisation lists, to all has to be done via setters unless you create attributes on the heap.

The constructor's signature will look similar to

   EnumerateAndInitSolution2petsc_actionsets_InitVertexDoFs0(int treeNumber);

where the treeNumber is -1 if this is the global instance of the action set owned by a rank, or a number greater or equal 0 if this action set is a clone of the glocal action set that's used by one tree traversal.