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 QBX-specific 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 Fourier-Bessel expansions in 2D, and spherical harmonics (with point-and-shoot) 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 per-box 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 non-QBX 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 per-stage 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 non-QBX 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 OpenCL-based 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
.