June 18 - Jun 25, 2023: Week 4

This week, I’ve been continuing the PR https://github.com/hameerabbasi/xsparse/pull/25. I am currently running into a segfault when running the unit-tests of coiterating over a (dense, hashed) levels because the hashed level seems like it is trying to access a previous element after already iterating through it. This is an issue because `min_ik` is getting set to a previous index since hashed level iterates out of order.

 

My suspicion is that the `min_ik` design needs to be changed to account for co-iterating over unordered levels. I will discuss this with my mentors.

 

Since I wasn’t able to discuss merge lattices with my mentors last week, here are the same notes for this week’s discussion:

 

The MergeLattice at a high level should take in a tuple of levels that are “merge points” on the merge lattice. In addition, it should take in a index expression that dictates how the levels are merged.The index expression in taco uses a set of strings like `expr = C(i, j) = A(i,j) + B(i,j);`, whereas we would want to define an arbitrarily complex index expression… I still have to do some more reading to get an idea of how this part is implemented.

 

Internally, the MergeLattice given the index expression will be able to determine which levels are co-iterated. Moreover, it must construct the `F` function that is passed to `Coiterate`. 

 

Overall, we would like the following higher-level function as well:

1. Construct a union (disjunction) over lattice points

2. Construct an intersection (conjunction) over lattice points

 

A merge lattice is constructed per index iterator in a tensor operation. For example, say we have:

Aij = (Bij + Cij) @ Dij

 

To set index i for A, we have to iterate over B_i, C_i and D_i.

To set index j for A, we have to iterate over B_*j, C_*j, and D_*j.

 

Each index constitutes a merge lattice that we need to construct to then call Coiteration. We want to extract the operators “+” and “*” to determine addition and multiplication, where addition is converted to a disjunction and multiplication is converted to a disjunction.
 

In the following example:

 

A_i = b_i + c_i d_i 

 

Has a conjunction and disjunction. We proceed by:

 

1. Create leaf of the merge lattice from the tensor access rule(?

2. Create merge lattice for c_i d_i by computing conjunctive merge (ciΛ di) a_i = this if this lattice point is reached

3. Create merge lattice for b_i since there is no other conjunctive merge with it.

4. Create upper-most merge latticepoint for disjunctive merge (bi) v (ciΛ di)

   1. So the merge lattice points starts with a whole expression that is a disjunction among conjunctions

   2. Then it traverses through each lattice point, which trims down parts that are not necessary for co-iteration 

 

Questions:

1. What is the general input for a merge lattice? What is calling it? Will we have to implement, for example, an iteration graph?

2. Do we implement the “LatticePoint”? 

3. How do we expect the “tensor operations” to be represented?