Source code for pyop3.axis_tree.visitors.layout

from __future__ import annotations

import collections
import typing
import weakref

import numpy as np
from immutabledict import immutabledict as idict
from petsc4py import PETSc

import pyop3.expr
import pyop3.sf
from pyop3 import utils
from pyop3.axis_tree import (
    Axis,
    AxisTree,
    merge_axis_trees,
)
from pyop3.axis_tree.tree import (  # TODO: move this to visitors?
    full_shape,
    replace_exprs,
    create_section_with_arrays,
)
from pyop3.cache import memory_cache
from pyop3.dtypes import IntType
from pyop3.expr import (
    AxisVar,
    Dat,
    ExpressionT,
    LinearDatBufferExpression,
    LoopIndexVar,
)
from pyop3.expr.base import NaN, get_loop_tree
from pyop3.insn import exscan, loop_

from .size import compute_axis_tree_component_size

if typing.TYPE_CHECKING:
    from pyop3.types import *


[docs] @PETSc.Log.EventDecorator() @pyop3.cache.with_self_heavy_cache # cache on the axis tree def compute_layouts(axis_tree: AxisTree) -> idict[ConcretePathT, ExpressionT]: """Compute the layout functions for an axis tree. Layout functions are expressions that take axis variables (symbolic indices per axis) and evaluate to an integer offset. As the simplest possible example consider the axis tree: {"A": 5} This tree has only a single axis and so it only has a single layout function: {"A": None}: i_A Here ``{"A": None}`` refers to the path through the tree where the layout resides and ``i_A`` is the layout function. Since the tree only has a single axis the mapping between axis indices and offsets is trivially identity. Note that this tree will also have the zero layout: {}: 0 meaning that if you are at the root of the tree then the offset must be zero. Parameters ---------- axis_tree : The axis tree to compute the layouts of. Returns ------- tuple[immutabledict.immutabledict, pyop3.StarForest] Mapping from path through the axis tree to the layout function, plus the star forest. Examples -------- For more examples please refer to ``tests/pyop3/unit/test_layout.py``. 1. Linear axis tree ~~~~~~~~~~~~~~~~~~~ For the simple axis tree (equivalent to a 2D numpy array): .. code-block:: text {"A": 5} └──➤ {"B": 3} the layout functions are: .. code-block:: text { {}: 0, {"A": None}: 3*i_A, {"A": None, "B": None}: 3*i_A + i_B, } 2. Multi-component axis tree ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For the axis tree: .. code-block:: text {A: [{0: 3}, {1: 4}]}} ├──➤ {B: 2} └──➤ {C: 1} the layout functions are: .. code-block:: text { {}: 0, {"A": 0}: 2*i_A, {"A": 0, "B": None}: 2*i_A + i_B, {"A": 1}: i_A + 6, {"A": 1, "C": None}: i_A + i_C + 6, } 3. Ragged axis tree ~~~~~~~~~~~~~~~~~~~ TODO 4. Multi-region axis tree ~~~~~~~~~~~~~~~~~~~~~~~~~ For the axis tree: .. code-block:: text {A: [{a: 1}, {b: 1}]} ├──➤ {B: [{x: 2}, {y: 1}]} └──➤ {C: [{x: 2}, {y: 1}]} where 'a' and 'b' are axis components with size 1 and 'x' and 'y' are component *regions*, we expect to have the following data layout: .. code-block:: text [ a0, a1, b0, b1 || a2, b2 ] "x" "y" In other words all entities in the 'x' region are partitioned to occur before those in 'y'. This means that the layout functions are as follows: .. code-block:: text { {}: 0, {"A": "a"}: NaN, {"A": "a", "B": None}: [[0, 1, 4]][i_A, i_B], {"A": "b"}: NaN, {"A": "b", "C": None}: [[2, 3, 5]][i_A, i_C], } The {"A": "a"} and {"A": "b"} entries are NaNs because they do not address contiguous data and so are meaningless. """ if isinstance(axis_tree, weakref.ReferenceType): axis_tree = axis_tree() return _compute_layouts_cached(axis_tree) relabeled_layouts, sf = _compute_layouts_cached(axis_tree._canonicalized) unrelabeler = axis_tree._canonical_unrelabeler layouts = idict({ unrelabeler.visit_path(path): unrelabeler(expr) for path, expr in relabeled_layouts.items() }) return layouts, sf
def _compute_layouts_cached_hashkey(axis_tree): return axis_tree._canonical_cache_key # @memory_cache( # heavy=True, # hashkey=_compute_layouts_cached_hashkey, # get_comm=lambda tree: tree.comm, # ) def _compute_layouts_cached(axis_tree: AxisTree) -> idict[ConcretePathT, ExpressionT]: if axis_tree.is_empty: return idict({idict(): None}), pyop3.sf.NullStarForest(0) # First traverse the axis tree and compute everything we can. to_tabulate = [] tabulated = {} layouts = _prepare_layouts(axis_tree, idict(), 0, to_tabulate, tabulated, ()) # add zero for the root layouts = layouts | {idict(): 0} # Now tweak the offsets for multi-region components. This is necessary because # the initial traversal treats axis components in isolation and so the strides # across regions are not yet known. # # As an example consider the following multi-region tree: # # {A: [1, 1]} # ├──➤ {B: [{x: 2}, {y: 1}]} # └──➤ {C: [{x: 2}, {y: 1}]} # # Here 'x' and 'y' are the different regions that we want to partition. Hence # we want the final layout to be: # # [ a0b0, a0b1, a1c0, a1c1 || a0b2, a1c2 ] # "x" "y" # # Since the offsets for each component are computed in isolation the current # relevant layout functions are: # # { # {"A": 0, "B": None}: [[0, 1, 2]][i_A, i_B] # {"A": 1, "C": None}: [[0, 1, 2]][i_A, i_C] # } # # whereas the correct values are: # # { # {"A": 0, "B": None}: [[0, 1, 4]][i_A, i_B] # {"A": 1, "C": None}: [[2, 3, 5]][i_A, i_C] # } # # To compute this we track a global offset and add it to arrays for each # region. In this case this results in: # # 1. regions = {"x"}, starts = [0, 0], [[0, 1, 2]][i_A, i_B], [[0, 1, 2]][i_A, i_C] # 2. regions = {"x"}, starts = [0, 2], [[0, 1, 2]][i_A, i_B], [[2, 3, 2]][i_A, i_C] # 3. regions = {"y"}, starts = [2, 2], [[0, 1, 4]][i_A, i_B], [[2, 3, 2]][i_A, i_C] # 4. regions = {"y"}, starts = [2, 3], [[0, 1, 4]][i_A, i_B], [[2, 3, 5]][i_A, i_C] # # TODO: There are particular cases (e.g. multiple regions but only a single # component or no matching regions) where it is sufficient to do an affine # layout instead of tabulating a start expression. We currently do not detect # this. starts = [0] * len(to_tabulate) visited_regions_per_offset_dat = collections.defaultdict(set) for regions in axis_tree.region_sets: for i, (offset_axes, offset_dat, _, _) in enumerate(to_tabulate): matching_regions = regions.intersection(offset_axes._all_region_labels) # Axes do not match the current region set, this means that it is # zero-sized. if not matching_regions: continue # Also skip if we've already looked at this region set for this dat. # For example if one tree branch only has owned/ghost whereas the # other has owned/ghost and unconstrained/constrained then we only want # to visit once. if matching_regions in visited_regions_per_offset_dat[offset_dat]: continue visited_regions_per_offset_dat[offset_dat].add(matching_regions) # Set 'allow_missing' to true because not all axes will reference the # fullest set of regions regioned_axes = offset_axes.with_region_labels(regions, allow_missing=True) assert not regioned_axes._all_region_labels # confusing! # Add the global offset to the values in this region if starts[i] != 0: # don't bother adding 0 to things loop_(ix := regioned_axes.iter(), offset_dat[ix].iassign(starts[i]), eager=True) # Figure out how large the looped-over part of the tree is (including subaxes) # as this will inform the stride size. step_size = axis_tree.linearize(offset_axes.leaf_path, partial=True).with_region_labels(regions, allow_missing=True).size or 1 # We have to make sure that step_size is a unique buffer, as it can # crop up in the layout expressions of offset_dat, causing chaos. if isinstance(step_size, pyop3.expr.ScalarBufferExpression): new_buffer = step_size.buffer_view.buffer.copy() new_buffer_view = step_size.buffer_view.record_new(buffer=new_buffer) step_size = step_size.record_new(buffer_view=new_buffer_view) # Add to the starting offset for all arrays apart from the current one for j, _ in enumerate(starts): if i != j: starts[j] = starts[j] + step_size # Construct the star forest for the axis tree if to_tabulate: # sf stuff offset_sfs = [] for _, offset_dat, sizes, offset_pt_sf in to_tabulate: # offset_dat maps pts in the offset_dat to offsets (obviously) # and offset_sf maps local pts in the offset dat to remote ones # we can use this to build a new sf mapping between offsets section = create_section_with_arrays( offset_pt_sf.comm, sizes, offset_dat.data_ro.ravel(), ) new_sf = pyop3.sf.create_petsc_section_sf(offset_pt_sf.sf, section) offset_sfs.append(pyop3.sf.StarForest(new_sf, axis_tree.comm)) sf = pyop3.sf.StarForest.merge(offset_sfs) else: sf = pyop3.sf.NullStarForest(axis_tree.local_size) # Lastly 'freeze' the offset dats so they can no longer be modified for _, offset_dat, _, _ in to_tabulate: offset_dat.buffer.freeze() return layouts, sf def _prepare_layouts(axis_tree: AxisTree, path_acc, layout_expr_acc, to_tabulate, tabulated, parent_axes) -> idict: """Traverse the axis tree and compute the layout functions. Any layout functions related to regions and thus requiring global tabulation are marked as such during the traversal. Parameters ---------- layout_expr_acc : The accumulated layout function from the traversal of the parent axes. Each layout function is always the sum of the per-axis layout with this. """ from pyop3.expr.visitors import get_shape layouts = {} axis = axis_tree.node_map[path_acc] # Counter that tracks the offset between axis components. start = 0 for component in axis.components: path_acc_ = path_acc | {axis.label: component.label} subtree = axis_tree.subtree(path_acc_) if not subtree.is_empty: # NOTE: THis is really confusing, _all_region_labels will drop nones subtree_has_non_trivial_regions = len(subtree._all_region_labels) > 0 else: subtree_has_non_trivial_regions = False # NOTE: we need to keep region information here so we can loop over it in _tabulate_regions linear_axis = axis.linearize(component.label) parent_axes_ = parent_axes + (linear_axis,) # The subtree contains regions so we cannot have a layout function here. if subtree_has_non_trivial_regions: assert layout_expr_acc == 0 layout_expr_acc_ = 0 layouts[path_acc_] = NaN() # At the bottom region - now can compute layouts involving all regions elif component.has_non_trivial_regions and not subtree_has_non_trivial_regions: offset_axes = AxisTree.from_iterable(parent_axes_) if subtree: offset_dat, steps = _tabulate_regions(offset_axes, subtree.size, axis_tree.comm) else: offset_dat, steps = _tabulate_regions(offset_axes, 1, axis_tree.comm) # At this point we have a star forest that relates entries in a # specific component to corresponding entries on other ranks. Since # we are now moving to an offset-focused view of the world we need # to transform this star forest to map between entries in 'offset_dat'. # This is achieved simply by composing the component star forest with # a section describing the number of unknowns for each component entry. # The only complication is that the component carrying a star forest # can be at any point in the tree, not necessarily at the root or leaf. # Identify which axis (component) in the axes that we have seen is # the one with a star forest component_sf = None component_sf_path = {} for offset_axis in offset_axes.axes: if offset_axis.component.sf is not None: component_sf = offset_axis.component.sf break component_sf_path |= {offset_axis.label: offset_axis.component.label} if component_sf is not None: # Now get the section and build the new star forest. By default the # section will drop values for all but the first region but here we # don't want this to happen component_sf_sec = offset_axes.regionless().section(component_sf_path) offset_sf = component_sf.with_section(component_sf_sec) else: offset_sf = pyop3.sf.local_sf(offset_axes.local_size, offset_axes.comm) to_tabulate.append((offset_axes, offset_dat, steps, offset_sf)) assert layout_expr_acc == 0 layout_expr_acc_ = offset_dat.concretize(linear=True) layouts[path_acc_] = layout_expr_acc_ # At leaves the layout function is trivial elif subtree.is_empty: layout_expr_acc_ = layout_expr_acc + AxisVar(linear_axis) + start layouts[path_acc_] = layout_expr_acc_ # Tabulate else: step_expr = _accumulate_step_sizes(subtree.size, linear_axis, axis_tree.comm) # if linear_axis not in utils.just_one(get_shape(step_expr)).nodes: if linear_axis.label not in {n.label for n in utils.just_one(get_shape(step_expr)).nodes}: step_expr = AxisVar(linear_axis) * step_expr layout_expr_acc_ = layout_expr_acc + step_expr + start layouts[path_acc_] = layout_expr_acc_ start += compute_axis_tree_component_size(axis_tree, path_acc, component.label) if axis_tree.node_map[path_acc_]: sublayouts = _prepare_layouts(axis_tree, path_acc_, layout_expr_acc_, to_tabulate, tabulated, parent_axes_) layouts |= sublayouts return idict(layouts) @memory_cache(heavy=True) def _accumulate_step_sizes(size_expr: LinearDatBufferExpression, linear_axis: Axis, comm): import pyop3.visitors from pyop3.expr.visitors import get_shape # If the current axis does not form part of the step expression then the # layout function is actually just 'size_expr * AxisVar(axis)'. if linear_axis.label not in {n.label for n in utils.just_one(get_shape(size_expr)).nodes}: return size_expr # linear_axis has to be isomorphic to the expression but it needn't match exactly linear_axis = utils.just_one({n for n in utils.just_one(get_shape(size_expr)).nodes if n.label == linear_axis.label}) # We do an accumulate (exscan) over a single axis. This means that things # always start from zero and so we can add the result to the accumulated # layout functions. # do the moral equivalent of # # for i # for j # (the current axis) # offset[i, j] = offset[i, j-1] + size[i, j] # by definition the current axis is in size_expr but other axes may be needed from 'linear_axis' offset_axes_subtree = merge_axis_trees((utils.just_one(get_shape(size_expr)), full_shape(linear_axis.as_tree())[0])) size_expr_loop_tree, size_expr_loop_var_replace_map = get_loop_tree(size_expr) offset_axes = size_expr_loop_tree.add_subtree(size_expr_loop_tree.leaf_path, offset_axes_subtree) # remove current axis as we need to scan over it loc = utils.just_one(path for path, axis_ in offset_axes.node_map.items() if axis_ == linear_axis) outer_loop_tree = offset_axes.drop_node(loc) assert linear_axis not in outer_loop_tree.nodes offset_dat = Dat.zeros(offset_axes.regionless(), dtype=IntType) size_expr_alt0 = pyop3.visitors.replace(size_expr, size_expr_loop_var_replace_map) if not outer_loop_tree.is_empty: ix = outer_loop_tree.iter() axis_to_loop_var_replace_map = { AxisVar(ax): LoopIndexVar(ix, ax) for ax in ix.iterset.nodes } size_expr_alt = pyop3.visitors.replace(size_expr_alt0, axis_to_loop_var_replace_map) assignee = offset_dat[ix].concretize() scan_axis = replace_exprs(linear_axis, axis_to_loop_var_replace_map) loop_( ix, exscan(assignee, size_expr_alt, "+", scan_axis, assignee.comm), eager=True ) else: exscan(offset_dat.concretize(linear=True), size_expr, "+", linear_axis, offset_dat.comm, eager=True) offset_expr = offset_dat.concretize(linear=True) # more subst needed - replace the axes with loop indices... if not size_expr_loop_var_replace_map: return offset_expr else: invmap = utils.invert_mapping(size_expr_loop_var_replace_map) return pyop3.visitors.replace(offset_expr, invmap) # This gets the sizes right for a particular dat, then we merge them above # NOTE: I can't cache this because the result is mutated # @memory_cache(heavy=True) def _tabulate_regions(offset_axes, step, comm): # Regions are always tabulated using all available free indices (i.e. all # parent axes) because they get interleaved. # TODO: explain this algorithm using # # {A: [{x: 2}, {y: 1}]} # └──➤ {B: [{u: 2}, {v: 1}]} # # [ 00, 01, 10, 11 || 02, 12 || 20, 21 || 22 ] # "xu" "xv" "yu" "yv" # from test_nested_mismatching_regions. Focus on how this is special because # we have the requisite region information in this case. # Construct the permutation from the natural ordering to the actual one. # Using the case above as an example this means generating the array # # [0, 1, 3, 4, 2, 5, 6, 7, 8] # # This is done by looping over each region set in turn and writing the # offsets into a contiguous array. In this case this means writing # [0, 1, 3, 4] for region set 'xu', then [2, 5] for 'xv' into the next # available entries and so on. locs = np.full(offset_axes.local_size, -1, dtype=IntType) ptr = 0 for regions in offset_axes.region_sets: regioned_offset_axes = offset_axes.with_region_labels(regions).regionless() if not regioned_offset_axes.is_linear: raise NotImplementedError("Doesn't strictly have to be linear here") region_offset_dat = Dat.empty(regioned_offset_axes.materialize(), dtype=IntType) offset_expr = utils.just_one(regioned_offset_axes.leaf_subst_layouts.values()) region_offset_dat.assign(offset_expr, eager=True, eager_strategy="compile") region_size = regioned_offset_axes.local_size locs[ptr:ptr+region_size] = region_offset_dat.data_ro.ravel() ptr += region_size # We now have the necessary permutation but to compute offsets we actually # need to know the size of each entry. This is done by evaluating the 'step' # expression. # Note that unlike for the ragged case the offset computations here include # all of the available axes (there is no axis-wise 'exscan' here). This is # because the axes above this have not yet been tabulated so accumulation # is not a concern. step_dat = Dat.zeros(offset_axes.regionless(), dtype=IntType) step_dat.assign(step, eager=True, eager_strategy="compile") # But the steps here are in the wrong order since they do not account for # the region interleaving. We therefore need to: # # 1. Reorder the steps into 'region' order reordered_steps = step_dat.data_ro.ravel()[locs] # 2. Accumulate these steps to give us offsets reordered_offsets = utils.steps(reordered_steps) # 3. Undo the reordering offsets = reordered_offsets[utils.invert(locs)] return Dat(step_dat.axes, data=offsets), step_dat.data_ro.ravel()