API for merge lattice implementation

[hameerabbasi]

As mentioned in yesterday's weekly meeting, here is the API for merge lattices, in psuedo-C++ syntax:

// The Operand can be a SingleLevel or another and/or
class BinaryFn {};
class And<class... Operands>: BinaryFn {};
class Or<class... Operands>: BinaryFn {};
class SingleLevel<std::size_t Index>: BinaryFn {};

// This will be a ForwardIterator
// Item_type: std::pair<IK, std::tuple<std::optional<PK_of_each_level>>>
// Need to figure out how to get PK_of_each_level. Hint: Type traits
class CoIterate<class BinFn, tuple<class... Levels>> {};

cc @bharath2438

[bharath2438]

@hameerabbasi I've understood and started working on this. I had a doubt though, is Operands referring to formats such as COO or CSR? If so, how are they combined into a class?

[hameerabbasi]

Operands refers to other BinaryFns. The "base level" is a SingleLevel, which specifies the index at which that level is present in the tuple<class... Levels> tuple.

[hameerabbasi]

So you would use it like this example for Compressed * Compressed:

CoIterate<And<SingleLevel<0>, SingleLevel<1>>, tuple<Compressed, Compressed>>

[bharath2438]

@hameerabbasi What will the base class BinaryFn contain?

[hameerabbasi]

There doesn't need to be a base class, just added it to show the interface.

You might find if constexpr useful in the implementation.

[bharath2438]

@hameerabbasi Would I be using if constexpr to check whether the template parameter is And or Or and emit different merges based on the condition in CoIterate?

[bharath2438]

@hameerabbasi Once we generate the loops, how do we actually merge into the output? Will we be using a reference to the vals of the output? Or do we just assemble and return a Level?

[hameerabbasi]

We need a ForwardIterator, as discussed.

[bharath2438]

We need a ForwardIterator, as discussed.

Okay, just like the iter_helper for regular iterators returns (IK, PK), this forward_iterator must return (IK, PK) for the merged level?

[hameerabbasi]

It will yield a std::pair<IK, std::tuple<std::optional<PK_of_each_level>>>.

[hameerabbasi]

The optional tells us for which levels the IK is present.

[bharath2438]

@hameerabbasi The PK of each level refers to the levels that are being merged for a particular dimension?

[hameerabbasi]

That's correct.

[bharath2438]

That's correct.

In that case, can I use the PK obtained from the iter_helper of a given level and put it into the tuple?

[hameerabbasi]

Only if the IK you get is equal to the minimum. Like in the codegen algorithm.

[bharath2438]

Only if the IK you get is equal to the minimum. Like in the codegen algorithm.

@hameerabbasi I'm not understanding how we can merge when there's different operators in the expression, something like A(i) = B(i) + C(i) * D(i). In such a scenario, we will have to define some precedence like the AND should be merged first and then the OR...Do we again go for recursion here?

[hameerabbasi]

This will be represented by a consteval bool function: a | c & d. You shouldn't worry too much about precedence and expression building yet -- Just abstract that away and think about iteration for now. You have an n-input boolean function and n levels, your job is just to co-iterate over or locate into those levels.

[hameerabbasi]

The boolean function defines the "pattern" -- when the output is "empty" and when it is not, based on when the inputs are or aren't "empty".

[bharath2438]

@hameerabbasi Okay now I have a fair idea of what is to be done. I have a question though, how do I "emit" variables for the iterators of the n levels? For example, I would need to use the iter_helper of these levels to get the IKs and PKs, so would I be using something like a tuple to store these iterators?

[bharath2438]

@hameerabbasi how do we get the types of IK and PK to define the forward_iterator? Also, I'm not sure about how to create a tuple of iterators using std::tie, as tuples are immutable, and we cannot append elements to a tuple.

[hameerabbasi]

I think IK and PK should be taken in the constructor.

[hameerabbasi]

Or that there should also be an iter_helper function like in the levels.