Efficient circuit clustering for area and power reduction in FPGAs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient circuit clustering for area and power reduction in FPGAs

Full text

Pdf (936 KB)

Source

International Symposium on Field Programmable Gate Arrays archive
Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays table of contents

Monterey, California, USA

Session: Physical Design table of contents

Pages: 59 - 66

Year of Publication: 2002

ISBN:1-58113-452-5

Authors

Amit Singh	University of California, Santa Barbara, Santa Barbara, CA
Malgorzata Marek-Sadowska	University of California, Santa Barbara, Santa Barbara, CA

Sponsor

SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 62, Citation Count: 25

Additional Information:

abstract references cited by collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/503048.503058 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Elaheh Bozorgzadeh , Seda Ogrenci-Memik , Majid Sarrafzadeh, RPack: routability-driven packing for cluster-based FPGAs, Proceedings of the 2001 conference on Asia South Pacific design automation, p.629-634, January 2001, Yokohama, Japan [doi>10.1145/370155.370567]
	2	Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
	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	Vaughn Betz , Jonathan Rose , Alexander Marquardt, Architecture and CAD for Deep-Submicron FPGAs, Kluwer Academic Publishers, Norwell, MA, 1999
	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	Jason Cong , M'Lissa Smith, A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design, Proceedings of the 30th international conference on Design automation, p.755-760, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165119]
	8	Jason Cong , Sung Kyu Lim, Edge separability based circuit clustering with application to circuit partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.429-434, January 2000, Yokohama, Japan [doi>10.1145/368434.368728]
	9	André DeHon, Balancing interconnect and computation in a reconfigurable computing array (or, why you don't really want 100% LUT utilization), Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.69-78, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296431]
	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.
	13	D. J. -H. Huang , A. B. Kahng, When clusters meet partitions: new density-based methods for circuit decomposition, Proceedings of the 1995 European conference on Design and Test, p.60, March 06-09, 1995
	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.
	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	Alexander (Sandy) Marquardt , Vaughn Betz , Jonathan Rose, Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.37-46, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296426]
	19	G. Parthasarathy , M. Marek-Sadowska , Arindam Mukherjee , Amit Singh, Interconnect complexity-aware FPGA placement using Rent's rule, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.115-121, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368806]
	20	Amit Singh , Ganapathy Parthasarathy , Malgorzata Marek-Sadowska, Interconnect resource-aware placement for hierarchical FPGAs, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	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.
	22	http://www.xilinx.com
	23	http://www.altera.com

CITED BY 25

	Amit Singh , Malgorzata Marek-Sadowska, FPGA interconnect planning, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA
	Bo Hu , Malgorzata Marek-Sadowska, Fine granularity clustering for large scale placement problems, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Deming Chen , Jason Cong , Yiping Fan, Low-power high-level synthesis for FPGA architectures, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea
	Fei Li , Deming Chen , Lei He , Jason Cong, Architecture evaluation for power-efficient FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	Deming Chen , Jason Cong, Register binding and port assignment for multiplexer optimization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.68-73, January 27-30, 2004, Yokohama, Japan
	Deming Chen , Jason Cong, Delay optimal low-power circuit clustering for FPGAs with dual supply voltages, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA
	Karl Schabas , Stephen D. Brown, Using logic duplication to improve performance in FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA
	A. Gayasen , Y. Tsai , N. Vijaykrishnan , M. Kandemir , M. J. Irwin , T. Tuan, Reducing leakage energy in FPGAs using region-constrained placement, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA
	Marvin Tom , Guy Lemieux, Logic block clustering of large designs for channel-width constrained FPGAs, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Suresh Srinivasan , A. Gayasen , N. Vijaykrishnan , T. Tuan, Leakage control in FPGA routing fabric, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	David Sheldon , Frank Vahid, A pipelined binary tree as a case study on designing efficient circuits for an FPGA in a bram aware design, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA
	Joey Y. Lin , Deming Chen , Jason Cong, Optimal simultaneous mapping and clustering for FPGA delay optimization, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	David Yeager , Darius Chiu , Guy Lemieux, Congestion estimation and localization in fpgas:: a visual tool for interconnect prediction, Proceedings of the 2007 international workshop on System level interconnect prediction, March 17-18, 2007, Austin, Texas, USA
	Yajun Ran , Malgorzata Marek-Sadowska, Via-configurable routing architectures and fast design mappability estimation for regular fabrics, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.9, p.998-1009, September 2006
	Deming Chen , Jason Cong , Peichen Pan, FPGA Design Automation: A Survey, Foundations and Trends® in Electronic Design Automation, v.1 n.3, p.139-169, January 2006
	Jianhua Li , Laleh Behjat , Jie Huang, An effective clustering algorithm for mixed-size placement, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Marvin Tom , David Leong , Guy Lemieux, Un/DoPack: re-clustering of large system-on-chip designs with interconnect variation for low-cost FPGAs, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Y. Ran , M. Marek-Sadowska, Via-configurable routing architectures and fast design mappability estimation for regular fabrics, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.25-32, November 06-10, 2005, San Jose, CA
	Julien Lamoureux , Steven J. E. Wilton, On the Interaction Between Power-Aware FPGA CAD Algorithms, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.701, November 09-13, 2003
	Taneem Ahmed , Paul D. Kundarewich , Jason H. Anderson , Brad L. Taylor , Rajat Aggarwal, Architecture-specific packing for virtex-5 FPGAs, Proceedings of the 16th international ACM/SIGDA symposium on Field programmable gate arrays, February 24-26, 2008, Monterey, California, USA
	Kyoung-Hwan Lim , YongHwan Kim , Taewhan Kim, Interconnect and communication synthesis for distributed register-file microarchitecture, Proceedings of the 44th annual conference on Design automation, June 04-08, 2007, San Diego, California
	Jason Cong , Junjuan Xu, Simultaneous FU and register binding based on network flow method, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany
	David Sheldon , Frank Vahid, Don't forget memories: a case study redesigning a pattern counting ASIC circuit for FPGAs, Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis, October 19-24, 2008, Atlanta, GA, USA
	Qiang Wang , Subodh Gupta , Jason H. Anderson, Clock power reduction for virtex-5 FPGAs, Proceeding of the ACM/SIGDA international symposium on Field programmable gate arrays, February 22-24, 2009, Monterey, California, USA
	Kristofer Vorwerk , Andrew Kennings , Jonathan W. Greene, Improving simulated annealing-based FPGA placement with directed moves, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, v.28 n.2, p.179-192, February 2009

Collaborative Colleagues:

Amit Singh: colleagues

Malgorzata Marek-Sadowska: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player