FMM Cost Model¶
This module helps predict the running time of each step of FMM
FMMTranslationCostModel
describes the translation or evaluation cost of a
single operation. For example, m2p describes the cost for translating a single
multipole expansion to a single target.
AbstractFMMCostModel
uses FMMTranslationCostModel
and calibration
parameter to compute the total cost of each step of FMM in each box. There is an
AbstractFMMCostModel
, implemented by FMMCostModel
.
examples/cost_model.py
demostrates how the calibration and evaluation
are performed.
A similar module in pytential extends the functionality of his module to incorporate QBXspecific operations.
Translation Cost of a Single Operation¶

class
boxtree.cost.
FMMTranslationCostModel
(ncoeffs_fmm_by_level, uses_point_and_shoot)¶ Provides modeled costs for individual translations or evaluations.
Note
Current implementation assumes the calibration parameters are linear in the modeled cost. For example, var(“c_p2l”) * self.ncoeffs_fmm_by_level[level] is valid, but var(“c_p2l”) ** 2 * self.ncoeffs_fmm_by_level[level] is not.

boxtree.cost.
make_pde_aware_translation_cost_model
(dim, nlevels)¶ Create a cost model for FMM translation operators that make use of the knowledge that the potential satisfies a PDE.
For example, this factory is used for complex Taylor and FourierBessel expansions in 2D, and spherical harmonics (with pointandshoot) in 3D.

boxtree.cost.
make_taylor_translation_cost_model
(dim, nlevels)¶ Create a cost model for FMM translation based on Taylor expansions in Cartesian coordinates.
Cost Model Classes¶

class
boxtree.cost.
AbstractFMMCostModel
(translation_cost_model_factory=<function make_pde_aware_translation_cost_model>)¶ An interface to obtain both FMM operation counts and calibrated (e.g. in seconds) cost estimates.
To obtain operation counts only, use
get_unit_calibration_params()
withcost_per_stage()
orcost_per_box()
.To calibrate the model, pass operation counts together with timing data to
estimate_calibration_params()
.To evaluate the calibrated models, pass the calibration parameters from
estimate_calibration_params()
tocost_per_stage()
orcost_per_box()
.
Evaluation

cost_per_box
(queue, traversal, level_to_order, calibration_params, ndirect_sources_per_target_box=None, box_target_counts_nonchild=None)¶ Predict the perbox costs of a new traversal object.
 Parameters
queue – a
pyopencl.CommandQueue
object.traversal – a
boxtree.traversal.FMMTraversalInfo
object.level_to_order – a
numpy.ndarray
of shape (traversal.tree.nlevels,) representing the expansion orders of different levels.calibration_params – a
dict
of calibration parameters. These parameters can be obtained viaestimate_calibration_params()
orget_unit_calibration_params()
.ndirect_sources_per_target_box – a
numpy.ndarray
orpyopencl.array.Array
of shape (ntarget_boxes,), the number of direct evaluation sources (list 1, list 3 close, list 4 close) for each target box. You may findget_ndirect_sources_per_target_box()
helpful. This argument is useful because the same result can be reused for p2p, p2qbxl and tsqbx.box_target_counts_nonchild – a
numpy.ndarray
orpyopencl.array.Array
of shape (nboxes,), the number of targets which need evaluation. For example, this is useful in QBX by specifying the number of nonQBX targets. If None, all targets are considered, namely traversal.tree.box_target_counts_nonchild.
 Returns
a
numpy.ndarray
orpyopencl.array.Array
of shape (nboxes,), where the ith entry represents the cost of all stages for box i.

cost_per_stage
(queue, traversal, level_to_order, calibration_params, ndirect_sources_per_target_box=None, box_target_counts_nonchild=None)¶ Predict the perstage costs of a new traversal object.
 Parameters
queue – a
pyopencl.CommandQueue
object.traversal – a
boxtree.traversal.FMMTraversalInfo
object.level_to_order – a
numpy.ndarray
of shape (traversal.tree.nlevels,) representing the expansion orders of different levels.calibration_params – a
dict
of calibration parameters. These parameters can be obtained viaestimate_calibration_params()
orget_unit_calibration_params()
.ndirect_sources_per_target_box – a
numpy.ndarray
orpyopencl.array.Array
of shape (ntarget_boxes,), the number of direct evaluation sources (list 1, list 3 close, list 4 close) for each target box. You may findget_ndirect_sources_per_target_box()
helpful. This argument is useful because the same result can be reused for p2p, p2qbxl and tsqbx.box_target_counts_nonchild – a
numpy.ndarray
orpyopencl.array.Array
of shape (nboxes,), the number of targets which need evaluation. For example, this is useful in QBX by specifying the number of nonQBX targets. If None, all targets are considered, namely traversal.tree.box_target_counts_nonchild.
 Returns
a
dict
, mapping FMM stage names to cost numbers.
Calibration

estimate_calibration_params
(model_results, timing_results, time_field_name='wall_elapsed', additional_stage_to_param_names=())¶  Parameters
model_results – a
list
of the modeled cost for each step of FMM, returned bycost_per_stage()
with unit calibration parameters (fromget_unit_calibration_params()
)timing_results – a
list
of the same length as model_results. Each entry is adict
filled with timing data returned by boxtree.fmm.drive_fmmtime_field_name – a
str
, the field name from the timing result. Usually this can be “wall_elapsed” or “process_elapsed”.additional_stage_to_param_names – a
dict
for mapping stage names to parameter names. This is useful for supplying additional stages of QBX.
 Returns
a
dict
of calibration parameters. If there is no model result for a particular stage, the estimated calibration parameter for that stage is NaN.
Utilities

abstract
aggregate_over_boxes
(per_box_result)¶ Sum all entries of per_box_result into a number.
 Parameters
per_box_result – an object of
numpy.ndarray
orpyopencl.array.Array
, the result to be sumed. Returns
a
float
, the result of the sum.

static
get_unit_calibration_params
()¶

abstract
get_ndirect_sources_per_target_box
(queue, traversal)¶ Collect the number of direct evaluation sources (list 1, list 3 close and list 4 close) for each target box.
 Parameters
queue – a
pyopencl.CommandQueue
object.traversal – a
boxtree.traversal.FMMTraversalInfo
object.
 Returns
a
numpy.ndarray
orpyopencl.array.Array
of shape (ntarget_boxes,), with each entry representing the number of direct evaluation sources for that target box.
 Parameters
translation_cost_model_factory – a function, which takes tree dimension and the number of tree levels as arguments, returns an object of
FMMTranslationCostModel
.

class
boxtree.cost.
FMMCostModel
(translation_cost_model_factory=<function make_pde_aware_translation_cost_model>)¶ An OpenCLbased realization of
AbstractFMMCostModel
.Note
For methods in this class, argument traversal should live in device memory.
 Parameters
translation_cost_model_factory – a function, which takes tree dimension and the number of tree levels as arguments, returns an object of
FMMTranslationCostModel
.