README.md

Research related to ABC

ABC is a very popular opensource Logic Synthesis project, some of the research implemented in ABC or related to ABC is recorded here.

This repo also helps people who want to read ABC code properly, research paper is a good start before accessing plain code.

Most of the paper referenced here can be found at Alan Mishchenko's publication page.

Another EPFL Isils group also has very high quality synthesis research, feel free to add anything interesting to the list.

Command and Research Related

Structure & algorithm

Some structure concept such as K-feasible cuts, priority cuts, MFFC in ABC can be found in following research paper.

• Quick Look under the Hood of ABC
  A brief but important manual helps understand basic network types and structures in ABC.

• CUDD package
  A manual helps get familar with CUDD package.

• EXTRA library
  Should be used together with CUDD package.

• Liberty Reference Manual, there's probably a new version though, if anyone has a legal reference link, please update.

• Priority Cuts Defination
  Priority cuts are cuts with cost function.

• Factor Cus Defination
  There are two ways of generating cuts, top-down or bottom-up.

• Cut Ranking and Pruning: Enabling A General And Efficient FPGA Mapping Solution

• Fast Heuristic Minimization of Exclusive-Sums-of-Products
  ESOP minimizer EXORCISM-4, compared with early EXMIN2/MINT/EXORCISM-2/EXORCISM–3.

• ISOP(Irredundant Sum-of-product computation)
  Which is always computed by Minato-Morreale Algorithm, there is one Pseudo code in the appendix part, the turth table library in Kitty also has an implementation.
  Note BDD package seems have internal interface. (Reference needed).

IO & Util Group

aigaug

• Verilog-to-PyG – A Framework for Graph Learning and Augmentation on RTL Designs
• Logic-level augmentation.
• Relevant repository.

read_aiger

• Local Two-Level And-Inverter Graph Minimization without Blowup
  This one is referenced in ABC when constructing AIG.
• AIGER 1.9 AND Beyond
• The AIGER And-Inverter Graph (AIG) Format Version 20071012
  This version is much more detailed than the latest one and illustrates the original AIG format and how to parse it. If you are working on a parser, read this carefully, I recommend reading the aiger parser in lorina, which is implemented in regular expression, in ABC, this is done by hard-core char by char shifting.
  Prof Armin Biere's repo would help you do the transformation between aig and other format.

read_bench

• Read a bench format file

read_blif

• Berkeley Logic Interchange Format(BLIF)
• BLIF-MV
  BLIF-MV format is the extended BLIF format.

read_genlib & print_genlib

• genlib format is SIS genlib format
  *Note this is not an offical source, it would be appreciate if anyone could provide an official source.

read_super

• Concepts of supergates can be found in Reference0 and Reference1.

super

• In ABC this command for constructing supergates only accepts a library in genlib format, if you are using a standard cell library, dump a genlib first.

testnpn

• Fast Boolean Matching Based on NPN Classification
• Fast Adjustable NPN Classification Using Generalized Symmetries

double

• double can be used to increase the size of the current aig network, and functionally speaking, you could generate larger case more realistic than MtM benchmark. - Reference

&cec

• Parallel Combinational Equivalence Checking
  Note that exact -P and -S switch cannot be found here, if anyone has found the exact implementation in the paper, please update.

write_edgelist

• Verilog-to-PyG – A Framework for Graph Learning and Augmentation on RTL Designs
• Graph Extraction.

write_bench

• This command by default write out the LUT network, if you prefer the traditional gate representation, turn on -l.

Optimization Group

strash
Structure hashing

bdd
Binary decision diagram.
*Note that ROBDD is cananical but even with structure hashing, AIG is not cananical, this is simple but important.

bidec
Bi-decomposition.
Reference: An Algorithm for Bi-Decomposition of Logic Functions (Compared to SIS, better delay result achieved.)

dsd

• The Disjunctive Decomposition of Logic Functions
  This command implements the vary 4 cases in the paper above.
• Other Disjoint Support Decomposition reference:
  • Minato-DeMicheli
  • Sasao-Matsuura
  • An approach to disjoint-support decomposition of logic functions
    This implementation should be in EXTRA library.

eliminate

• Reference: "For example, the operation “eliminate” collapses a node into its fanouts if the worth of a node computed using this metric did not exceed a specified threshold."("this metric" stands for FFLC.)

&fx

• Fast extract from The Testability-Preserving Concurrent Decomposition and Factorization of Boolean Expressions

ftune

• FlowTune: End-to-end Automatic Logic Optimization Exploration via Domain-specific Multi-armed Bandit
  Note that this command is not in the original ABC, the detail of the implementation is here.

fraig

• FRAIGs: A Unifying Representation for Logic Synthesis and Verification
  Construct aig and make sure it's semi-canonical, the concept semi-canonical can be compared with ROBDD, which is totally canonical.
  *Note that the MVSIS link in the paper is no longer avaiable, unofficial source code could be retrived from the Traditional Logic synthesis tools part below.

orchestrate

• DAG-aware Synthesis Orchestration
• Greedy local optimization and domain specific optimization with orchestation of rewrite/refactor/resub.

profile

• It profiles the gate strcuture in network, uses reverse engineer, helps when using transparent-boxing strategy and optimizing with don't care.
• -a HA and FA: Structural reverse engineering of arithmetic circuits

rewrite/refactor/balance

• DAG-Aware AIG Rewriting A Fresh Look at Combinational Logic Synthesis
  *Note that based on this thread, you should consider using drw/drf.
• For balance, check the original paper about bi-decomposition.
• Note that in ABC, balance command have -d and -s option but implemented unproperly which leads to same result, in mockturtle, the same algorithm skips these two options.

resub

• Scalable Logic Synthesis using a Simple Circuit Structure
  *Note that this resub is technology-independent, there is technology-dependent resub in reference, they have similar idea.

&reshape

• Control Logic Restructuring for Area Optimization
  *Note that although this command is already in ABC, no real implementation is available.

rr

• Scalable Logic Synthesis using a Simple Circuit Structure
  The concept of redundancy removal can be found here. The original redundancy removal could still be found in ABC source code but is not registered in the tool, so you can't use it directly, it is marked as absolete.
  *Note: "...Therefore, don’t-care-based two-level minimization performed in ... using ESPRESSO is not needed for AIG."

satclp

• Progressive Generation of Canonical Irredundant Sums of Products Using a SAT Solver

lutmin

• Encoding of Boolean functions and its application to LUT cascade synthesis
  The paper itself does not mention ABC but in this paper, reference links lutmin here.

lutpack

• Fast Boolean Matching for LUT Structures

dchoice
*Note: "The command dchoice uses various methods for rewriting the AIG to minimize the number of AIG nodes while not increasing the number of its levels. In particular, dchoice strives for smaller delay by “balancing”, which decreases the number of AIG levels by decomposing “wide-input” AND gates in a balanced way." - Reference

if -S

• Mapping into LUT Structures

if -g

• Delay Optimization Using SOP Balancing
  *Openroad flow use SOP balance in their script (Update 2024.1.2).
  Optimize some aig structure rw/rf/b can't optimize.

if -y

• Lazy Man’s Logic Synthesis
  Frequency based method to collect better pattern from design. Can even deal with patterns SOP-balance can not break.

if -u

• Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Mapper Group

map
There are tons of ideas and tricks inside the mapper, this list will be extended.

• Technology Mapping with Boolean Matching, Supergates and Choices
• Logic effort: Designing for speed on the back of an Evelope
  Core theory, logic effort.
• Gain-Based Technology Mapping for Discrete-Size Cell Libraries
  Some gain-based method reference.
  This reference is closely related to standard cell library mapping, which has discrete-size in each cell class (which means assumption of continuously sizeable cells does not hold).
• Why delay estimation is logarithmic? High-Level Delay Estimation for Technology-Independent logic Equations

if

• Combinational and Sequential Mapping with Priority Cuts

&sif

• Mapping and Retiming Revisited

smap & sfpga

• Integrating Logic Synthesis, Technology Mapping, and Retiming

Other reference

• Recommend this slide about technology mapping by Prof Jie-Hong Roland Jiang.
• FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs
  FlowMap
• Chortle: A Technology Mapping Program for Lookup Table-Based Field Programmable Gate Arrays
  Chortle
• Chortle-crf Fast Technology Table-Based Mapping for FPGAs
  Chortle-crf
• DAGON: Technology Binding and Local Optimization by DAG Matching
  The well known DAGON, you could probably see this in any reference(especially lecture slides/research paper etc) online. Based on treeifying and dynamic programming.
• Delay-Optimal Technology Mapping by DAG Covering
  DAG mapper
  *Note: Faster than tree covering method in DAGON.
• Logic Decomposition during Technology Mapping
  Graph mapper
  *Note: "Using supergates and choices, the mapper outperforms both Graph Map and DAG mapper in delay and area and has a significantly shorter run-time." - Reference.

Post-Mappinng Group

speedup

• Global Delay Optimization using Structural Choices
  *Note: ABC LUT library format also has examples in this paper. Since all optimization is on AIG as strash is performed after time tracing and critical node marking, so change these two part will help applying the algorithm after standard cell mapping.

mfs & mfs2

• Scalable Don’t-Care-Based Logic Optimization and Resynthesis
  Re-sub based resynthesis + don't care based resynthesis

mfs3

• Versatile SAT-based Remapping for Standard Cells
  Experiment is performed after amap and &nf -R 1000.
  *Note: mfs & mfs2 are for LUT-based FPGAs while mfs3 is for standard cells.
  *Gain-based approach deals with delay information.

NPN

• Classifying n-Input Boolean Functions
  Very clear illustration of P/NPN class and examples are shown.

Delay target optimization

• Enabling Exact Delay Synthesis
  Personally really recommend this paper which combines timing information with supergates and optimizes searching using P classes with timing pattern.

Area target optimization

Traditional Logic synthesis tools

• Old Logic synthesis tools
  Espresso, SIS, MVSIS are here.
  *Note: Some of the algorithm in ABC is directly from SIS and MVSIS.

Benchmarks

Here are some famous benchmarks from research/paper above.

• ESPRESSO benchmark
• IWLS 2022 Benchmarks
• IWLS 2005 Benchmarks
• IWLS 2024 Benchmarks
• EPFL combinational benchmark suite
  There's also a paper related to the benchmark.
  *Note that case hyp is quite big and skip it if necessary.
• Official AIG benchmarks can be found at here.
• ISCAS
• ITC99
• MCNC
• ISPD’02 IBM Mixed-Size Placement Benchmarks
• ISPD’98 Circuit Benchmark Suite - Reference
• ISPD04 IBM Standard Cell Benchmarks with Pads
• MPC Benchmark
• Crypto Benchmark

Other repo

Yosys and OpenRoad-flow-scripts are good place to find out discussion about ABC since original ABC repo's issues are not very active.

SAT solver

This repo from CMU can give you a brif introduction on the DIMACS format and how to use SAT solver as an interface.

I was trying to matain a collection list of SAT solvers but I have found that PySAT seems contain all the well-known SAT solvers.

There's a detailed introduction on MiniSAT.

Performance

• Yosys+ABC9 in FPGA is catching up with industry level performance. - Reference

• IWLS 2024: Yosys+ABC(Lasy Man Based): Insights from Basilisk: Are Open-Source EDA Tools Ready for a Multi-Million-Gate, Linux-Booting RV64 SoC Design?

TODO

Some of the implementation was originally been written into the traditional tools such as MVSIS or SIS.
It's better to check if ABC contains the following.

• “S&S-based and BDD-based resubstitution algorithms were implemented in the resynthesis package used to improve the quality of standard-cell technology mapping in MVSIS” - Reference