3.5.5. Partitioned Folds

Partitioned fold

Operators

Output family length

\(d = \pfold{f}{\textit{init}}{\textit{part}}\ c\)

\(f: D \times C \rightarrow D\)

\(|d| \le |c|\)

\(\textit{init}: \opt{\iset{d}} \rightarrow D\)

\(\textit{part}: \{\iset{c}\} \rightarrow \mathbb{P}(\iset{c})\)

As mentioned in Section 2.5, a fold can be defined as a transformation of a family of data to a single value:

\[d = \fold{f}{\textit{init}}\ \ifamily{c}{c}\]

where the user-defined operation \(f\) is applied repeatedly between an accumulated value (initialized by \(init\)) and each element of the input family.

In a framework context, however, multiple fold results are often desired in the same program for the same kind of computation. Consider the workflow in Fig. 3.1, which processes Spills, identified by the index \(j\) or, more specifically, the tuple \((S\ j)\). Each Spill is unfolded into a family of APAs, which are identified by the pair of indices \(jk\) or, more specifically, the tuple \((S\ j, A\ k)\). The energies of the \(\textit{GoodHits}\) data products in Fig. 3.1 are summed across APAs per Spill using the \(\textit{fold(sum\_energy)}\) node.

Instead of creating one fold result, we thus use a partitioned fold to create one summed energy data-product per Spill:

\begin{align*} [E_{(S\ 1)}&,\ \dots,\ E_{(S\ n)}] \\ &= \pfold{\textit{sum\_energy}}{\textit{init}}{\textit{into\_spills}}\ [hs_{(S\ 1,\ A\ 1)},\ hs_{(S\ 1,\ A\ 2)},\ \dots,\ hs_{(S\ n,\ A\ 1)},\ hs_{(S\ n,\ A\ 2)},\ \dots] \end{align*}

where \(E_{(S\ j)}\) denotes the \(\textit{TotalHitEnergy}\) data product for Spill \(j\), and \(hs_{(S\ j,\ A\ k)}\) is the \(\textit{GoodHits}\) data product for APA \(k\) in Spill \(j\).

The above equation can be expressed more succinctly as:

\[[E_j]_{j \in \iset{\text{out}}} = \pfold{\textit{sum\_energy}}{\textit{init}}{\textit{into\_runs}}\ [hs_i]_{i \in \iset{\text{in}}}\]

where

\begin{align*} \iset{\text{in}} &= \{(S\ 1,\ A\ 1),\ (S\ 1,\ A\ 2),\ \dots,\ (S\ n,\ A\ 1),\ (S\ n,\ A\ 2), \dots\}, \text{and}\\ \iset{\text{out}} &= \{(S\ 1),\ \dots, (S\ n)\}\ . \end{align*}

3.5.5.1. Partitions

Factorizing a set of data into non-overlapping subsets that collectively span the entire set is called creating a set partition [Wiki-Partition]. Each subset of the partition is called a cell [1]. In the above example, the role of the \(\textit{into\_spills}\) operation is to partition the input family into Spills so that there is one fold result per Spill. In general, however, the partitioning function is of the form \(\textit{part}: \{\iset{c}\} \rightarrow \mathbb{P}(\iset{c})\), where:

  • the domain is the singleton set that contains only the index set \(\iset{c}\) (i.e. \(\textit{part}\) can only be invoked on \(\iset{c}\)), and

  • the codomain is the set of partitions of \(\iset{c}\) or \(\mathbb{P}(\iset{c})\); note that the output index set \(\iset{d} \in \mathbb{P}(\iset{c})\).

The function \(\textit{part}\) also establishes an equivalence relationship on the index set \(\iset{c}\), where each element of the index set is mapped to a cell of the partition. The number of elements in the output family \(d\) corresponds to the number of partition cells.

As of this writing, the only partitions supported are those that correspond to the names of data layers. The partition \(\textit{into\_spills}\) can thus be represented by the string "Spill", which denotes that there is one partition spell per Spill.

3.5.5.2. Initializing the Accumulator

A crucial ingredient of the fold is the accumulator, which stores the fold result while it is being formed. Each accumulator is initialized by invoking a user-defined operation \(\textit{init}: \opt{\iset{d}} \rightarrow D\), which returns an object that has the same type \(D\) as the fold result [2]. The \(\opt{\iset{d}}\) domain means that:

  1. \(\textit{init}\) can receive an argument corresponding to the identifier of a cell, which is a member of the output index set \(\iset{d}\). In the example above, the relevant identifier would be that of the Spill–i.e. \((S\ j)\).

  2. \(\textit{init}\) can be invoked with no arguments, thus producing the same value each time the accumulator is initialized. This is equivalent to initializing the accumulator with a constant value.

The implementation of \(\textit{init}\) for the total good-hits energy fold results is to return the constant \(0\).

3.5.5.3. Fold Operation

A cell’s fold result is obtained by repeatedly applying a fold operation to the cell’s accumulator and each element of that cell’s input family. The fold operation has the signature \(f: D \times C \rightarrow D\), where \(D\) represents the type of the accumulator/fold result, and \(C\) is the type of each element of the input family.

In the above example, the function \(\textit{sum\_energy}\) receives a floating-point number \(E_{(S\ i)}\), representing the accumulated good-hits energy for Spill \(j\) and “combines” it with the good-hits object \(hs_{(S\ j,\ A\ k)}\) that belongs to APA \(k\) in spill \(j\). This combination involves calculating the energy represented by the \(\textit{GoodHits}\) data product \(hs_{(S\ j,\ A\ k)}\) and adding that to the accumulated value. This “combined” value is then returned by \(\textit{sum\_energy}\) as the updated value of the accumulator [3]. The function \(\textit{sum\_energy}\) is repeatedly invoked to update the accumulator with the \(\textit{GoodHits}\) data product. Once all \(\textit{GoodHits}\) data products in Spill \(j\) have been processed by \(\textit{sum\_energy}\), the accumulator’s value becomes the fold result for that Spill.

3.5.5.4. Operator Signatures

Operator

Allowed signature

\(f\)

void function_name(result_type&, P1, Pn..., Rm...) [quals];

\(\textit{init}\)

as constant:

result_type{...}

as function:

result_type function_name() [quals];

as function:

result_type function_name( <cell identifier> ) [quals];

\(\textit{part}\)

Name of data layer for output data product

The fold’s result_type must model the created data-product type described in Section 3.3.2. A fold algorithm may also create multiple data products by using a result_type of std::tuple<T1, ..., Tn> where each of the types T1, ..., Tn models a created data-product type.

3.5.5.5. Registration Interface

The \(\textit{fold(sum\_energies)}\) node in Fig. 3.1 would be represented in C++ as:

void sum_energy(double& total_hit_energy, hits const& hs) { ... }

PHLEX_REGISTER_ALGORITHMS(config)
{
  products("TotalHitEnergy") =
    fold(
      "sum_hit_energy",       // <= Node name for framework
      sum_energy,             // <= Fold operation
      0.,                     // <= Initializer for each fold result
      "Spill",                // <= Partition level (one fold result per Spill)
      concurrency::unlimited  // <= Allowed concurrency
    )
    .family("GoodHits"_in("APA"));
}

In order for the user-defined algorithm sum_energy algorithm to be safely executed concurrently, protections must be in place to avoid data races when updating the total_hit_energy result object from multiple threads. Possible solutions include using std::atomic_ref<double> [4], placing a lock around the operation that updates total_hit_energy (less desirable due to inefficiencies), or perhaps using std::atomic<double> [5] instead of double to represent the data product.

Footnotes

References