Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. SAT Based Exact Synthesis using DAG Topology Families
 
conference paper

SAT Based Exact Synthesis using DAG Topology Families

Haaswijk, Winston  
•
Mishchenko, Alan
•
Soeken, Mathias  
Show more
January 1, 2018
2018 55Th Acm/Esda/Ieee Design Automation Conference (Dac)
55th ACM/ESDA/IEEE Design Automation Conference (DAC)

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3195970.3196111
Web of Science ID

WOS:000446034500130

Author(s)
Haaswijk, Winston  
Mishchenko, Alan
Soeken, Mathias  
De Micheli, Giovanni  
Date Issued

2018-01-01

Publisher

IEEE

Publisher place

New York

Published in
2018 55Th Acm/Esda/Ieee Design Automation Conference (Dac)
ISBN of the book

978-1-4503-5700-5

Subjects

Computer Science, Artificial Intelligence

•

Computer Science, Hardware & Architecture

•

Computer Science

•

graphs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LSI1  
LSI2  
Event nameEvent placeEvent date
55th ACM/ESDA/IEEE Design Automation Conference (DAC)

San Francisco, CA

Jun 24-28, 2018

Available on Infoscience
December 13, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/151845
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés