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() with cost_per_stage() or cost_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() to cost_per_stage() or cost_per_box().

cost_per_box(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

• 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 via estimate_calibration_params() or get_unit_calibration_params().

• ndirect_sources_per_target_box – a numpy.ndarray or pyopencl.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 find get_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 or pyopencl.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 or pyopencl.array.Array of shape (nboxes,), where the ith entry represents the cost of all stages for box i.

cost_per_stage(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

• 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 via estimate_calibration_params() or get_unit_calibration_params().

• ndirect_sources_per_target_box – a numpy.ndarray or pyopencl.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 find get_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 or pyopencl.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.

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 by cost_per_stage() with unit calibration parameters (from get_unit_calibration_params())

• timing_results – a list of the same length as model_results. Each entry is a dict filled with timing data returned by boxtree.fmm.drive_fmm

• time_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.

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 or pyopencl.array.Array, the result to be sumed.

Returns

a float, the result of the sum.

static get_unit_calibration_params()

Parameters

translation_cost_model_factory – a function, which takes tree dimension and the number of tree levels as arguments, returns an object of TranslationCostModel.

class boxtree.cost.FMMCostModel(queue, 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

• queue – a pyopencl.CommandQueue object on which the execution of this object runs.

• translation_cost_model_factory – a function, which takes tree dimension and the number of tree levels as arguments, returns an object of TranslationCostModel.