Calyx Static Summer 2023 Lab Notebook

[calebmkim]

Starting a lab notebook for updates on Calyx Static.

[calebmkim]

• Met w/ Andrew and Pai last Friday, and implemented Static Par and Static Seq in CIRCT. It was pretty easy, but the main benefit was getting familiar w/ the CIRCT repo.
• Going to work on adding static if to CIRCT as well
• I'm also trying to write Polybench tests in the Affine Dialect. Polygeist may help with this. To that end, I'm trying to download circt on havarti since it takes up a lot of space. Getting circt/llvm/mlir on havarti might also help when we try to get Hector working as well.

On the Calyx end (at a lower priority) we can think of ways of improving QoR as well.

[rachitnigam]

Awesome! Seems like everything is going well. One thought: in case Polygeist ends up being too brittle/not useful for benchmarks, we can consider writing the benchmarks directly in the affine dialect.

[calebmkim]

Yeah, I was thinking of at least trying to write benchmarks directly in affine. Even if it doesn't work out, I will still get familiarity with the Affine Dialect which could help if I wanted to do something like use Polygeist as a frontend for a rough draft and then tinker with the result (which Andrew mentioned as an option).

[calebmkim]

Since we're going to talk about virtual operators today, I decided to put down some of my thoughts/questions on the it.

I imagine the syntax would be something like: mult0 = virtual mult(32) or something like that to declare a virtual 32 bit multiplier. You can use this like you would an regular multiplier. However, the Calyx will at some point turn this virtual operator into an actual hardware primitive, e.g., std_mult_pipe(32).

Questions

• Should virtual operator have predefined signatures? The reason why I ask is that some of the multipliers, such as the pipelined multiplier, doesn't use a done signal, whereas other versions of a multiplier do use a done signal; but it seems like we would want a virtual multiplier to be able to be "realized" as either option.
• When in the compilation pipeline should we convert virtual operators into actual hardware modules? (Pretty early on, I would guess)
• This is perhaps the main question, that has always been a bit confusing to me with virtual operators: how should we determine what hardware modules to use? Mapping logical memories to physical memories #1151 suggests virtual memories, in which the size of the memory would determine what physical memory we map it to, which makes sense. Is there an equivalent type of criteria we could use for things like multipliers?

[calebmkim]

I was thinking about our discussion about getting default settings for inlining yesterday.

More specifically, I was thinking about the new_fsm attribute for static control, but I was realizing that it probably won't even be helpful: the main benefit of the new_fsm attribute is that it simplifies the fsm's control logic. But for static control, our fsm is just a counter that always increments by one every cycle. So splitting it up a large fsm into several smaller fsms in this context wouldn't actually simplify any logic: it would just split (for example) one 20 bit register into 5 18-bit registers (but the control logic is equally simple for all of them: you just add 1 each time either way). In fact, the 5 18-bit registers might have more complicated logic now since we have to guard when we increment them.

So it seems like it may not even be worth it to implement new_fsm for static control.
Does my reasoning make sense?

Either way, I'll try to get resource numbers on the benchmarks in calyx-resource-eval when we fully inline and compare it.

[rachitnigam]

That's a good point @calebmkim! One other benefit of @new_fsm is that it splits the FSM so that there is a lower "signal fan-out" ratio which can be prohibitive when attempting to build high-frequency designs.

[calebmkim]

I've begun trying to generate (inefficient) Calyx Polybench designs by going from: MLIR Affine -> MLIR SCF -> CIRCT Calyx -> Native Calyx (e.g., here).

However, before I generate more designs, there are a few questions that I'd like feedback on (perhaps we can discuss this more in depth during out Thursday meeting):

1. What data type should we use? Our options are Floating Point, Fixed Point, or Integers.
2. How large should the benchmarks be? (they provide default sizes for: mini, small, medium, large, extra large)
3. What should the actual .futil file look like? More specifically, arrays need to be initialized to hold non-zero values. Should this initialization be done in the .futil file (i.e., there is a Calyx while loop that is going in and initializing the arrays), or should it be done somewhere else, and the .futil file reads from an external json of (already initialized) memory values?

3. is arguably the most urgent question to answer, since 1) and 2) seem like we can (pretty easily) switch between if we change our minds.

[rachitnigam]

For (3), I'd suggest starting with just using the JSON-based input loading. For any large design, the data input step will be dominated by the compute kernel

[calebmkim]

That's what I was thinking too.

[calebmkim]

Another thing that might be worth thinking about:

The Hector paper directly compares against Calyx's systolic array generator.
It may be worth trying to look at revisiting the systolic array generator to see what kind of cycle count and resource usage we get with this new static syntax stuff (and an opportunity to use pipelined primitives as well)

I'll add this as a possible frontend on the project board

[rachitnigam]

Yeah, that's exactly what I was thinking too!

[calebmkim]

One small thing that I'm running into when going from C->SCF->Calyx. We're currently doing the benchmarks using ints. But some of the benchmarks need to perform square root.

Is there an operator in MLIR to get the square root for integers? (something equivalent to the Calyx primitive that does integer square root, which basically takes the floor of the square root of any integer).

In c, you can do this by doing a cast (int) sqrt(x)...
But then in MLIR it gets translated to

// 1) cast x to a floating point 
// 2) perform floating point sqrt using the `math` dialect in MLIR 
// 3) cast x back to an int 

I'm wondering if there is a single operation in MLIR to define this.

[rachitnigam]

Tricky one! I think sqrt is usually exposed as an external function in these situations (for example, in Dahlia) and is supposed to be linked in by some other header file. @andrewb1999 might have some more insight on exactly the right way to do it but more likely than not, this is just hard to express in the current flow and we might have to give up on those benchmarks.

Maybe we can go beyond the just the linear algebra kernels and implement other kernels to supplement our benchmarks?

[calebmkim]

Sounds good. Do you have an idea about which other kernels we should try out next? There's:

• Datamining (so covariance and correlation)
• Medley (which includes 3 benchmarks)
• Stencils

[rachitnigam]

Whatever doesn’t need custom functions would be good. Stencils for example is a classic although the computations are better suited to systolic kinds of programs

[calebmkim]

I'm trying to lower scf.for loops to repeat statements.
My plan is to start with the most basic possible examples of for loops to lower: ones where we a) are able to tell the number of iterations statically (e.g., if the upper bound is the result of a memory read we can't lower it) and b) where there are no iter_args (e.g., we won't lower this example):

%final_sum = scf.for %iv = %lb to %ub step %step 
    iter_args(%sum_iter = %sum_0) -> (i32) {
  // for loop body
  scf.yield %sum_next : i32
}

Plan

My plan is just to create a repeat statement as follows:

// initialize idx to lower bound 
repeat num_repeats {
  // for loop body, which might use idx's value 
  // group that adds step to idx 
} 

I was wondering if this sounds fine.

It's been a bit difficult for me to figure out how to make a //group that adds step to idx, but hopefully I can figure out.
Edit: the reason why it's difficult to make this group is because I'm not really that familiar w/ the codebase ...
All the examples of doing Calyx adds in the codebases are lowerings of arith.addi operations.... but in this case, there's no explicit arith.addi operation that I'm trying to lower. I'm trying to look at the code that handles arith.addi and see if I can use that as inspiration to create a group that adds to a register, but no luck yet.

[sampsyo]

While I am no scf expert, this seems about right to me! I like the idea of starting simple with the scf.for loops that are already almost Calyx repeat loops.

I don't have great advice about how to generate MLIR-Calyx code for the increment… but maybe starting with the MLIR OpBuilder API would be an acceptable place to start?

[calebmkim]

For the SCF->Calyx stuff, I just realized that for about 1/2 of the benchmarks, we can't compile scf.for->calyx repeat.
The reason is that if we have something like

scf.for i = 0 to 30 {
  scf.for j = 0 to i {
    ...
  } 
} 

the nested for loop obviously can't be a repeat statement.
In this case, we have to run scf-for-to-while before lowering to Calyx.

I still think there are benefits to be gained from the 1/2 of the benchmarks for which we have to compile scf.for->calyx repeat, but it makes lowering kind of weird. And on the bright side, I just tested the 1/2 of the benchmarks that you can compile scf.for->calyx repeat and they work.

[sampsyo]

Got it; this makes sense! In these cases, the bounds are dynamic, but in a very "affine"/"polyhedral" way, rather than being "interestingly" dynamic.

One option for these cases, which is probably very bad, is to "pad out" the loops so they run for a constant number of iterations but only do something for the ones that matter. Like this, in pseudocode:

for i = 0 to 30:
  for j = 0 to 30:
    if j < i:
      ...

That's one way to get static bounds at the cost of lots of wasted time…

[calebmkim]

(I know it's not summer anymore, but I want a place to write this down):

I was thinking about getting a hypothetical (but concrete) example, where the static par blocks allow us to produce designs that are faster than before (this can help make us make the case that auto-parallelization, if we implement it, needs to rely on our static constructs).

Suppose we have the following groups:
A and B take 1 cycles.
C and D take 10 cycles.

Also suppose the following requirements:
A and C both must come before B
A must come before D.

We can schedule this using static par as follows:

static par { static seq {A; D;} static seq {C; B}} 

This takes 1 + 10 = 11 cycles.
Crucially, this is not valid if we take away the "static" keyword, since taking away the static keyword would remove the guarantee that A before B.

The best possible (dynamic) schedule, unless I'm missing something, is this:

seq {A; par {C; D;} B; } 

which takes at best 1 + 10 + 1 = 12 cycles (in reality it would take longer bc it would waste cycles in between groups). However, this is the best possible schedule. In the context of auto-parallelization, it is probably not realistic for a compiler to find the best schedule in general.
In reality, a compiler that implements a heuristic (like some sort of greedy algorithm) might schedule:

seq {par {A;C}; par {D;B} } 

which takes at best 10 + 10 = 20 cycles (even worse).

[rachitnigam]

Makes sense to the keep this around as a lab notebook! I think this is a cool idea and I'm not certain that optimality is out of reach here: if we stare carefully, I think we can pose it as a scheduling problem and write an optimal greedy solution.

[calebmkim]

Note about the generated Post-Op component

Just to give background on the systolic array: 1) The systolic array component 2) The post op component and 3) the main/controller component that connects (1) and (2), meaning (3) ends up being very RTL-like, since it's just a bunch of assignments that wire together ports.
Unfortunately, the post op component (2) also ends up being pretty RTL-like: because the systolic array component (1) presents its output r0_value for a given r0_idx for exactly one cycle before moving onto the next r0_idx, the post op component, must write into a register when receiving the r0_value in order not to lose it (at least for dynamic post-ops. Static post ops can avoid this by confidently knowing which cycle they are going to need each value). This results in a bunch of RTL-like assignments in the post op component (2) that read from r0_value, r0_idx, etc. and write to the appropriate register.
This is fine in terms of correctness, it just make the code less readable.
We could try get the post op component (2) to read from some sort of FIFO to avoid the complicated RTL-like assignments but I would have to think more about this.

[rachitnigam]

Hm, thanks for writing this up! I think this is a tricky problem because it’s be nice to have some sort of structured representation for the ready valid signal. Maybe a lightweight form of FIFOs that don’t have any internal storage and instead just block the read till a value is available could be a starting point?

[calebmkim]

Yeah, I think we can explore possible options for this synchronously.