Source code for pyop3.visitors.compress_indirections

from __future__ import annotations

import collections
import contextlib
import functools
import itertools
import numbers
from typing import Any

from immutabledict import immutabledict as idict
from petsc4py import PETSc

import pyop3.axis_tree
import pyop3.collections
import pyop3.expr
import pyop3.index_tree
import pyop3.insn
import pyop3.node
from pyop3 import utils

# TODO: account for non-affine accesses in arrays and selectively apply this
INDIRECTION_PENALTY_FACTOR = 5

MINIMUM_COST_TABULATION_THRESHOLD = 128
"""The minimum cost below which tabulation will not be considered.

Indirections with a cost below this are considered as fitting into cache and
so memory optimisations are ineffectual.

"""

MAX_COST_CONSIDERATION_FACTOR = 3
"""Maximum factor an expression cost can exceed the minimum and still be considered."""


# TODO: This isn't really a visitor like this...
[docs] @PETSc.Log.EventDecorator() def materialize_indirections(insn: pyop3.insn.Instruction, *, compress: bool = False) -> pyop3.insn.Instruction: if compress: selector = _select_candidate_indirections_compress else: selector = _select_candidate_indirections_nocompress materialize_idxs = selector(insn) # Eagerly return if there are no symbolic dats to materialise and insert if not materialize_idxs: return insn # Now materialize the right bits and return return _insert_materialized_indirections(insn, materialize_idxs)
def _select_candidate_indirections_compress(insn): # This optimisation is collective but since the array size is part of the # heuristic one can get differing optimisation choices on different ranks. We # therefore perform all the heuristics on rank 0 and broadcast the selections. return pyop3.mpi.safe_noncollective( insn.comm, lambda: _select_candidate_indirections_compress_serial(insn), root=0, ) def _select_candidate_indirections_compress_serial(insn): import pyop3 candidates = _collect_candidate_indirections(insn, compress=True) candidates = _trim_candidates(candidates) # Optimise the search tree by only considering disjoint subsets of # candidates. For example, if we have candidates # # {a: [A, B, C, D], b: [X, Y]} # # we can speed things up by only investigating 4+2 options instead # of 4*2. disjoint_subsets: list[tuple[dict, set]] = [] for terminal_id, terminal_candidates in candidates.items(): terminal_symdats = { loc for _, _, symdats in terminal_candidates for loc, _, _ in symdats } disjoint_subsets.append( ({terminal_id: terminal_candidates}, terminal_symdats) ) # Fixed point iteration to ensure subsets are fully disjoint while True: new_disjoint_subsets = [] for terminal_id, terminal_candidates in candidates.items(): terminal_symdats = { loc for _, _, symdats in terminal_candidates for loc, _, _ in symdats } for subset_candidates, subset_symdats in new_disjoint_subsets: if terminal_symdats.intersection(subset_symdats): subset_candidates[terminal_id] = terminal_candidates subset_symdats.update(terminal_symdats) break else: # not found in an existing subset, create a new one new_disjoint_subsets.append( ({terminal_id: terminal_candidates}, terminal_symdats) ) if new_disjoint_subsets == disjoint_subsets: break else: disjoint_subsets = new_disjoint_subsets # Now select the combination with the lowest combined cost. We can make savings here # by sharing indirection maps between different arguments. For example, if we have # # dat1[mapA[mapB[mapC[i]]]] # dat2[mapB[mapC[i]]] # # then we can (sometimes) minimise the data cost by having # dat1[mapA[mapBC[i]]] # dat2[mapBC[i]] # # instead of # # dat1[mapABC[i]] # dat2[mapBC[i]] materialize_idxs = pyop3.collections.OrderedSet() for candidate_subset, _ in disjoint_subsets: best_subset_symdat_locs = None min_subset_cost = None for shared_candidate in utils.expand_collection_of_iterables(candidate_subset): symdat_costs = { loc: cost for _, _, symdats in shared_candidate.values() for loc, _, cost in symdats } cost = 0 for _, cost_expr, symdats in shared_candidate.values(): cost += pyop3.expr.visitors.evaluate(cost_expr, name_vars=symdat_costs) # Subsequent expressions can reuse the array, so cost nothing for loc, _, _ in symdats: symdat_costs[loc] = 0 if best_subset_symdat_locs is None or cost < min_subset_cost: best_subset_symdat_locs = pyop3.collections.OrderedSet([ loc for _, _, symdats in shared_candidate.values() for loc, _, _ in symdats ]) min_subset_cost = cost assert best_subset_symdat_locs is not None materialize_idxs.update(best_subset_symdat_locs) return pyop3.collections.OrderedFrozenSet(materialize_idxs) def _trim_candidates(candidates): # Find the best cost if we look at each terminal independently. This # provides a useful upper bound. max_cost = 0 for terminal_id, terminal_candidates in candidates.items(): min_terminal_cost = min( (cost for cost, _, _ in terminal_candidates), default=0 ) max_cost += min_terminal_cost assert isinstance(max_cost, numbers.Integral) # Drop any immediately bad candidates (that exceed this cost). Also # skip over any terminals that don't generate any symbolic dats. trimmed_candidates = {} for terminal_id, terminal_candidates in candidates.items(): if len(terminal_candidates) == 0: continue trimmed_terminal_candidates = [] min_terminal_cost = min((cost for cost, _, _ in terminal_candidates), default=0) for cost, cost_expr, sym_dats in terminal_candidates: if cost <= max_cost and cost <= min_terminal_cost * MAX_COST_CONSIDERATION_FACTOR: trimmed_terminal_candidates.append((cost, cost_expr, sym_dats)) trimmed_candidates[terminal_id] = trimmed_terminal_candidates return trimmed_candidates def _select_candidate_indirections_nocompress(insn): candidates = _collect_candidate_indirections(insn, compress=False) symdat_locs = pyop3.collections.OrderedSet() for terminal_id, terminal_candidates in candidates.items(): if not terminal_candidates: continue _, _, terminal_symdats_info = utils.just_one(terminal_candidates) for loc, _, _ in terminal_symdats_info: symdat_locs.add(loc) return pyop3.collections.OrderedFrozenSet(symdat_locs) class _CandidateIndirectionsCollector(pyop3.node.NodeVisitor): def __init__(self): self._collecting = False super().__init__() @contextlib.contextmanager def collecting(self): """Context manager used when we are actually collecting candidate indirections. When this context is active we want flat iterables back, not mappings. """ prev = self._collecting self._collecting = True yield self._collecting = prev def get_cache_key(self, node, **kwargs): return (*super().get_cache_key(node, **kwargs), self._collecting) @functools.singledispatchmethod def process(self, obj: pyop3.obj.Object, /, *args, **kwargs) -> tuple[tuple[Any, int, int], ...]: utils.raise_missing_dispatch_handler(obj) def _null(self, obj: Any, /, **kwargs): """Handler for terminals where we don't do anything.""" if self._collecting: return ((0, 0, ((self.index, obj, 0),)),) else: return idict({}) # {{{ pyop3.expr @process.register def _(self, op: pyop3.expr.BinaryOperator, /, *, compress: bool) -> tuple: if not self._collecting: return utils.merge_dicts( self(x, compress=compress) for x in op.operands ) operand_candidatess = tuple( self(o, compress=compress) for o in op.operands ) candidates = [] for operand_candidates in itertools.product(*operand_candidatess): cost_per_operand, cost_expr_per_operand, symdats_per_operand = \ zip(*operand_candidates, strict=True) # If there is at most one non-zero operand cost then there is no point # in compressing the expression. if sum(cost > 0 for cost in cost_per_operand) <= 1: compress = False # NOTE: This isn't quite correct. For example consider the expression # 'mapA[i] + mapA[i]'. The cost is just the cost of 'mapA[i]', not double. candidate_cost = sum(cost_per_operand) candidate_cost_expr = sum(cost_expr_per_operand) candidate_symdats = sum(symdats_per_operand, ()) candidates.append((candidate_cost, candidate_cost_expr, candidate_symdats)) if compress: # Now also include a candidate representing the packing of the expression # into a Dat. The cost for this is simply the size of the resulting array. # Only do this when the cost is large as small arrays will fit in cache # and not benefit from the optimisation. if any(cost > MINIMUM_COST_TABULATION_THRESHOLD for cost, _, _ in candidates): op_axes = utils.just_one(pyop3.expr.visitors.get_shape(op)) op_loop_axes = pyop3.expr.visitors.get_loop_axes(op) op_cost = op_axes.local_size for loop_axes in op_loop_axes.values(): for loop_axis in loop_axes: op_cost *= loop_axis.component.local_size if not isinstance(op_cost, numbers.Integral): raise NotImplementedError("Ragged sizes are not supported") cost_expr = pyop3.expr.NameVar(self.index) symdat = pyop3.expr.CompositeDat(op_axes, {op_axes.leaf_path: op}) symdat_info = (self.index, symdat, op_cost) candidates.append((op_cost, cost_expr, (symdat_info,))) return tuple(candidates) @process.register def _( self, expr: pyop3.expr.LinearDatBufferExpression, /, *, compress: bool, ): if not self._collecting: with self.collecting(): return idict({self.index: self(expr.layout, compress=compress)}) # The cost of an expression dat (i.e. the memory volume) is given by... TODO # Remember that the axes here described the outer loops that exist and that # index expressions that do not access data (e.g. 2i+j) have a cost of zero. # dat[2i+j] would have a cost equal to ni*nj as those would be the outer loops # TODO: can this be nicer? I have other routines for getting shapes from expressions dat_axes = utils.just_one(pyop3.expr.visitors.get_shape(expr.layout)) dat_loop_axes = pyop3.expr.visitors.get_loop_axes(expr.layout) dat_cost = dat_axes.local_size for loop_axes in dat_loop_axes.values(): for loop_axis in loop_axes: dat_cost *= loop_axis.component.local_max_size assert isinstance(dat_cost, numbers.Integral) candidates = [] layout_candidates = self(expr.layout, compress=compress) for layout_cost, layout_cost_expr, layout_symdats in layout_candidates: # TODO: Only apply penalty for non-affine layouts that actually involve an indirection candidate_cost = dat_cost + layout_cost * INDIRECTION_PENALTY_FACTOR candidate_cost_expr = dat_cost + layout_cost_expr * INDIRECTION_PENALTY_FACTOR candidates.append((candidate_cost, candidate_cost_expr, layout_symdats)) if compress: if any(cost > MINIMUM_COST_TABULATION_THRESHOLD for cost, _, _ in candidates): # We use a symbolic expression for the overall cost because we # need to be able to replace costs with zeros if we end up sharing # materialised dats between terminals. cost_expr = pyop3.expr.NameVar(self.index) symdat = pyop3.expr.CompositeDat(dat_axes, {dat_axes.leaf_path: expr}) symdat_info = (self.index, symdat, dat_cost) candidates.append((dat_cost, cost_expr, (symdat_info,))) return tuple(candidates) @process.register def _( self, dat_expr: pyop3.expr.NonlinearDatBufferExpression, /, **kwargs, ) -> idict: assert not self._collecting return utils.merge_dicts( self(l, **kwargs) for l in dat_expr.layouts.values() ) @process.register def _(self, tern: pyop3.expr.TernaryOperator, /, **kwargs) -> idict: return utils.merge_dicts(self(x, **kwargs) for x in tern.operands) @process.register(pyop3.expr.AxisVar) @process.register(pyop3.expr.LoopIndexVar) @process.register(pyop3.expr.Scalar) @process.register(pyop3.expr.ScalarBufferExpression) @process.register(pyop3.expr.OpaqueTerminal) @process.register(pyop3.expr.NaN) def _(self, var, *args, **kwargs): return self._null(var, *args, **kwargs) @process.register def _(self, mat_expr: pyop3.expr.MatPetscMatBufferExpression, /, *, compress: bool) -> idict: candidates = {} layouts = [mat_expr.row_layout, mat_expr.column_layout] for i, layout in enumerate(layouts): assert isinstance(layout, pyop3.expr.CompositeDat) op_cost = pyop3.expr.visitors.loopified_shape(layout)[0].local_size cost_expr = pyop3.expr.NameVar((self.index, i)) symdat = layout symdat_info = ((self.index, i), symdat, op_cost) candidates[self.index, i] = ((op_cost, cost_expr, (symdat_info,)),) return idict(candidates) @process.register def _(self, mat_expr: pyop3.expr.MatArrayBufferExpression, /, *, compress: bool) -> idict: candidates = {} with self.collecting(): layoutss = [mat_expr.row_layouts, mat_expr.column_layouts] for i, layouts in enumerate(layoutss): for j, (path, layout) in enumerate(layouts.items()): candidates[self.index, i, j] = self( layout, compress=compress ) return idict(candidates) # }}} # {{{ pyop3.insn @process.register(pyop3.insn.NullInstruction) @process.register(pyop3.insn.Exscan) # assume we are fine def _(self, null: pyop3.insn.InstructionList, /, **kwargs) -> idict: return idict() @process.register def _(self, insn_list: pyop3.insn.InstructionList, /, **kwargs) -> idict: return utils.merge_dicts( (self(insn, **kwargs) for insn in insn_list), ) @process.register(pyop3.insn.Loop) def _(self, loop: pyop3.insn.Loop, /, **kwargs) -> idict: return utils.merge_dicts( ( self(stmt, **kwargs) for stmt in loop.statements ), ) @process.register def _(self, terminal: pyop3.insn.NonEmptyTerminal, /, *, compress: bool) -> idict: candidates = {} for i, arg in enumerate(terminal.arguments): per_arg_candidates = self(arg, compress=compress) candidates |= per_arg_candidates return idict(candidates) # }}} # {{{ misc @process.register def _(self, var: numbers.Number, *args, **kwargs): return self._null(var, *args, **kwargs) # }}} def _collect_candidate_indirections( obj: pyop3.obj.Object, *, compress: bool, ): collector = _get_candidate_indirections_collector() collector.index = () # reset counter collector._index_stack = collections.defaultdict(itertools.count) return collector(obj, compress=compress) # FIXME: the cache here is disabled because it was leaking memory # We heavy cache this visitor so we can reuse its cache if possible, but we have # to be careful to only work with heavy caches on COMM_SELF because the visitor # is only ever called on one rank and the result broadcast. # @pyop3.cache.memory_cache(heavy=True, get_comm=lambda: MPI.COMM_SELF) def _get_candidate_indirections_collector(): return _CandidateIndirectionsCollector() class _MaterializedIndirectionsInserter(pyop3.node.NodeVisitor): def __init__(self, comm): self.comm = comm self._linear = False super().__init__() @contextlib.contextmanager def enforce_linear(self): prev = self._linear self._linear = True yield self._linear = prev def get_cache_key(self, node, **kwargs): return (*super().get_cache_key(node, **kwargs), self._linear) @functools.singledispatchmethod def process(self, obj: pyop3.obj.Object, /, *args, **kwargs): utils.raise_missing_dispatch_handler(obj) # {{{ pyop3.expr @process.register def _(self, op: pyop3.expr.Operator, /, *, materialize_idxs) -> tuple: if self.index in materialize_idxs: assert self._linear op_axes = utils.just_one(pyop3.expr.visitors.get_shape(op)) symdat = pyop3.expr.CompositeDat(op_axes, {op_axes.leaf_path: op}) return pyop3.expr.visitors.materialize_composite_dat(symdat, self.comm, linear=True) else: new_operands = [ self(o, materialize_idxs=materialize_idxs) for o in op.operands ] return op.with_operands(new_operands) @process.register def _(self, expr: pyop3.expr.LinearDatBufferExpression, /, *, materialize_idxs): if self.index in materialize_idxs: assert self._linear dat_axes = utils.just_one(pyop3.expr.visitors.get_shape(expr.layout)) symdat = pyop3.expr.CompositeDat(dat_axes, {dat_axes.leaf_path: expr}) return pyop3.expr.visitors.materialize_composite_dat(symdat, self.comm, linear=True) else: with self.enforce_linear(): new_layout = self(expr.layout, materialize_idxs=materialize_idxs) return expr.record_new(layout=new_layout) @process.register def _(self, dat_expr: pyop3.expr.NonlinearDatBufferExpression, /, **kwargs): assert not self._linear with self.enforce_linear(): new_layouts = idict({ path: self(l, **kwargs) for path, l in dat_expr.layouts.items() }) return dat_expr.record_new(layouts=new_layouts) @process.register(pyop3.expr.AxisVar) @process.register(pyop3.expr.LoopIndexVar) @process.register(pyop3.expr.Scalar) @process.register(pyop3.expr.ScalarBufferExpression) @process.register(pyop3.expr.OpaqueTerminal) @process.register(pyop3.expr.NaN) def _(self, var, **kwargs): return var @process.register def _(self, mat_expr: pyop3.expr.MatPetscMatBufferExpression, /, *, materialize_idxs): assert (self.index, 0) in materialize_idxs assert (self.index, 1) in materialize_idxs new_row_layout = pyop3.expr.visitors.materialize_composite_dat( mat_expr.row_layout, self.comm, linear=False ) new_column_layout = pyop3.expr.visitors.materialize_composite_dat( mat_expr.column_layout, self.comm, linear=False ) return mat_expr.record_new(row_layout=new_row_layout, column_layout=new_column_layout) @process.register def _(self, mat_expr: pyop3.expr.MatArrayBufferExpression, /, **kwargs): new_layoutss = [] layoutss = [mat_expr.row_layouts, mat_expr.column_layouts] with self.enforce_linear(): for layouts in layoutss: new_layouts = { path: self(layout, **kwargs) for path, layout in layouts.items() } new_layoutss.append(idict(new_layouts)) new_row_layouts, new_column_layouts = new_layoutss return mat_expr.record_new(row_layouts=new_row_layouts, column_layouts=new_column_layouts) # }}} # {{{ pyop3.insn @process.register def _(self, insn_list: pyop3.insn.InstructionList, /, **kwargs) -> pyop3.insn.InstructionList: new_instructions = tuple( self(insn, **kwargs) for insn in insn_list ) return insn_list.record_new(instructions=new_instructions) @process.register def _(self, loop: pyop3.insn.Loop, /, **kwargs): new_statements = tuple(self(stmt, **kwargs) for stmt in loop.statements) return loop.record_new(statements=new_statements) @process.register def _(self, assignment: pyop3.insn.NonEmptyArrayAssignment, /, **kwargs): new_assignee = self(assignment.assignee, **kwargs) new_expression = self(assignment.expression, **kwargs) return assignment.record_new(_assignee=new_assignee, expression=new_expression) @process.register(pyop3.insn.StandaloneCalledFunction) @process.register(pyop3.insn.Exscan) # NOTE: not really ideal, relies on not traversing in other visitor @process.register(pyop3.insn.NullInstruction) def _(self, insn, *args, **kwargs): return insn # }}} # {{{ misc @process.register def _(self, var: numbers.Number, /, **kwargs): return var # }}} def _insert_materialized_indirections(obj: pyop3.obj.Object, materialize_idxs) -> pyop3.insn.Instruction: return _MaterializedIndirectionsInserter(obj.comm)(obj, materialize_idxs=materialize_idxs)