EqMap: FPGA LUT Technology Mapping w/ E-Graphs

EqMap is Verilog-to-Verilog tool that attempts to superoptimize FPGA technology mapping using E-Graphs. Our experiments show that equality saturation techniques can improve logic sut selection and ultimately produce smaller circuits than the commercial tools.

You can read the docs here.

Getting Started

Dependencies for Users

• rustup
  • Crate Used (these are fetched automatically)
  • egg, bitvec, clap, indicatif, sv-parser, serde_json
• Yosys 0.33
• Optional CBC Solver

Dependencies For Developers

• VSCode Extensions
  • Rust Analyzer Extension
  • VerilogHDL Extension
• RTL Tools
  • Verilator
  • Verible

Building the Tools

First, check the prerequisites for building. For basic functionality, you will need the Rust toolchain and a Yosys 0.33 install. Linux is preferred, but MacOS and WSL should work without much trouble.

cargo build

cargo run --release -- tests/verilog/mux_reg.v # Sanity check

Bring Your Own RTL

You can also try to synthesize your own verilog module my_file.v as long as there are no multi-bit top-level ports:

source utils/setup.sh # Add eqmap script to PATH

eqmap my_file.v

Use --help to get an overview of all the options the compiler has:

``` $ eqmap --help Technology Mapping Optimization with E-Graphs

Usage: eqmap_fpga [OPTIONS] [INPUT] [OUTPUT]

Arguments: [INPUT] Verilog file to read from (or use stdin) [OUTPUT] Verilog file to output to (or use stdout)

Options: --report If provided, output a JSON file with result data -a, --assert-sat Return an error if the graph does not reach saturation -f, --no-verify Do not verify the functionality of the output -c, --no-canonicalize Do not canonicalize the input into LUTs -d, --decomp Find new decompositions at runtime --disassemble Comma separated list of cell types to decompose into -r, --no-retime Do not use register retiming -v, --verbose Print explanations (generates a proof and runs slower) --min-depth Extract for minimum circuit depth -k, --k Max fan in size allowed for extracted LUTs -w, --reg-weight Ratio of register cost to LUT cost -t, --timeout Build/extraction timeout in seconds -s, --node-limit Maximum number of nodes in graph -n, --iter-limit Maximum number of rewrite iterations -h, --help Print help -V, --version Print version ```

You will likely want to use the --report <file> flag to measure improvements in LUT count and circuit depth.

Features

The project has three conditionally compiled features:

1. egraph_fold (deprecated)
2. exactness (used for ILP exact synthesis, requires CBC)
3. cut_analysis (on by default)
4. graph_dumps (enables the serialization module and --dump-graph argument)

To build with any of these features enabled:

source utils/setup.sh <feature>

Docs

You can generate most of the documentation with cargo doc.