Exact DAG-Aware Rewriting
Heinz Riener, Alan Mishchenko, Mathias Soeken
Abstract
We present a generic resynthesis framework for optimizing Boolean networks parameterized with a multi-level logic representation, a cut-computation algorithm, and a resynthesis algorithm. The framework allows us to realize powerful optimization algorithms in a plug-and-play fashion. We show the framework's versatility by composing an exact DAG-aware rewriting engine. Disjoint-support decomposition and SAT-based exact synthesis together with efficient caching strategies enable the algorithm to resynthesize larger parts of the logic. DAGaware rewriting is used to compute the gain of resynthesis while taking the benefit of structural hashing into account.
Topics & Concepts
RewritingComputer scienceParameterized complexityHash functionDisjoint setsTheoretical computer scienceComputationRepresentation (politics)HeuristicsAlgorithmProgramming languageMathematicsDiscrete mathematicsPolitical sciencePoliticsLawOperating systemFormal Methods in VerificationProtein Degradation and InhibitorsSynthetic Organic Chemistry Methods