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

Article

Interconnect resource-aware placement for hierarchical FPGAs

Authors:

Ganapathy Parthasarathy,

Malgorzata Marek-SadowskaAuthors Info & Claims

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

Pages 132 - 136

Published: 04 November 2001 Publication History

Abstract

In this paper, we utilize Rent's rule as an empirical measure for efficient clustering and placement of circuits on hierarchical FPGAs. We show that careful matching of design complexity and architecture resources of hierarchical FPGAs can have a positive impact on the overall device area. We propose a circuit placement algorithm based on Rent's parameter and show that our clustering and placement techniques can improve the overall device routing area by as much as 21% for the same array size, when compared to a state-of-art FPGA placement and routing tool.

References

[1]

M.J. Alexander, J.P. Cohoon, J.L. Ganley, G. Robins, "An Architecture-driven approach to FPGA routing using multi-weighted graphs", Proc. Euro-DAC, 1994, pp.259-264.

Digital Library

[2]

E. Bozogzadeh, S. Ogrenci-Memik, M. Sarrafzadeh, "RPack: Routability-driven Packing for Cluster-Based FPGAs", Proceedings, Asia-South Pacific Design Automation Conference, January 2001.

Digital Library

[3]

V. Betz, J. Rose "VPR: A New Packing, Placement and Routing tool for FPGA research", Proc Seventh FPLA, pp. 213-222, 1997.

Digital Library

[4]

V. Betz, J. Rose, "Cluster-Based Logic Blocks for FPGAs:Area-Efficiency vs. Input sharing and Size", IEEE Custom Integrated Circuits Conference, 1997, pp.551-554.

[5]

V. Betz, J. Rose, and A. Marquardt, "Architecture and CAD for Deep-Submicron FPGAs", Kluwer Academic Publishers, 1999.

Digital Library

[6]

S. Brown, J. Rose, Z.G. Vranesic, "A Stochastic model to predict the routability of Field programmable gate arrays", IEEE Trans. on CAD, Dec. 1993, pp.1827-1838.

Digital Library

[7]

P.K. Chan, M.D. Schlag, J.Y. Zien, "On routability prediction for field programmable gate-arrays, Proc. Design Automation Conf. 1993, pp.326-330.

Digital Library

[8]

J. Cong, and Y. Ding, "FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs". IEEE Trans. on Computer-Aided Design, Jan. 1994, Vol. 13, No. 1, pp. 1-12.

[9]

A. DeHon "Balancing Interconnect and Computation in a Reconfigurable Array (or why you don't really want 100% LUT utilization", Proc. FPGA 1999.

Digital Library

[10]

S. Devadas, "Optimal Layout via Boolean Satisfiability", Proc. ICCAD, 1989, pp.294-297.

[11]

W.E. Donath, "Placement and Average Interconnect requirements of Computer logic", IEEE Trans. Circuits and Systems, CAS-26:272-277, 1979.

[12]

A.A.El Gamal, "Two-dimensional stochastic model for interconnections in master-slice integrated circuits", IEEE Trans. on Circuits and Systems, CAS_28:127-138, Feb, 1981

[13]

L. Hagen, A.B. Kahng, F.J. Kurdahi, "On the Intrinsic Rent Parameter and Spectra-based Partitioning Methodologies", IEEE Trans. on CAD, pp.27-36, Vol. 13, No. 1, Jan 1994.

Digital Library

[14]

S. Kirpatrick, C.D. Gelatt, M.P. Vecchi, "Optimization by Simulated Annealing", Science, 220:671-680, 1983.

[15]

B.S. Landman, R.L. Russo, "On a pin versus block relationship for partitions of logic graphs", IEEE Trans. on Computers, C-20:1469-1479, 974.

Digital Library

[16]

H. Van Marck, D. Stroobandt, J. Van Campenhout, "Towards an extension of Rent's rule for describing local variations in interconnect complexity" Proc. 4th Intl. Symposium for Young Computer Scientists, pp.136-141, 1995.

[17]

A. Marquardt, V. Betz and J. Rose, "Using Cluster-Based Logic Blocks and Timing-Driven Packing to Improve FPGA Speed and Density," ACM/SIGDA International Symposium on Field Programmable Gate Arrays, Monterey, CA, February 1999, pp. 37-46.

Digital Library

[18]

D. Stroobandt, P. Verplaeste, J. Van Campenhout, "Generating synthetic benchmark circuits for evaluating CAD tools", IEEE Trans. on CAD, 19(9):1011-1022, September 2000.

Digital Library

[19]

R.G. Wood, R.A. Rutenbar, "FPGA routing and routability estimation using Boolean Satisfiability", Proc. Intl. Symposium on FPGAs" Feb 1997.

Digital Library

[20]

Y.L. Wu, S. Tsukiyama, M. Marek-Sadowska, "Graph based analysis of 2-D FPGA routing" IEEE Trans. CAD, (1):33-44, Jan 1996.

Digital Library

[21]

http://www.xilinx.com

[22]

http://www.altera.com

Cited By

Das JWilton S(2013)Towards development of an analytical model relating FPGA architecture parameters to routabilityACM Transactions on Reconfigurable Technology and Systems10.1145/2499625.24996276:2(1-24)Online publication date: 2-Aug-2013
https://dl.acm.org/doi/10.1145/2499625.2499627
Das JWilton SWawrzynek JCompton K(2011)An analytical model relating FPGA architecture parameters to routabilityProceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1950413.1950449(181-184)Online publication date: 27-Feb-2011
https://dl.acm.org/doi/10.1145/1950413.1950449
Mercaldi MSwanson SPetersen APutnam ASchwerin AOskin MEggers SGibbons PVishkin U(2006)Modeling instruction placement on a spatial architectureProceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures10.1145/1148109.1148137(158-169)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1148109.1148137
Show More Cited By

Index Terms

Interconnect resource-aware placement for hierarchical FPGAs
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Very large scale integration design
    1. Application-specific VLSI designs
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Improved placement for hierarchical FPGAs exploiting local interconnect resources
SBCCI '09: Proceedings of the 22nd Annual Symposium on Integrated Circuits and System Design: Chip on the Dunes

The majority of networks subject to routing in almost every FPGA design consist of networks with only 2 to 4 terminals. These usually connect to directly adjacent logic cells. In order to make best use of this circumstance commercial FPGA architecture ...
Routing-architecture-aware analytical placement for heterogeneous FPGAs
DAC '15: Proceedings of the 52nd Annual Design Automation Conference

Placement is a crucial stage for FPGA implementation. Most FPGA placers optimize their placement results by minimizing half-perimeter wirelength (HPWL). Due to the segmented routing architecture in FPGAs, however, the HPWL function cannot model routed ...
Clock-aware placement for large-scale heterogeneous FPGAs
ICCAD '17: Proceedings of the 36th International Conference on Computer-Aided Design

A modern FPGA often contains an ASIC-like clocking architecture which is crucial to achieve better skew and performance. Existing conventional FPGA placement algorithms seldom consider clocking resources, and thus may lead to clock routing failures. To ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2001

656 pages

ISBN:0780372492

Conference Chair:
Rolf Ernst
Tech. Univ. of Braunschweig, Braunschweig, Germany

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE Circuits & Systems Society
The IEEE Computer Society DATC

Publisher

IEEE Press

Publication History

Published: 04 November 2001

Check for updates

Qualifiers

Article

Conference

ICCAD01

Sponsor:

SIGDA

ICCAD01: International Conference on Computer Aided Design

November 4 - 8, 2001

California, San Jose

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
325
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Das JWilton S(2013)Towards development of an analytical model relating FPGA architecture parameters to routabilityACM Transactions on Reconfigurable Technology and Systems10.1145/2499625.24996276:2(1-24)Online publication date: 2-Aug-2013
https://dl.acm.org/doi/10.1145/2499625.2499627
Das JWilton SWawrzynek JCompton K(2011)An analytical model relating FPGA architecture parameters to routabilityProceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays10.1145/1950413.1950449(181-184)Online publication date: 27-Feb-2011
https://dl.acm.org/doi/10.1145/1950413.1950449
Mercaldi MSwanson SPetersen APutnam ASchwerin AOskin MEggers SGibbons PVishkin U(2006)Modeling instruction placement on a spatial architectureProceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures10.1145/1148109.1148137(158-169)Online publication date: 30-Jul-2006
https://dl.acm.org/doi/10.1145/1148109.1148137
Ran YMarek-Sadowska M(2005)Via-configurable routing architectures and fast design mappability estimation for regular fabricsProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129606(25-32)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129606
Hu BMarek-Sadowska MPileggi LKuehlmann A(2002)Congestion minimization during placement without estimationProceedings of the 2002 IEEE/ACM international conference on Computer-aided design10.1145/774572.774681(739-745)Online publication date: 10-Nov-2002
https://dl.acm.org/doi/10.1145/774572.774681
Mo FBrayton RPileggi LKuehlmann A(2002)Whirlpool PLAsProceedings of the 2002 IEEE/ACM international conference on Computer-aided design10.1145/774572.774652(543-550)Online publication date: 10-Nov-2002
https://dl.acm.org/doi/10.1145/774572.774652
Singh AMarek-Sadowska MSchlag MTrimberger S(2002)Efficient circuit clustering for area and power reduction in FPGAsProceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays10.1145/503048.503058(59-66)Online publication date: 24-Feb-2002
https://dl.acm.org/doi/10.1145/503048.503058

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents