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

Article

Free access

Performance-driven simultaneous place and route for island-style FPGAs

Authors:

Rob A. RutenbarAuthors Info & Claims

ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

Pages 332 - 338

Published: 01 December 1995 Publication History

PDF eReader Publisher Site

Abstract

Abstract: Sequential place and route tools for FPGAs are inherently weak at addressing both wirability and timing optimizations. This is primarily due to the difficulty of accurately predicting wirability and delay during placement. A new performance-driven simultaneous placement/routing technique has been developed for island-style FPGA designs. On a set of industrial designs for Xilinx 4000-series FPGAs, our scheme produces 100% routed designs with 8%-15% improvement in delay when compared to the Xilinx XACT5.0 place and route system.

References

[1]

S. K. Nag and R. A. Rutenbar, "Performance-Directed Simultaneous Place and Route for Row-based FPGAs," Proc. ACM/IEEE DAC, June 1994.

Digital Library

[2]

W. Carter et. al., "A User Programmable Reconfigurable Gate Array," Proc. 1986 IEEE CICC, May 1986.

[3]

C. Sechen and K. W. Lee, "An Improved Simulated Annealing Algorithm for Row-Based Placement," Proc. of ICCAD, 1988.

[4]

N. Bhatt and D. Hill, "Routable Technology Mapping for FPGAs", FPGA Workshop, 1992.

[5]

P. K. Chan et. al., "On Routability Prediction for Field Programmable gate Arrays," Proc. 30th DAC, June 1993.

Digital Library

[6]

S. Brown, J. Rose and Z. Vranesic, "A detailed Router for Field-Programmable Gate Arrays", Proceedingss of ICCAD, 1990.

[7]

N. Togawa, M. Sato, and T. Ohtsuki, "Maple: A Simultaneous Technology Mapping, Placement, and Global Routing Algorithm for Field-Programmable Gate Arrays", Proceedings IEEE ICCAD, 1994.

Digital Library

[8]

Y.-W. Chang, S. Thakur, K. Zhu and D.F. Wong, "A New Global Routing Algorithm for FPGAs," Proceedings IEEE ICCAD, 1994.

Digital Library

[9]

J. Frankle, "Iterative and Adaptive Slack Allocation for Performance-driven Layout and FPGA Routing", Proc. of DAC, 1992.

Digital Library

[10]

L.E. McMurchie and C. Ebling, "PathFinder: A Negotiation- Based Performance-Driven Router for FPGAs", Proc. Int'l Symposium on Field-Programmable Gate Arrays, Feb. 1995.

Digital Library

[11]

S. Kirkpatrick et. al., "Optimization by Simulated Anneal- : ing," Science, vol. 220, nO. 4598, 13 May, 1983.

[12]

R. J. Francis et. al., "Chortle: A Technology Mapping Program for Lookup Table-Based Field Programmable Gate Arrays", Proc of 27th DAC, 1990.

Digital Library

[13]

Ercolani and G. De Michelli, "Technology Mapping for Electrically Programmable Gate Arrays", Proc. of 28th DAC, 1991.

Digital Library

[14]

P. S. Sawkar and D. E. Thomas, "Performance Directed Technology Mapping for Table-Look-Up Based FPGAs," Proc. of3Oth DAC, 1993.

Digital Library

[15]

M. D. Huang, F. Romeo and A. Sangiovanni-Vincentelli, "An Efficient Cooling Schedule for Simulated Annealing," Proc. of lCCAD, 1986.

[16]

S. Hustin and A. Sangiovanni-Vincentelli, "TIM, a new standard cell placement program based on simulated annealing algorithm", presented at the IEEE Physical Design Workshop on Placement and Floorplanning, Hilton Head, SC, April 1987.

[17]

C. Y. Lee, "An Algorithm for Path Connections and Its Applications", IRE Transactions on Electronic Computers, 1961.

[18]

F. Rubin, "The Lee Connection Algorithm", IEEE Transactions on Computing, 1974, vol C-23.

[19]

Sudip K. Nag, "Performance-Driven Simultaneous Place and Route for FPGAs", Ph.D. Dissertation, <affiliation deleted>, 1995.

[20]

W. C. Elmore, "The Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers", Journal of Applied Physics, 1948.

Cited By

So KHutton MChow P(2008)Enforcing long-path timing closure for FPGA routing with path searches on clamped lexicographic spiralsProceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays10.1145/1344671.1344677(24-34)Online publication date: 24-Feb-2008
https://dl.acm.org/doi/10.1145/1344671.1344677
Rautela DKatti R(2005)Design and Implementation of FPGA Router for Efficient Utilization of Heterogeneous Routing ResourcesProceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design10.1109/ISVLSI.2005.26(232-237)Online publication date: 11-May-2005
https://dl.acm.org/doi/10.1109/ISVLSI.2005.26
Lee KWong MHauck S(2001)LRouteProceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays10.1145/360276.360290(12-20)Online publication date: 1-Feb-2001
https://dl.acm.org/doi/10.1145/360276.360290
Show More Cited By

Index Terms

Performance-driven simultaneous place and route for island-style FPGAs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Technology mapping algorithms for sequential circuits using look-up table based FPGAS
GLSVLSI '95: Proceedings of the Fifth Great Lakes Symposium on VLSI (GLSVLSI'95)

This paper presents a set of algorithms for mapping sequential circuits onto look-up table based FPGAs and explores how it is possible to reduce the time delay and simplify the final routing results of this mapping. We define several new terms which are ...
Timing-driven partitioning-based placement for island style FPGAs

In traditional field programmable gate array (FPGA) placement methods, there is virtually no coupling between placement and routing. Performing simultaneous placement and detailed routing has been shown to generate much better placement qualities, but ...
Fast timing-driven partitioning-based placement for island style FPGAs
DAC '03: Proceedings of the 40th annual Design Automation Conference

In this paper we propose a partitioning-based placement algorithm for FPGAs. The method incorporates simple, but effective heuristics that target delay minimization. The placement engine incorporates delay estimations obtained from previously placed and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design

December 1995

748 pages

ISBN:0818672137

Chairman:
Richard Rudell
Synopsys, Inc., Mountain View, CA

Copyright © Copyright (c) 1995 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 December 1995

Check for updates

Author Tags

Qualifiers

Article

Conference

ICCAD '95

Sponsor:

SIGDA
IEEE-CS

ICCAD '95: International Conference on Computer Aided Design

November 5 - 9, 1995

California, San Jose, USA

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
321
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)29

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

So KHutton MChow P(2008)Enforcing long-path timing closure for FPGA routing with path searches on clamped lexicographic spiralsProceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays10.1145/1344671.1344677(24-34)Online publication date: 24-Feb-2008
https://dl.acm.org/doi/10.1145/1344671.1344677
Rautela DKatti R(2005)Design and Implementation of FPGA Router for Efficient Utilization of Heterogeneous Routing ResourcesProceedings of the IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design10.1109/ISVLSI.2005.26(232-237)Online publication date: 11-May-2005
https://dl.acm.org/doi/10.1109/ISVLSI.2005.26
Lee KWong MHauck S(2001)LRouteProceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays10.1145/360276.360290(12-20)Online publication date: 1-Feb-2001
https://dl.acm.org/doi/10.1145/360276.360290
Chang YChang YDe Micheli G(2000)An architecture-driven metric for simultaneous placement and global routing for FPGAsProceedings of the 37th Annual Design Automation Conference10.1145/337292.337582(567-572)Online publication date: 1-Jun-2000
https://dl.acm.org/doi/10.1145/337292.337582
Marquardt ABetz VRose JTrimberger SHauck S(2000)Timing-driven placement for FPGAsProceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays10.1145/329166.329208(203-213)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.1145/329166.329208
Wood RRutenbar REbeling C(1997)FPGA routing and routability estimation via Boolean satisfiabilityProceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays10.1145/258305.258322(119-125)Online publication date: 9-Feb-1997
https://dl.acm.org/doi/10.1145/258305.258322

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten