skip to main content
10.1145/1353629.1353652acmconferencesArticle/Chapter ViewAbstractPublication PagesispdConference Proceedingsconference-collections
research-article

A framework for layout-level logic restructuring

Published: 13 April 2008 Publication History

Abstract

It is well known that optimizations made by traditional logic synthesis tools often correlate poorly with post-layout performance; this is largely a result of interconnect effects only visible after layout. As a result, several attempts at physically aware logic synthesis have been made (e.g.,[2], [9], [14], [4], [7], [12], [16], [15]). In this paper a corrective methodology is proposed for timing-driven logic restructuring at the placement level; the approach currently focuses on LUT-based FPGAs.
Driven by placement level static timing analysis, the method induces relatively large, timing-critical fan-in trees via (temporary) replication as in [9]. Such trees are then reimplemented where the degrees of freedom include functional decomposition of LUTs, subject graph covering/mapping, and physical embedding. A dynamic programming algorithm optimizes over all of these freedoms simultaneously. All simple disjoint decompositions (i.e., Ashenhurst style) are encoded in the subject tree/graph using choice nodes similar to those in [11]. At the same time, because embedding is done simultaneously, interconnect delay is directly taken into account
We have implemented the framework and in many cases we were able to approach a fixed flip-flop lower-bound on achievable clock period. Promising experimental results are reported with average 14.8% (up to 37.4%) clock period reduction compared with the timing-driven placement from VPR [13] and average 6.6% (upto 17%) reduction compared with the basic fan-in tree embedder from [9].

References

[1]
Ashenhurst, R. L.: The decomposition of switching functions. The annals of the Harvard computation laboratory, XXIX:74--116, 1959.
[2]
G. Beraudo and J. Lillis. Timing optimization of FPGA placements by logic replication. In Proc. of ACM/IEEE DAC, pages 196--201, June 2003.
[3]
K. C. Chen, J. Cong, Y. Ding, A. Kahng, and P. Trajmar. DAG-map: graph-based FPGA technology mapping for delay optimization. IEEE Design & Test, pages 7--20, Sept. 1992.
[4]
G. Chen and J. Cong. Simultaneous timing-driven placement and duplication. In Proc. of ISFPGAs, pages 51--59, Feb. 2005.
[5]
J. Cong, Y. Ding, An optimal technology mapping algorithm for delay minimization in lookup-table based FPGA designs, ICCAD, 1992.
[6]
R. J. Francis, J. Rose, Z. Vranesic, Chortle-crf: Fast Technology Mapping for Lookup Table-Based FPGA, DAC, 1991.
[7]
H. Kim, J. Lillis, and M. Hrkić. Techniques for Improved Placement Coupled Logic Replication. GLSVLSI, 2006.
[8]
Kohavi, Z.: Switching and Finite Automata Theory. McGraw-Hill Book Company, 1978.
[9]
M. Hrkić, J. Lillis, and G. Beraudo. An approach to placement-coupled logic replication. IEEE TCAD, vol. 20, issue 11, 2006.
[10]
Y. Kukimoto, R. Brayton, and P. Sawkar. Delay-optimal technology mapping by DAG covering. In DAC, 1998.
[11]
E. Lehman, Y. Watanabe, J. Grodstein, and H. Harkness. Logic decomposition during technology mapping, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 16(8):813--834, August 1997.
[12]
J. Lin, A. Jagannathan, and J. Cong, Placement-Driven Technology Mapping for LUT-Based FPGAs, ISFPGAs, 2003.
[13]
A. Marquardt, V. Betz, and J. Rose. Timing-driven placement for FPGAs. In ISFPGAs, 2000.
[14]
K. Schabas and S. D. Brown. Using logic duplication to improve performance in FPGAs. In Proc. of ISFPGAs, 2003.
[15]
D. Singh, S. Brown, An area-efficient timing closure technique for FPGAs using Shannon's expansion, Integration, the VLSI Journal, vol. 40, Issue 2, Feb. 2007.
[16]
P. Suaris, L. Liu, Y. Ding, N. Chou, Incremental Physical Resynthesis for Timing Optimization, ISFPGAs, 2004.
[17]
A. Srivastava, R. Kastner, and M. Sarrafzadeh. Timing driven gate duplication: Complexity issues and algorithms. In Proc. of ICCAD, 2000.

Cited By

View all
  • (2013)Mountain-mover: An intuitive logic shifting heuristic for improving timing slack violating paths2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2013.6509620(350-355)Online publication date: Jan-2013
  • (2009)Physical optimization for FPGAs using post-placement topology rewritingProceedings of the 2009 international symposium on Physical design10.1145/1514932.1514955(91-98)Online publication date: 29-Mar-2009

Index Terms

  1. A framework for layout-level logic restructuring

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISPD '08: Proceedings of the 2008 international symposium on Physical design
    April 2008
    218 pages
    ISBN:9781605580487
    DOI:10.1145/1353629
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 April 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. logic resynthesis
    2. timing optimization

    Qualifiers

    • Research-article

    Conference

    ISPD '08
    Sponsor:
    ISPD '08: International Symposium on Physical Design
    April 13 - 16, 2008
    Oregon, Portland, USA

    Acceptance Rates

    Overall Acceptance Rate 62 of 172 submissions, 36%

    Upcoming Conference

    ISPD '25
    International Symposium on Physical Design
    March 16 - 19, 2025
    Austin , TX , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)5
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2013)Mountain-mover: An intuitive logic shifting heuristic for improving timing slack violating paths2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2013.6509620(350-355)Online publication date: Jan-2013
    • (2009)Physical optimization for FPGAs using post-placement topology rewritingProceedings of the 2009 international symposium on Physical design10.1145/1514932.1514955(91-98)Online publication date: 29-Mar-2009

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media