Article

Fine granularity clustering for large scale placement problems

Authors:

Malgorzata Marek-SadowskaAuthors Info & Claims

ISPD '03: Proceedings of the 2003 international symposium on Physical design

Pages 67 - 74

https://doi.org/10.1145/640000.640017

Published: 06 April 2003 Publication History

Abstract

In this paper we present a linear-time Fine Granularity Clustering (FGC) algorithm to reduce the size of large scale placement problems. FGC absorbs as many nets as possible into Fine Clusters. The absorbed nets are expected to be short in any good placement; therefore the clustering process does not affect the quality of results. We compare FGC with a connectivity-based clustering algorithm proposed in [1] and simulated-annealing-based algorithm in TimberWolf [2], both of which also reduce the number of external nets between clusters. The experimental results show that our algorithm achieves better net absorption than the previous approaches while using much less CPU time for large scale problems. With our FGC algorithm, we propose a Fast Placer Implementation (FPI) framework, which combines our FGC-based size reduction with traditional placement techniques to handle large-scale placement problems. We compared FPI placement results with a public-domain fast standard cell placer Capo[4] on large scale benchmarks. The results show that FPI can reduce CPU time for large scale placement by a factor of 3~5x while obtaining placement results of comparable or better quality.

References

[1]

S. Hauck and G. Borriello, "An evaluation of bipartitioning techniques", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol 16, No. 8, 1997.

Digital Library

[2]

W. Sun and C. Sechen, "Efficient and effective placement for very large circuits", Proc. IEEE Intl. Conf. Computer-Aided Design, pp. 170--177, 1993.

Digital Library

[3]

C. M. Fiduccia and R. M. Mattheyses, "A linear time heuristic for improved network partitions", Proc. Design Automation Conf, pp. 241--247, 1982.

Digital Library

[4]

A. E. Caldwell, A. B. Kahng, I. L. Markov, "Can recursive bisection alone produce routable placements", Design Automation Conference, 2000, pp. 260--263.

Digital Library

[5]

J. Garbers, H. J. Promel, and A. Steger, "Finding clusters in VLSI circuits", in Proc. Int. Conf. Computer-Aided Design, 1990, pp. 520--523.

[6]

J. Cong, L. Hagen and A. B. Kahng, "Random walks for circuit clustering", Proc. IEEE Intl. ASIC Conf. 1991, pp. 14.2.1--14.2.4.

[7]

C. J. Alpert and A. B. Kahng. "A general framework for vertex ordering, with application to netlist clustering", Proc. IEEE Intl. Conf. Computer-Aided Design, 1994, pp.63--67.

Digital Library

[8]

D. J. Huang and A. B. Kahng, "When clusters meet partitions: new density-based methods for circuit decomposition", In Proc. European Design and Test Conf., pp. 60--64, 1995

Digital Library

[9]

J. Cong and M.L. Smith, "A parallel bottom-up clustering algorithm with applications to Circuit Partitioning in VLSI design", Proc. ACM/IEEE Design Automation Conf. 1993.

Digital Library

[10]

Y. C. Wei and C. K. Cheng, "Ratio cut partitioning for hierarchial designs", IEEE trans. on Computer-Aided Design, pp 911--921, 1992.

[11]

D. M. Schuler and E. G. Ulrich, "Clustering and linear placement", In Proc. Design Automation Conf. 1972.

Digital Library

[12]

L. Hagen and A. B. Kahng, "A new approach to effective circuit clustering", Proc. IEEE Intl. Conf. on Computer-Aided Design, 1992, pp. 422--427.

Digital Library

[13]

C. J. Alpert and A. B. Kahng, "Recent directions in netlist partitioning: a survey", Integration, the VLSI Journal, pp. 1--81, 1995.

Digital Library

[14]

J. Cong and S. K. Lim, "Edge separability based circuit clustering with application to circuit partitioning", Proc. ASP-DAC, 2000, pp. 429--434.

Digital Library

[15]

A. Singh, G. Parthasarathy, M. Marek-Sadowska, "Efficient circuit clustering and placement for area and power reduction in FPGAs", In Proc. Intl. Symp. on Field Programmable Gate Arrays, 2002, pp. 59--66.

Digital Library

[16]

C. C. Chang, J. Cong and Z. Pan, "Physical hierarchy generation with routing congestion control", In Proc. Intl. Symp. on Physical Design, 2002, pp. 36--41.

Digital Library

[17]

http://gigascale.org/bookshelf/

[18]

J.M.Kleinhans, G.Sigl, F.M.Johannes and K.J.Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. CAD, vol.10, no.3, Mar1991, pp.356--365.

Digital Library

Cited By

Rakai LFarshidi ABehjat LWestwick D(2012)A new length-based algebraic multigrid clustering algorithmVLSI Design10.1155/2012/3952602012(8-8)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1155/2012/395260
Rakai LBehjat LMartin SAguado J(2012)An algebraic multigrid-based algorithm for circuit clusteringApplied Mathematics and Computation10.1016/j.amc.2011.10.084218:9(5202-5216)Online publication date: Jan-2012
https://doi.org/10.1016/j.amc.2011.10.084
Tsota KKoh CBalakrishnan VRoychowdhury J(2009)A study of routability estimation and clustering in placementProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687468(363-366)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687468
Show More Cited By

Index Terms

Fine granularity clustering for large scale placement problems
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design

Recommendations

Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs
DAC '08: Proceedings of the 45th annual Design Automation Conference

Routability is a challenging cost metric for modern large-scale mixed-size placement. Most existing routability-driven placement algorithms apply whitespace allocation to relieve the routing congestion. Nevertheless, we observe that whitespace ...
An Effective Floorplan-Guided Placement Algorithm for Large-Scale Mixed-Size Designs

In this article we propose an effective algorithm flow to handle modern large-scale mixed-size placement, both with and without geometry constraints. The basic idea is to use floorplanning to guide the placement of objects at the global level. The flow ...
Simultaneous placement with clustering and duplication
DAC '04: Proceedings of the 41st annual Design Automation Conference

Clustering, duplication, and placement are critical steps in a cluster-based FPGA design flow. Clustering has a great impact on the wirelength, timing, and routability of a circuit. Logic duplication is an effective method for improving performance ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '03: Proceedings of the 2003 international symposium on Physical design

April 2003

218 pages

ISBN:1581136501

DOI:10.1145/640000

General Chair:
Massoud Pedram
USC
,
Program Chair:
Charles J. Alpert
IBM

Copyright © 2003 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 April 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISPD03

Sponsor:

ISPD03: International Symposium on Physical Design

April 6 - 9, 2003

CA, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
229
Total Downloads

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

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rakai LFarshidi ABehjat LWestwick D(2012)A new length-based algebraic multigrid clustering algorithmVLSI Design10.1155/2012/3952602012(8-8)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1155/2012/395260
Rakai LBehjat LMartin SAguado J(2012)An algebraic multigrid-based algorithm for circuit clusteringApplied Mathematics and Computation10.1016/j.amc.2011.10.084218:9(5202-5216)Online publication date: Jan-2012
https://doi.org/10.1016/j.amc.2011.10.084
Tsota KKoh CBalakrishnan VRoychowdhury J(2009)A study of routability estimation and clustering in placementProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687468(363-366)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687468
Fathi BBehjat LRakai LCheng CReda S(2009)A pre-placement net length estimation technique for mixed-size circuitsProceedings of the 11th international workshop on System level interconnect prediction10.1145/1572471.1572480(45-52)Online publication date: 26-Jul-2009
https://dl.acm.org/doi/10.1145/1572471.1572480
Zhang XTakeuchi TToyonaga M(2009)Cell Merge: A basic-pre-clustering clustering algorithm for placement2009 IEEE International Conference on IC Design and Technology10.1109/ICICDT.2009.5166262(47-50)Online publication date: May-2009
https://doi.org/10.1109/ICICDT.2009.5166262
Li JBehjat LHuang JMadden PPan D(2007)An effective clustering algorithm for mixed-size placementProceedings of the 2007 international symposium on Physical design10.1145/1231996.1232020(111-118)Online publication date: 18-Mar-2007
https://dl.acm.org/doi/10.1145/1231996.1232020
Li JBehjat LKennings A(2007)Net ClusterIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2007.89233926:4(669-679)Online publication date: 1-Apr-2007
https://dl.acm.org/doi/10.1109/TCAD.2007.892339
Behjat LLi JRakai LHuang J(2007)Two Clustering Preprocessing Techniques for Large-Scale Circuits2007 IEEE International Symposium on Circuits and Systems10.1109/ISCAS.2007.378191(1057-1060)Online publication date: May-2007
https://doi.org/10.1109/ISCAS.2007.378191
Li JBehjat LRakai L(2007)Clustering algorithms for circuit partitioning and placement problems2007 18th European Conference on Circuit Theory and Design10.1109/ECCTD.2007.4529654(547-550)Online publication date: Aug-2007
https://doi.org/10.1109/ECCTD.2007.4529654
Viswanathan NMin Pan Chu C(2007)FastPlace 3.0Proceedings of the 2007 Asia and South Pacific Design Automation Conference10.1109/ASPDAC.2007.357975(135-140)Online publication date: 23-Jan-2007
https://dl.acm.org/doi/10.1109/ASPDAC.2007.357975
Show More Cited By

View Options

Get Access

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