Detecting support-reducing bound sets using two-cofactor symmetries
Authors: 
Jin S. Zhang, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Jerry R. BurchAuthors Info & Claims
Pages 266 - 271
Abstract
Detecting support-reducing bound sets is an important step in Boolean decomposition. It affects both the quality and the runtime of several applications in technology mapping and re-synthesis. This paper presents an efficient heuristic method for detecting support-reducing bound sets using two-cofactor symmetries. Experiments on the MCNC and ITC benchmarks show an average 40x speedup over the published exhaustive method for bound set construction.
References
[1]
A. Mishchenko, X. Wang, and T. Kam. "A new enhanced constructive decomposition and mapping algorithm". Proc. DAC '03, pp. 143--147, June 2003.
[2]
V. N. Kravets. "Constructive multi-level synthesis by way of functional properties", PhD Thesis, University of Michigan, 2001.
[3]
V. N. Kravets and K. A. Sakallah. "Constructive library-aware synthesis using symmetries", Proc. DATE '00, pp. 208--216, 2000.
[4]
V. N. Kravets and K. A. Sakallah. "Re-synthesis of multi-level circuits under tight constraints using symbolic optimization", Proc. ICCAD '02, pp. 687--693, 2002.
[5]
R. L. Ashenhurst. "The decomposition of switching functions", Computational Lab, Harvard University, Vol. 29, pp. 74--116, 1959.
[6]
A. Curtis. "New approach to the design of switching circuits", Van Nostrand, Princeton, NJ, 1962.
[7]
R. E. Bryant. "Graph-based algorithms for Boolean function manipulation", IEEE Trans. Comp., Vol. C-35, No. 8, pp. 677--692, August 1986.
[8]
Y. T. Lai, M. Pedram and S. B. K. Vrudhula. "BDD-based decomposition of logic functions with applications to FPGA synthesis", Proc. DAC '93, pp. 642--647, 1993.
[9]
T. Sasao. "FPGA design by generalized functional decomposition", In T. Sasao (ed.), Logic Synthesis and Optimization, Kluwer Academic publishers, 1993.
[10]
C. R. Edward and S. L. Hurst. "A digital synthesis procedure under function symmetries and mapping methods", IEEE Trans. On Computers, vol. C-27, No.11, pp. 985--997, November 1978.
[11]
B.-G. Kim and D. L. Dietmeyer. "Multilevel logic synthesis of symmetric switching functions", IEEE Trans. CAD, 10(4), pp.436--446, April 1991.
[12]
Y.-T. Lai, S. Sastry, and M. Pedram. "Boolean matching using binary decision diagrams with applications to logic synthesis and verification", Proc. ICCAD, pp. 452--458, October 1992.
[13]
Ch. Scholl, D. Möller, P. Molitor, and R. Drechsler. "BDD minimization using symmetries", IEEE Trans. CAD, 18(2) pp. 81--100, February 1999.
[14]
M. Chrzanowska-Jeske, W. Wang, J. Xia, and M. Jeske. "Disjunctive decomposition of switching functions using symmetry information," Proc IEEE SBCCI '00, pp. 67, September 2000.
[15]
V. Bertacco and M. Damiani. "Disjunctive decomposition of logic functions", Proc. ICCAD '97, pp. 78--82, 1997.
[16]
J. S. Zhang, M. Chrzanowska-Jeske, A. Mishchenko, and J. R. Burch. "Fast computation of generalized symmetries in Boolean functions", Proc. IWLS '04, pp. 424--430, June 2004.
[17]
F. Somenzi. CUDD Package, Release 2.3.1. http://vlis.Colorado.EDU/~fabio/CUDD/cuddIntro.html
[18]
A. Mishchenko. EXTRA Library of DD procedures. http://www.ee.pdx.edu/~alanmi/research/extra.htm
Recommendations
Spherical two-distance sets
A set S of unit vectors in n-dimensional Euclidean space is called spherical two-distance set, if there are two numbers a and b so that the inner products of distinct vectors of S are either a or b. It is known that the largest cardinality g(n) of ...
Postplacement rewiring by exhaustive search for functional symmetries
We propose two new algorithms for rewiring: a postplacement optimization that reconnects pins of a given netlist without changing the logic function and gate locations. In the first algorithm, we extract small subcircuits consisting of several gates ...
An upper bound for the number of independent sets in regular graphs
Write I(G) for the set of independent sets of a graph G and i(G) for |I(G)|. It has been conjectured (by Alon and Kahn) that for an N-vertex, d-regular graph G, i(G)@?(2^d^+^1-1)^N^/^2^d. If true, this bound would be tight, being achieved by the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2005 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
- IEEE SSCS Shanghai Chapter
- IEEE Beijing Section
- SIGDA: ACM Special Interest Group on Design Automation
- Fudan University
- IEEE CAS
- Chinese Institute of Electronics
- Shanghai IC Industry Association
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 18 January 2005
Check for updates
Qualifiers
- Article
Conference
ASPDAC05
Sponsor:
Acceptance Rates
Overall Acceptance Rate 466 of 1,454 submissions, 32%
Upcoming Conference
ASPDAC '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 56Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
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