July 10 - Jul 16, 2023: Week 7

This week, I continued work on implementing the compile-time check for valid co-iteration.

 

The algorithm proceeds by calling two functions during instantiation of the Coiterate class.

1. Are all levels ordered, or has the locate function?

   1. If this does not return true, then error out

2. Next, check a more complicated compile-time check:

   1. Where we use template recursion up to a depth of 1024 to check all possible combinations of unordered levels with “true/false” input to `m_comparisonHelper`

      1. We are template recursing over levels. E.g. for each unordered level, we can run 2 static_asserts m_comparisonHelper(..., true,...) and m_comparisonHelper(..., false, …)

      2. If the level we are checking is ordered, just static_assert false in the correct place.

      3. Note: most likely we will never really hit the 1024 depth limit in practice because the higher-level API will most likely consolidate the tensor operations with temporary workspaces in the middle.

   2. E.g.
      
      m_levelsTuple = (A, B, C, D)
      
      And
      
      A, and D are unordered with locate() function defined and B and C are ordered.
      
      We want to check that the output is always false:

      1. m_comparisonHelper(false, false, false, false)

      2. m_comparisonHelper(true, false, false, true)

      3. m_comparisonHelper(false, false, false, true)

      4. m_comparisonHelper(true, false, false, false)

 

I have C++ code that defines a class called Coiterate. Coiterate gets as input a tuple of levels, represented by `m_levelsTuple`. The goal is to perform a compile-time check that goes through all levels in `m_levelsTuple`. Each level must be ordered, or have the `locate` function defined.

To determine if a level is ordered, we can check each level’s `LevelProperties::is_ordered` namespace property. For example, `A::LevelProperties::is_ordered` would determine if `A` is ordered or not. To determine if a level has the `locate` function defined, we have the following `has_locate_v` function.
 

 

Merge Lattice:

 

[Summary] Each input to the merge lattice is a stack of levels (i.e. dimensions), and we need to determine are we actually recursing into this specific input at this dimension or not, and if so, call Coiterate… If not, what do we do?

 

If a level is broadcasted, then it would not be present. Then since that “level is not there”, we may need to construct helper classes to represent what that level should be. If the level above tells you that the current level is present/not, then you put true/false and fix it in the `m_comparisonHelper`. 

 

Input indices to output indices:

1. Single uint_p index which is number of output dimensions
   E.g. 2 in this example

2. For each input’s levels, we have a list of integers corresponding to
   [0, 1] and [0, 1] (can use std::vector since it is constexpr as of C++20)
   
   The lists should be the same length as the input they correspond to. Not necessarily the size of the output dimensions (e.g. 2 in this case).

 

A_ij + B_ij = C_ij

Another example:

A_i + B_j = C_ij

1. Output dimension = 2

2. Input dimension lists: [0] and [1]

 

TODO:

1. Start thinking about writing unit-tests first regarding merge lattices (keep in mind the code should be compile-time as much as possible)

2. Sketching out the API, possibly from taco:

   1. Comment about where we got it from and the license

   2. Change string operations to index operations

   3. Keep in mind the above input -> output index operations

3. Keep reviewing the first taco paper and Kjolstad’s thesis