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

Article

Efficient circuit clustering for area and power reduction in FPGAs

Authors:

Malgorzata Marek-SadowskaAuthors Info & Claims

FPGA '02: Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays

Pages 59 - 66

https://doi.org/10.1145/503048.503058

Published: 24 February 2002 Publication History

Abstract

We present a routability-driven bottom-up clustering technique for area and power reduction in clustered FPGAs. This technique uses a cell connectivity metric to identify seeds for efficient clustering. Effective seed selection, coupled with an interconnect-resource aware clustering and placement, can have a favorable impact on circuit routability. It leads to better device utilization, savings in area, and reduction in power consumption. Routing area reduction of 35% is achieved over previously published results. Power dissipation simulations using a buffered pass-transistor-based FPGA interconnect model are presented. They show that our clustering technique can reduce the overall device power dissipation by an average of 13%.

References

[1]

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

[2]

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

Digital Library

[3]

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.

[4]

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

Digital Library

[5]

J. Cong, L. W. Hagen, and A.B. Kahng, "Random Walks for Circuit Clustering", Proc IEEE Conf. on ASIC pp. 14.2.1 -14.2.4, June 1991.

[6]

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.

[7]

J. Cong and M. Smith, "A Parallel Bottom-up Clustering Algorithm with Applications to Circuit Partitioning in VLSI Design", Proc Design Automation Conf, 1993, pp. 755-60.

Digital Library

[8]

J. Cong and S. K. Lim, "Edge Separability based Circuit Clustering With Application to Circuit Partitioning", IEEE/ACM Asia South Pacific Design Automation Conference, pp. 429- 434, 2000.

Digital Library

[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]

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

[11]

J. Garbers, H.J. Promel, and A. Steger, "Finding Clusters in VLSI Circuits", ICCAD 1990, pp. 520-523.

[12]

L. W. Hagen and A. B. Kahng, "Combining Problem Reduction and Adaptive Multi-Start: A New Technique for Superior Iterative Partitioning", IEEE Transactions on Computer-Aided Design, 1997, pp. 709-717.

Digital Library

[13]

D. J.H Huang and A. B. Kahng, "When Clusters Meet Partitions: New Density-Based Methods for Circuit Decomposition", Proc European Design and Test Conf, 1995, pp. 60-64.

Digital Library

[14]

A. B. Kahng and R. Sharma, "Studies of Clustering Objectives and Heuristics for Improved Standard-Cell Placement", UCLA CS Dept report, January 1997.

[15]

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

[16]

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

[17]

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.

[18]

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

[19]

G. Parthasarathy, M. Marek-Sadowska, A. Mukherjee, A. Singh, "Interconnect-Complexity Aware Placement for FPGAs using Rent's Rule", Proc. of 3rd System Level Interconnect Prediction Workshop, April 2001.

Digital Library

[20]

A. Singh, G. Parthasarathy, M. Marek-Sadowska, "Interconnect- Resource Aware Placement for Hierarchical FPGAs", Proceedings of International Conference on Computer-Aided Design, November 2001.

Digital Library

[21]

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

[22]

http://www.xilinx.com

[23]

http://www.altera.com

Cited By

Thurmer KBetz V(2024)VIPER: A VTR Interface for Placement with Error ResilienceProceedings of the 14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3665283.3665300(99-108)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3665283.3665300
Tu KTang XYu CJosipović LChu ZTu KTang XYu CJosipović LChu Z(2024)Physical ImplementationFPGA EDA10.1007/978-981-99-7755-0_10(165-206)Online publication date: 1-Feb-2024
https://doi.org/10.1007/978-981-99-7755-0_10
Murray KPetelin OZhong SWang JEldafrawy MLegault JSha EGraham AWu JWalker MZeng HPatros PLuu JKent KBetz V(2020)VTR 8ACM Transactions on Reconfigurable Technology and Systems10.1145/338861713:2(1-55)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.1145/3388617
Show More Cited By

Recommendations

Efficient circuit clustering for area and power reduction in FPGAs

We utilize Rent's rule as an empirical measure for efficient clustering and placement of circuits in clustered Field Programmable Gate Arrays (FPGAs). We show that careful matching of resource availability and design complexity during the clustering and ...
Delay optimal low-power circuit clustering for FPGAs with dual supply voltages
ISLPED '04: Proceedings of the 2004 international symposium on Low power electronics and design

This paper presents a delay optimal FPGA clustering algorithm targeting low power. We assume that the configurable logic blocks of the FPGA can be programmed using either a high supply voltage (high-Vdd) or a low supply voltage (low-Vdd). We carry out ...
Clock power reduction for virtex-5 FPGAs
FPGA '09: Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays

Clock network power in field-programmable gate arrays (FPGAs) is considered and two complementary approaches for clock power reduction in the Xilinx Virtex-5 FPGA are presented. The approaches are unique in that they leverage specific architectural ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FPGA '02: Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays

February 2002

257 pages

ISBN:1581134525

DOI:10.1145/503048

General Chair:
Martine Schlag,
Program Chair:
Steve Trimberger

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

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 February 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

FPGA02

Sponsor:

SIGDA

FPGA02: ACM/SIGDA International Symposium on Field Programmable Gate Arrays

February 24 - 26, 2002

California, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

70
Total Citations
View Citations
857
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Thurmer KBetz V(2024)VIPER: A VTR Interface for Placement with Error ResilienceProceedings of the 14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3665283.3665300(99-108)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3665283.3665300
Tu KTang XYu CJosipović LChu ZTu KTang XYu CJosipović LChu Z(2024)Physical ImplementationFPGA EDA10.1007/978-981-99-7755-0_10(165-206)Online publication date: 1-Feb-2024
https://doi.org/10.1007/978-981-99-7755-0_10
Murray KPetelin OZhong SWang JEldafrawy MLegault JSha EGraham AWu JWalker MZeng HPatros PLuu JKent KBetz V(2020)VTR 8ACM Transactions on Reconfigurable Technology and Systems10.1145/338861713:2(1-55)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.1145/3388617
Wang YTrefzer MBale SWalker JTyrrell A(2019)Multi‐objective optimisation algorithm for routability and timing driven circuit clustering on FPGAsIET Computers & Digital Techniques10.1049/iet-cdt.2018.511513:4(273-281)Online publication date: 19-Feb-2019
https://doi.org/10.1049/iet-cdt.2018.5115
Singhal LIyer MAdya S(2017)LSCProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062279(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062279
Hutton MBetz VAnderson J(2016)FPGA Synthesis and Physical DesignElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-18(373-413)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-18
Mehri HAlizadeh B(2015)Analytical performance model for FPGA-based reconfigurable computingMicroprocessors & Microsystems10.1016/j.micpro.2015.09.00939:8(796-806)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.micpro.2015.09.009
Pangracious VMarrakchi ZMehrez HPangracious VMarrakchi ZMehrez H(2015)Two Dimensional FPGAs: Configuration and CAD FlowThree-Dimensional Design Methodologies for Tree-based FPGA Architecture10.1007/978-3-319-19174-4_4(73-94)Online publication date: 26-Jun-2015
https://doi.org/10.1007/978-3-319-19174-4_4
Feng WGreene JVorwerk KPevzner VKundu ABetz VConstantinides G(2014)Rent's rule based FPGA packing for routability optimizationProceedings of the 2014 ACM/SIGDA international symposium on Field-programmable gate arrays10.1145/2554688.2554763(31-34)Online publication date: 26-Feb-2014
https://dl.acm.org/doi/10.1145/2554688.2554763
Liu HRajavel SAkoglu A(2013)Integration of Net-Length Factor with Timing- and Routability-Driven Clustering AlgorithmsACM Transactions on Reconfigurable Technology and Systems10.1145/25173246:3(1-21)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1145/2517324
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents