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