Papers

Notes on Papers

HIDE: A Hardware Intelligent Description Environment (2006)

This paper is old at this point, 20 years old, but it does some still lacking among modern HDLs: proper structural descriptions. It's writing in the context of Verilog, VHDL, System-C, and stuff like that which is still largely the norm, though I think this is before many of the functional embedded HDLs like Clash or Spade or Chisel. HIDE is itself most similar to these functional HDLs, but differs in being based on logic programming instead of functional programming (though of course those disceplines are very related). The most similar piece of work to this is Lava.

The primary abstraction of HIDE is a block. These can be 2d rectangles or 3d prisms where each side has a list of named, directional ports. HIDE includes separate special ports called controls on blocks for stuff like reset and clock which are used by like every component. Many ports can be collected together into busses. This is how you represent multi-bit signals.

Blocks are composed in the obvious way, horizontally, vertically and above or below (for 3d blocks). Circuits are 2d, however so 3d blocks end up getting projected onto the plane as either a horizontal or vertical line. Blocks are wired together by matching input and output ports by their number/column. For example, in 2d with two blocks horizontally layed out, the first output port from the left block's east side would connect to the first input port on the right block's west side. This works the same in 3d except now there are columns. It's also possible to override this default mapping with an nc function but you still are connecting blocks to adjacent blocks. Sometimes you might have blocks A -> B -> C and want to connect a port in A to C. Then you can use nc([..., (i, thru), ...]) to add an input port to B's west side which passes through to a port at the end of B's port list on its east side. This this the gist of it, but there are a bunch of other constructors which basically allow you to do whatever connections you want. They also allow you to insert "free action" computation like shifts.

There is a relatively straightforward mapping from the Prolog circuit definition to tree structure called a configuration data structure (CDS). The CDS contains stuff like width, height, location, ports, and child blocks.

The simple compilation scheme does very well, probably because its equivelent to just doing a full custom layout. Especially for the systolic gemm example they give. I'd really wonder how well this works compared to current EDA tools. I'm also kind of sketch with their utilization numbers. Sure they have way less utilization and get a similar fmax but I'd bet that's just because they have a small design. I'd like to see if this pattern continues with designs closer to FPGA utilization. I'd doubt the EDA tools care too much about minimizing utilization as much as they care just getting the design to fit.

This effectively forces users to write code purely structurally. The authors do a good job totally ignoring most control logic. Writing an FSM in HIDE is probably pain. This also might be skill issue, but I find HIDE totally illegible when trying to understand it. Still, it's cool that this seems to show some sort of structural model isn't totally dead on arrival. I think the main interesting bit here is the automatic port connections. This is super important for readability and solves one of the problems in many HDLs where you have a bunch of silly wire names everywhere. This is partially solved by HDLs which allow modules to "return" values (e.g. spade or some of the embedded functional ones), but in that case doesn't generalize easily: if you have multiple things which are logically outputs or form some handshake like a rdy/val handshake, you have to wrap this output in some struct. This is sort of also the case in HIDE with busses, but I don't think you need them nearly as much. The thing this doesn't do as well is being able to do module().thing().other_thing() as now you have general graphs instead of linked lists. The implicit version with h_seq or v_seq kind of does this but not as well. This feels like simply a limitation of prolog.

RapidStream IR: Infrastructure for FPGA High-Level Physical Synthesis

This paper is a follow up to a previous Rapidstream paper. The gist of that paper is to break HLS designs up into blocks with some defined interface and then lay them out with ILP (I think). There are a lot of moving parts to this one, it is one of those papers describing a larger project so it kind of enumerate a bunch of parts in an ecosystem of sorts.

One difference the authors try to make is to frame themselves as not HLS but something my 2 minutes of searching seems to tell me is something the authors made up, high-level physical synthesis (HLPS). The dichotomy the authors try to make is HLS systems don't do a good job at considering quirks of the underlying hardware (FPGAs in their case). For example, the AMD Versal VP1552 FPGA has multiple dies with slow die to die communication. HLS wouldn't take into account these slow crossings, but HLPS does. If this is indeed what the authors are trying to say, I think this is a pretty silly distinction.

The birds eye procedure the authors give for HLPS is first analyze a high level spec and look for connections between atomic modules which are more tolerant to latency (e.g. they permit optimizations, e.g. piplining). This is done with heuristically looking at the spec and identifying patterns which look like things like handshakes or valid protocols. The design is then partitioned such that each partition has latency tolerant external ports (or as latency tolerant as possible). This is also just a bag full of heuristics and optimization I think. These partitions are then placed with some metrics to lower congestion and finally routed. The paper focuses on the middle part, how to represent these partitions.

The IR is pretty straightforward. The primary has modules, named structures with ports, wires, and additional metadata. These modules can either be leaf modules, which are atomic pieces of the design (e.g. IPs or RTL) or grouped modules, which contain a collection of other modules and sepcify how those modules are wired together. Additional metadata can contain things like floorplan constraints, resource utilization, and other useful things for optimization. One important special piece of metadata, given the name an interface, annotates a set of ports on the design describing some relation they have, e.g. they are used with a piece of data to preform a rdy/val handshake. This is in part what is meant by "latency tolerant" and is used for optimizations. In addition, there are a couple invariants which keep hte IR nice: wires connect precisely two modules, submodules' ports connect to exactly one wire or constant, and all ports are connected.

One thing to note about this IR is much of the behavioral information is lost outside of references in leaf modules. The goal here is not to totally specify designs but to serve as a medium for doing pnr hierarchically and to serve as a sort of lingua franca between different FPGAs.

The passes on the IR are relatively striaghtforward and used to implement the steps of HLPS the paper describes. There is a pass to wire together imported leaf modules (it does this by creating a big router "aux" module). There are passes to infer interfaces, split leaf modules (e.g. the monolithic aux module created when wiring together leaves). There are also flattening and unflattening passes and optimization passes. The paper has details, but it do kind of just be a compiler. The main flow is load in the design. Uses pases to reconstruct hierarchy and partition it. Then flatten the design (so it's more friendly to ILP), and use AutoBridge to do floorplanning. Finally, do the interconnect synthesis and insert pipeline stages if need be.

Unsurprisingly, this does pretty good and can enable module level parallelism for synthesis. Improvements are among most metrics but especially frequency. Maybe interestingly, but also intuitive is, the resource utilization is nearly identical. The benefit is atomic components are being placed better, not like new logic or massive reductions in logic or things.

In my view, there is a lot of cool engineering work here, but the standout innovation is that extra "interface" bit of metadata annotating module ports allowing them to be optimized in special ways if they have that annotation. This seems to do really well impoving fmax. That and optimization towards placing each block. The future work mentions integrating this with RapidStream, which seems interesting, as making stuff super parallel and higherarchical seems the way to go here. My mental model here is this is this is living in the world of tools which try to figure out better way take a bunch of kind of disparate designs which can be (mostly) processed in parallel and wiring them together. Kind of like what does linking look like lol. I wonder if you could properly design a high performance interface so you could do something kind of like linking (like where you have a bunch of gds files with a bunch of placeholder connections on their ports and those get rewritten during "link time" and there is some guarentee by the algorithm and file format that you hit timing and are DRC/LVS clean or whatever.

I do wish the paper went into a bit more detail about how these steps were actually implemented. I didn't see a huge amount on how the final interconnects worked out, though it seems they were just written to somewhat structural verilog and fed into a normal pnr flow. This is a little disapointing, because it leaves the big problem of "how to parallelize PnR" still pretty unexplored. Totally unrelated, but I wonder if you could do elatic designs (e.g. elastic cgras) to get around this because maybe for some reason those are way easy to get timing closure for and compose. But yeah, doing routing in pieces seems really hard. RapidStream of course proposes something (and it's mentioned integrating with it is future work) but I don't know where that is. The website is down :cry:.

λλ: A Programming Language for Silicon Photonics

I'm currently mostly thinking about layout/placement so I don't have nearly as many thoughts about this one. It's a nice paper (with a long appendix I haven't read, classic PL paper). It describes a cute little language with a linear type system modeling some constraints of silicon photonics. The programming language itself is basically a simple functional language with some primitives matching what's needed by silicon photonics. The cool part is the ILP which does a possibly interesting thing to me where it encodes the direction an input comes from using a binary s variables indexed. This makes it so you can't have inputs from multiple directions at the same time. Other than that, it did kind of just seems like an ILP. Overall solid paper, but I don't think super interesting to me right now.

PLD: Fast FPGA Compilation to make Reconfigurable Acceleration Compatible with Modern Incremental Refinement Software Development

That title is long. But the idea is one probably any software engineer writing an accelerator for an FPGA has felt. The big idea of the paper is pretty simple: split the reconfigurable area of an FPGA into a number of "pages" which can be configured indepenantly. The pages themselves are connected by a network each page knows how to communicate with. The frontend compiling to this are C kernals connected together using a streaming interface. That is, each C kernal is connected to others forming a dataflow graph (the system is inspired by Kahn Process Networks). Each kernal is mapped to a page, and the FPGA is flashed with a network to allow these pages to communicate.

In order to support incremental refinement, there are multiple levels of "optimization" allowed for mapping the kernals to pages. -O0 is flashing the page with a premade RISC-V softcore and then compiling the kernal to RISC-V. -O1 is compiling the kernal to verilog and flashing the page. -O3 is basically just FPGA flow. As expected, -O0 takes seconds, -O1 takes tens of minutes, and -O3 takes a couple hours, and of course -O3 is basically normal performance, -O1 is an order of magnitude worse, and -O0 is even more orders of magnitudes slower. Pretty straightforward at a high level but the engineering work to actually make this a reality probably made at least one person loose their hair.

Some of the main takeaways here are this idea works, and the bottleneck tends to be the network facilitating communication between the kernals. And, as expected the area demands tend to be higher. The most frustating part of this is that compiling each page still takes tens of minutes except at -O0. -O0 is still super helpful because being able to test stuff on board to make sure things are wired up right is extrememly helpful, but it's not great for trying to adjust stuff for performance. Though, maybe this isn't as much a thing for HLS anyway. My understanding is making pages smaller to reduce compile times is for three main reasons:

This is very reasonable for FPGAs, but I wonder if this constraint could be lessened for ASICs. Though of course then the end goal is totally different, getting a good enough approximation of a final PnR to tweak parts of a design for performance or area or power or other reasons. In that case, the order of magnitude decrease in quality would probably not be good, though maybe it would be okay because per page the reduction in quality is probably not much.

Overall, the idea seems to be in the same ballpark as some of the rapidstream stuff I've been reading: "HLS makes some dependency graph which can be broken up into atomic blocks are wired together." A big difference here is done kind of "realtime" and incrementally with a static global network. An important thing about stuff like this is it starts from HLS looking things which don't specify stuff as strictly as RTL descriptions. For example, the model of computation here is higher level, thinking about parges blocking on other pages for data, instead of lower level "what is happening to each register at every cycle." It's not totally clear how to bridge this gap if we wanted to do something like this for RTL. It seems like some higher level interface is really what is needed and streaming interfaces are just really common in HLS. I wonder if there is some precise way to characterize what an interface allowing this "hotswapping" of components would have to look like. I haven't thought very hard about this so it might be kind of obvious. Well, certainly a streaming interface give enough wiggle room as described here. But yeah, cool paper and intense seeming engineering.