Details

Autor(en) / Beteiligte

• Haaswijk, Winston
• Soeken, Mathias
• Mishchenko, Alan
• De Micheli, Giovanni

Titel

SAT Based Exact Synthesis using DAG Topology Families

Ist Teil von

• 2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC), 2018, p.1-6

Ort / Verlag

IEEE

Erscheinungsjahr

2018

Quelle

IEEE/IET Electronic Library (IEL)

Beschreibungen/Notizen

• SAT based exact synthesis is a powerful technique, with applications in logic optimization, technology mapping, and synthesis for emerging technologies. However, its runtime behavior can be unpredictable and slow. In this paper, we propose to add a new type of constraint based on families of DAG topologies. Such families restrict the search space considerably and let us partition the synthesis problem in a natural way. Our approach shows significant reductions in runtime as compared to state-of-the-art implementations, by up to 63.43%. Moreover, our implementation has significantly fewer timeouts compared to baseline and reference implementations, and reduces this number by up to 61%. In fact, our topology based implementation dominates the others with respect to the number of solved instances: given a runtime bound, it solves at least as many instances as any other implementation.