Article

Post-placement rewiring and rebuffering by exhaustive search for functional symmetries

Authors:

V. BertaccoAuthors Info & Claims

ICCAD '05: Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design

Pages 56 - 63

Published: 31 May 2005 Publication History

Abstract

Separate optimizations of logic and layout have been thoroughly studied in the past and are well documented for common benchmarks. However, to be competitive, modern circuit optimizations must use physical and logic information simultaneously. In this work, we propose new algorithms for rewiring and rebuffering - a post-placement optimization that reconnects pins of a given netlist without changing the logic function and gate locations. These techniques are compatible with separate layout and logic optimizations, and appear independent of them. In particular, when the new optimization is applied before or after detailed placement, it approximately doubles the improvement in wirelength. Our contributions are based on exhaustive search for functional symmetries in sub-circuits consisting of several gates. Our graph-based symmetry finding is more comprehensive than previously known algorithms - it detects permutational and phase-shift symmetries on multiple input and output wires, as well as hybrid symmetries, creating more opportunities for rewiring and rebuffering.

References

[1]

{1} S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa and I. L. Markov, "Unification of Partitioning, Floorplanning and Placement", ICCAD, 2004, pp. 550-557.

Digital Library

[2]

{2} F. A. Aloul, A. Ramani, I. L. Markov, and K. A. Sakallah, "Solving Difficult Instances of Boolean Satisfiability in the Presence of Symmetry", IEEE Trans. on CAD, Sep. 2003, pp. 1117-1137.

Digital Library

[3]

{3} V. Bertacco and M. Damiani, "Boolean Function Representation Based on Disjoint-Support Decompositions", ICCD, Oct. 1996, pp. 27-32.

Digital Library

[4]

{4} A. E. Caldwell, A. B. Kahng and I. L. Markov, "Can Recursive Bisection Alone Produce Routable Placements?", DAC, 2000, pp. 693-698.

Digital Library

[5]

{5} A. E. Caldwell, A. B. Kahng and I. L. Markov, "Toward CAD-IP Reuse: The MARCO GSRC Bookshelf of Fundamental CAD Algorithms", IEEE Design and Test, May 2002, pp. 72-81.

Digital Library

[6]

{6} http://vlsicad.eecs.umich.edu/BK/PlaceUtils/

[7]

{7} C. W. Chang, M. F. Hsiao, B. Hu, K. Wang, M. Marek-Sadowska, C. H. Cheng, and S. J. Chen, "Fast Postplacement Optimization Using Functional Symmetries", IEEE Trans. on CAD, Jan. 2004, pp. 102-118.

Digital Library

[8]

{8} C. W. Chang and M. Marek-Sadowska, "Single-Pass Redundancy Addition and Removal", ICCAD, Nov. 2001, pp. 606-609.

Digital Library

[9]

{9} S. C. Chang, L. P. P. P. van Ginneken, and M. Marek-Sadowska, "Circuit Optimization by Rewiring," IEEE Trans. on Computers, Sep. 1999, pp. 962-969.

Digital Library

[10]

{10} J. Cong and W. Long, "Theory and Algorithm for SPFD-Based Global Rewiring", IWLS, June 2001, pp. 150-155.

[11]

{11} P. T. Darga, M. H. Liffiton, K. A. Sakallah, and I. L. Markov, "Exploiting Structure in Symmetry Detection for CNF", DAC, 2004, pp. 530-534.

Digital Library

[12]

{12} N. Eén and N. Söorensson, "An Extensible SAT-solver", Theory and Apps of Satisfiability Testing, SAT, 2003, pp. 502-518.

[13]

{13} V. N. Kravets and K. A. Sakallah, "Generalized Symmetries in Boolean Functions", ICCAD, 2000, pp. 526-523.

Digital Library

[14]

{14} V. N. Kravets, "Constructive Multi-Level Synthesis by Way of Functional Properties", Ph. D. Thesis, Univ. of Michigan, 2001.

Digital Library

[15]

{15} A. Mishchenko, "Fast Computation of Symmetries in Boolean Functions", IEEE Trans. on CAD, Nov. 2003, pp. 1588-1593.

Digital Library

[16]

{16} D. Moller, J. Mohnke, and M. Weber, "Detection of Symmetry of Boolean Functions Represented by ROBDDs", ICCAD, 1993, pp. 680-684.

Digital Library

[17]

{17} S. Panda, F. Somenzi, and B. F. Plessier, "Symmetry Detection and Dynamic Variable Ordering of Decision Diagrams", ICCAD, 1994, pp. 628-631.

Digital Library

[18]

{18} D. E. Wallace, "Recognizing input equivalence in digital logic", IWLS, 2001, pp. 207-212.

[19]

{19} G. Wang, A. Kuehlmann, and A. Sangiovanni-Vincentelli, "Structural Detection of Symmetries in Boolean Functions", ICCD, 2003, pp. 498-503

Digital Library

[20]

{20} Y. L. Wu, W. Long, and H. Fan, "A Fast Graph-Based Alternative Wiring Scheme for Boolean Networks", International VLSI Design Conference, 2000, pp. 268-273.

Digital Library

[21]

{21} S. Yamashita, H. Sawada, and A. Nagoya, "A New Method to Express Functional Permissibilities for LUT Based FPGAs and Its Applications", ICCAD, 1996, pp. 254-261.

Digital Library

Cited By

Yuan KKuo CJiang JLi MHenkel J(2013)Encoding multi-valued functions for symmetryProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561977(771-778)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561977
Xiang HRen HTrevillyan LReddy LPuri RCho MSaxena PChang Y(2010)Logical and physical restructuring of fan-in treesProceedings of the 19th international symposium on Physical design10.1145/1735023.1735046(67-74)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.1145/1735023.1735046
Wu KMarculescu DBenini LDe Micheli GAl-Hashimi BMueller W(2009)Joint logic restructuring and pin reordering against NBTI-induced performance degradationProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874640(75-80)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874640
Show More Cited By

Recommendations

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 ...
Fast post-placement rewiring using easily detectable functional symmetries
DAC '00: Proceedings of the 37th Annual Design Automation Conference

Timing convergence problem arises when the estimations made during logic synthesis can not be met during physical design. In this paper, an efficient rewiring engine is proposed to explore maximal freedom after placement. The most important feature of ...
Post-Placement Pin Optimiztion
ISVLSI '05: Proceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design

Pin assignment is the process of placing pins on the boundary of a chip or macro during chip design. Problem is that cell placement and pin assignment form a chicken and egg problem: cell placement needs pin positions, while pin positions should be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '05: Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design

May 2005

1032 pages

ISBN:078039254X

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 31 May 2005

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
104
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yuan KKuo CJiang JLi MHenkel J(2013)Encoding multi-valued functions for symmetryProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561977(771-778)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561977
Xiang HRen HTrevillyan LReddy LPuri RCho MSaxena PChang Y(2010)Logical and physical restructuring of fan-in treesProceedings of the 19th international symposium on Physical design10.1145/1735023.1735046(67-74)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.1145/1735023.1735046
Wu KMarculescu DBenini LDe Micheli GAl-Hashimi BMueller W(2009)Joint logic restructuring and pin reordering against NBTI-induced performance degradationProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874640(75-80)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874640
Chang KMarkov IBertacco V(2008)Postplacement rewiring by exhaustive search for functional symmetriesACM Transactions on Design Automation of Electronic Systems10.1145/1255456.125546912:3(1-21)Online publication date: 22-May-2008
https://dl.acm.org/doi/10.1145/1255456.1255469
Chang KMarkov IBertacco VGielen G(2007)Automating post-silicon debugging and repairProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326093(91-98)Online publication date: 5-Nov-2007
https://dl.acm.org/doi/10.5555/1326073.1326093
Papa DMarkov IChong PHirose F(2006)Utility of the OpenAccess database in academic researchProceedings of the 2006 Asia and South Pacific Design Automation Conference10.1145/1118299.1118408(440-441)Online publication date: 24-Jan-2006
https://dl.acm.org/doi/10.1145/1118299.1118408

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents