calyx
calyx copied to clipboard
Add One-Hot Encoding for Static FSMs
Adds support for OHE encoding for static FSMs.
You can pass -x compile-static:one-hot-cutoff=n
, where n
is the "cutoff", i.e., the maximum number of states that an FSM can take before we switch from one-hot to binary encoding. (The default cutoff value is 0, which means we default to binary encoding every time). I didn't put in a ton of thought into this-- I'm definitely open to changing this. (One thing I did think about was #1969)
A few design decisions:
- Do we start the OHE at 0001 or 0000? I chose to start at 0001 but it required adding another primitive register that initializes to 1. If we choose to start OHE at 0000, then it just makes querying and counting to 0 more annoying (and use more logic), since you can no longer just use a shifter for adding and use check a single bit for querying. (But I also have gotten OHE starting at 0000 working as well, if you would rather do that).
- Testing: I changed
tests/correctness/static-control/
andtests-correctness/static-interface/
to additionally test one-hot FSMs for any size 64 bits or under. Should I also change the Polybench tests to do this? I made this change locally and all tests pass-- lmk if this sounds good or not.
Awesome stuff @calebmkim! I think once we merge this, it would be cool to do a synthesis study using the benchmarks we've collected to see what the effect of various one-hot thresholds is and picking a better default. My thought is that we probably want to use OHE as often as we can? This is complicated by loops which might have high trip counts.
Yeah (we should test empirically on different benchmarks) but my intuition is that OHE should be profitable apart from loops/other high cycle counts.