Proposal: use xlsynth-g8r for stable/understandable QoR analysis metrics

[cdleary]

It has recently been noted that there is significant uncertainty that can result from serializing XLS computations through verilog to downstream tools to establish subsequent quality-of-result metrics. See 049ca86

In other domains of computer performance measurement/optimization we sometimes adopt tools that give determinstic and comprehensible results even when working on top of unpredictable / inscrutible underlying phenomenon; e.g. we perhaps use cachegrind to count cycles in an understood way even if the out of order engine in our CPU is defying our precise measurements. It's been studied that optimizations are difficult to establish as wins in all environments (see e.g. the work on stabilizer and the associated very good talks https://www.youtube.com/watch?v=r-TLSBdHe1A ), yet we as a community want to define procedures that allow us to make forward progress on things that we have solid reason to believe are of benefit in an abstract sense.

To this end, in the xlsynth Rust crate repository there's a sub-crate called "g8r" which is a pretty simple / understandable yet effective "gate mapper", in that it converts from (optimized) XLS IR into a gate-level representation. This is similar in some ways to the booleanifier, but significantly more built out to be representative / reasonable at this level of abstraction. Arguably this is the "missing link" in what XLS (defined as the codebase in this github repo) does today, as XLS analysis and understanding otherwise stops at the composite operation level for delay modeling / analysis. Following in ABC's footsteps g8r is based on an and-inverter graph that has some basic optimizations performed on it: folding, structural hashing, and simulate-to-identify-redundancies-then-prove-them (fraiging, as I understand it). It gives a deterministic "live node count" and "deepest path" in a process-node-agnostic fashion, and it computes logical effort to reflect the impact of fanout along the critical path.

g8r is the engine in the ir2gates command in the xlsynth-driver that I showed in the issue filed here: #2045 (comment) Me and my team use this to understand how XLS computations are likely to map down in an abstract sense to provide a compass on what's likely better and a mechanism/codebase that allows us to soundly dig into "why".

As we had suggested in the discussion section of https://arxiv.org/pdf/2401.12343 this sort of metric could be used as a fast/efficient driver for ISDC feedback / FDO and avoid challenges we can have with the granularity at which we perform min cuts. g8r can dump out XLS IR post gate mapping and it has facilities for proving the decomposed gate form equivalent to the original via check_ir_equivalence_main.

I also propose we adopt a cute logo for it similar to the attached. This is perhaps the most important point of discussion!

[ericastor]

Speaking for myself only: I'm going to need to think about what evidence I'd want to see before adopting this, then maybe try to gather it - unless you already have correlation data you can share? (EDIT: If you can't share the data, that makes sense - I'm sure it's on proprietary IP - but can you share the methodology, and maybe a sketch of the results?)

My main issues come from the fact that techmapping is a hard problem that can definitely make things behave differently than the AIG you put into it... and that we know from internal experiments that AIGs are measurably inferior to Yosys+OpenSTA for both delay & area estimation, at least for some analysis approaches. (I'm not sure if they accounted for fanout in their AIG analysis, but I would certainly hope so.)

Also, are you making a specific claim when you say g8r is a source of more stable QoR estimates? If you're referencing the extreme input sensitivity of ABC and other logic-synthesis tools, I'd want to see some evidence that you've solved that problem... since no one else has. 😄 (I will not name names, but we haven't found any evidence that any toolchain of known quality produces an insignificant level of noise for QoR measurements.)

[allight]

I'm somewhat concerned with brining in a project which contains a mirror of the xls ir parser and ir structs as a dependency. It would make doing any changes to the xls ir much more complicated.

[cdleary]

I had discussed this with @meheff and he didn't object at the time, exposing the surface area for all the IR nodes through the C API is a similar burden to implementing it on the other side of the fence given its current stability level vs simplicity. g8r notably only works on XLS IR functions.

[allight]

Sure just a concern. I wonder if it might be worthwhile to go back to a node-code-generator thing to keep it all in sync WRT structs (or something like https://github.com/google/crubit assuming its able to handle our irs. @hzeller any idea if that would work?) though. The IR is pretty static now but some of @scampanoni plans envision pretty major changes.

[ericastor]

Coming back to this a bit later - of course it makes sense if you can't share numbers or specific results, I'm certain you tested this on proprietary IP.

However - can you explain your methodology? For example, how did you convince yourself that g8r was well-correlated with synthesized results? What sort of sources did you use? (Did you have a natural way to produce variations on the same XLS code? How many variations did you use for your input?) What sort of tests did you use to measure how strong the correlation was?

If you have questions about any results we've shared along the same lines, I'd be glad to answer those too.