This week, I’ve focused on finishing the PR to add co-iteration of non-ordered levels as long as they are part of a conjunction with ordered levels. That involves some checking of the packed parameter `levels` and the function `f`.

For instance: F(a, b, c) = a & (b | c), that is F is a function that takes in boolean values representing a, b, c and then does some boolean expression on them. During initialization of the Coiterate, we would be able to know what levels are ordered during compile-time since these are properties of the levels. So say a and b are ordered, then we would just need to test "F(a, b, c)", which we would run the function F(false, false, true), which evaluates to false.

Say c is unordered, then check F(false, false, true) so we would check F(false, false, false), so for all combinations of unordered levels, check True/False for those.

For storing what levels are formatted: have a constexpr function with tuple of levels input that spits out a tuple of true/false indicating ordered/unordered elements in levels.

For dereferencing: Have to modify the algorithm to only return the PKs for the ordered ones and then locate into all unordered levels.

Along the way, I also started adding Doxygen style C++ docstrings to the relevant LOC I’m altering. To build locally, I needed to:

1. Install bison and link it:
   brew install bison
   brew upgrade bison
   brew link bison –force
    

2. Install doxygen following the instructions here: https://www.doxygen.nl/download.html
    

3. Build documentation site locally:
   cmake -S documentation -B build/doc
   cmake --build build/doc --target GenerateDocs
   # view the docs

open build/doc/doxygen/html/index.html

This allows me to check the validity of my docstrings locally, rather than pushing to the PR branch and letting CI take awhile to do so.

Another PR that arose was adding the ability for instances of level formats to access their level properties and querying whether or not the level is ordered, compact, unique, branchless and full. https://github.com/hameerabbasi/xsparse/pull/22 This is close to being merged and is waiting on review.

Summary and Notes:

The first week, I took some notes on the end-goal of the XSparse package. At a higher level, XSparse will eventually integrate with a Python API in a lazy fashion. Similar to dask, we can envision an API such as:

# this is just some tensor operation defined in memory, but X holds the function signature, rather than the values of X

X = A + B @ Y / C - D @ E

Where each element in the above equation corresponds to a tensor that is properly shaped. We see that this is a composition of tensor operations and may be stored in a variety of different formats, so we only “evaluate” the expression when a user called “compute(X)”.

# this would actually compute the values of X and store in memory

X = sparse.compute(X)

This would be enabled by a runtime compilation e.g. using cppyy, which is a runtime package that automatically generates Python bindings from C++. Thus, we need efficient compiler-time C++ code that will generate efficient code for operating on any combinations of levels and tensor operations. Thus, the focus of this project is to implement such abstractions.

The core part of this project is the idea of the merge lattice, which is essentially coiterating over multiple level formats. Merge lattices is a higher-level construct that begins placing meaning to the levels that are co-iterated. For example, given a tuple of tensors that are joined by different operators (e.g. +, *, /, -), we will have a single tensor output usually. Each input dimension of each tensor will get mapped to an output dimension that we care about. 

For example, say we have the following operation written in Einstein notation: 

output_ij = input1_ik input2_kj

=> figure out what loops to write in tensor notation

= take Einstein summation as input

-> generate code base off of that

Work:

I’ve continued work on my PR https://github.com/hameerabbasi/xsparse/pull/19, where I want to add co-iteration ability for levels with unordered format combined with ordered formats in a conjunctive merge (AND operation; analogous to tensor multiplication). The idea is that 0’s will not contribute to the result, so we only need to iterate over the ordered formats, and locate into the unordered formats. Once the iteration over the ordered formats is complete, then we are good because even if there are non-zeros left in the unordered formats, they are irrelevant.

Clarifying Questions to Ask Mentors:

1. If we only get unordered formats, is this supported? I would say… no?

2. If we get an arbitrary combination of ordered and unordered formats, that is fine as long as the unordered formats all have “locate” function right?

Work to do:

1. Continue reviewing the phd thesis of Fredrik Berg Kjølstad http://tensor-compiler.org/files/kjolstad-phd-thesis-taco-compiler.pdf

2. Sketch out ideas for how to add co-iteration with a subset of level formats being of the form “locate”

   1. The current co-iteration codebase co-iterates over all passed in levels, which is a special case of what we want.

   2. We need to store the indices of the levels that are ordered.

   3. We then want to co-iterate over the ordered level formats and at each (index, pointer), we want to locate into the unordered formats:

      1. If any of the unordered formats returns NULLOPT (i.e. a value of 0), then note the result will not contain anything at this index. But continue iterating

      2. Once all ordered formats reach the end, then we have reached the end of the co-iteration.