More Web Proxy on the site http://driver.im/

research-article

Postplacement rewiring by exhaustive search for functional symmetries

Authors:

Igor L. Markov,

Valeria BertaccoAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 12, Issue 3

Article No.: 32, Pages 1 - 21

https://doi.org/10.1145/1255456.1255469

Published: 22 May 2008 Publication History

Abstract

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 from the design and reconnect pins according to the symmetries of the subcircuits. To enhance the power of symmetry detection, we also propose a graph-based symmetry detector that can identify permutational and phase-shift symmetries on multiple input and output wires, as well as hybrid symmetries, creating abundant opportunities for rewiring. Our second algorithm, called long-range rewiring, is based on reconnecting equivalent pins and can augment the first approach for further optimization. We apply our techniques for wirelength optimization and observe that they provide wirelength reduction comparable to that achieved by detailed placement.

References

[1]

Adya, S. N., Chaturvedi, S., Roy, J. A., Papa, D. A., and Markov, I. L. 2004. Unification of partitioning, placement and floorplanning. In Proceedings of the ICCAD. 550--557.

Digital Library

[2]

Aloul, F. A., Ramani, A., Markov, I. L., and Sakallah, K. A. 2003. Solving difficult instances of Boolean satisfiability in the presence of symmetry. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 22, 9, 1117--1137.

Digital Library

[3]

Bertacco, V. and Damiani, M. 1997. The disjunctive decomposition of logic functions. In Proceedings of the ICCAD. 78--82.

Digital Library

[4]

Caldwell, A. E., Kahng, A. B., and Markov, I. L. 2000. Can recursive bisection alone produce routable placements? In Proceedings of the DAC. 477--482.

Digital Library

[5]

Caldwell, A. E. and Markov, I. L. 2002. Toward CAD-IP reuse: A web bookshelf of fundamental algorithms. IEEE Des. Test Comput. 19, 3, 72--81.

Digital Library

[6]

Chai, D. and Kuehlmann, A. 2005. Building a better Boolean matcher and symmetry detector. In Proceedings of the IWLS. 391--398.

[7]

Chai, D. and Kuehlmann, A. 2006. A compositional approach to symmetry detection in circuits. In Proceedings of the IWLS. 228--234.

[8]

Chang, C.-W. J., Hsiao, M.-F., Hu, B., Wang, K., Marek-Sadowska, M., Cheng, C.-K., and Chen, S.-J. 2004. Fast postplacement optimization using functional symmetries. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 23, 1, 102--118.

Digital Library

[9]

Chang, C.-W. J. and Marek-Sadowska, M. 2001. Single-Pass redundancy addition and removal. In Proceedings of the ICCAD. 606--609.

Digital Library

[10]

Chang, K.-H., Markov, I. L., and Bertacco, V. 2005. Post-Placement rewiring and rebuffering by exhaustive search for functional symmetries. In Proceedings of the ICCAD. 56--63.

Digital Library

[11]

Chang, K.-H., Markov, I. L., and Bertacco, V. 2006. Keeping physical synthesis safe and sound. Tech. rep. CSE-TR-522-06, University of Michigan.

[12]

Chang, S.-C., Cheng, K.-T., Woo, N. S., and Marek-Sadowska, M. 1997. Postlayout logic restructuring using alternative wires. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 16, 6, 587--596.

Digital Library

[13]

Chang, S.-C., van Ginneken, L. P. P. P., and Marek-Sadowska, M. 1999. Circuit optimization by rewiring. IEEE Trans. Comput. 48, 9, 962--970.

Digital Library

[14]

Cong, J. and Long, W. 2001. Theory and algorithm for SPFD-based global rewiring. In Proceedings of the IWLS. 150--155.

[15]

Darga, P. T., Liffiton, M. H., Sakallah, K. A., and Markov, I. L. 2004. Exploiting structure in symmetry detection for CNF. In Proceedings of the DAC. 530--534.

Digital Library

[16]

Eén, N. and Sörensson, N. 2003. An extensible SAT-solver. In Proceedings of the SAT. 502--518.

[17]

GSRCBookshelf. 2007. http://vlsicad.eecs.umich.edu/BK.

[18]

Hrkic, M., Lillis, J., and Beraudo, G. 2004. An approach to placement-coupled logic replication. In Proceedings of the DAC. 711--716.

Digital Library

[19]

IWLSBenchmarks. 2005. http://iwls.org/iwls2005/benchmarks.html.

[20]

Jiang, Y.-M., Krstic, A., Cheng, K.-T., and Marek-Sadowska, M. 1997. Post-Layout logic restructuring for performance optimization. In Proceedings of the DAC. 662--665.

Digital Library

[21]

Kravets, V. N. and Sakallah, K. A. 2000. Generalized symmetries in Boolean functions. In Proceedings of the ICCAD. 526--532.

Digital Library

[22]

Lu, F., Wang, L.-C., Cheng, K.-T. T., Moondanos, J., and Hanna, Z. 2004. A signal correlation guided circuit-SAT solver. J. UCS 10, 12, 1629--1654.

[23]

Mishchenko, A. 2003. Fast computation of symmetries in Boolean functions. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 22, 11, 1588--1593.

Digital Library

[24]

OpenCores. 2007. http://www.opencores.org/.

[25]

Panda, S., Somenzi, F., and Plessier, B. 1994. Symmetry detection and dynamic variable ordering of decision diagrams. In Proceedings of the ICCAD. 628--631.

Digital Library

[26]

Pomeranz, I. and Reddy, S. M. 1994. On determining symmetries in inputs of logic circuits. IEEE Trans. Comput. Aided Des. Integrated Circ. Syst. 13, 11, 1428--1434.

Digital Library

[27]

Saucy. 2007. http://vlsicad.eecs.umich.edu/bk/saucy/.

[28]

Wang, G., Kuehlmann, A., and Sangiovanni-Vincentelli, A. L. 2003. Structural detection of symmetries in Boolean functions. In Proceedings of the ICCD. 498--503.

Digital Library

[29]

Wllace, D. E. 2001. Recognizing input equivalence in digital logic. In Proceedings of the IWLS. 207--212.

[30]

Wu, Q., Chen, C. Y. R., and Acken, J. M. 1994. Efficent Boolean matching algorithm for cell libraries. In Proceedings of the ICCD. IEEE Computer Society, Washington, DC, 36--39.

Digital Library

[31]

Wu, Y.-L., Long, W., and Fan, H. 2000. A fast graph-based alternative wiring scheme for Boolean networks. In Proceedings of the VLSI Design. 268--273.

Digital Library

Cited By

Kahng ALienig JMarkov IHu JKahng ALienig JMarkov IHu J(2022)Timing ClosureVLSI Physical Design: From Graph Partitioning to Timing Closure10.1007/978-3-030-96415-3_8(223-267)Online publication date: 15-Jun-2022
https://doi.org/10.1007/978-3-030-96415-3_8
Reis AMatos J(2017)Physical Awareness Starting at Technology-Independent Logic SynthesisAdvanced Logic Synthesis10.1007/978-3-319-67295-3_4(69-101)Online publication date: 16-Nov-2017
https://doi.org/10.1007/978-3-319-67295-3_4
Katebi HSakallah KMarkov IHenkel J(2013)Generalized Boolean symmetries through nested partition refinementProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561976(763-770)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561976
Show More Cited By

Index Terms

Postplacement rewiring by exhaustive search for functional symmetries
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Combinatorial techniques for mixed-size placement

While recent literature on circuit layout addresses large-scale standard-cell placement, the authors typically assume that all macros are fixed. Floorplanning techniques are very good at handling macros, but do not scale to hundreds of thousands of ...
Post-placement rewiring and rebuffering by exhaustive search for functional symmetries
ICCAD '05: Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design

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 ...
Improvements on efficiency and efficacy of SPFD-based rewiring for LUT-based circuits

This paper proposes two set-of-pairs-of-functions-to-be-distinguished (SPFD)-based rewiring algorithms to be used in a multi-tier rewiring framework, which employs multiple rewiring techniques. The first algorithm has two unique features: 1) a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 12, Issue 3

August 2007

427 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1255456

Issue’s Table of Contents

Copyright © 2008 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 22 May 2008

Accepted: 01 January 2007

Revised: 01 November 2006

Received: 01 November 2005

Published in TODAES Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
216
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kahng ALienig JMarkov IHu JKahng ALienig JMarkov IHu J(2022)Timing ClosureVLSI Physical Design: From Graph Partitioning to Timing Closure10.1007/978-3-030-96415-3_8(223-267)Online publication date: 15-Jun-2022
https://doi.org/10.1007/978-3-030-96415-3_8
Reis AMatos J(2017)Physical Awareness Starting at Technology-Independent Logic SynthesisAdvanced Logic Synthesis10.1007/978-3-319-67295-3_4(69-101)Online publication date: 16-Nov-2017
https://doi.org/10.1007/978-3-319-67295-3_4
Katebi HSakallah KMarkov IHenkel J(2013)Generalized Boolean symmetries through nested partition refinementProceedings of the International Conference on Computer-Aided Design10.5555/2561828.2561976(763-770)Online publication date: 18-Nov-2013
https://dl.acm.org/doi/10.5555/2561828.2561976
Mishchenko AEen NBrayton RCase MChauhan PSharma NMacii E(2013)A semi-canonical form for sequential AIGsProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485481(797-802)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485481
Kim JKim Y(2013)Efficient statistical leakage analysis using deterministic cell leakage modelsMicroelectronics Journal10.1016/j.mejo.2013.06.01444:9(764-773)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1016/j.mejo.2013.06.014
Shen RTan SWang HXiong J(2012)Fast Statistical Full-Chip Leakage Analysis for Nanometer VLSI SystemsACM Transactions on Design Automation of Electronic Systems10.1145/2348839.234885517:4(1-19)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1145/2348839.2348855
Haghdad KJaffari JAnis M(2012)Power grid analysis and verification considering temperature variationsMicroelectronics Journal10.1016/j.mejo.2011.12.00843:3(189-197)Online publication date: Mar-2012
https://doi.org/10.1016/j.mejo.2011.12.008
Salman EQi Q(2011)Path Specific Register Design to Reduce Standby Power ConsumptionJournal of Low Power Electronics and Applications10.3390/jlpea10101311:1(131-149)Online publication date: 15-Apr-2011
https://doi.org/10.3390/jlpea1010131
Kahng ALienig JMarkov IHu JKahng ALienig JMarkov IHu J(2011)Timing ClosureVLSI Physical Design: From Graph Partitioning to Timing Closure10.1007/978-90-481-9591-6_8(219-264)Online publication date: 27-Jan-2011
https://doi.org/10.1007/978-90-481-9591-6_8
Kim WDo KKim Y(2010)Statistical leakage estimation based on sequential addition of cell leakage currentsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2009.201395618:4(602-615)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1109/TVLSI.2009.2013956
Show More Cited By

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents