Articles on Adam2392's Blog

Aug 28 - Sep 3, 2023: Week 14

adam2392@gmail.com (Adam2392) — Fri, 25 Aug 2023 20:12:59 +0000

This week, I am finishing my final PR to fix the Coiteration algorithm: https://github.com/hameerabbasi/xsparse/pull/31.

This will enable coiterations over levels that are nested within other levels. As such, we can define multiple Coiterate objects that co-iterate over each dimension respectively.

With this, the ground-work will be laid to very easily implement the MergeLattice Coiterator, which is just an abstraction on top of this idea of calling multiple coiterators.

The final PR now shows a unit-test that Co-iterates over two sets of nested levels, which each together define a CSR matrix. It is done with a conjunctive merge, so the unit-test defines how the API must be specifically defined. There were a few errors that I ran into that were hard to debug, but it turns out they were consequences of how I was leveraging the Coiterate API, which is slightly unforgiving right now.

Aug 21 - Aug 27, 2023: Week 13

adam2392@gmail.com (Adam2392) — Mon, 21 Aug 2023 00:28:26 +0000

This week, I was sick so did not have a lot of time for work.

However, I did play around with the new API for the Coiterate that we needed to get working. Specifically, I realized that if we pass in a tuple of PKs and IKs into Coiterate, then we need to adapt various other parts of the API, which assumed the PK was a single element. This may present some challenges that I will aim to finish as the last sprint of my GSoC.

Aug 14 - Aug 20, 2023: Week 12

adam2392@gmail.com (Adam2392) — Mon, 14 Aug 2023 17:29:55 +0000

This week, I finished up the PR to add implementation of a Tensor. I also identified a flaw with the previous Coiteration implementation. For the remainder of the GSoC I will work on fixing that flaw.

Basically, the Coiterate iterator should take in a tuple of indices and a tuple of Pks if coiterating over a set of levels defined by a stack of levels.

Aug 7 - Aug 13, 2023: Week 11

adam2392@gmail.com (Adam2392) — Thu, 10 Aug 2023 01:37:43 +0000

This week, I finished up the PR to add static_assert to the container-traits. I also simplified the Tensor implementation PR and submitted it for review/merge.

The bulk of my work now has to do with implementing a version of the Coiterate over the Tensor classes now, instead of over single levels.

Now, merge lattice takes in a tuple of Tensors:

Constructor: we can compile-time check that the tensor shapes align? I don’t know how to do this, so probably a future PR.
Algorithm:

The algorithm must initialize a coiterator over levels for the index into the level given to the merge lattice. It will advance, dereference and compare elements until this coiterator is done. Then it will advance the coiterator above.

Ex:

Expression: (A_ij + B_ij) @ C_j = D_i

Tensors: (A, B, C)

Indices: [(0, 1), (0, 1), (1)]

How would the iterator function? Initialize iter1 = Coiterate(A_i*, B_i*, true). Initialize iter2 = Coiterate (A_*j, B_*j, C_j).

If iter2 != end:

Advance iter2;

Else:

Advance iter1;

Reset iter2; // what would this mean? Iter2 now must take in the new IK and PK from iter1 to know where to start

My intuition stems from: https://github.com/hameerabbasi/xsparse/blob/10b91002e246a16d2e14db8495faafa3774d383e/test/source/compressed_test.cpp#L63-L77

Questions:

Basically, what sort of objects do I need to handle in the iterator of MergeLattice class? Should I store a tuple of ``Coiterate`` classes for each tuple of levels from the Tensors?
Am I thinking about this correctly?

July 31 - Aug 6, 2023: Week 10

adam2392@gmail.com (Adam2392) — Sat, 29 Jul 2023 01:01:46 +0000

This week, I finished the compile-time check validity of coiteration in the PR [ENH] Check validity of coiteration. This has a few hacks, but it works and is able to raise a compiler-error when co-iteration with a disjunctive merge with an unordered level is involved.

I am starting to understand the merge lattice class more. It is simply another abstraction on iteration that now iterates over collections of tensors instead of collections of levels like co-iteration does.

As a few pre-steps towards implementing the merge lattice, I also added a PR that adds compile-time checks for valid methods to be defined for any container traits that would store indices in the sparse tensor, or the pointers to the next level (or data array): Adding required member functions of abstract container traits. This tightens up the API to allow users to define their own custom containers as long as they implement a certain API.

I also started working on the Tensor class implementation. The tensor class now connects a collection of levels to actual data and represents a sparse n-dimensional array. [ENH] Adding Tensor implementation. This probably will take up most of my next week, since I will need to understand how to implement the iterator over the tensor. This will require initializing iterators over all the levels that define the tensor and then also dereferencing to get the right indices and data.

A few questions I’ll have to figure out this week are:

How to initialize the iterators of each level?
How to design the Tensor’s iterator? Should I follow a design similar to `Coiterate` since they are both at a high-level iterating over a collection of levels?
What should dereference do? My thinking is return a tuple of indices (i.e. IKs) and then the data value, which is just the PK pointer into the data vector.

I.e. tensor* -> (1, 0, 5) 60.3 returns the value at index (1, 0, 5) in the 3D sparse array with non-zero value 60.3 there.
Does it matter if we iterate over an unordered level?

July 17 - Jul 23, 2023: Week 8

adam2392@gmail.com (Adam2392) — Sat, 22 Jul 2023 18:33:09 +0000

`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:

My recursion to check the template is not working properly.

Tensor Questions:

What operations should a tensor have?
1. Should it have insert value at indices?
2. No, because it should be defined during compile-time.
What checks should it do during construction?
How is the template datatype used?

MergeLattice Questions:

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

}

public:

{

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.

July 10 - Jul 16, 2023: Week 7

adam2392@gmail.com (Adam2392) — Wed, 12 Jul 2023 17:52:10 +0000

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.

Are all levels ordered, or has the locate function?
1. If this does not return true, then error out
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:

Single uint_p index which is number of output dimensions
E.g. 2 in this example
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:

Start thinking about writing unit-tests first regarding merge lattices (keep in mind the code should be compile-time as much as possible)
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
Keep reviewing the first taco paper and Kjolstad’s thesis

July 3 - Jul 9, 2023: Week 6

adam2392@gmail.com (Adam2392) — Thu, 06 Jul 2023 02:45:58 +0000

I discussed the following debuggers for C++:UBSan and Valgrind. And if I can get my Linux machine working, gdb. I started using LLDB on VSCode C++ and it was wonderful.

I was able to solve with the help of my mentors the compiler-time refactoring of the code. Each functionality within the coiterator now fully unwraps into a level check:

Computing the min_ik: we now ignore the unordered levels when we do this.
Advance_iter: we now ignore the unordered levels when we do this.
Compare: we now only compare the ordered levels and default to ‘true’ for unordered level comparisons.

The coiterator has the implicit assumption that only ordered levels are supported if there is a disjunctive merge. If there is a conjunctive merge, it must contain at least one ordered level and for all other unordered levels, they must have the `locate` function defined.

In order to make sure this is valid during compile-time, we want to implement a compile-time check during the instantiation of the coiterator. This was the initial goal of the PR, but since we uncovered a bunch of problems, we had to table it. Now that we have refactored the code into a more generalized state, we can revisit this compile-time check.

The way this is done is via fold expression most likely:

If:

* 1. the levels are all ordered (i.e. has the `is_ordered == True` property)

* 2. if any of the level are do not have the is_ordered property, it must have the locate

* function, else return False. Then do a check that `m_comparisonHelper` defines

* a conjunctive merge (i.e. AND operation).

* Otherwise, coiteration is not allowed.

The check with respect to `m_comparisonHelper` must be done for all unordered levels.

June 25 - Jul 2, 2023: Week 5

adam2392@gmail.com (Adam2392) — Wed, 28 Jun 2023 20:23:42 +0000

I discussed the following debuggers for C++:UBSan and Valgrind. And if I can get my Linux machine working, gdb. I started using LLDB on VSCode C++ and it was wonderful.

Refactored the `get_PKs_level` function into two functions now where the `get_PKs_level` helps pass the fold expression and the corresponding iterator to the `get_PK_level` function, which can then use the iterator to perform compile-time if/else functions, such as dereferencing, or locating into the iterator.

Furthermore, I spent this week refactoring the C++ code specifically for calculating the “min_ik”, “advancing the iterators” and “getting the PKs”, which all follow a design that is more readable, yet still compile-time evaluated.

June 18 - Jun 25, 2023: Week 4

adam2392@gmail.com (Adam2392) — Sat, 24 Jun 2023 16:21:14 +0000

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:

Construct a union (disjunction) over lattice points
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:

Create leaf of the merge lattice from the tensor access rule(?
Create merge lattice for c_i d_i by computing conjunctive merge (ciΛ di) a_i = this if this lattice point is reached
Create merge lattice for b_i since there is no other conjunctive merge with it.
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:

What is the general input for a merge lattice? What is calling it? Will we have to implement, for example, an iteration graph?
Do we implement the “LatticePoint”?
How do we expect the “tensor operations” to be represented?

June 11 - June 18: Week 3

adam2392@gmail.com (Adam2392) — Fri, 16 Jun 2023 20:14:16 +0000

This week, I’ve been digging into the details of how to best carry out co-iteration when there are levels that are not ordered. The thinking before was that co-iteration when there is a conjunctive merge was we can make the following changes:

Advancing iterators: Advance only the ordered level iterators, since the other iterators can do `locate(PKM1, min_ik)`.
Dereferencing iterators to get PKs: Since we have locate, we can directly get the PK for a unordered level with the `locate()` function.

However, in 1., this is not as straightforward. Say we have A \intersect B and A has 1000 non-zero elements and B has 1 non-zero element. If A is ordered and B is not, we have to iterate over the entirety of A, when in reality, we should be able to exit early. The dereferencing part though can definitely be implemented and should be changed.

Other improvements I have made in the code are:

Add `BaseTraits::I i` as an unused parameter in `hashed::iter_helper`

iteration_helper iter_helper([[maybe_unused]] typename BaseTraits::I i,typename BaseTraits::PKM1 pkm1)
In `Coiterate::coiteration_helper`, I changed the initialization of the `iterators` member to

std::tuple<typename levels::iteration_helper::iterator...=""> it) noexcept

From

std::tuple<typename levels::levelcapabilities::iteration_helper::iterator...=""> it) noexcept

Where we remove LevelCapabilities from the namespace. This was required since the `iteration_helper` for the hashed level is not implemented as part of the `LevelCapabilities` namespace, so this change allows `Coiterate` to be defined with some levels that include a hashed level.</typename></typename>
Rename `Coiterate::coiteration_helper::iterator.locate` to `deref_PKs`, since that is what it is actually doing.

template <class iter=""></class>

inline auto deref_PKs(iter i) const noexcept

{

return (std::get<0>(*i) == min_ik)

? std::optional<std::tuple_element_t<1, decltype="">>(</std::tuple_element_t<1,>

std::get<1>(*i))

: std::nullopt;

}

Also in the actual `get_PKs` function, we now use locate if the iterator has the locate function, otherwise we apply dereferencing.

inline auto get_PKs() const noexcept

{

/**

* @brief Return tuple of PKs from each level.

* @details If the level is ordered, return the PK from the iterator using

* dereferencing `*iter`. If the level is unordered, return the PK from

* the iterator using `iter.locate()`.

return std::apply(

[&](auto&... args)

{

return std::make_tuple((has_locate_v<decltype(args)></decltype(args)>

? args.locate(m_coiterHelper.m_pkm1, min_ik)

: deref_PKs(args))...);

this->iterators);

}

The only issue is that this produces a compiler error.

Besides these improvements, I started reviewing the MergeLattice implementation inside the existing taco compiler. The code here is implemented using run-time code. There the implementation uses a builder class to construct a MergeLattice.

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:

Construct a union (disjunction) over lattice points
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.

In the following example:

A_i = b_i + c_i d_i

Has a conjunction and disjunction. We proceed by:

Create leaf of the merge lattice from the tensor access rule(?
Create merge lattice for c_i d_i by computing conjunctive merge (ciΛ di) a_i = this if this lattice point is reached
Create merge lattice for b_i since there is no other conjunctive merge with it.
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:

What is the general input for a merge lattice? What is calling it? Will we have to implement, for example, an iteration graph?
Do we implement the “LatticePoint”?
How do we expect the “tensor operations” to be represented?

Week 2 - Hashed LevelCapabilities and Learning more Compile-time template metaprogramming

adam2392@gmail.com (Adam2392) — Thu, 08 Jun 2023 20:04:25 +0000

This week, I’ve finished the PR adding level properties as a public member to the level classes.

However, now I am encountering difficulties in adding the ability for hash levels to be coiterated on. Currently, the `Coiterate` class implements a coiteration_helper class, which in turn currently relies on initializing iteration helpers from each level.

```

std::tuple<typename Levels::LevelCapabilities::iteration_helper...> m_iterHelpers;

…

, m_iterHelpers(std::apply([&](auto&... args)

{ return std::tuple(args.iter_helper(i, pkm1)...); },

coiterate.m_levelsTuple))

```

For example, in the above code, we see that `m_iterHelpers` initalizes the `iter_helper` inside each level in `m_levelsTuple`. In addition, `m_iterHelpers` is a tuple of iteration_helpers, but hash levels do not contain this level capability. I need to implement a modification in the design, so that `m_iterHelpers` is only defined on the subset of levels that are ordered.

However, it turns out that this is not an issue that requires tackling. Instead, I realized upon inspection and meeting with my mentor Hameer that all levels should have an `iteration_helper` defined through the `LevelCapabilities` namespace inside their class. The `hashed` level contains an `iteration_helper`, but not through the `LevelCapabilities` class, so the next step I realized was to refactor the existing implementation of the `hashed::iterator`, so that it was contained within the `LevelCapabilities` namespace. This is a bit complicated because the hashed level implements a custom iterator and there is some advanced template metaprogramming going on, which I have to figure out. Currently I’m running into two sets of errors that are confusing to me:

```

/Users/adam2392/Documents/xsparse/include/xsparse/util/base_traits.hpp:34:9: error: static_assert failed due to requirement 'std::is_convertible_v<xsparse::util::container_traits<std::vector, std::set, std::unordered_map>, unsigned long>' "`PK` must be convertible to uintptr_t."

static_assert(std::is_convertible_v<PK, uintptr_t>,

^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

```

And

```

/Users/adam2392/Documents/xsparse/test/source/hashed_test.cpp:31:34: error: no member named 'iter_helper' in 'xsparse::levels::hashed<std::tuple<>, unsigned long, unsigned long, xsparse::util::container_traits<std::vector, std::set, std::unordered_map>, xsparse::level_properties<false, false, false, false, false>>'

for (auto const [i2, p2] : h.iter_helper(ZERO))

~ ^

```

Future Work - Although this simple PR on improving the co-iteration algorithm has turned into quite a rabbit hole, the main bulk of the GSoC is dedicated to implementing and testing a “merge lattice” data structure, which will leverage the complete co-iteration algorithm.

We briefly discussed merge lattices. Merge Lattices co-iterate over subset of levels that are necessary based on properties of the function. For example:

E.g. A_ij + B_ik

When iterating over i, both A and B are iterated. When iterating over j, only A is iterated. When iterating over k only B is iterated.

Review:

Taco paper: on only dense/hashed
Taco code: but note they implement this in runtime, rather than at compile time
- And we need to re-write things in compile-time

Week 1 - Coiteration and exposing level properties PR

adam2392@gmail.com (Adam2392) — Fri, 02 Jun 2023 19:44:26 +0000

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:

Install bison and link it:
brew install bison
brew upgrade bison
brew link bison –force
Install doxygen following the instructions here: https://www.doxygen.nl/download.html
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.

Community Bonding and First Week

adam2392@gmail.com (Adam2392) — Fri, 26 May 2023 14:42:46 +0000

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:

If we only get unordered formats, is this supported? I would say… no?
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:

Continue reviewing the phd thesis of Fredrik Berg Kjølstad http://tensor-compiler.org/files/kjolstad-phd-thesis-taco-compiler.pdf
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.