Calyx in 2022

[rachitnigam]

Calyx has come a long way since been published in 2020. We've built a lot of new tools, frontends, and passes on top of Calyx, all of which has been summarized in our previous blog post. The goal of this post is to set directions for work on Calyx in 2022. We've had a bunch of interest from the CIRCT community, along with the awesome work on the Calyx dialect lead by @cgyurgyik and @mortbopet. Moving forward, we'd like to get feedback from the community of potential Calyx users on what things are crucial in enabling adoption in the future and how can we best support them. To this end, we're collecting feedback from the community on Calyx-related work they'd like to see done–from specific engineering tasks to the bigger vision stuff. Being a small research team, we can't guarantee all of it will be done but we'd like to prioritize that affect the most users and be more community led.

To start us off, here are a few things that I think are important going forward:

1. State of Calyx in CIRCT: The Calyx CIRCT dialect has feature parity with respect to the native implementation. However, a majority of the compiler passes, including the core lowering passes, are implemented in the native compiler making it a hard dependency on folks using the Calyx-CIRCT flow. Going forward, I can think of a few ways to align the native and CIRCT efforts:

   • Reimplement everything in CIRCT: This involved reimplementing everything in the native compiler using CIRCT and unlikely to be done unless we have more engineering resources.
   • Use CIRCT data structures in the native compiler: In this approach, we bless the CIRCT generated C++-based code as the default way to construct and interact with Calyx. Then, we can update the Rust-based compiler to only use those data structures through an FFI. This largely has the effect of unifying the IR analysis and optimization machinery while keeping our work on the native compiler functional.
   • Aligning the textual representations: Currently, the Calyx-native and Calyx-CIRCT representations do not look the same. We can either update the CIRCT-based parser to use the native format or vice-versa. The better approach is probably taking the good parts from each format and coming up with something uniform.
   • Status-quo: This involves continuing with what we already have–both CIRCT and Calyx-native can export code into each other's textual format.

2. Well-defined Semantics: @EclecticGriffin's work on the Calyx Interactive Debugger (CIDR) uncovered several gaps in the semantics of Calyx, specifically with interfaces and control operators.

   • Timing behavior of control operators: Calyx groups and components use a latency-insensitive interface and therefore do not reason about the exact cycle-level behavior of the circuit. Latency-sensitive compilation is treated as just an optimization and is not required for correctness. However, while attempting to define a precise go-done interface, we discovered some problems with the underspecification of the timing behavior of the seq operator which leads to incorrect optimizations. The key problem is that in order to retain the isolation properties of groups while relying on component-based done signals, we have to know something about what part of group execution overlaps. Continued work on this aims to make the timing behavior more precise.
   • Done signals: done signals correspond to ready signal in a traditional ready-valid interface and are used pervasively by Calyx components and primitives. However, unlike data signals, done signals need to be manipulated very carefully since they signal passage of abstract time steps in the execution of the design. Careless use can result in unexpected behavior: #621, #788. Our work next year will focus on precisely defining the semantics of done signals and describing how they can extended to pipelined designs.

3. Parallel Execution: While technically a part of (2), the complexity of the par operator deserves its own thread (pun unintended). Calyx's existing par operator is very loosely specified: it guarantees that all children of a par block execute once and scheduled in some order; there is no explicit guarantee that all children start executing at the same time even though the lowering passes currently follow this strategy. In the future, we'd like to move away from this form of unstructured parallelism which devolves into the same kind of pervasive parallelism in hardware designs and is not very amenable to automatic optimization and analysis. We've played around with a few different ideas for structured parallelism operators:

   • par as an optimization: The current semantics implemented by CIDR treats par blocks purely as an optimization of seq; it is always acceptable to replace par with seq and assume the program remains functionally correct. The native compiler, on the other hand, treats par blocks in the same way as hardware parallelism: all assignments are active and input ports with multiple drivers result in a runtime error. In addition to this mismatch, this implementation of par cannot express traditional producer-consumer examples.
   • par with explicit synchronization: This would amount to implementing a "fence" instruction in Calyx which tells the compiler where the synchronization points in the control program are. While this probably enables us to express the largest kinds of parallel patterns, the hardware cost of generating a "fence" is not obvious in the same way that the cost of other control operators is.
   • Queue-based parallelism: This would involve implementing a compiler-blessed queue primitive that is guaranteed to implement the expected synchronization. While this easily captures the kind of queue-based pipeline parallelism common in many accelerators, it is not the cleanest approach; it is not easy to specify the interface of this queue and probably not easy to just exchange the underlying Verilog implementation in the same way we can exchange other primitives.

There are a lot of other things to discuss here but I'm going to leave it to here. If you have thoughts on what could make Calyx more useful for you, no matter how specific, please share them with us!

[cgyurgyik]

Use CIRCT data structures in the native compiler: In this approach, we bless the CIRCT generated C++-based code as the default way to construct and interact with Calyx. Then, we can update the Rust-based compiler to only use those data structures through an FFI. This largely has the effect of unifying the IR analysis and optimization machinery while keeping our work on the native compiler functional.

Is the essential idea here to generate LLVM/MLIR C++ data structures from Rust? I wonder if others folks would be interested in this. I imagine this would also be a massive undertaking.

Aligning the textual representations: Currently, the Calyx-native and Calyx-CIRCT representations do not look the same. We can either update the CIRCT-based parser to use the native format or vice-versa.

The CIRCT-based parser conforms (for the most part) with the syntax used in MLIR (LangRef). I don't think diverging from this is a good idea.

[mikeurbach]

In MLIR, the printed syntactical form is mostly used for debugging, testing, and things of this nature. That part of the infrastructure isn't intended to be used in a production compiler, more in tools like mlir-opt or circt-opt. For first-class interfacing with external tools, MLIR also supports a notion of "translations". For example, reading and writing LLVM IR, or HLO protobufs. I think we should be clear that what we have right now in CIRCT is a translation, i.e. you type circt-translate -export-calyx. I think it is important to keep it that way. Evoling the CIRCT dialect's printed form to look more like the form that the existing compiler accepts could make things easier on the eyes, but I do not think it is a good idea to make that syntax load bearing.

[rachitnigam]

@mikeurbach does it make more sense to define an align the bit-format for the native compiler and make sure that it's compatible with the CIRCT emitted IR?

[mikeurbach]

Sorry, I missed your previous reply. Perhaps, but I don't know anything about the bit-format of the native compiler.

I actually came here to say something else related to this thread.

Is the essential idea here to generate LLVM/MLIR C++ data structures from Rust? I wonder if others folks would be interested in this. I imagine this would also be a massive undertaking.

In last week's CIRCT ODM, @fabianschuiki mentioned the Moore compiler has stood up bindings to the CIRCT dialects. This appears to be in progress here: fabianschuiki/moore#234. It seems like that could be a shared dependency for both Moore and Calyx, and with Rust bindings for the Calyx dialect, that could lower the effort to "use CIRCT data structures in the native compiler".

[fabianschuiki]

This sounds like a great idea! The bindings to CIRCT don't really try to create a safe wrapper around CIRCT in the Rust sense, but just provide an API to emit LLHD/HW/Comb ops more or less conveniently from Rust code. I'd be happy to turn this into a shared dependency to make porting easier 👍

[rachitnigam]

Ah, this is precisely the kind of setup I was thinking. It would be very useful to have this built into the native compiler so that we can start closer CIRCT integration and long-term only rely on CIRCT to do code gen.

[stephenneuendorffer]

I'm mostly interested in a solution that lives at the FSMD level of abstraction. I think that when you start looking about expanding Calyx the language, this is where I start to think about MLIR as being part of the solution. These other levels of abstraction (e.g. handshake) solve a different problem than the FSMD aspect. Maybe we need to start to decouple Calyx the language from the MLIR dialect that represents FSMD stuff in MLIR?

[rachitnigam]

By this I assume you mean adding new operators within the Calyx language itself? Or were you thinking of different axes for extending the language?

[stephenneuendorffer]

It sounds like you're interested in 'making Calyx a richer language'. I see this as useful for a user-facing language, but not necessarily for tools that need a dialect to solve the FSMD problem. To me a richer user language would go hand-in-hand with additional higher level dialects to go along with it. I'd like to make sure that we have a good optimization framework in place even for the current Calyx language/dialect and abstraction level. Today I don't feel limited in our HLS work by the Calyx dialect and would prefer to see higher level concerns handled by other dialects.

[stephenneuendorffer]

I think alot of the core semantic questions are very interesting, too. :)

[rachitnigam]

Yup! I think as always, there is a surprising amount of details that need to be figured out to define with the semantics. I think Calyx's whole thing about latency-insensitive by default and latency-sensitive as an optimization makes things even more tricky.

[mikeurbach]

The big thing I'd like to see is a lowering from the Calyx MLIR dialect to CIRCT's hardware dialects. I think "Reimplement everything in CIRCT" makes it sounds a bit scary, but this seem like a worthwhile strategy in the long term. I think @stephenneuendorffer was alluding to this, but when you are in MLIR, expanding the "language" amounts to mixing in new dialects. This is a really cool thing. Also, CIRCT has a pretty solid set of optimizations and a Verilog emitter that quite robust and only getting more mature. It would be great to take advantage of these on the backend.

Tactically, I think we already have a decent start from @cgyurgyik to build on incrementally. As far as I understand, the core passes implemented in the original Calyx paper are currently implemented in CIRCT. Next step would be to take the lowered Calyx IR and translate that to CIRCT's HW/Comb/Seq dialects. I can't commit to working on this full-, or even part- time, but this is something I am personally interested in working on. I think once a thin path is fleshed out, we can pile on more interesting things incrementally (e.g. rewrite the compile control pass to use the new top-down algorithm, add other interesting passes, etc.).

[cgyurgyik]

As far as I understand, the core passes implemented in the original Calyx paper are currently implemented in CIRCT.

This is not true. There was an effort on my part to begin this over the summer, but we instead focused on developing a Calyx dialect -> Calyx native emitter. There is still plenty of work in this sector to be done.

[mikeurbach]

Got it. At any rate, I am still interested in fleshing this out.

[rachitnigam]

I think "Reimplement everything in CIRCT" makes it sounds a bit scary, but this seem like a worthwhile strategy in the long term.

Our simulator and debugger infrastructure is currently built on top of the native IR as well so that's something that would need to be transitioned to the CIRCT infrastructure. At least in the short term, "rewriting everything in CIRCT" still involves maintaining the Rust infrastructure.

[mikeurbach]

One more idea I've had brewing about Calyx... Has anyone given any thought to extensible/user-defined primitives? As far as I understand, the primitive libraries used thus far are hand-coded Verilog.

I am thinking about a world where Calyx is more deeply integrated in CIRCT. It could be really interesting to let users plug primitive libraries into Calyx that are themselves implemented using other CIRCT tools. For example, one could write the library using PyCDE, Chisel, Edith, or whatever generator framework can connect to CIRCT, and flows targetting Calyx could use primitives from such a library.

I'm asking about this because the scheduling infrastructure in CIRCT depends heavily on exactly what primitives you have and their properties, and I'm looking ahead to where I might want to define some new primitives for use with the scheduling tools and Calyx.

[rachitnigam]

So, the native compiler already operates with an extensible primitive library. Calyx native has extern and primitive definitions which allow users to define interfaces to arbitrary verilog modules which get linked in by the backend. For example, we have an implementation for a synthesizable divider which has a primitive interface exposed to the Calyx compiler. The two options for such generator frameworks to interact with Calyx are:

1. Directly generate Calyx components, or
2. Generate Verilog programs along with primitive definitions

I think there is still an open question about which abstraction in MLIR can be used to express these kinds of definitions and work with them.

[mikeurbach]

Interesting, thanks for the pointer. I will ponder how the native compiler does this.