Cited By
View all- Yu CXiao HDe Micheli G(2018)Developing synthesis flows without human knowledgeProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196026(1-6)Online publication date: 24-Jun-2018
Advanced datapath synthesis using graph isomorphism
Abstract
This paper presents an advanced DAG-based algorithm for datapath synthesis that targets area minimization using logic-level resource sharing. The problem of identifying common specification logic is formulated using unweighted graph isomorphism problem, in contrast to a weighted graph isomorphism using AIGs. In the context of gate-level datapath circuits, our algorithm solves the unweighted graph isomorphism problem in linear time. The experiments are conducted within an industrial synthesis flow that includes the complete high-level synthesis, logic synthesis and placement and route procedures. Experimental results show a significant runtime improvements compared to the existing datapath synthesis algorithms.
References
[1]
L. Stok, "Data path synthesis," Integration, the VLSI journal, vol. 18, no. 1, pp. 1--71, 1994.
[2]
G. D. Micheli, Synthesis and Optimization of Digital Circuits. McGraw-Hill Higher Education, 1994.
[3]
M. Potkonjak and J. Rabaey, "Optimizing Resource Utilization using Transformations," Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 13, no. 3, pp. 277--292, 1994.
[4]
M. B. Srivastava and M. Potkonjak, "Optimum and Heuristic Transformation Techniques for Simultaneous Optimization of Latency and Throughput," Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, vol. 3, no. 1, pp. 2--19, 1995.
[5]
J. Cong and J. Xu, "Simultaneous FU and Register Binding-based on Network Flow Method," in Design, Automation and Test in Europe, 2008. DATE'08. IEEE, 2008, pp. 1057--1062.
[6]
S. Roy, M. Choudhury, R. Puri, and D. Z. Pan, "Towards optimal performance-area trade-off in adders by synthesis of parallel prefix structures," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 10, pp. 1517--1530, 2014.
[7]
C. Yu, M. J. Ciesielski, M. Choudhury, and A. Sullivan, "Dag-aware logic synthesis of datapaths," in Proceedings of the 53rd Annual Design Automation Conference, DAC 2016, Austin, TX, USA, June 5--9, 2016, 2016, pp. 135:1--135:6.
[8]
A. Mishchenko, S. Chatterjee, and R. Brayton, "DAG-aware AIG Rewriting A Fresh Look at Combinational Logic Synthesis," in 43rd DAC. ACM, 2006, pp. 532--535.
[9]
S. Umeyama, "An eigendecomposition approach to weighted graph matching problems," IEEE transactions on pattern analysis and machine intelligence, vol. 10, no. 5, pp. 695--703, 1988.
[10]
A. Mishchenko et al., "ABC: A System for Sequential Synthesis and Verification," URL http://www.eecs.berkeley.edu/alanmi/abc, 2010.
[11]
E. Goldberg, "Equivalence Checking of Dissimilar Circuits II," Technical report, Tech. Rep., 2004.
[12]
R. E. Bryant, "Graph-based Algorithms for Boolean Function Manipulation," Computers, IEEE Transactions on, vol. 100, no. 8, pp. 677--691, 1986.
[13]
A. Kuehlmann and F. Krohm, "Equivalence checking using cuts and heaps," in Proceedings of the 34th annual Design Automation Conference. ACM, 1997, pp. 263--268.
[14]
E. Goldberg, M. Prasad, and R. Brayton, "Using sat for combinational equivalence checking," in Proceedings of the conference on Design, automation and test in Europe. IEEE Press, 2001, pp. 114--121.
[15]
M. Soeken, B. Sterin, R. Drechsler, and R. Brayton, "Simulation graphs for reverse engineering," in Proceedings of 15th FMCAD. FMCAD, 2015, pp. 152--159.
[16]
W. Li, H. Saidi, H. Sanchez, M. Schäf, and P. Schweitzer, "Detecting similar programs via the weisfeiler-leman graph kernel," in International Conference on Software Reuse. Springer, 2016, pp. 315--330.
[17]
S. Mitra, L. J. Avra, and E. J. McCluskey, "Efficient multiplexer synthesis techniques," IEEE Design & Test of Computers, vol. 17, no. 4, pp. 90--97, 2000.
[18]
L. Stok, D. Kung, and et al., "BooleDozer: Logic Synthesis for ASICs," IBM Journal of Research and Development, vol. 40, no. 4, pp. 407--430, 1996.
Recommendations
DAG-aware logic synthesis of datapaths
DAC '16: Proceedings of the 53rd Annual Design Automation ConferenceTraditional datapath synthesis for standard-cell designs go through extraction of arithmetic operations from the high-level description, high-level synthesis, and netlist generation. In this paper, we take a fresh look at applying high-level synthesis ...
Advanced datapath synthesis using graph isomorphism
2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)This paper presents an advanced DAG-based algorithm for datapath synthesis that targets area minimization using logic-level resource sharing. The problem of identifying common specification logic is formulated using unweighted graph isomorphism problem, ...
Dataflow Graph Partitioning for Area-Efficient High-Level Synthesis with Systems Perspective
Area efficiency in datapath synthesis is a widely accepted goal of high-level synthesis. Applications represented by their dataflow graphs are synthesized using resource sharing principles to reduce the area. However, existing resource sharing ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- CEDA: Council on Electronic Design Automation
- SIGDA: ACM Special Interest Group on Design Automation
- IEEE-CAS: Circuits & Systems
In-Cooperation
- IEEE-EDS: Electronic Devices Society
Publisher
IEEE Press
Publication History
Published: 13 November 2017
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ICCAD '17
Sponsor:
- CEDA
- SIGDA
- IEEE-CAS
ICCAD '17: IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN
November 13 - 16, 2017
California, Irvine
Acceptance Rates
Overall Acceptance Rate 457 of 1,762 submissions, 26%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 59Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)1
Reflects downloads up to 02 Mar 2025
Other Metrics
Citations
Cited By
View all- Yu CXiao HDe Micheli G(2018)Developing synthesis flows without human knowledgeProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196026(1-6)Online publication date: 24-Jun-2018
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in