Lazy sparse tensor generators?

[paul-tqh-nguyen]

This was inspired by #259.

Possibly not sane optimization idea (let's call this the "lazy generators idea"):

• The tensors created by these NumPy functions are predictable. Let's call these tensor generators.
• Ideally, we'd be able to fuse these with generic ops to avoid using up the space it takes to create them.
• Example from GraphWave:

I = np.eye(4)
L = generate_L()
ans = L + I

• In the example above, we'd ideally be able to fuse the generator with the graphblas.apply/graphblase.update used in the ans line.
• This is analogous to using lazy generators in Python, e.g.

>>> a = [11,22,33]
>>> b = itertools.count()
>>> ans = [a_e+b_e for a_e, b_e in zip(a, b)]
>>> ans
[11, 23, 35]

• Ideally, we'd have some representation in our GraphBLAS dialect to represent these lazy tensor generators. We might need a new type (called "lazy_sparse_tenesor_generator") or something. Our ops might be able to fuse them more easily that way.
• Ideally, we'd also be able to fuse generators like we do in Python, e.g.

>>> a = range(3)
>>> b = itertools.count(100)
>>> ans = (a_e+b_e for a_e, b_e in zip(a, b))
>>> ans # still a lazy generator
<generator object <genexpr> at 0x7fd54c056bd0>
>>> list(ans) # the tensor isn't reified until we hit this point
[100, 102, 104]

Ideally, we'd also have the following ideas implemented (these would serve as reasonable tests):

• We'd be able to combine np.diag(np.ones(3)) into np.eye(3).
• ans would be a lazy generator here to be used elsewhere:

I = np.eye(4)
ans = graphblas.apply(I, "fill", right=c99_f64)

It might be a good idea to have a generic lazy tensor generator initializer op. It might look like this for np.ones([7, 9]):

        %final_ans = graphblas.init_lazy_gen : tensor<7x9xi64, #CSR64> {
            ^bb0(%row: index, %col: index):
              graphblas.yield SOMETHING %c1_i64 : i64
          }

• We might have to have the body take 2 different signatures (one for matrices and one for vectors) depending on the output sparse layout.
• This would easily fuse with a graphblas.apply op.

I think the key idea behind all of this is that blocks are analogous to functions, and we can heavily optimize code using functional programming techniques.

---

GraphWave also motivated a graphblas.outer_product. This might be easily implemented via #251?

We could take that idea even further and make the #251 op return a lazy sparse tensor generator.

---

Heck, why not make graphblas.apply return a lazy generator as well? And all of our other ops?

It's unclear if all of our current GraphBLAS dialect ops can work as lazy generators.

• My biggest concern is matrix multiply. It might be possible to do it lazily, but I'm unsure. I think anything that requires aggregation cannot be done lazily (or at least easily without a cache of some sort, which will possibly be not worth the memory/locality cost), e.g. graphblas.reduce_to_vector.
• Side Quest: However, we could do the masking part of matrix multiply (and other ops) lazily. Would it be worth making the masking a separate op?

If many of our ops are lazy ops, they can be dichotomized into lazy ops and reifying ops. This'll open the door toward using profile-guided optimization to tell us when to insert a reification op that simply turns a lazy op into one that writes out to memory. There's a trade-off between laziness/memory-saving and locality that PGO might be able to solve.