July 17 - Jul 23, 2023: Week 8

Published: 07/22/2023

`Tensor` would be a tuple of levels and the last level will point into the data vector

  • “one Tensor” per tensor involved in the tensor operation. E.g. A+ B= C has A, B and C as a `Tensor`.

  • TODO: add some validations and stuff, but initially we can have it as just a lightweight template class to hold a “bunch of levels”.


Coiterate questions:

  1. My recursion to check the template is not working properly.


Tensor Questions:

  1. What operations should a tensor have?

    1. Should it have insert value at indices?

    2. No, because it should be defined during compile-time.

  2. What checks should it do during construction?

  3. How is the template datatype used?


MergeLattice Questions:

  1. What operations should a mergeLattice do?

    1. How does a mergeLattice work in the context of say (A_ij + B_ij) @ D_i = C_i?

      1. In this case, F := (A || B) && D would be our “function passed”

        1. When iterating over i, F(A_i, B_i, D_i) gets the booleans based on if values are present

        2. When iterating over j for a fixed i, F(A_ij, B_ij, true) gets the booleans based on if values in A_ij, B_ij are present

        3. “j” is advanced if “i”

      2. Vector of indices for A,B,D, C is (0, 1), (0, 1), (0), (0, 1)

      3. Order of iteration = i, then j

      4. E.g. merger = MergeLattice(pair((A, (0, 1)), (B, (0,1)), (D, (0)))

      5. Since D_ij is not present, we would skip “j” in A and B when iterating

      6. merger.merge_iterators()

    2. E.g. of something not possible with the constraint on increasing indices in vectors: D_ij + A_ji 


`MergeLattice` would take in a tuple of these input Tensors:

  • E.g. The input Tensors would be (A, B)

  • Tuple of vector of integers of the same length as the tuple of input tensors.

    • Can check this during compile-time.

  • For each tuple element, i.e. Tensor in `input_tensors`, and vector[int] in `input_indices`, we would check the number of levels associated with that `Tensor` and the size of the vector. They should match.

    • We need a tuple of tuple of integers at compile time, rather than a tuple of vectors.

      • Or constexpr std::vector

      • This can be compile-time check ideally if so.

  • For each input indices, they should be strictly increasing (for now)

    • We can relax this restriction once workspaces are implemented

  • We also want the function F

  • Note: the coiterator already knows the current start/end when we pass in valid Ik/Pk from the previous levels. I.e. it infers the start/end iterators for the current level.


template <class F, typename… Levels>

class MergeLattice(std::tuple[Levels]& input_levels, int output_dims, std::tuple[std::vector[int]] input_indices)


// constexpr check that no input_indices are greater than output_dims

// constexpr check that input_indices lists each has same length as each vector of input levels

// second check: each std::vector[int] should be the size of the input level dimension

// Notes: see above





inline constexpr auto get_merge_points() const noexcept


// return a vector of mergepoints



inline constexpr auto merge_iterators() const noexcept


// k-way/two-way merge algorithm(?) that is, we merge an iterator into 1

// uses a coiterator over a subset of the iterators that can be co-iterated over

// then iterates over them and assigns them into a new level/iterator(?) e.g. dense?




If that level exists in upper level, then we would go below and recurse and fix the upper level to true. 


If we are doing an outersum. For example:


A_i + B_j = C_ij


Function `F` would be `A || B`.


For A, we would put in `true` for the function whenever A value exists and then loop over B, and when A value doesn’t exist, then put in `false` for the function and loop over B as well.

If `F` was `A && B`, then this would not loop over B. It would be like giving an empty A level fixing A values always to missing for all values of B.


Iterate over each level, find out if it has a value in the upper level. If there is no upper-level, then just check if there's a value now in this level corresponding to `true` as the initial value per input.


Coiterate over everything that exists for that dimension and then for other values put in the false/true that we get.