Optimizing Evaluation Cost

A symbolic tensor expression as built up from Products and Sums says what to compute, but not how: a flat sequant::Product of several tensors leaves the pairwise contraction order unspecified, and a sequant::Sum of many terms leaves their evaluation order unspecified too. Both choices can change the number of floating-point operations (and the size of intermediates) by orders of magnitude for the large tensor contractions typical of coupled-cluster and other many-body methods. sequant::optimize() chooses good orderings for both, turning a symbolic expression into one that is also efficient to evaluate or translate into code (see Code Generation).

Each sequant::Product is optimized on its own. The search does not consider the peak memory of evaluating several expressions together (e.g. all residual equations of a coupled-cluster method), nor the savings from an intermediate that several of them could share.

What it does

Given an expression (or a ResultExpr), sequant::optimize():

  • picks a pairwise contraction order for every sequant::Product, minimizing a cost metric (the total floating-point operation count, by default) using each index’s basis extent (sequant::IndexBasis::extent()), and

  • reorders the summands of every sequant::Sum so that summands sharing common intermediates end up next to each other, which helps downstream common-subexpression elimination recognize them.

// registers the occupied ("i") / virtual ("a") spaces with concrete
// extents, which optimize() needs to estimate contraction cost
mbpt::load(mbpt::Convention::SR);

// a chain of 3 tensors written as one flat Product; SeQuant does not
// commit to a pairwise evaluation order until one is asked for
auto expr = ex<Tensor>(L"A", bra{L"a_1"}, ket{L"i_1"}) *
            ex<Tensor>(L"B", bra{L"i_1"}, ket{L"i_2"}) *
            ex<Tensor>(L"C", bra{L"i_2"}, ket{L"a_2"});

// optimize() picks a pairwise contraction order (and, for a Sum, reorders
// summands to share intermediates) that minimizes a cost metric -- by
// default the total floating-point operation count, using
// IndexBasis::extent() for index extents
auto optimized = optimize(expr);

std::wcout << optimized << std::endl;

Here, contracting A with B first (rather than B with C) is cheaper given the relative sizes of the occupied and virtual spaces involved, so sequant::optimize() groups them into an explicit sub-product before multiplying by C — visible above as the extra parenthesization in the optimized expression’s structure.

Tuning

sequant::optimize() takes an OptimizeOptions struct exposing further, more advanced controls. Its full field list is API-reference material (see sequant::OptimizeOptions), but a few matter for everyday use:

  • objective_function selects the cost metric. The default, DenseFLOPs, minimizes the floating-point operation count, the metric used throughout the literature on contraction ordering. DenseTimeSpace, the objective intended for production, minimizes a performance cost first — the operation count, or a roofline estimate that also charges data movement (see roofline below) — and the peak size of all simultaneously live tensors second, so among equally fast schedules it picks the one with the lowest peak memory. Its batched variant, DenseTimeSpaceBatched, additionally slices a large mode into blocks to bound peak memory under a budget — substantial enough to have its own page: see Batched (Memory-Bounded) Evaluation.

  • volatile_weight makes operations that must be rebuilt every iteration (those depending on a leaf marked by BatchPolicy::is_volatile_leaf) count more than ones whose results can be cached.

  • The optional roofline parameters make the performance cost account for data movement as well as arithmetic; see Roofline performance cost.

  • Common-subexpression elimination during the contraction search (CSEOptions::subnet) is supported only by DenseFLOPs; leave it disabled for DenseTimeSpace and DenseTimeSpaceBatched. Enabling it with either trips an assertion, and where assertions are compiled out (SEQUANT_ASSERT_BEHAVIOR=IGNORE) CSE is silently skipped.